Yurin's Land - LevelDB_01: 爱，延迟与局部性

传说在计算机纪元的某个清晨，第零日尚未被定义，混沌只是一片未初始化的内存。
第一天，Jeff Dean 说，要有计算，于是有了分布式系统，延迟被测量，尾延迟被恐惧。
第二天，他分开了存储与计算，于是数据开始在集群之间流动，如同洪水。
第三天，他让索引生长，于是查询有了路径，复杂度被驯服。
第四天，他创造了缓存，于是时间被折叠，过去与现在几乎无差。
第五天，他定义了一致性与可用性的边界，于是系统学会在不完美中运行。
第六天，他看着世间万物——日志、表。
到了第七天，天地万物都已平稳运行。Jeff Dean 决定给自己放个假。下午三点一刻，阳光正好，他端起一杯锡兰红茶，准备享受难得的闲暇。
然而，当他想记录红茶随时间冷却的温度日志时，发现当时宇宙默认的 B+ 树数据库在面对海量随机写入时，产生了 IO 瓶颈。高并发下的锁竞争让系统的响应慢了足足 0.5 毫秒——这让他眉头微微一皱。
为了不让阻塞的线程破坏下午茶的雅兴，他轻叹一口气，放下了茶杯。在等红茶降温到最佳饮用温度的十五分钟里，随手基于 LSM-Tree 机制，创造了轻量级、极速的键值对存储引擎。
于是，LevelDB 就这样在第七天的下午茶时间诞生了。（这个下午茶还诞生了 Google 的 MapReduce 和 TensorFlow，但那是另一个故事了。）

Yurin 正在学习 LevelDB 的实现，被 TableIterator 中的 seek 方法折磨要疯了，于是写写博客，暂时借口摸鱼。因为 Yurin 是 Zig 批，所以这篇博客的代码示例都是 Zig 写的。Z 门！

应知应会

现代计算机为了提高性能，做了很多远超冯诺依曼体系的优化，其中最重要的就是缓存行（Cache Line）。

CPU 的缓存是以缓存行为单位进行读写的，通常一个缓存行的大小是 64 字节。这意味着当 CPU 访问内存时，会将包含该地址的整个缓存行加载到缓存中。

var x: [64]u8 = undefined; // 假设 x[0] 刚好位于一个 Block 的起始位置
for (x) |*byte| {
    // 访问 x 中的任意一个 byte 都会将整个缓存行加载到缓存中
    _ = byte.*;
}

现代 DDR5 的工作频率通常是 4800 MHz，而 CPU 的主频可能在 3 GHz 左右。每个 CPU 时钟周期大约是 0.33 纳秒，而访问内存的延迟可能在 100 纳秒以上。也就是说，访问内存可能需要数百个 CPU 时钟周期。因此，CPU 设计了多级缓存（L1、L2、L3）来减少访问内存的次数。每当 CPU 访问一个内存地址时，它会先检查缓存中是否有对应的数据，如果没有，就会从内存中加载整个缓存行到缓存中。因此，访问内存时，如果数据在同一个缓存行中，CPU 只需要加载一次缓存行，就可以访问多个数据，这就是所谓的空间局部性。

虽然但是，~~OS 是一款由 Vendor 开发的开放世界冒险游戏~~，CPU 和内存并不被单个程序独占，OS 调度时会发生

# a0 = current_ctx
# a1 = next_ctx

# 保存当前上下文
sd ra, 0(a0)
sd sp, 8(a0)
sd s0, 16(a0)
...
sd s11, 104(a0)

# 保存 pc
sd ra, 112(a0)

# 恢复下一个上下文
ld ra, 0(a1)
ld sp, 8(a1)
ld s0, 16(a1)
...
ld s11, 104(a1)

ld t0, 112(a1)   # next pc

# 跳转
jr t0

然后就发生了神秘的 jump，CPU 的指令流水线被打乱。

