The log on disk

Lesson 1 ended with a rule. When the broker answers OK to a send, the message must survive a restart. In practice that means the broker writes the message to disk before it answers.

That rule has a price, and checkout pays it. The shop moved Asha's confirmation email onto a queue to bring checkout down from 1,000 ms to about 300 ms. If every send now waits for a disk, the broker could give some of that time back.

Here is the puzzle for this lesson. Take one ordinary hard disk. Store messages on it one way, and it handles about 50 messages a second, which is not enough for the shop's sale. Store the same messages on the same disk another way, and it handles about 278,000 a second. The disk did not change. The messages did not change. Only one thing is different: where on the disk each write lands.

By the end of this lesson you will know why. You will also have built the second layout piece by piece: the file, the bytes of one record, the files the log is split into, the index that finds a record, and the memory that makes reading a recent record almost free. And you will see what the disk adds to Asha's checkout. It is a few millionths of a second.

Two Ways to Keep Messages on Disk

Start with the design most people would draw first. Call it design A: a file of slots. The file is cut into fixed slots of 1 KB. Each slot holds one message, or nothing.

send(m):    find a free slot, write m into it            one write, somewhere in the file
receive():  pick a full slot, track it in memory         no disk write
delete(s):  mark slot s as free, so it can be reused     one write, somewhere in the file

Receive does not write to disk. Lesson 1 showed why it does not need to: after a restart, the broker can treat every message that was not deleted as ready. Some will go out twice, and the consumer already handles duplicates.

Now design B: a log. A log here means a file that the broker only ever adds to at the end. It never changes a byte that is already written.

send(m):    add m at the end of the file                 one write, always at the end
receive():  hand out the next message, track it in memory     no disk write
delete(id): note in memory that id is done               no write into the file

Delete does not touch the file at all. That raises an obvious question: if delete never removes anything, where do deleted messages go? For now, they stay. This lesson splits the log into pieces that can be dropped whole, and lesson 5 drops them.

Both designs keep the same promise: when the broker says OK, the message is written. Now price them.

Why Position Matters on a Hard Disk

A hard disk stores data on platters that spin. An arm moves a head across the platters to read and write. To write at a given place, two slow things must happen first:

1. The arm moves to the right track. This is a seek.
2. The disk waits until the right place on the track spins under the head.

Only then does the write happen, and the write itself is fast. A common 7,200 rpm disk spins 120 times a second. On average, the place you want is half a turn away:

