DEV Community: Axel N'cho

Using LMAX Disruptor to build a high-performance in-memory event broker in Java.

Axel N'cho — Mon, 29 Dec 2025 00:17:45 +0000

I spend most of my time writing Python code for data analysis and engineering, filesystem operations, and web projects, with some Go thrown in sometimes because concurrency seems simpler or Rust for novelty. But I started programming with C and learned OOP through Java back in the day. After seven years away from the JVM, I got curious about what's changed and decided to dive back in by building something performance-critical. The result is an event router that processes 7+ million dispatches per second on a laptop by eliminating the two main bottlenecks: locks and memory allocation.

Why Java when Python and Go exist?

As a Python developer, I'd typically reach for libraries like PyPubSub or Blinker for event handling, which work well for I/O-bound applications but struggle with CPU-intensive event processing due to the GIL for Python versions before 3.14. Go's channel-based concurrency model handles events elegantly with goroutines, and libraries like EventBus provide pub-sub patterns that feel natural in Go's ecosystem. However, neither ecosystem has a direct equivalent to Disruptor's mechanical sympathy approach. Python's interpreter overhead and Go's garbage collector (though better than Python's) both introduce latency that becomes visible at millions of events per second. If you're building a system where a few microseconds per event multiplied by millions of events actually matters (financial systems, real-time analytics, game servers), Java's mature JIT compilation, fine-tuned GC options, and libraries like Disruptor that exploit CPU cache behavior offer performance that's hard to match.

Typical event bus based on locks

A typical event bus uses queues wrapped in synchronized blocks. When thread A wants to publish an event, it locks the queue, adds the event, and unlocks. Thread B does the same. At high throughput, threads spend more time waiting for locks than doing actual work. Java's ConcurrentLinkedQueue helps but still uses compare-and-swap operations that create memory barriers.
Another issue is object allocation. Creating a new Event object for each message generates garbage. With millions of events per second, the garbage collector runs constantly and pauses the application.

The ring buffer

Disruptor is basically a very good application of the circular buffer, a fundamental data structure where a fixed-size array wraps around to reuse slots. Anyone who's studied data structures and algorithms has likely encountered this pattern, but Disruptor optimizes it specifically for multi-threaded event processing with lock-free mechanics.

The GIF from https://upload.wikimedia.org/wikipedia/commons/f/fd/Circular_Buffer_Animation.gif.

Picture a circular array of 16,384 pre-allocated Event slots. Publishers claim the next available slot, write their data directly into it, and mark it ready. Consumers read from their current position and advance forward. No locks. No allocations. Just atomic sequence numbers that coordinate who writes where. The ring wraps around, reusing the same Event objects forever.

When a producer publishes, it calls ringBuffer.next() to claim a sequence number, copies data into ringBuffer.get(sequence), and calls ringBuffer.publish(sequence). By copying, I mean setting the valus of the attributes of current Event instance so there is no need to create a new instance. Here is a simple example:

import com.lmax.disruptor.dsl.Disruptor;
import com.lmax.disruptor.dsl.ProducerType;

/**
 * A router is an event bus for subscribers to attach to and receive relevant events.
 */
public class EventRouter {

    private final @NotNull Disruptor<@NotNull Event> disruptor;
    private final @NotNull RingBuffer<@NotNull Event> ringBuffer;

    /**
     * Publish an event in the event bus.
     */
    public void publish(@NotNull Event e) {
        String type = e.getType();
        long sequence = this.ringBuffer.next();
        try {
            // type, from, payload and timestamp are custom attributes for the custom Event class.
            Event bufferedEvent = ringBuffer.get(sequence);
            # The following are arbitrary attributes.
            bufferedEvent.setType(e.getType());
            bufferedEvent.setFrom(e.getFrom());
            bufferedEvent.setPayload(e.getPayload());
            bufferedEvent.setTimestamp(e.getTimestamp());
        } finally {
            this.ringBuffer.publish(sequence);
        }
    }
}

The consumer sees published sequences and processes them in order.

Dispatch strategy

Once an event is in the ring buffer, the router dispatches it to subscribers. Each event type has a subscriber list to identify all its subscribers quickly. When an event arrives, the router looks up its type and submits a task to a thread pool for each subscriber.

/**
 * Thread pool for dispatching events to subscribers.
 */
private final ExecutorService DISPATCH_POOL =
        Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

...

/**
 * Dispatch an event to all its subscribers.
 */
private void dispatch(@NotNull Event e, long sequence, boolean endOfBatch) {
    // See section 'Copy-on-Write subscribers'
    SubscriberList holder = this.subscribers.get(e.getType());
    if (holder == null) return;
    var subs = holder.list;
    if (subs.isEmpty()) return;
    if (subs.size() == 1) subs.getFirst().onEvent(e);
    else {
        for (Subscriber sub : subs) DISPATCH_POOL.submit(() -> sub.onEvent(e));
    }
}

The thread pool size matches CPU cores. This parallelizes subscriber callbacks across multiple threads while keeping the main ring buffer processing single-threaded and fast.

Each subscriber has its own single-threaded executor onEvent that queues incoming events. This preserves ordering per subscriber (event A always processes before event B if A was published first) while preventing one slow subscriber from blocking others.

/**
 * A subscriber listens to a given number of event types in his scope's range.
 */
public abstract class Subscriber implements AutoCloseable {
    /***
     * This executor ensures events are processed one at a time, in the order they are received,
     * without blocking the event router. */
    @NotNull
    private final ExecutorService exec = Executors.newSingleThreadExecutor();
    /**
     * Return the scope of this subscriber.
     */
    @NotNull
    public abstract Scope scope();
    /**
     * Process an event received from a router.
     */
    protected abstract void processEvent(@NotNull Event e);
    /**
     * Send data to this subscriber. This is fast and does not block the caller.
     */
    public final void onEvent(@NotNull Event e) {
        this.exec.submit(() -> this.processEvent(e));
    }
    @Override
    public void close() throws TimeoutException, InterruptedException {
        this.exec.shutdown();
        if (!this.exec.awaitTermination(1, TimeUnit.MINUTES))
            throw new TimeoutException("subscriber's executor thread termination timed out");
    }
}

Choosing a `WaitStrategy`

Disruptor offers several wait strategies that control how consumers behave when no new events are available. Among others, there are:

BlockingWaitStrategy uses locks and is CPU-friendly but adds latency.
BusySpinWaitStrategy burns CPU cycles in a tight loop for the lowest possible latency.
SleepingWaitStrategy backs off progressively, balancing CPU usage with reasonable latency.

I chose YieldingWaitStrategy because it sits in the middle ground. When no events are ready, it calls Thread.yield() to hint to the scheduler that other threads can run, then immediately checks again. This keeps latency low without pinning the CPU at 100% like busy spinning would. For a system that processes bursts of events with occasional quiet periods, yielding provides good throughput without wasteful spinning during idle times.

Additional features of this experimental event bus

Scope-based security

Events have scope levels:

PUBLIC (visible to remote actors)
FEDERATED (visible to trusted servers)
PRIVATE (local trusted actors)
ROOT (full access).

Components can only interact with events at or below their scope level.
When registering an event type, its scope must be specified. When subscribing to an event type, the router checks that the specified scope is broad enough to encompass the event type's scope. When publishing an event, the router verifies that the event type exists. This prevents untrusted code from accessing sensitive event streams.
The EventRegistry stores registered events and their type as a ConcurrentHashMap<String, Scope>. Looking up an event's scope is a single hash table read, adding microseconds of overhead.

Copy-on-Write subscribers

Each event type maps to a SubscriberList containing an immutable List<Subscriber>. When someone subscribes, the router creates a new list with the additional subscriber and swaps it in atomically.

Readers see a consistent snapshot without synchronization. Writers pay the cost of copying the list, but subscriptions are rare compared to event dispatches. This optimizes the hot path (dispatching) at the expense of the cold path (subscribing).

Benchmark results

The benchmark spawns 4 producer threads that each publish 250,000 events across 5 event types. Each type has 4 subscribers, creating 4M total dispatch operations (1M events × 4 subscribers each).

On an Intel Core i7-13600H with 16GB RAM (and other programs running), average time over 50 runs was 922ms, giving 4.34M dispatches per second.

On an Intel Core Ultra 7-155H with 32GB RAM, it dropped to 528ms, giving 7.58Mdispatches per second.

These numbers were obtained for light string payloads and subscribers that just increment a counter. Real-world throughput depends on what subscribers actually do with the events, but the router itself adds minimal latency. Disruptor is advertised to perform way better.

What this experimental even bus does not do

There's no filtering beyond event type.
There's no wildcards, no content-based routing, no priority queues.
There's no guaranteed delivery. If a subscriber falls too far behind and the ring buffer wraps around, old unprocessed events get overwritten. The ring buffer has 16K slots per the default configuration, so this requires being 16K events behind, but it can happen.
There's no persistence. Events exist only in memory. If the process crashes, in-flight events are lost. This is an in-process event bus, not a message queue like Kafka.
The single-threaded executor per subscriber means slow subscribers build up queues in their executor. There's no back-pressure mechanism to slow down publishers when consumers can't keep up.

To conclude

Disruptor was developed by LMAX, a trading platform that aims to be the "fastest trading platform in the world". It was very fun to understand and use this library while diving back in the Java ecosystem after seven years away.

The code is available on GitHub.

In-depth file management in Python: Underlying tooling and advanced functionalities

Axel N'cho — Mon, 10 Mar 2025 15:49:22 +0000

File management in Python extends beyond simple read/write operations. Understanding the underlying memory-disk interactions and system calls together with and advanced features like buffering, locking and memory mapping is essential for optimizing performance and avoiding pitfalls.

1. File handling and system calls

When you use Python’s open() function, the interpreter interacts with the OS through system calls like open(), read(), write(), and close(). These system calls interface with the kernel to manage file I/O efficiently.

For example, the following Python code:

with open("example.txt", "w") as file:
    file.write("Hello, World!")

translates to (on Unix systems):

open("example.txt", O_WRONLY | O_CREAT | O_TRUNC, 0666) - Opens or creates the file.
write(fd, "Hello, World!", 13) – Writes 13 bytes to the file.
close(fd) – Closes the file descriptor.

On Windows, the equivalent system calls differ slightly.

2. Buffering, cache layers, and the role of `flush()`

Buffering and Cache Layers

File I/O in Python involves multiple layers of caching:

Application-level buffer (Python’s internal buffer): stores data before passing it to the OS.
OS buffer (Page cache): temporarily holds data in memory before writing to disk.
Disk cache (Drive controller): hardware-level caching before physical storage.

Python's flush() and fsync() interact differently with these layers.

The Role of `flush()`

The flush() method forces Python to move data from its internal buffer to the OS buffer, but it does not guarantee immediate disk persistence.

file = open("example.txt", "w")
file.write("Important data")
file.flush()  # Transfers data to OS buffer

`flush()` vs `fsync()`

flush(): moves data from Python’s internal buffer to the OS buffer but doesn’t force a physical disk write.
os.fsync(fd): ensures data is written from the OS buffer to disk, reducing crash risks (works on Unix and Windows).

Example ensuring persistence:

import os
file = open("example.txt", "w")
file.write("Critical log entry")
file.flush()
os.fsync(file.fileno())  # Ensures data is physically written to disk
file.close()

Multi-threading and multi-processing considerations

When multiple threads or processes write to the same file, buffer inconsistencies may occur. Without proper handling, some writes may be lost or interleaved incorrectly.

Scenario: multiple processes writing to the same file

import os, time
from multiprocessing import Process

def write_data():
    with open("shared.txt", "a") as file:
        file.write("Process writing...")
        file.flush()
        os.fsync(file.fileno())  # Ensures data persistence

if __name__ == "__main__":
    processes = [Process(target=write_data) for _ in range(5)]
    for p in processes: 
        p.start()
    for p in processes: 
        p.join()

In this case, flush() ensures immediate buffer transfer to the OS, and fsync() guarantees that all processes persist their changes.

Handling Cache Conflicts

If multiple processes access the same file, OS-level caching can cause inconsistencies. The lack of synchronization between cache layers means that different processes might see outdated data unless proper mechanisms are used. The flush() method ensures that data is moved from Python’s internal buffer to the OS buffer, but it does not guarantee a physical write to disk. If multiple agents write to the same file and only flush() is called without fsync(), data remains in the OS buffer and could be lost if a system crash occurs before the OS writes it to disk. However, in scenarios where performance is critical and occasional data loss is acceptable (e.g., logging systems or temporary file writes) and agents only access the memory version of the file for long processing, calling only flush() can reduce I/O overhead and improve efficiency by allowing the OS to handle disk writes asynchronously.

3. File descriptors

Every open file is associated with a file descriptor, an integer representing an open file (Unix only). Windows has an object called a handle that is used in much the same way that Unix uses file descriptors. The file descriptor limit per process for Unix is around 1024 and as far as I know, there is no such a limit on Windows.

file = open("example.txt", "w")
print(file.fileno())  # Outputs file descriptor number

This descriptor is used in system calls like fsync().

4. File locking mechanisms

When working with shared files, locking prevents race conditions.

Advisory locks: fcntl.lockf() (Unix only): for processes that cooperate "peacefully". The kernel keeps track of the locks but doesn't enforce them - it's up to the applications to obey them. This way the kernel doesn't need to deal with situations like dead-locks.
Mandatory locks: flock() (Unix only), msvcrt.locking() (Windows): kernel enforced file locking.

Example of advisory locking (Unix):

import fcntl
with open("shared.txt", "w") as file:
    fcntl.flock(file, fcntl.LOCK_EX)  # Exclusive lock
    file.write("Locked access\n")
    fcntl.flock(file, fcntl.LOCK_UN)  # Release lock

Locks are essential in multi-threaded or multi-process environments.

5. Memory-mapped files (`mmap`)

For efficient file access, mmap allows mapping a file’s content directly into memory (Unix and Windows).

Memory-mapped file objects behave like both bytearray and like file objects. You can use mmap objects in most places where bytearray are expected. For example, you can use the re module to search through a memory-mapped file. You can also change a single byte by doing obj[index] = 97, or change a subsequence by assigning to a slice: obj[i1:i2] = b'...'. You can also read and write data starting at the current file position, and seek() through the file to different positions.

Benefits:

Speeds up large file access by avoiding repeated I/O calls.
Enables direct memory access without copying buffers.

6. Asynchronous file I/O

For non-blocking file operations, use asyncio and aiofiles (cross-platform):

import asyncio
import aiofiles

async def read_file():
    async with aiofiles.open("example.txt", "r") as f:
        content = await f.read()
        print(content)

asyncio.run(read_file())

Async file handling is useful in high-performance applications.

7. Working with temporary files

Use tempfile to create temporary files (cross-platform):

import tempfile
with tempfile.NamedTemporaryFile() as temp:
    temp.write(b"Temporary content")
    print(f"Temp file created at: {temp.name}")

Temporary files are auto-deleted upon closure unless the delete parameter of the constructor is set to False.

8. Avoiding disk fragmentation

Disk fragmentation occurs when files or pieces of files get scattered throughout your disks. Not only do hard disks get fragmented, but removable storage can also become fragmented. This can cause poor disk performance and overall system degradation.

You can preallocate disk space for a file then write it sequentially without changing its size. This is useful when we want to reduce the risk of disk fragmentation. I found an answer on stackoverflow addressing the matter. Briefly, it's possible with the msvcrt module on windows. However it seems that's not possible on Unix. os.posix_fallocate() actually does the exact opposite: it sets the file's apparent length to the length you give it, but allocates it as a sparse extent on the disk, so writing to multiple files simultaneously will still result in fragmentation. Ironic, isn't it, that Windows has a file management feature that POSIX lacks ?

9. Best practices for efficient file management

Use buffered I/O wisely: avoid excessive flushing (flush()/fsync()) unless necessary.
Leverage memory-mapped files: optimize access for large files.
Use locking in concurrent environments: prevent race conditions.
Prefer asynchronous file handling: improve performance in I/O-bound tasks.
Use context managers (with ... statement): ensures proper resource cleanup.

Conclusion

Beyond basic file operations, Python provides deep interaction with system-level file handling through buffering, memory-mapped files, asynchronous I/O, and file locking. Understanding these mechanisms helps in writing efficient, robust, and scalable file management code.

References

Beyond arrays and linked lists: Exploring powerful data structures for efficient problem solving

Axel N'cho — Sun, 02 Feb 2025 00:05:39 +0000

Most developers are familiar with fundamental data structures like arrays, linked lists, and hash tables. However, many advanced data structures exist that can optimize performance and solve complex problems more efficiently. Understanding these data structures can make a significant difference in writing optimized code and handling large-scale data efficiently. In this article, we will explore Tries, Segment trees, Skip lists, and Bloom filters.

1. Tries: fast lookups for dictionary-like data

Use case: Tries (prefix trees) are particularly useful for applications involving search auto-completion, spell checking, and IP routing.

How they work

A trie is a tree-like data structure where each node represents a character of a string. Strings with common prefixes share the same branches, making lookup operations efficient.

Operations and complexity

Insertion: O(n), where n is the length of the string
Search: O(n)
Memory usage: Can be high due to pointer overhead

Example Use Case: Implementing an Auto-Complete Feature

Before diving into the implementation, let's first understand the problem we aim to solve. An auto-complete feature suggests words or phrases based on user input, improving user experience in search bars, text editors, and messaging applications. This requires efficient lookup and retrieval of words that share common prefixes.

To achieve this, we use a Trie.

Insertion

Conceptually, insertion works by traversing the tree character by character:

Start from the root node.
For each character in the word:
- if the character does not exist in the current node’s children, create a new node
- move to the child node corresponding to the character
After processing all characters, mark the last node as the end of a word.

Search

Searching follows a similar traversal process:

Start from the root node.
For each character in the word:
- if the character does not exist in the current node’s children, return False
- move to the child node corresponding to the character
If all characters are found and the last node is marked as a word ending, return True; otherwise, return False.

Below is an implementation in Python:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

2. Segment trees: Efficient range queries

Use case: Segment trees are ideal for answering range queries quickly, such as finding the sum or minimum value in a given range.

How they work

A segment tree is a binary tree where each node represents an interval. The root represents the entire range, while the leaves represent individual elements. Updates and queries are performed efficiently through tree traversal.

Operations and Complexity

Build tree: O(n)
Range query: O(log n)
Update operation: O(log n)

Example use case: Range sum query

Given an array, the problem here consists of computing the sum of all values in a specified range. In addition to being a common problem in competitive programming, range sum queries (RSQ) have a wide array of practical applications across various domains. These include data analytics, where RSQ can efficiently calculate cumulative statistics like moving averages; financial systems, where it helps track balances or transactions over time; and image processing, where it allows for quick computation of pixel sums over regions of an image. They are also useful in fields like game development, geospatial data analysis, and IoT systems, where aggregating values over specific ranges or time intervals is often required.

We will use a segment tree.

First, let's initialize the tree. We will implement the tree as an array.

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

nums: This is the initial input array (e.g., a list of integers).
n: Stores the size of the input array nums.
tree: Initializes an array (or list) of size 2*n to store the segment tree. The segment tree is built in a bottom-up manner:
- the first n elements (from n to 2*n - 1) will store the elements of the input array nums
- the remaining elements (from index 1 to n - 1) will store the sum of the segments (ranges) of the array.

Buiding the segment tree

The first for loop fills in the leaf nodes of the tree (starting from index n to 2*n - 1).

The second for loop goes from the last non-leaf node (n - 1) upwards to the root (index 1) and calculates the sum for each internal node based on the sum of its two child nodes.

Updating the array

def update(self, index, value):
    pos = self.n + index
    self.tree[pos] = value
    while pos > 1:
        pos //= 2
        self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

index: The index of the element in the original array that needs to be updated.
value: The new value that the element at the specified index should have.

Updating the Tree

The element at index indexin the original array is updated. The position in the tree is calculated as n + index.

The value at that position in the tree is updated to the new value.

After updating the leaf, the method continues upwards to update the sum values of the internal nodes. At each step, the node value is updated as the sum of its two children.

The query method

Now, let's dive in the crux of the problem : computing the sum of items in a specified range using an already built segment tree.

def query(self, left, right):
    l, r = self.n + left, self.n + right
    res = 0
    while l < r:
        if l % 2:
            res += self.tree[l]
            l += 1
        if r % 2:
            r -= 1
            res += self.tree[r]
        l //= 2
        r //= 2
    return res

left and right: The range for which we want to compute the sum (inclusive of left and exclusive of right).

Querying the Tree

l and r are the positions corresponding to left and right in the tree (adjusted by adding n).

We traverse the tree and sum the elements in the given range:

If l is an odd index, it is a right child, so we add tree[l] to the result and increment l to move to the next index.
If r is an odd index, it is a left child, so we add tree[r] to the result and decrement r to move to the previous index.

After each step, both l and r are halved to move upwards to the parent nodes.

The loop continues until the range is fully processed, and the result is returned.

Here is the full SegmentTree class.

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        pos = self.n + index
        self.tree[pos] = value
        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

    def query(self, left, right):
        l, r = self.n + left, self.n + right
        res = 0
        while l < r:
            if l % 2:
                res += self.tree[l]
                l += 1
            if r % 2:
                r -= 1
                res += self.tree[r]
            l //= 2
            r //= 2
        return res

3. Skip lists: Probabilistic alternative to balanced trees

Use case: Skip lists offer an alternative to balanced trees for maintaining sorted data with efficient insert, delete, and search operations. They are faster than simple linked lists and at the same time easier the implement than balanced trees.

How they work

Skip lists use multiple layers of linked lists where higher levels "skip" over elements, allowing faster searches. The probability of an element appearing at a higher level follows a geometric distribution.

Operations and Complexity

Insertion: O(log n)
Search: O(log n)
Deletion: O(log n)

Example use case: Ordered data storage with fast lookups

The problem being here is the efficient storage and management of ordered data, enabling fast search, insertion, and deletion operations. In traditional data structures like linked lists or arrays, these operations can be slow, especially as the data grows. Skip lists solve this by organizing the data across multiple levels, allowing quick navigation through the list and reducing the time complexity of search and updates to O(logn).

First, let's create a node for the skip list.

class Node:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)