想象一下，你正在精心构建一座积木城堡，突然 OS 调度器这个不讲理的房东闯进来，把你直接扔到大街上，把房间租给了一个正在运行 chrome.exe 的疯子。当你好不容易排队重新进屋时，发现你的城堡被拆得干干净净，地板上只剩下一堆不认识的碎片… （哎呀，这 OS 怎么那么坏啊😭）

所以仅仅是空间局部性，并不能保证 CPU 的缓存命中率，将规模的读写集中在特定区域，保证时间局部性也是非常重要的。

不是因为缓存一定会命中，而是因为一旦命中，它就必须“值得“。

应知应会副本

当我们使用 malloc 分配内存时，运行时通常会执行类似的操作

const actual_len = @max(len +| @sizeOf(usize), alignment.toByteUnits());
const slot_size = math.ceilPowerOfTwo(usize, actual_len) catch return null;
const class = math.log2(slot_size) - min_class;
if (class < size_class_count) {
    const addr = a: {
        const top_free_ptr = global.frees[class];
        if (top_free_ptr != 0) {
            const node: *usize = @ptrFromInt(top_free_ptr + (slot_size - @sizeOf(usize)));
            global.frees[class] = node.*;
            break :a top_free_ptr;
        }

        const next_addr = global.next_addrs[class];
        if (next_addr % bigpage_size == 0) {
            const addr = allocBigPages(1);
            if (addr == 0) return null;
            //std.debug.print("allocated fresh slot_size={d} class={d} addr=0x{x}\n", .{
            //    slot_size, class, addr,
            //});
            global.next_addrs[class] = addr + slot_size;
            break :a addr;
        } else {
            global.next_addrs[class] = next_addr + slot_size;
            break :a next_addr;
        }
    };
    return @ptrFromInt(addr);
}
const bigpages_needed = bigPagesNeeded(actual_len);
return @ptrFromInt(allocBigPages(bigpages_needed));

（感恩 Andrew Kelley 提供的 std.heap.BrkAllocator 的实现）

分配器通常首先尝试 freelist 中是否有合适大小的内存块，如果有，就直接返回；如果没有，就从预分配的内存区域中分配新的内存块。最坏的情况是需要分配一个新的内存块

此时将触发复杂的内存管理操作，包括：

进行 brk 或 mmap 系统调用来请求更多的内存
OS 下沉内核，OS 仅修改进程的虚拟地址空间映射表，并不立即分配物理内存页
恢复上下文，重新调度线程
更新分配器的内部数据结构以跟踪新的内存块
初次访问新分配的内存块时，可能会触发缺页中断 Page Fault
OS 处理缺页中断，分配物理内存页，并将其映射到进程的虚拟地址空间中
恢复上下文，重新调度线程

显而易见的，前两种情况是快路径，跳转位置仍在当前程序的局部空间，而最后一种则会发生多次的用户态-内核态切换

LevelDB 为什么不慌

存在频繁内存读写的场景，LevelDB 选择了 LSM-Tree 作为底层数据结构。LSM-Tree 的设计理念是将写操作集中在内存中进行，减少对磁盘的频繁访问，从而提高写性能。

道理我都懂，所以和上文有什么关系？

咳咳，为了克服传统 malloc 系列函数性能不可控的问题，在性能敏感路径上，LevelDB 使用了竞技场分配器(アリーナアロケータ)

什么是 Arena？它是一种内存分配策略，预先分配一大块内存，并在其中进行小块内存的分配，并在生命周期结束时，一次性清理所有内容。

我们可以写一个非常简单的 POC

const Arena = struct {
    backed_allocator: std.mem.Allocator,
    buffer: []u8,
    offset: usize,

    pub fn init(gpa: std.mem.Allocator, size: usize) !Arena {
        return Arena{
            .buffer = try gpa.alloc(u8, size),
            .offset = 0,
        };
    }

    pub fn deinit(self: *Arena) void {
        self.backed_allocator.free(self.buffer);
    }

    pub fn alloc(self: *Arena, len: usize) ![]u8 {
        if (self.offset + len > self.buffer.len) {
            return error.OutOfMemory;
        }
        const slice = self.buffer[self.offset .. self.offset + len];
        self.offset += len;
        return slice;
    }
} // 该 POC 未考虑内存对齐

