Day 1: Pack Web Metadata into a Contiguous Byte Array — and Measure the Cost of Cache Misses

Pack Web Metadata into a Contiguous Byte Array — and Measure the Cost of Cache Misses

In academic computer science, data structures are abstract graphs. A linked list is drawn as a series of boxes connected by arrows. You are taught that inserting an element into a linked list is an $O(1)$ operation, while inserting into an array is $O(N)$ because you must shift elements.

But when your code runs on physical hardware inside a high-throughput system, these abstract models can mislead you. In a modern production environment, a linked list is often one of the slowest ways to store and traverse sequential data.

Today, we will build the foundation of the Relic Browser's metadata index. We will pack web crawl metadata into a raw, contiguous byte array, write a zero-allocation parser to read it, and measure exactly how much faster it is than a traditional pointer-heavy linked list.

The Production Stakes: Why Pointers Kill Throughput

In 2013, the Apache Cassandra team faced a scaling bottleneck. Cassandra uses an in-memory write buffer called a Memtable to store incoming writes before flushing them to disk as SSTables. Originally, these Memtables were composed of standard JVM objects containing pointers to other objects.

As write throughput scaled to hundreds of thousands of operations per second, two things happened:

1. 1.Garbage Collection (GC) Storms: The JVM garbage collector had to trace millions of tiny, short-lived objects on the heap, leading to multi-second stop-the-world pauses.

2. 2.CPU Starvation: Even when the CPU was at 100% utilization, profiling showed it was spending up to 70% of its cycles waiting for memory to arrive from RAM. The CPU was stalled on cache misses because the Memtable's pointer-heavy structures were scattered randomly across physical memory.

To solve this, Cassandra introduced off-heap, contiguous memory allocators (Slab Allocators). By packing records sequentially into raw byte buffers, they bypassed GC entirely and maximized CPU cache locality.

To understand why this works, we must look at how physical CPUs fetch data.

                  [ CPU Core ]
                       │
         Reads 64-byte Cache Lines (Fast: ~1-4ns)
                       ▼
               [ L1/L2/L3 Cache ]
                       │
          If missed, fetches from RAM (Slow: ~100ns)
                       ▼
             [ Main Memory (RAM) ]
 
  Contiguous Layout (Packed Bytes):
  ┌──────────────────┬──────────────────┬──────────────────┐
  │ Record 0 (32B)   │ Record 1 (32B)   │ Record 2 (32B)   │  <-- Single 64B cache line
  └──────────────────┴──────────────────┴──────────────────┘      gets 2 full records!
 
  Pointer-Chasing Layout (Linked List):
  ┌──────────────┐      ┌──────────────┐      ┌──────────────┐
  │ Node 0 (Heap)│ ───> │ Node 1 (Heap)│ ───> │ Node 2 (Heap)│  <-- Scattered in RAM.
  └──────────────┘      └──────────────┘      └──────────────┘      Each hop is a cache miss.

The Intuition: The Library Scroll

Imagine you are researching history in a library.

A linked list is like a scavenger hunt. You find a card that says: "The treaty text is on Shelf 4, Row B." You walk to Shelf 4, read the paragraph, and find another note: "The next paragraph is on Shelf 12, Row F." You spend 90% of your time walking across the library floor and only 10% reading.

A contiguous array is a continuous scroll of paper. Every line of the treaty is written directly below the previous one. You sit at your desk and slide your eyes down the page. Your eyes never have to wait for your legs to catch up.

In hardware, the library floor is your system's Main Memory (RAM). The desk is your CPU's L1/L2 Cache. When you read a single byte from RAM, the CPU does not fetch just that byte. It fetches a 64-byte block called a cache line and places it in the cache.

If your records are packed sequentially next to each other, a single memory fetch pulls multiple records into the CPU cache simultaneously. The next reads are virtually instant (1 nanosecond). If your records are scattered across the heap via pointers, every single pointer dereference forces the CPU to stall for up to 100 nanoseconds while waiting for RAM to deliver the next block.

The Architecture: Packing Metadata

To build the Relic Browser's high-speed indexing engine, we will layout our web metadata records into a flat []byte slice. Each record contains:

• Status Code: 4-byte unsigned integer (uint32)

• Latency: 8-byte unsigned integer (uint64, microseconds)