value: The value stored in the node
forward: A list that contains "pointers" (or references) to the next nodes at different levels. The length of this list is determined by the level of the node (i.e., how many "layers" or "links" the node will have). The higher the level, the more "express lanes" the node has for faster traversal.

The levelis the number of layers the node will occupy. A node at level 0 will have only one link, while a node at level k will have k+1 links (or pointers) at different levels.

Now the SkipList class.

class SkipList:
    def __init__(self, max_level=16):
        self.head = Node(-1, max_level)
        self.max_level = max_level
        self.level = 0

head: The "sentinel" or starting node of the skip list, which doesn’t store any meaningful data (value = -1). This node spans all possible levels up to max_level.
max_level: The maximum possible level in the skip list.
level: The current highest level used in the skip list.

The random_levelmethod

For a new node, we generate a random level at which the node will be based on a probabilistic approach. On average, about 50% of the nodes will have a higher level than the previous one, meaning that the level distribution follows a geometric distribution.

import random

def random_level(self):
    lvl = 0
    while random.random() < 0.5 and lvl < self.max_level:
        lvl += 1
    return lvl

Insertion

Fist, we have to find the position to insert.

update = [None] * (self.max_level + 1)
node = self.head
for i in range(self.level, -1, -1):
    while node.forward[i] and node.forward[i].value < value:
        node = node.forward[i]
    update[i] = node