one turn           = 60 s / 7,200 turns = 8.33 ms
average wait       = half a turn         = 4.17 ms     (the Exos X20 datasheet says 4.16 ms)
seek + wait        = about 10 ms per random write      (the figure Kafka's design docs use)
random writes      = 1 s / 10 ms         = about 100 a second

Design A writes to a different place for almost every operation: the free slot for a send, and some old slot for a delete. Each one pays the seek and the wait. Two writes per message:

most messages a second = 100 writes / 2 writes per message = 50 messages a second

Now play lesson 1's sale on that disk:

sale peak, no outage:  40 sends + 40 deletes   =  80 writes a second   (80% of the disk)
draining the backlog:  40 sends + 100 deletes  = 140 writes a second   (more than the disk can do)

During the drain, the provider can take 100 emails a second, but the disk cannot record 100 deletes a second. After the 40 sends, it has room for only 60:

deletes the disk allows = 100 - 40 sends        = 60 a second
drain rate              = 60/s - 40/s new       = 20 a second
time to empty           = 3,600 / 20/s          = 180 s, not the 60 s lesson 1 planned

And while the disk is fully busy, every send waits in line behind other writes. That line is added to Asha's checkout.

Design B never seeks during normal work. Every write lands where the last one ended, so the head is already in place. The disk writes as fast as the platter passes under it. The Exos X20 datasheet gives that speed as 285 MB/s at its fastest:

messages a second = 285,000,000 bytes/s / 1,024 bytes = about 278,000
gap to design A   = 278,000 / 50                      = about 5,600 times

That is the puzzle's answer. The disk is fast at one thing, writing the next byte, and slow at another, going somewhere else. Design A asks it to go somewhere else for every message. Design B never does.

This is not a number from a textbook only. Kafka's design documentation reports the same effect on real hardware: an array of six 7,200 rpm disks wrote "about 600MB/sec" in order, and "only about 100kB/sec" at random places, a gap of over 6,000 times.

Two honest notes about these numbers:

• A disk can reorder waiting writes. If the broker keeps 16 writes waiting at once, the drive can pick a shorter path between them. The datasheet gives 550 random 4 KB writes a second that way. That lifts design A to about 275 messages a second. It is still about a thousand times less than appending.
• 278,000 a second is what the drive can absorb, not what the broker can promise. Each send also wants proof that its bytes reached the drive before OK. How many sends can wait for that proof, and how to share it between them, is the subject of lesson 3.

On an SSD the Gap Shrinks, and the Reason Changes

Most brokers today run on SSDs. An SSD has no arm and no platter, so there is no seek and no rotation. Does the log still matter?

Take a common consumer SSD, the Samsung 990 PRO. Its datasheet gives:

sequential write                           = 6,900 MB/s
random 4 KB writes, one at a time (QD1)    = 80,000 a second x 4,096 B = 328 MB/s
gap                                        = 6,900 / 328               = about 21 times
random 4 KB writes, 32 waiting (QD32)      = 1,550,000 a second x 4,096 B = about 6,350 MB/s

"QD" is queue depth: how many writes are waiting at once. With 32 waiting, the drive spreads them across its internal chips in parallel, and random writes come close to sequential speed.

Be honest about the shop. Design A on this SSD does 80,000 / 2 = 40,000 messages a second, even one write at a time. The email queue needs 40. On this drive, design A is fast enough for emails.

So why does every serious broker still use a log on SSDs? Because the reasons change. There are three.

1. A drive writes whole pages. Storage is written in fixed blocks, never single bytes. The operating system moves file data in 4 KB pages, and the 990 PRO's random write figure is for 4 KB writes. Design A changes 1 KB to send and a few bytes to delete, but each change rewrites a whole 4 KB page:

design A, per message:  send rewrites one 4 KB page, delete rewrites it again  = 8 KB written
design B, per message:  the message appended once                              = about 1 KB written

Design A writes about 8 times more bytes for the same work. Every byte written uses up some of the drive's life: flash cells survive a limited number of writes.

2. Flash cannot overwrite in place. A flash chip writes in pages of 2 to 16 KB, but it can only erase in much larger erase blocks, typically hundreds of KB to a few MB. A page can be written only after its whole block is erased. So when design A "overwrites" a slot, the drive actually writes the new version somewhere else and marks the old page dead. Later, to reuse a block, the drive must copy the pages in it that are still alive to a new place, then erase the block. This background copying is called garbage collection, and every copy is an extra write the broker never asked for.

Garbage collection is cheap when a whole block dies at the same time: there is nothing alive to copy. A 2017 study of SSDs, "The Unwritten Contract of Solid State Drives", names this as a rule: clients "should group writes by the likely death time of data". A log does exactly that. Messages written together sit together, and when the broker later drops a whole old piece of the log, they die together. Design A scatters messages of every age across the file and frees them one by one, which is the worst case for the drive.

3. Datasheet speeds are best cases. The 990 PRO's numbers were measured with its fast write cache active, on a fresh drive. The same study separates "immediate performance" (what a pattern gets at first) from "sustainable performance" (what it keeps getting after the drive has been busy for a while). Scattered small overwrites look fine at first and degrade once garbage collection starts. Appending in large pieces keeps the drive in its fast mode.

The study also warns against a simple slogan. It calls "random writes considered harmful" an oversimplified myth. The rules that matter include large requests and grouping data that dies together. A log follows both.

Never Overwrite: What the Log Gives You at No Extra Cost

Speed is the reason people usually give for logs. There is a second reason, and for a broker it matters as much: a log never changes bytes it already wrote.

Look at design A when the power fails in the middle of a write. The broker is putting a new message into a slot. That slot shares a 4 KB page with three other messages, each one already acknowledged with an OK. A page write cut off halfway can leave a page that is part old, part new. Databases know this well. PostgreSQL's documentation says that "a page write that is in process during an operating system crash might be only partially completed, leading to an on-disk page that contains a mix of old and new data". So design A can destroy messages it promised to keep, while writing a different message.

A log cannot do that. Every write goes past the end of what already exists. A crash can damage only the end of the file: the last record, which was still being written. Everything before it is exactly as it was. Lesson 3 uses this to recover after a crash: read the file from a known good point, find where the damage starts, and cut the file there.

The same property makes reading simple. Readers look at bytes the writer will never touch again, so readers and the writer do not need to wait for each other. Kafka's design documentation puts it this way: on a log, "all operations are O(1) and reads do not block writes or each other."

Where Ready, In Flight and Deleted Live

Lesson 1 gave every message one of three states: ready (waiting for a worker), in flight (held by a worker, with a deadline), and deleted (done). In design A, the state was written into each slot. In a log, nothing is ever rewritten. So where do the states go?

Give each message a number: its position in the log. The first message ever written is 0, the next is 1, and so on. That number is the message's offset. Then the broker keeps three offsets:

• end: where the next send will be written.
• cursor: the oldest message that has never been handed to a worker. Everything from the cursor to the end is ready.
• head: the oldest message that is not deleted yet. Everything before the head is deleted.

Between the head and the cursor are messages that have been handed out at least once. Each one is in flight, or deleted, or ready again because its deadline passed. The broker tracks which in memory.

Here is the email queue at 14:00:00.4, just after worker W1 receives Asha's message. Her message was written at offset 1,268,410. Lesson 1 worked out that at normal traffic about 3.5 sends run at once, so the head trails the cursor by only a few messages:

offset:   1,268,406 | 1,268,407   1,268,408   1,268,409   1,268,410 | 1,268,411
          deleted   | in flight   deleted     in flight   in flight | (next send goes here)
                    |                                     (Asha)    |
                    ^ head                                          ^ cursor = end

Offset 1,268,408 is already deleted. Its worker was fast. But the head cannot move past 1,268,407, because that message is still in flight. The head moves only when the oldest message is done.

Each operation now changes a few numbers, and only send writes into the log:

send(m):        append m at end; end = end + 1
receive():      take a message from the ready-again list if there is one,
                else take the one at cursor and set cursor = cursor + 1;
                add (offset, deadline) to the in-flight table
delete(offset): remove offset from the in-flight table and mark it done;
                while the message at head is done: head = head + 1
deadline passes: move the offset from the in-flight table to the ready-again list

Lesson 4 builds the in-flight table and the deadlines properly. Lesson 5 builds deletion: the done marks, the moving head, and dropping old data.

What survives a restart? The end needs no saving: it is wherever the last good record in the file ends. The head is saved now and then in a small file next to the log. After a restart, the broker treats every message from the saved head onward as ready. Some of those were already deleted, like 1,268,408, so they go out a second time. That is the at-least-once trade from lesson 1, and it is what keeps recovery simple. Lesson 5 shows that saving only the head can resend far too much after a restart, and adds a small record for every delete. Lesson 3 covers how to save that small file so that a crash never leaves half of it.

What the Log Costs

• Deleted messages still take space. A deleted message stays in the file until its whole piece of the log is dropped. The broker trades disk space for never having to rewrite a file.
• One slow message holds the head back. If a message stays in flight for a long time, or fails again and again, the head cannot pass it. Lesson 5 shows how to free disk anyway, one segment at a time, and what to do with messages that never succeed.
• The states live outside the log. The broker needs memory for the in-flight table and a small saved file for the head. The log alone does not tell you which messages are done.

One Record, Byte by Byte

The log is a sequence of records, one per message. A record is the bytes the broker writes for one message. The reader must be able to walk the file from any known starting point and pull out records one by one, and it must be able to tell a good record from a damaged one. Here is the format this course uses:

record:
  length    4 bytes   how many bytes follow this field
  checksum  4 bytes   CRC-32C of the id and the body
  id        8 bytes   this message's offset in the log
  body      n bytes   the message, exactly as the producer sent it
numbers are big-endian: most significant byte first

Here is Asha's message as it sits in the file. The body is 37 bytes of text: {"order":4127,"email":"confirmation"}.

byte   hex                                                text               field
 0     00 00 00 31                                                           length = 49
 4     44 05 f4 73                                                           checksum
 8     00 00 00 00 00 13 5a ba                                               id = 1,268,410
16     7b 22 6f 72 64 65 72 22 3a 34 31 32 37 2c 22 65    {"order":4127,"e   body
32     6d 61 69 6c 22 3a 22 63 6f 6e 66 69 72 6d 61 74    mail":"confirmat   body
48     69 6f 6e 22 7d                                     ion"}              body

Check the numbers:

length       = checksum + id + body = 4 + 8 + 37   = 49   = 0x31
whole record = length field + 49     = 4 + 49       = 53 bytes
id           = 0x135aba = 1x16^5 + 3x16^4 + 5x16^3 + 10x16^2 + 11x16 + 10 = 1,268,410
checksum     = CRC-32C over the 45 bytes of id and body = 0x4405f473

Each field is there because a specific failure happens without it.

Length, so the reader can find the next record. Bodies have different sizes. Without a length, the reader cannot tell where Asha's body ends and the next record begins. With it, the reader steps forward record by record: read 4 bytes, read that many more, repeat. The length comes first because it is the one thing the reader needs before it can read anything else. A reader should also reject a length that is larger than the broker's maximum message size. That is a cheap first test that the bytes it is looking at really are the start of a record.

Checksum, so the reader can tell a damaged record from a real one. A checksum is a short number computed from a run of bytes. If any of the bytes change, the number almost certainly changes too. The writer computes it and stores it. The reader computes it again and compares.

Here is what it protects against. Flip the lowest bit of byte 25 of Asha's record. That byte is 0x34, the character 4. With the bit flipped it becomes 0x35, the character 5. The body now says {"order":5127,...}. It is still valid text. It is still a valid order number. Without a checksum, the broker would hand it to a worker, and some other customer would get Asha's confirmation. With a checksum, the reader computes CRC-32C over the changed bytes and gets 0xe6107f47, not the stored 0x4405f473. The broker knows the record is damaged.

The same check catches a record that was only partly written when the power failed. Lesson 3 relies on it: after a crash, the broker walks the last part of the log and cuts the file at the first record whose checksum does not match.

This course uses CRC-32C, a 32-bit cyclic redundancy check with the Castagnoli polynomial. Two reasons. First, its guarantees are known: an n-bit CRC detects every run of damaged bits up to n bits long, and it misses a longer run of damage with a chance of only about 1 in 2^32, which is 1 in about 4.3 billion. Second, it is cheap: modern Intel and ARM processors have an instruction that computes it in hardware. Kafka uses CRC-32C for its records too.

Notice what the checksum does not cover: the length field. That is deliberate, and Kafka and NATS do the same. If the length is damaged, the reader takes the wrong bytes as the record. The checksum test then runs over those wrong bytes, and it fails.

Id, so a record says which message it is. If records follow each other with no gaps, the reader could compute an offset by counting. Storing it costs 8 bytes per record, and buys three things:

• When the broker looks a record up (later in this lesson), it lands near the record and steps forward. Reading the id tells it exactly where it is. If the id is not what it expects, something is wrong, and the broker can stop instead of sending the wrong message.
• The log describes itself. Anything derived from the log, like the index later in this lesson, can be rebuilt from the log alone. Lesson 8 copies records between machines with their ids attached.
• Counting breaks the day records are removed from the middle of an old file. Some brokers do that to save space (lesson 5). A stored id stays correct.

Body, the message itself. The broker never parses it. To the broker it is n bytes. Only the producer and the consumer know it means "send the confirmation for order 4127".

The fixed part of every record costs space:

header            = 4 + 4 + 8      = 16 bytes
Asha's record     = 16 + 37        = 53 bytes     (the header is 30% of it)
an average record = 16 + 1,024     = 1,040 bytes  (the header is 1.5% of it)

For 1 KB messages the header hardly matters. For tiny messages it is a large share. Kafka answers this by grouping many records into one batch that shares one header. You will see that format at the end of the lesson.

Real formats often add fields. A timestamp is the most common one: it records when the message was written, which helps to keep or drop data by age (lesson 5). NATS JetStream stores a timestamp in every record, as you will see at the end of this lesson. Our broker leaves it out of the record. It keeps send times in a separate small file, the time index, which you will meet later in this lesson.

Some messages need a few extra fields: a due time for a delayed message, and two ids for an ordered queue (lesson 6). Our broker puts them in an optional attributes section between the id and the body, inside the bytes the checksum covers. The top bit of the length field says whether the section is there, the same trick NATS uses, which you will see at the end of this lesson. A reader clears that bit before it uses the length. Asha's confirmation has no attributes, so her record stays 53 bytes.

Segments: Many Files Instead of One

So far the log has been one file that grows forever. It cannot stay that way, and the first reason is deletion. To give back the space used by old, deleted messages, the broker must remove the start of the log. The standard file interface can shorten a file only from the end. It cannot cut off the start.

So the broker splits the log into many files. Each file is a segment: one file of the log on disk. Only the newest segment, the active segment, receives writes. When it is full, the broker closes it and starts a new one. Older segments never change again. When every message in a segment is deleted, the broker can drop the whole file in one step, wherever it sits in the log. That is lesson 5's job. This lesson only sets it up.

Our broker starts a new segment when the next record would push the active one past 64 MiB:

before appending a record of size r:
  if position + r > 64 MiB:
      close the active segment
      start a new file, named after the offset of the record about to be written
  append the record; position = position + r

Each segment is named after the offset of its first record, its base offset, padded with zeros to 20 digits. The padding makes an alphabetical sort of the file names the same as a numeric sort. Here is the email queue's directory at 14:00:00.4:

emails/00000000000001114102.log     64 MiB    offsets 1,114,102 to 1,179,570
emails/00000000000001179571.log     64 MiB    offsets 1,179,571 to 1,245,035
emails/00000000000001245036.log     growing   offsets 1,245,036 onward   (active)

Each full segment holds about 65,000 messages of about 1 KB:

1,179,571 - 1,114,102 = 65,469 messages
67,108,864 bytes / 65,469 messages = about 1,025 bytes each

To find the segment that holds a given offset, the broker keeps the base offsets in a sorted list in memory and picks the largest base offset that is not greater than the target. For Asha's offset 1,268,410, that is 1,245,036, the active segment.

Choosing the Segment Size

The size is a trade. Here is how long one segment lasts for the email queue at different sizes:

normal traffic = 5 messages/s x 1,024 bytes = 5,120 bytes a second
 
4 MiB    = 4,194,304 / 5,120     =     819 s  = about 14 minutes
64 MiB   = 67,108,864 / 5,120    =  13,107 s  = about 3.6 hours
100 MiB  = 104,857,600 / 5,120   =  20,480 s  = about 5.7 hours
1 GiB    = 1,073,741,824 / 5,120 = 209,715 s  = about 58 hours

There is also a hard ceiling. The index in the next section stores positions inside a segment in 4 bytes. Four bytes can count up to 2^32 bytes, which is 4 GiB. A segment must stay below that.

Real brokers chose very different sizes, because they were built for different traffic. Kafka's default segment is 1 GiB. NSQ's disk queue starts a new file every 100 MiB. NATS JetStream uses 4 MiB blocks for work-queue streams and 8 MiB for others. Our broker uses 64 MiB.

Finding a Record by Its Offset

Most of the time the broker reads the log in order. It keeps the cursor's file and byte position, reads the next record, and moves on. No search is needed.

But sometimes it must jump. Go back to lesson 1. W1 receives Asha's message at 14:00:00.4 and dies. At 14:00:30.4 her deadline passes and the message is ready again. W2 receives it. To hand it to W2, the broker needs the body.

Our broker's in-flight table (lesson 4) does not keep bodies. For each message it keeps the offset and the deadline. An offset is 8 bytes, and a body can be much larger, so the table stays small no matter how big messages are. The body is on disk anyway. So the broker has one task: given offset 1,268,410, find the record.

It already knows the segment: 1,245,036. Inside the segment, Asha's record is at position 23,959,523, about 24 MB into the file. The broker does not know that number. How does it find it?

Option 1: scan from the start of the segment. Read every record and check its id until 1,268,410 appears. That reads about 24 MB. From a hard disk at 285 MB/s:

scan time = 23,959,523 bytes / 285,000,000 bytes/s = about 84 ms, for one message

During a backlog, many messages come back after their deadline. Paying 84 ms of disk time for each one is too much.

Option 2: a dense index. Keep a second file, the offset index, with one entry per record: the record's offset and its position. An entry needs 8 bytes: 4 for the offset counted from the segment's base offset (the relative offset), 4 for the position. Finding a record is now a binary search. But the index grows with the number of records, and small records make it large.

Option 3: a sparse index. Keep one entry for every 4 KB of log, not for every record. Find the closest entry at or before the target, then step forward through the few records in between.

Why is option 3 almost as fast as option 2? Because of how storage moves data. A drive reads whole pages, and the operating system reads and caches files in 4 KB pages. Reading one byte from a page costs the same as reading the whole page. So an index finer than one entry per page buys almost nothing: the records it would skip are in the page the broker has to read anyway.

Our broker's rule: when it appends a record, if more than 4,096 bytes have been written since the last index entry, it writes a new entry for this record. At the same moment it writes an entry to a second small file, the time index: the time of this append (8 bytes) and the same relative offset (4 bytes). Kafka keeps the same pair of indexes, as its code at the end of this lesson shows. So the broker knows every message's send time to within one 4 KB step, a few messages, without storing a time in each record. Lesson 5 uses this to drop data by age.

dense, 53-byte records  = 67,108,864 / 53 = 1,266,205 entries x 8 bytes = 10,129,640 bytes
sparse                  = 67,108,864 / 4,096 = 16,384 entries x 8 bytes = 131,072 bytes

The sparse index has another good property: its size depends on how many bytes the segment holds, not on how many messages. Tiny messages do not make it bigger.

Walking the Lookup

Here is the lookup for offset 1,268,410, step by step.

Step 1: pick the segment. The largest base offset not greater than 1,268,410 is 1,245,036.

Step 2: make the offset relative.

relative offset = 1,268,410 - 1,245,036 = 23,374

Step 3: binary search the segment's index for the largest entry not greater than 23,374. Near Asha's record, the index holds:

The answer is the entry for 23,371, at position 23,956,421. The index has at most one entry per 4 KB written so far, so the search is short:

entries so far  <= 23,959,523 / 4,096 = about 5,850
comparisons     <= 13, because 2^13 = 8,192 is more than 5,850

Step 4: step forward through the log. Start reading records at position 23,956,421:

Each next position is the previous position plus the record size: 23,956,421 + 1,012 = 23,957,433, and so on.

Step 5: check the record. Compute CRC-32C over the id and body, compare it with 0x4405f473, and hand the body to W2.

The step forward read 3,155 bytes, from 23,956,421 to the end of Asha's record at 23,959,576. That is two 4 KB pages. Compare that with 24 MB for the scan.

Why does Asha's record not have its own index entry? The last entry was written at 23,371. By the time Asha's record was appended, only 1,012 + 1,187 + 903 = 3,102 bytes had been written since then, which is not more than 4,096. The next entry went to 23,376, when the count reached 3,102 + 53 + 1,064 = 4,219 bytes.

The Index Is a Copy, Not the Truth

The index holds nothing the log does not already have. Every entry can be computed again by walking the segment and reading each record's length and id. So the index is a cache of the log. If the broker crashes and the index is damaged or behind, the broker throws it away and rebuilds it from the log. That is lesson 3's job, and it is the second reason every record stores its own id.

This also sets a rule for writing: append the record to the log first, then add the index entry. If the broker crashes between the two, the index is only missing an entry, and a missing entry costs a slightly longer step forward, never a wrong answer.

The time index is the one part that is not a pure copy, because the log holds no times. If its newest entries are lost in a crash, the broker writes them again with the time of the restart. Those few messages then look a little younger than they are. They are kept a little longer, never dropped early.

The Page Cache: Why Recent Reads Never Touch the Disk

Everything so far has talked about "writing to disk". That is not what happens when a program calls write(), and the difference is the last piece of this lesson.

When the broker calls write() to append a record, the operating system copies the bytes into its own memory, into a set of 4 KB pages that mirror parts of files. This memory is the page cache. The pages are marked as changed, and write() returns. The operating system writes the changed pages to the drive later, in the background. Because a log's changes are all at the end, those background writes are long sequential runs, the fast case from earlier. Kafka's design documentation describes this: the operating system will "group smaller logical writes into large physical writes."

Reading works the same way in reverse. When the broker reads part of a file, the operating system first checks the page cache. If the page is there, the read is a memory copy. If not, it reads the page from the drive and keeps it in the cache. When it sees a program reading a file in order, it also reads the next pages ahead, before they are asked for.

How fast is this? On one laptop (Apple M1 Max, macOS), 100,000 appends of 1 KB each with write() took a median of about 4 µs each. Reading back a recent 1 KB record took a median of under 1 µs. Those are one machine's numbers, not a general figure, but the order of magnitude is the point: microseconds, the cost of copying memory.

Now apply it to the shop.

• Asha's redelivery. Her record was written at 14:00:00.3 and read again at 14:00:30.4, 30 seconds later. It is in the page cache. The lookup from the previous section, the index search and the step forward, runs entirely in memory.
• The outage backlog. 3,600 messages of 1 KB are about 3.6 MB. All of it stays in memory while it drains.
• How much fits. The page cache uses memory that programs are not using. Each GiB of it holds:

1,073,741,824 bytes / 5,120 bytes a second = 209,715 s = about 2.4 days of normal email traffic

So for the email queue, on a machine with a GiB or more of free memory, reads touch the drive only when a consumer is days behind, or right after the whole machine restarts and the cache is empty. Kafka's documentation describes the same effect on busy clusters: when consumers are mostly caught up, "you will see no read activity on the disks whatsoever as they will be serving data entirely from cache."

Why the Broker Does Not Keep Its Own Cache

A broker could keep recent messages in its own memory instead. Kafka's design documentation explains why it does not, and the reasons apply to any broker:

• The data would be in memory twice: once in the broker's own cache and once in the page cache.
• The page cache survives a broker restart. The documentation says this cache "will stay warm even if the service is restarted, whereas the in-process cache will need to be rebuilt in memory".

That last point has a consequence for lesson 1 that is easy to miss.

What Survives a Restart Now

The page cache belongs to the operating system, not to the broker process. When the broker process exits, for a crash or a deploy, the pages it wrote stay in the operating system's memory. The operating system still writes them to the drive. A new broker process on the same machine reads them back from the cache.

Go back to break three of lesson 1. An engineer redeploys the broker 80 seconds into the outage, with 3,200 messages waiting. With design B, every one of those messages went through write() before its OK. The process restarts, and all 3,200 are still there. The log alone fixes that failure, before a single extra step.

But not every failure is a process restart. If the whole machine loses power, or the operating system itself crashes, the changed pages that were not yet written to the drive are gone. write() never promised more than that. The Linux manual says it plainly: "A successful return from write() does not make any guarantee that data has been committed to disk." Closing that gap means asking the operating system to push the bytes to the drive and waiting until it has. That is fsync, it is much slower than write(), and it is the whole of lesson 3.

What This Did to Checkout

Lesson 1 promised that writing every message to disk would not undo the 300 ms checkout. Here is the account:

checkout with the email inside it           = 1,000 ms
checkout with the email on a queue          =   300 ms + one call to the broker
the broker's append into the page cache     =     0.004 ms (about 4 µs, measured on one laptop)
share of checkout                           = 0.004 / 300 = about 0.001%

The log makes the write cheap in three ways. It never seeks, so the drive works at its sequential speed. It never rewrites old bytes, so each message costs one write of about its own size. And the bytes go into the page cache first, so the broker's call returns in microseconds.

The price, stated plainly: this OK survives a broker restart, but not a power failure. Lesson 3 decides when the broker may say OK, measures what fsync costs, and shows how one fsync can cover many messages at once.

How Real Brokers Lay Out the Log

Three open-source brokers made these choices in three different ways. Each one shows one part of this lesson clearly.

NSQ: Length, Body, and a New File Every 100 MiB

NSQ is an open-source message broker written in Go, under the MIT license. Its disk storage lives in a separate package, go-diskqueue, also MIT. The excerpts below are from go-diskqueue at commit ff2a02e. NSQ creates one disk queue per topic and per channel, with a file size limit of 100 MiB by default.

This is the start of writeOne, the function that appends one message. A few lines earlier, totalBytes is set to 4 + dataLen: a 4-byte length plus the data.

	// will not wrap-around if maxBytesPerFile + maxMsgSize < Int64Max
	if d.writePos > 0 && d.writePos+totalBytes > d.maxBytesPerFile {
		if d.readFileNum == d.writeFileNum {
			d.maxBytesPerFileRead = d.writePos
		}
 
		d.writeFileNum++
		d.writePos = 0
 
		// sync every time we start writing to a new file
		err = d.sync()
		if err != nil {
			d.logf(ERROR, "DISKQUEUE(%s) failed to sync - %s", d.name, err)
		}
 
		if d.writeFile != nil {
			d.writeFile.Close()
			d.writeFile = nil
		}
	}

diskqueue.go lines 377 to 396.

Line by line:

• The comment notes that adding the two sizes cannot overflow a 64-bit number with sane settings.
• if d.writePos > 0 && d.writePos+totalBytes > d.maxBytesPerFile is the segment rule from this lesson. If the file is not empty and this message would push it past the limit, start a new file. The writePos > 0 part means a single message larger than the limit still gets written, alone in its own file.
• The inner if handles a reader that is reading the same file as the writer. It records the file's final size, writePos, so the reader knows where this file ends and when to move to the next one.
• d.writeFileNum++ picks the next file number, and d.writePos = 0 starts at the beginning of it. NSQ names files by a counter, not by an offset, for example name.diskqueue.000002.dat (line 546).
• d.sync() forces the finished file to the drive and saves the queue's positions. The comment says it happens every time a new file starts. Lesson 3 covers what sync does and why.
• if err != nil logs a failed sync but does not stop the write.
• The last block closes the old file. The next lines of writeOne open the new file when writeFile is nil.

And this is the end of writeOne, where the record is built and written:

	d.writeBuf.Reset()
	err = binary.Write(&d.writeBuf, binary.BigEndian, dataLen)
	if err != nil {
		return err
	}
 
	_, err = d.writeBuf.Write(data)
	if err != nil {
		return err
	}
 
	// only write to the file once
	_, err = d.writeFile.Write(d.writeBuf.Bytes())
	if err != nil {
		d.writeFile.Close()
		d.writeFile = nil
		return err
	}
 
	d.writePos += totalBytes
	d.depth += 1
 
	return err

diskqueue.go lines 417 to 439.

Line by line:

• d.writeBuf.Reset() empties a buffer that is reused for every record.
• binary.Write(..., binary.BigEndian, dataLen) puts the 4-byte length into the buffer, most significant byte first, the same byte order as this course's format.
• d.writeBuf.Write(data) puts the message bytes after the length.
• d.writeFile.Write(d.writeBuf.Bytes()) is the only call that touches the file: one write() for the whole record. As the comment says, the record goes to the file in one piece, not as a length and then a body. This write() lands in the page cache, as this lesson described.
• If the write fails, the file is closed and forgotten, so the next write reopens it.
• d.writePos += totalBytes moves the end of the log forward by the record's size.
• d.depth += 1 counts one more message waiting in the queue.

So NSQ's disk record is a 4-byte length and the data. What is in the data? NSQ's server builds it in Message.WriteTo (nsqd/message.go lines 39 to 65, NSQ commit 85cf10c): an 8-byte timestamp, a 2-byte attempt count, a 16-byte message id, and then the body. So NSQ's record has a length, an id and a body, like ours, plus a timestamp. It has no checksum. When NSQ reads a record, the only check it can make is that the length is between a minimum and a maximum (lines 326 to 332). A record whose body is damaged but whose length looks normal passes. Lesson 3 shows what that costs after a crash.

NSQ also has no index, and it does not need one. Its id is a unique label, not a position. NSQ reads each disk queue in order, once. Its read position is a file number and a byte position (readFileNum, readPos), saved together with the write position in a small metadata file. When a message is handed from the disk queue to the channel, the read position moves past it (lines 700 to 703), and from then on the message lives in memory. In this lesson's terms, NSQ's head and cursor are the same position. That is simpler: no jumping back, so no index. It is also why, as lesson 1 showed, NSQ's in-flight messages exist only in memory.

Kafka: A Sparse Index Every 4 KB

Apache Kafka is an open-source log-based broker written in Java and Scala, under the Apache 2.0 license. The excerpts are from commit 03e6606. Kafka's unit of writing is a batch: a group of records sent together, sharing one header.

This is how a segment appends batches and decides when to add an index entry, from LogSegment.java:

    public void append(long largestOffset,
                       MemoryRecords records) throws IOException {
        if (records.sizeInBytes() > 0) {
            // ...
            int physicalPosition = log.sizeInBytes();
 
            ensureOffsetInRange(largestOffset);
 
            // append the messages
            long appendedBytes = log.append(records);
            // ...
 
            for (RecordBatch batch : records.batches()) {
                long batchMaxTimestamp = batch.maxTimestamp();
                long batchLastOffset = batch.lastOffset();
                if (batchMaxTimestamp > maxTimestampSoFar()) {
                    maxTimestampAndOffsetSoFar = new TimestampOffset(batchMaxTimestamp, batchLastOffset);
                }
 
                if (bytesSinceLastIndexEntry > indexIntervalBytes) {
                    offsetIndex().append(batchLastOffset, physicalPosition);
                    timeIndex().maybeAppend(maxTimestampSoFar(), shallowOffsetOfMaxTimestampSoFar());
                    bytesSinceLastIndexEntry = 0;
                }
                var sizeInBytes = batch.sizeInBytes();
                physicalPosition += sizeInBytes;
                bytesSinceLastIndexEntry += sizeInBytes;
            }
        }
    }

storage/.../log/LogSegment.java lines 250 to 280. The two cuts remove trace logging.

Line by line:

• append(largestOffset, records) receives one or more batches already in their on-disk format, and the largest offset among them.
• if (records.sizeInBytes() > 0) skips an empty append.
• physicalPosition = log.sizeInBytes() reads the current size of the segment file. That is where the new bytes will start: the end of the log.
• ensureOffsetInRange(largestOffset) checks that the offset, minus the segment's base offset, still fits in the index's 4-byte relative offset, and throws an error if it does not. It is a last safety check. Before appending, Kafka already starts a new segment when the segment is too big, too old, its index is full, or the offsets would not fit (shouldRoll, lines 167 to 173). This is the 4-byte limit from this lesson, enforced.
• log.append(records) writes all the batches at the end of the file in one call.
• The loop walks the batches that were written, to update the indexes.
• The three timestamp lines keep track of the newest timestamp in the segment. Kafka uses it to find messages by time and to decide when a segment is old enough to drop (lesson 5).
• if (bytesSinceLastIndexEntry > indexIntervalBytes) is this lesson's sparse rule. indexIntervalBytes defaults to 4,096.
• offsetIndex().append(batchLastOffset, physicalPosition) adds an entry: this batch's last offset, and the position where the batch starts. Kafka indexes batches, not single records.
• timeIndex().maybeAppend(...) adds a matching entry to a second index, by time.
• bytesSinceLastIndexEntry = 0 starts counting again.
• The last three lines move the position past this batch and add its size to the count.

The index file's own comment gives its format: each entry is "a 4 byte "relative" offset and a 4 byte file location", relative to the segment's base offset, so offset 55 in a segment that starts at 50 "would be stored as 5" (OffsetIndex.java lines 42 to 56). The same comment says: "No attempt is made to checksum the contents of this file, in the event of a crash it is rebuilt." That is this lesson's "the index is a copy, not the truth".

The lookup itself is OffsetIndex.lookup (lines 88 to 106). It is step 3 of this lesson's walk: a binary search for the largest entry at or below the target, over an index file that is memory-mapped (its pages are mapped into the broker's memory, so reading an entry reads the page cache directly). If every entry is larger than the target, it returns the segment's base offset and position 0, and the step forward starts at the very beginning of the file.

The step forward happens in translateOffset, which calls offsetIndex().lookup(offset) and passes the position to searchForOffsetFromPosition. That function walks batches forward until it reaches the batch holding the target (LogSegment.java lines 398 to 401). Choosing the segment is floorSegment: "the log segment with the greatest offset less than or equal to the given offset", from a sorted map of base offsets (LogSegments.java lines 214 to 222). Segment files are named after their base offset, padded to 20 digits "so that ls sorts the files numerically" (LogFileUtils.java lines 95 to 108).

One detail in largestLowerBoundSlotFor shows how seriously Kafka takes the page cache. A plain binary search over a large index touches pages spread across the whole file. Most lookups are for recent offsets, near the end, so the pages in the middle of the index go cold and leave the page cache. Then a search that happens to land on one of them must wait for the disk. The comment in AbstractIndex.java reports that in Kafka's test this pushed "the at-least-once produce latency to jump to about 1 second from a few ms." Kafka's fix is to search the last 8 KB of the index first, a "warm" section that recent lookups keep in memory, and to search the rest only when the target is older (AbstractIndex.java lines 327 to 386). With 8-byte entries every 4 KB, those 8 KB cover about 4 MB of the newest log.

Kafka's checksum is per batch. The batch header holds a CRC-32C that "covers the data from the attributes to the end of the batch" (DefaultRecordBatch.java lines 45 to 71). Adding up the fields in that header gives 61 bytes, shared by every record in the batch. That is Kafka's answer to the header cost of small messages.

NATS JetStream: A Record With a Checksum

NATS is an open-source messaging server written in Go, under the Apache 2.0 license. JetStream is its storage layer. The excerpt is from nats-server at commit 64dda80. JetStream calls its segments message blocks, files named like 1.blk, 2.blk. This is how it writes the start of one record, from server/filestore.go:

	// Formats
	// Format with no header
	// total_len(4) sequence(8) timestamp(8) subj_len(2) subj msg hash(8)
	// With headers, high bit on total length will be set.
	// total_len(4) sequence(8) timestamp(8) subj_len(2) subj hdr_len(4) hdr msg hash(8)
 
	var le = binary.LittleEndian
 
	l := uint32(rl)
	hasHeaders := len(mhdr) > 0
	if hasHeaders {
		l |= hbit
	}
 
	// Reserve space for the header on the underlying buffer.
	mb.cache.buf = append(mb.cache.buf, make([]byte, msgHdrSize)...)
	hdr := mb.cache.buf[len(mb.cache.buf)-msgHdrSize : len(mb.cache.buf)]
	le.PutUint32(hdr[0:], l)
	le.PutUint64(hdr[4:], seq)
	le.PutUint64(hdr[12:], uint64(ts))
	le.PutUint16(hdr[20:], uint16(len(subj)))

server/filestore.go lines 7846 to 7866.

Line by line:

• The comment is the record format. A 4-byte total length, an 8-byte sequence, an 8-byte timestamp, a 2-byte subject length, the subject, the message, and an 8-byte hash at the end. The sequence is JetStream's offset: the message's position in the stream. The subject is the name the message was published to, such as orders.email.
• The second format is the same with message headers (key and value pairs a producer can attach) added before the body.
• le = binary.LittleEndian: NATS writes numbers least significant byte first. NSQ and this course use the opposite order. Either works, as long as every reader and writer agree.
• l := uint32(rl): rl is the full record length, header and hash included (fileStoreMsgSizeRaw, lines 10188 to 10195: 22 + subject + body + 8).
• if hasHeaders { l |= hbit } sets the top bit of the length to mark "this record has headers". A real record is never long enough to need that bit, so the bit is free to carry a flag.
• The next two lines grow the block's write buffer by msgHdrSize, 22 bytes, and take a slice over those 22 bytes. JetStream builds records in memory first, then writes the buffer to the file.
• The four Put lines fill the 22 bytes: length at byte 0, sequence at byte 4, timestamp at byte 12, subject length at byte 20. That is 4 + 8 + 8 + 2 = 22.

The lines right after this (7868 to 7892) append the subject, the headers and the body, then compute an 8-byte HighwayHash over the sequence, the timestamp, the subject, the headers and the body, and append it as the record's last 8 bytes. Like our CRC-32C, the hash does not cover the length. Unlike ours, it sits at the end of the record instead of near the start. Both work. A checksum at the end means the writer can compute it while the bytes stream past. A checksum near the start means the reader learns the expected value before it reads the body.

JetStream made one more choice worth noting. Its blocks are small: 4 MiB for work-queue streams and 8 MiB for others (dynBlkSize, lines 866 to 881). With blocks that small, JetStream keeps a dense index in memory, one 4-byte entry per message (cache.idx, lines 283 to 292), and builds it by scanning a block when the block is loaded (indexCacheBuf, line 8618). Small segments make a dense index cheap. Kafka's large segments make a sparse index necessary. Both are the same trade, priced at different sizes.

Side by Side

The Takeaway

1. A hard disk is fast at writing the next byte and slow at going somewhere else. Updating slots in place gives about 50 messages a second on one disk; appending to the end gives about 278,000 on the same disk. On SSDs the gap shrinks to about 21 times at one write at a time, but appending still writes about 8 times fewer bytes and keeps garbage collection cheap, because data written together dies together.
2. A log never changes bytes it already wrote. A crash can damage only the last record, never one the broker already said OK to. Readers and the writer never wait for each other.
3. Message states live beside the log, not in it: an end where sends go, a cursor for the next message never handed out, and a head before which everything is deleted. Only send writes into the log.
4. A record is length, checksum, id and body. The length finds the next record, the checksum catches damage, and the id lets a record say which message it is, so anything derived from the log can be rebuilt from it. Asha's record is 53 bytes at offset 1,268,410.
5. The log is split into segments, here 64 MiB each, named by base offset, so old data can later be dropped a whole file at a time. A sparse index, one 8-byte entry per 4 KB, finds any offset with one short binary search and a step forward of at most a page or two.
6. write() puts bytes in the page cache and returns in microseconds. Recent records are read back from memory. The page cache survives a broker restart but not a power failure.

The one sentence to keep: a broker makes durable writes cheap by only ever adding to the end of a file, and lets the operating system's memory serve the reads.

The log turned "write before OK" into a few microseconds. But those microseconds bought a write into memory, not onto the drive. The next lesson asks exactly when the broker may say OK, what it costs to wait for the drive, and how many messages a power failure can still take: fsync and the loss window.

References

• NSQ go-diskqueue repository, commit ff2a02e5299f130a68a7ffa6d200b9bb55671b73, MIT license (LICENSE)
• diskqueue.go L377-L396: starting a new file when the current one is full
• diskqueue.go L417-L439: writing a length-prefixed record in one write()
• diskqueue.go L326-L332: the reader's only check, a length between a minimum and a maximum
• diskqueue.go L545-L547: file names by counter
• diskqueue.go L700-L703: the read position moves when a message is handed to the channel
• NSQ repository, commit 85cf10c09c6c3c86160d6f0eb156f62d0efc1648, MIT license (LICENSE)
• nsqd/message.go L39-L65: what NSQ writes inside each record (timestamp, attempts, 16-byte id, body)
• nsqd/options.go L146-L149: MaxBytesPerFile default of 100 MiB
• Apache Kafka repository, commit 03e66064307d921ae62a80332ae7bfca2d361c54, Apache License 2.0 (LICENSE)
• LogSegment.java L250-L280: append and the sparse index rule
• LogSegment.java L167-L173: shouldRoll, when Kafka starts a new segment
• LogSegment.java L398-L401: translateOffset, index lookup then step forward
• OffsetIndex.java L42-L56: index entry format, 4-byte relative offset and 4-byte position, rebuilt after a crash
• OffsetIndex.java L88-L106: lookup
• AbstractIndex.java L327-L386: the warm section of the index and the page cache
• LogSegments.java L214-L222: floorSegment
• LogFileUtils.java L95-L108: segment names padded to 20 digits
• DefaultRecordBatch.java L45-L71: batch header and CRC-32C
• ServerLogConfigs.java L92-L98: index interval default of 4,096 bytes
• LogConfig.java L130: default segment size of 1 GiB
• Kafka broker configuration (Kafka 4.3 documentation): log.segment.bytes default 1073741824
• Kafka design (Kafka 4.3 documentation): "Don't fear the filesystem!" (600MB/sec linear vs 100kB/sec random writes, page cache, write-behind, cache stays warm after a restart), "Constant Time Suffices" (10 ms per seek, reads do not block writes), and caught-up consumers served entirely from cache
• NATS server repository, commit 64dda80fdd87b41b2afcdc5faf5d846db6c189b0, Apache License 2.0 (LICENSE)
• server/filestore.go L7846-L7866: JetStream record format and header
• server/filestore.go L10188-L10195: fileStoreMsgSizeRaw, the full record length
• server/filestore.go L7868-L7892: body and 8-byte HighwayHash
• server/filestore.go L866-L881: block sizes, 4 MiB for work queues and 8 MiB otherwise
• server/filestore.go L283-L292 and L8618: the in-memory per-block index
• Seagate Exos X20 data sheet: 7,200 rpm, 285 MB/s sustained transfer, 4.16 ms average latency, 550 random 4K writes a second at queue depth 16
• Samsung 990 PRO data sheet: 6,900 MB/s sequential write, 80K IOPS random 4KB write at QD1, 1,550K at QD32, measured with Intelligent TurboWrite active
• The Unwritten Contract of Solid State Drives (He, Kannan, Arpaci-Dusseau, Arpaci-Dusseau, EuroSys 2017): flash pages and erase blocks, garbage collection, grouping by death time, immediate vs sustainable performance
• PostgreSQL 18 documentation, Write Ahead Log settings: full_page_writes and partially written pages
• write(2), Linux manual page: "A successful return from write() does not make any guarantee that data has been committed to disk."
• Cyclic redundancy check (Wikipedia): burst error detection of an n-bit CRC, CRC-32C and its hardware support