显然的，大家在一个池子里混，内存局部性得到了保证。分配只需要调整一个指针，所以 Arena 的分配是 O(1) 的，且没有碎片化问题（因为不支持单个内存块的释放）。这使得它非常适合于需要频繁分配大量小内存块的场景，如 LSM-Tree 中的 MemTable。

专门为 Arena 优化的结构

因此，我们可以为 Arena 设计一个专门的 KV 存储结构，来进一步压榨 Arena 的潜力

const Entry = @This();
const Type = enum {
    put = 0,
    deletion = 1,
};

pub fn allocate(allocator: std.mem.Allocator, key: []const u8, value: []const u8, version: u56, entry_type: Type) !*Entry {
    // Allocate once for the entire struct, then slice it for the key and value.
    const key_length = std.math.divCeil(usize, std.math.log2_int_ceil(u32, @truncate(key.len)), 7) catch {
        @panic("Key length exceeds maximum encodable size of 2^35 bytes");
    };
    const value_length = std.math.divCeil(usize, std.math.log2_int_ceil(u32, @truncate(value.len + 8)), 7) catch {
        @panic("Value length exceeds maximum encodable size of 2^35 bytes");
    };

    const total_size = key_length + value_length + 8 + key.len + value.len;
    var buffer = try allocator.alignedAlloc(u8, .@"64", total_size);
    const entry: *Entry = @ptrCast(buffer.ptr);
    var data = buffer[@sizeOf(Entry)..];
    const value_offset = key_length + key.len + value_length;
    const tag_offset = value_offset + value.len;

    std.leb.writeUnsignedExtended(data[0..key_length], key.len);
    @memcpy(data[key_length .. key_length + key.len], key);
    std.leb.writeUnsignedExtended(data[key_length + key.len .. key_length + key.len + value_length], value.len + 8);
    @memcpy(data[value_offset .. value_offset + value.len], value);

    const tag_bytes: *[8]u8 = @ptrCast(data[tag_offset .. tag_offset + 8].ptr);
    std.mem.writeInt(u64, tag_bytes, (version << 8) | @intFromEnum(entry_type), .little);
    return entry;
}

我们期望一个存内高效的高效的结构，~~虽然这意味着乾碎整个结构体~~

核心问题在于，Entry 是一个变长的结构，如此这般，难以用结构体描述。不禁令人想到荒诞的 GNU 拓展 C 语法

struct {
    int pack_len;
    int pack[0];
}

既然变长，不如贯彻到底，作为高性能缓冲区，我们必然希望 KV pair 足够小，我们能够决定的，就只有元数据们

字段	变长？	类型
key_length	是	Variant32
key	是	[*]const u8
value_length	是	Variant32
value	是	[*]const u8
tag	否	u64

Variant32 是 ULEB128 的一个变种¹

不难看出，只要能压缩空间，Google 是什么都愿意做的，

如果你打算复刻一个 LevelDB 但不想承担其名号，建议起名 VariantDB 或 ArenaKV，这样在面试时可以理直气壮地说：‘我实现了一套基于变长整数编码的紧凑内存存储方案’，听起来比‘我抄了 LevelDB’高级多了

通过预先计算，我们成功的让 Entry 通过一次分配进行构造，确保了局部性，从而增强性能表现。

为什么不直接用 `usize` 存长度？

因为在 64 位系统上，一个 usize 会固定吃掉 8 个字节。而实际上大部分的 Key 和 Value 短得可怜（比如仅仅是一个 ID 或者简短的 JSON）。

Variant32（实际上就是 ULEB128 编码）的魔法在于：按需分配。它把每个字节的最高位（MSB）当作标志位，剩下的 7 位存数据。如果数据小于 128，只需要 1 个字节就能存下长度！举个例子，一个长度为 5 的 Key，用 usize 存要 8 字节，用 Variant32 只要 1 字节。省下的 7 字节，对于寸土寸金的 CPU L1 Cache 来说，简直是“巨大的恩赐”。

