I have been sitting on a project idea for a while. Vitals is a monitoring platform, the kind of thing that watches a large number of entities continuously and needs to act on what it sees in near real-time. The scope is ambitious enough that I want to get the foundational pieces right before anything else, and the most foundational piece is the scheduler, the component that decides what gets checked, when, and in what order.
This is the first log entry for Vitals. It is not about a finished thing. It is about the first serious problem I ran into, before a single line of production code existed.
I wanted the scheduler to have O(1) discovery and O(1) writes. A standard database index gives you something that feels fast in practice but is still O(log n) underneath, and the difference matters at scale. An O(log n) lookup on a million tasks is still fast. On ten million it starts to accumulate. I wanted to design around the problem rather than tune my way out of it later.
The design uses two structures working together. Sector Buckets handle discovery: each task type gets a pre-assigned sector, so finding where a task lives is a direct lookup, not a search. Ring Buffers handle writes: each sector has a fixed slot, so writing a record is a seek and a write, nothing more. Pre-allocate the file once. Carve it into fixed-size sectors. From that point on, every operation is a seek to a known offset.
I built the prototype in Python. The choice of mmap was deliberate: it maps the file directly into the process’s virtual address space, so instead of going through the kernel’s read and write syscalls on every operation, you access the file as if it were a block of memory. No buffering layer, no copy between kernel space and user space, just a direct pointer into the file. For a scheduler built around seeking to a known byte offset and writing a fixed record, that is exactly the right primitive. The mental model of the code and the mental model of the storage layout are the same thing.
Each record is described by a struct format string:
RECORD_FORMAT = "dQIBBHxxxxxxxx"
RECORD_SIZE = struct.calcsize(RECORD_FORMAT) # 32 bytes per recordThe characters map directly to field types: d is a 64-bit double for the timestamp, Q an unsigned 64-bit integer for the entity ID, I a 32-bit unsigned integer for the task type, B a single byte each for priority and status, H a 16-bit unsigned short for the retry count, and xxxxxxxx eight bytes of padding at the end. That brings the total to 32 bytes per record, which means two records fit exactly in a single 64-byte cache line. The eight bytes of padding inside each record leave room to add fields later without breaking the binary format of records already written to disk. struct.calcsize turns that description into an exact byte count, which is what makes the offset arithmetic possible. Every record is the same size, so every seek is a multiplication.
The 32-byte size also matters for how the CPU reads the data. Without padding the record is 24 bytes, and roughly every third record straddles two cache lines, which means the CPU needs to load both lines, extract the relevant bytes from each, and merge them into one value. On modern hardware, an access that crosses a cache line boundary costs somewhere between 30 and 70 percent more than one that doesn’t. At 32 bytes, two records sit exactly within one 64-byte line, and that overhead never comes up.
def upsert_task(self, mm, index, timestamp, entity_id, task_type, priority, status, retry_count):
record = struct.pack(RECORD_FORMAT, timestamp, entity_id, task_type, priority, status, retry_count)
mm.seek(index * RECORD_SIZE)
mm.write(record)Single-threaded, this worked exactly as designed. mm.seek is a direct offset calculation, index * RECORD_SIZE, no traversal. struct.pack operates on a fixed number of fields of fixed size. mm.write writes a fixed byte count to a known position. Every step is constant time. The per-operation O(1) claim holds.
The moment I tried to scale across multiple threads, Python’s GIL serialized everything. Each individual write was still O(1), but only one thread could execute at a time regardless of how many cores were available. I had an O(1) engine that couldn’t use more than one core.
To fix the concurrency problem, I had to choose between two architectures.
The first option was a coordinator: one dedicated thread owns the write path, everything else submits requests to it. Think of it like a single bank teller with a queue. Safe, predictable, easy to reason about. Also a hard ceiling on throughput, because no matter how many tasks are waiting, only one thing is ever writing.
The second option was what I would call a lock-free atomic claim. Instead of a central coordinator, threads compete directly to claim a sector. Each sector has a small state flag, a single integer in memory. A thread that wants to write reads the flag, and if the sector is unclaimed, atomically swaps it to a claimed state using Compare-and-Swap. CAS is a hardware instruction that says “set this value to X, but only if it is currently Y, and tell me whether you succeeded.” If two threads try to claim the same sector simultaneously, one wins and one retries. No locks, no queue, no single bottleneck. Every core can be writing in parallel as long as they are claiming different sectors.
Imagine ten engineers working on ten different whiteboards simultaneously, each one claiming their board by writing their name at the top before starting. If two reach for the same board at once, one sees the other’s name already there and moves to a different board. Nobody waits for a manager to assign boards. That is the atomic claim.
I chose this. I was not willing to accept the coordinator’s throughput ceiling. The Python prototype does not implement this yet. It is single-threaded by design, enough to prove the O(1) layout works. The Rust benchmark exists to answer the hardware question first, before writing the actual claim mechanism.
The same cache line constraint that shaped the record format applies here too, but the numbers are different. Each atomic flag is only 8 bytes, which means eight of them fit inside a single 64-byte cache line. That makes the problem much harder to avoid without deliberate padding.
Before implementing the claim mechanism itself, I needed to answer a simpler question: would cache-line isolation actually buy meaningful throughput in practice? The benchmark tests that specific question, two threads incrementing independent counters, nothing more. Python’s runtime sits too far from the hardware to stress-test something like this honestly. I needed a clean environment, no garbage collector, no runtime, as close to bare metal as I could get. So I wrote a diagnostic benchmark in Rust.
In Rust, sharing data across threads requires being explicit about ownership. You cannot hand a reference to a thread and assume it stays valid. Arc, an atomically reference-counted pointer, handles this: Arc::clone creates a new handle to the same allocation, not a copy of the data, so each thread gets its own reference to the same value without anyone exclusively owning it. When the last reference drops, the value is cleaned up.
Ordering::Relaxed means no synchronization guarantees between threads beyond the atomic operation itself. For a throughput benchmark measuring cache-line contention, that is the right choice. You are measuring raw write speed, not correctness.
let a = Arc::new(AtomicU64::new(0));
let b = Arc::new(AtomicU64::new(0));
let t1 = thread::spawn({
let a = Arc::clone(&a);
move || for _ in 0..iterations { a.fetch_add(1, Ordering::Relaxed); }
});
let t2 = thread::spawn({
let b = Arc::clone(&b);
move || for _ in 0..iterations { b.fetch_add(1, Ordering::Relaxed); }
});
t1.join().unwrap(); t2.join().unwrap();The black_box(()) at the end is not redundant. I assumed println! was enough to make the loops visible to the compiler, but running both versions proved otherwise. Without it, the compiler applies optimizations in release mode that collapse the timing difference between adjacent and padded. The call takes () and looks like it does nothing, but it is doing something real here.
black_box(());The benchmark uses fetch_add rather than compare_exchange because it is measuring memory layout, not the claim mechanism itself. The question is whether cache-line isolation buys throughput. The operation inside the loop does not matter as long as it writes to the atomic on every iteration.
The test ran without corruption. Both threads finished. The counts were correct. The throughput was terrible, which meant the architecture was right and the layout was wrong.
I assumed I had made the wrong architectural call. The lock-free approach felt like it had failed. I started pulling apart the memory layout to find out why.
The atomic claim flags were defined sequentially in memory, eight bytes each, packed tightly together by the compiler. That is the sensible default. But a CPU does not load memory eight bytes at a time. It loads sixty-four byte cache lines, the smallest unit the hardware moves between main memory and the CPU’s cache.
When Thread 1 updated its flag for Sector 0, the CPU loaded the entire 64-byte line into its cache. Thread 2’s flag for Sector 1 was in that same line, because at eight bytes each, eight flags fit inside a single cache line. The moment Thread 1 wrote to its flag, the CPU’s cache coherency protocol broadcast an invalidation signal to every core: this line has changed, discard your copy. Thread 2, trying to update a completely separate flag, had to wait for the line to be reloaded before it could proceed.
This is False Sharing. The two threads were not sharing data. They were sharing a cache line. My logical boundaries meant nothing to the hardware. The atomic claim was correct in software and invisible in silicon.
On Apple Silicon, the effect was harder to see at first. Apple Silicon’s P-cores have fast cache interconnects between them, which reduces the synchronization penalty when a cache line is invalidated across cores. I had to push to 100 million iterations before the gap appeared clearly. Whether it would show up faster on x86 hardware I can’t say for certain, I only ran this on Apple Silicon, but the architecture difference likely means the penalty would be more obvious there with a lower iteration count.
The fix was padding. If each flag occupies exactly one cache line, no two threads can ever invalidate each other’s line.
#[repr(align(64))]
struct Padded {
value: AtomicU64,
_padding: [u64; 7], // added later to enforce 64-byte isolation
}And the usage with the padded version:
let a = Arc::new(Padded { value: AtomicU64::new(0), _padding: [0; 7] });
let b = Arc::new(Padded { value: AtomicU64::new(0), _padding: [0; 7] });
let t1 = thread::spawn({
let a = Arc::clone(&a);
move || for _ in 0..iterations { a.value.fetch_add(1, Ordering::Relaxed); }
});#[repr(align(64))] forces the struct to align to a 64-byte boundary. The _padding field fills the remaining 56 bytes. Each Padded now owns one full cache line. Sector 0’s flag and Sector 1’s flag are physically isolated. Thread 1 and Thread 2 can write simultaneously without the hardware treating them as competitors.
Throughput went up 4 to 5x.
The lock-free architecture was not the mistake. The memory layout was.
What I am carrying forward from this is a constraint more than a lesson. O(1) is a statement about how an algorithm scales with input size. It says nothing about the constant factor, and the constant factor can be dominated entirely by things that have nothing to do with the algorithm: how data is laid out in memory, how the CPU loads it, how many threads end up fighting over the same 64 bytes of silicon. Two systems can both be O(1) and differ by an order of magnitude in practice.
Vitals is still early. The scheduler is not done. The next question is whether this cache-line discipline can be enforced from Python, or whether the write path needs to live in Rust. That is the next problem to work through. This one is at least understood.