The list update keeps track of the nodes at each level where we need to update the "forward" pointers.
We start from the highest level (level) and traverse each level down to level 0, searching for where the new node should be inserted.
We move through the list by comparing values, similar to how you might traverse a sorted list.
The update[i] array stores the nodes at each level just before where the new node will be inserted.

Next, we determine the level of the new node.

lvl = self.random_level()
if lvl > self.level:
    for i in range(self.level + 1, lvl + 1):
        update[i] = self.head
    self.level = lvl

The random_level() function is called to decide the level at which the new node will appear.
If the new node's level is greater than the current skip list's highest level (level), the update array is adjusted to point to the head node for the higher levels, and the list's level is updated.

Finally, we create and insert the new node.

new_node = Node(value, lvl)
for i in range(lvl + 1):
    new_node.forward[i] = update[i].forward[i]
    update[i].forward[i] = new_node

A new node is created with the chosen level.
The forward pointers of the new node are set to the corresponding nodes in the update list.
Finally, the update list is used to update the forward pointers of the nodes at each level, effectively inserting the new node at the correct position.

Here is the whole implementation:

import random

class Node:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=16):
        self.head = Node(-1, max_level)
        self.max_level = max_level
        self.level = 0

    def random_level(self):
        lvl = 0
        while random.random() < 0.5 and lvl < self.max_level:
            lvl += 1
        return lvl

    def insert(self, value):
        update = [None] * (self.max_level + 1)
        node = self.head
        for i in range(self.level, -1, -1):
            while node.forward[i] and node.forward[i].value < value:
                node = node.forward[i]
            update[i] = node
        lvl = self.random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl
        new_node = Node(value, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

Key Concepts to remember for a skip list:

Ordered data: The list is sorted as elements are inserted in order.
Multiple levels: The skip list has multiple layers to enable fast traversal (similar to binary search). The higher levels allow skipping over large sections of the list, reducing the search time.
Probabilistic balancing: The levels of the nodes are determined probabilistically (via random_level), so the skip list achieves good average performance without requiring expensive balancing operations (unlike balanced trees).

4. Bloom filters: Space-efficient membership queries

Use case: Bloom filters are useful when approximate membership queries are acceptable, such as detecting spam emails or caching.

Some real world applications of bloom filters :

Google Chrome uses Bloom filters in its ‘Safe Browsing’ feature. The Bloom filter helps quickly check if a URL is potentially harmful (such as known phishing or malware sites) without sending the actual URL to Google, thus enhancing privacy and speed.
Medium uses Bloom filters in its Recommendation module to avoid showing those posts that have already been seen by the user.
Cassandra/HBase uses bloom filters to optimize the search of data in an SSTable on the disk.
Akamai, a global content delivery network (CDN), uses Bloom filters for its web caching services. They help quickly determine whether a web object is stored in the cache, improving content delivery speed and efficiency.

How they work

A Bloom filter is a bit array that uses multiple hash functions to determine whether an element may be present. It sacrifices exact membership accuracy for space efficiency, thus might give false positives.

Operations and complexity

Insertion: O(k), where k is the number of hash functions
Query: O(k) (False positives possible, but never false negatives)
Space Complexity: O(m), where m is the size of the bit array

Example use case: Checking if an item was seen before

A Bloom filter is a probabilistic implementation of the abstract Set type. The problem here is to check wether an item has been seen before, thus present in a set.

Let's initialize the filter. We use the bitarray Python module for bit arrays.

from bitarray import bitarray

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size                
        self.hash_count = hash_count    
        self.bit_array = bitarray(size)  
        self.bit_array.setall(0)        # Initialize all bits to 0

size: The size of the bit array, determining how many bits it will contain. The larger the array, the fewer collisions and false positives we will have, but it requires more memory.
hash_count: The number of different hash functions that will be used to hash the item, affecting the accuracy and efficiency of the filter.
bit_array: A bit array initialized with all bits set to 0. The bit array will represent the set, where each bit position corresponds to a hash value of an item.

Hashes

import hashlib

def _hashes(self, item):
    return [int(hashlib.md5((item + str(i)).encode()).hexdigest(), 16) % self.size for i in range(self.hash_count)]

This function generates hash_count hash values for the given item.
It uses md5 to hash the item, with a unique index (i) added to the item string to generate different hash values for the same item. This ensures that different hash values are generated.
The hash value is converted into an integer and then reduced modulo the size of the bit array to ensure it fits within the range of the bit array size.
This gives us a list of hash_count indices corresponding to positions in the bit array.

Adding an item

def add(self, item):
    for h in self._hashes(item):
        self.bit_array[h] = 1

Checking if an item exists

def check(self, item):
    return all(self.bit_array[h] for h in self._hashes(item))

For the given item, we compute the hash values. If all the corresponding values in the bit array are set to 1, then the item might be in the set. If any of the corresponding values is 0, we can be sure that the item is not in the set.

Full example

from bitarray import bitarray
import hashlib

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def _hashes(self, item):
        return [int(hashlib.md5((item + str(i)).encode()).hexdigest(), 16) % self.size for i in range(self.hash_count)]

    def add(self, item):
        for h in self._hashes(item):
            self.bit_array[h] = 1

    def check(self, item):
        return all(self.bit_array[h] for h in self._hashes(item))

Conclusion

Understanding and utilizing these advanced data structures can significantly enhance a developer's ability to solve complex problems efficiently. Whether optimizing search operations with tries, performing fast range queries with segment trees, using skip lists for sorted data, or applying Bloom filters for probabilistic membership checks, these structures can be invaluable tools in your software engineering arsenal.

DEV Community: Axel N'cho

Using LMAX Disruptor to build a high-performance in-memory event broker in Java.

Why Java when Python and Go exist?

Typical event bus based on locks

The ring buffer

Dispatch strategy

Choosing a WaitStrategy

Additional features of this experimental event bus

Scope-based security

Copy-on-Write subscribers

Benchmark results

What this experimental even bus does not do

To conclude

In-depth file management in Python: Underlying tooling and advanced functionalities

1. File handling and system calls

2. Buffering, cache layers, and the role of flush()

Buffering and Cache Layers

The Role of flush()

flush() vs fsync()

Multi-threading and multi-processing considerations

Handling Cache Conflicts

3. File descriptors

4. File locking mechanisms

5. Memory-mapped files (mmap)

6. Asynchronous file I/O

7. Working with temporary files

8. Avoiding disk fragmentation

9. Best practices for efficient file management

Conclusion

References

Beyond arrays and linked lists: Exploring powerful data structures for efficient problem solving

1. Tries: fast lookups for dictionary-like data

How they work

Operations and complexity

Example Use Case: Implementing an Auto-Complete Feature

2. Segment trees: Efficient range queries

How they work

Operations and Complexity

Example use case: Range sum query

3. Skip lists: Probabilistic alternative to balanced trees

How they work

Operations and Complexity

Example use case: Ordered data storage with fast lookups

4. Bloom filters: Space-efficient membership queries

How they work

Operations and complexity

Example use case: Checking if an item was seen before

Conclusion

References

Choosing a `WaitStrategy`

2. Buffering, cache layers, and the role of `flush()`

The Role of `flush()`

`flush()` vs `fsync()`

5. Memory-mapped files (`mmap`)