既然写入的时候是硬核地按字节拼凑起来的，那么读的时候自然也要像剥洋葱一样，一层一层解析。因为 Entry 本质上只是一个指向这段连续内存起始位置的 Opaque Pointer，我们可以给它加上解析方法

pub inline fn getKey(self: *const Entry) []const u8 {
    const data_ptr: [*]const u8 = @ptrFromInt(@intFromPtr(self) + @sizeOf(Entry));
    const data = data_ptr[0..std.math.maxInt(usize)];
    var reader = std.Io.Reader.fixed(data);
    const key_len = reader.takeLeb128(u32) catch {
        @panic("Cannot read keylen");
    };
    return data_ptr[reader.seek .. reader.seek + key_len];
}

pub inline fn getValue(self: *const Entry) []const u8 {
    const data_ptr: [*]const u8 = @ptrFromInt(@intFromPtr(self) + @sizeOf(Entry));
    const data = data_ptr[0..std.math.maxInt(usize)];
    var reader = std.Io.Reader.fixed(data);
    const key_len = reader.takeLeb128(u32) catch {
        @panic("Cannot read keylen");
    };
    reader.seek += key_len;
    const value_len = reader.takeLeb128(u32) catch {
        @panic("Cannot read valuelen");
    };
    if (value_len < 8) {
        @panic("Value length must be at least 8 bytes to accommodate the tag");
    }
    return data_ptr[reader.seek .. reader.seek + value_len - 8];
}

pub inline fn getTag(self: *const Entry) ?u64 {
    const data_ptr: [*]const u8 = @ptrFromInt(@intFromPtr(self) + @sizeOf(Entry));
    const data = data_ptr[0..std.math.maxInt(usize)];
    var reader = std.Io.Reader.fixed(data);
    const key_len = reader.takeLeb128(u32) catch {
        @panic("Cannot read keylen");
    };
    reader.seek += key_len;
    const value_len = reader.takeLeb128(u32) catch {
        @panic("Cannot read valuelen");
    };
    if (value_len < 8) {
        @panic("Value length must be at least 8 bytes to accommodate the tag");
    }
    const tag_offset = reader.seek + value_len - 8;
    const tag_bytes: *const [8]u8 = @ptrCast(data_ptr[tag_offset .. tag_offset + 8].ptr);
    const tag = std.mem.readInt(u64, tag_bytes, .little);
    if (tag == 0) {
        return null; // No tag
    }
    return tag;
}

pub fn getVersion(self: *const Entry) u56 {
    const tag = self.getTag() orelse 0;
    return @truncate(tag >> 8);
}

pub fn getType(self: *const Entry) Type {
    const tag = self.getTag() orelse 0;
    return @enumFromInt(tag & 0xFF);
}

非常 hacky 的，我们就可以读取到 Key、Value、Version 和 Type 了

Tag 为什么变成 Version 和 Type 的组合了呢？

这是 LevelDB 有且仅有的 MVCC 残余了，有机会会讲的（也就是不一定会讲了）

下回予告

巨大的 Arena 已经分配，但在无序的字节之海中，普通的遍历只是徒劳的挣扎！

想要突破 O(N) 的绝望，就必须向信息论エントロピー探寻减小不确定性的法则。

正面还是反面？每一次掷出命运的硬币コイン，都在斩断复杂度的枷锁！

在迎战残酷的并发修罗场之前，让我们先在宁静的单线程里，构筑这奇迹的概率之塔！

Next Episode

探索サーチの法則 —— 掷出命运的硬币，纯粹的跳跃スキップ启动！

变长整数编码的一种，使用一个字节的最高位作为继续标志，剩余7位存储数据。每个字节可以表示0-127的数值，如果数值超过127，则需要更多字节来表示。
1