• Payload Size: 4-byte unsigned integer (uint32)

• URL Hash: 16 bytes (fixed-size MD5 digest)

This gives us a fixed record size of exactly 32 bytes. Because 32 divides evenly into 64, exactly two complete records fit into a single CPU cache line.

We will contrast this with a pointer-based linked list where each node is a heap-allocated struct containing pointers to its data and the next node. To simulate a real-world, long-running production heap where memory is fragmented, our linked list will have its physical node allocations shuffled in memory, while maintaining their logical sequence.

The Packed Layout Reader

To read from our flat byte array without allocating memory on the heap, we use direct offset math. Here is the core implementation pattern in Go:

// RecordSize is exactly 32 bytes, fitting perfectly into CPU cache lines
const RecordSize = 32

type PackedReader struct {
	data []byte
}

// ReadRecord extracts fields directly from the slice using offset math
func (r *PackedReader) ReadRecord(index int) (uint32, uint64, uint32) {
	offset := index * RecordSize
	
	// Read fields using BigEndian byte decoding
	statusCode := binary.BigEndian.Uint32(r.data[offset : offset+4])
	latency := binary.BigEndian.Uint64(r.data[offset+4 : offset+12])
	payloadSize := binary.BigEndian.Uint32(r.data[offset+12 : offset+16])
	
	return statusCode, latency, payloadSize
}

This code performs no heap allocations. It reads fields directly out of the already-loaded byte array, allowing the CPU to stream memory sequentially.

Trade-off Honesty

Before we implement this, we must acknowledge the trade-offs of contiguous, packed layouts:

If your system requires constant random insertions and deletions in the middle of a sequence, a contiguous array is a poor choice. But for the Relic Browser's indexing engine—where we write metadata sequentially and search it repeatedly—contiguous memory is the only way to sustain production throughput.

The Assignment: Variable-Length Field Offsets

Currently, our record layout uses a fixed-size 16-byte URL hash. In production, we want to store the actual variable-length URL string without sacrificing the cache locality of our fixed-size records.

Your assignment is to modify the packing engine to support variable-length URLs using a split-buffer architecture:

1. 1.Fixed Segment: A contiguous array of 32-byte records. Instead of storing the raw URL or a pointer, store a 4-byte offset and a 2-byte length pointing to a secondary contiguous byte array (the String Heap).

2. 2.Variable Segment (String Heap): A single, raw byte array containing all URL strings appended sequentially.

Goal

Implement the ReadURL method on the packed reader to fetch the variable-length string from the string heap using the offset and length stored in the fixed record.

Hints

• The fixed record layout should change:

• Bytes 0-3: Status Code

• Bytes 4-11: Latency

• Bytes 12-15: Payload Size

• Bytes 16-19: URL Offset in String Heap (uint32)

• Bytes 20-21: URL Length (uint16)

• Bytes 22-31: Unused/Padding

• To read the URL string without allocating a new string object during traversal, return a slice of the string heap: string(stringHeap[offset : offset+length]).

Solution Space

Here is the pattern for implementing the split-buffer variable-length reader:

type SplitBufferReader struct {
	fixedData  []byte
	stringHeap []byte
}

func (r *SplitBufferReader) ReadRecordAndURL(index int) (uint32, uint64, uint32, string) {
	offset := index * RecordSize
	
	statusCode := binary.BigEndian.Uint32(r.fixedData[offset : offset+4])
	latency := binary.BigEndian.Uint64(r.fixedData[offset+4 : offset+12])
	payloadSize := binary.BigEndian.Uint32(r.fixedData[offset+12 : offset+16])
	
	// Read the offset and length of the variable-length URL
	urlOffset := binary.BigEndian.Uint32(r.fixedData[offset+16 : offset+20])
	urlLen := binary.BigEndian.Uint16(r.fixedData[offset+20 : offset+22])
	
	// Slice directly into the string heap
	url := string(r.stringHeap[urlOffset : urlOffset+uint32(urlLen)])
	
	return statusCode, latency, payloadSize, url
}

This design keeps the primary index traversal contiguous and predictable, while isolating variable-length data to a secondary sequential read.

In the next lesson, Day 2: The Tension, we will explore how to perform high-speed sorting directly on these contiguous byte buffers without unpacking them into heap objects.