{"id":10020665,"date":"2025-03-04T23:06:01","date_gmt":"2025-03-04T15:06:01","guid":{"rendered":"https:\/\/itmax.cn\/?p=10020665"},"modified":"2025-03-04T23:06:01","modified_gmt":"2025-03-04T15:06:01","slug":"lsm-tree%e4%bb%8e%e5%85%a5%e9%97%a8%e5%88%b0%e5%85%a5%e9%ad%94%ef%bc%9a%e4%bb%8e%e9%9b%b6%e5%bc%80%e5%a7%8b%e5%ae%9e%e7%8e%b0%e4%b8%80%e4%b8%aa%e9%ab%98%e6%80%a7%e8%83%bd%e9%94%ae%e5%80%bc%e5%ad%98","status":"publish","type":"post","link":"https:\/\/itmax.cn\/?p=10020665","title":{"rendered":"LSM-TREE\u4ece\u5165\u95e8\u5230\u5165\u9b54\uff1a\u4ece\u96f6\u5f00\u59cb\u5b9e\u73b0\u4e00\u4e2a\u9ad8\u6027\u80fd\u952e\u503c\u5b58\u50a8 \uff5c \u5f97\u7269\u6280\u672f"},"content":{"rendered":"<h2>\u4e00\u3001\u5f15 \u8a00<\/h2>\n<p>LSM-Tree\uff08Log-Structured Merge Tree\uff09\u662f\u4e00\u79cd\u9ad8\u6548\u7684\u952e\u503c\u5b58\u50a8\u6570\u636e\u7ed3\u6784\uff0c\u5e7f\u6cdb\u5e94\u7528\u4e8eNoSQL\u6570\u636e\u5e93\u548c\u5927\u6570\u636e\u5904\u7406\u7cfb\u7edf\u4e2d\u3002\u5176\u6838\u5fc3\u601d\u60f3\u662f\u901a\u8fc7\u5206\u5c42\u3001\u6709\u5e8f\u5730\u5229\u7528\u78c1\u76d8\u987a\u5e8f\u5199\u5165\u7684\u6027\u80fd\u4f18\u52bf\uff0c\u4f18\u5316\u5199\u5165\u64cd\u4f5c\uff0c\u540c\u65f6\u727a\u7272\u90e8\u5206\u8bfb\u53d6\u6027\u80fd\u4ee5\u6362\u53d6\u66f4\u9ad8\u7684\u5199\u5165\u541e\u5410\u91cf\u3002<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184277\" alt=\"\u5f15\u8a00.jpeg\" title=\"\u5f15\u8a00.jpeg\"><br \/><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184278\" alt=\"\u5f15\u8a002.jpeg\" title=\"\u5f15\u8a002.jpeg\" loading=\"lazy\"><br \/>\u5728\u4e92\u8054\u7f51\u7684\u5404\u4e2a\u57fa\u7840\u8bbe\u65bd\u4e2d\uff0c\u4e0d\u8bba\u662f\u6570\u636e\u5e93\u8fd8\u662f\u7f13\u5b58\u4ea6\u6216\u662f\u5927\u6570\u636e\u6846\u67b6\uff0cLSM-Tree\u8fd9\u4e2a\u6570\u636e\u7ed3\u6784\u90fd\u662f\u5f88\u5e38\u89c1\u7684\u8eab\u5f71\u3002<\/p>\n<p>\u6211\u6bcf\u5929\u90fd\u5728\u4f7f\u7528\u8fd9\u4e2a\u5b58\u50a8\u5f15\u64ce\uff0c\u4f46\u662f\u5bf9\u5b83\u7684\u4e86\u89e3\u8fd8\u6d41\u4e8e\u8868\u9762\uff0c\u6240\u4ee5\u6211\u60f3\u8981\u81ea\u5df1\u5b9e\u73b0\u4e00\u6b21LSM-Tree\u52a0\u6df1\u7406\u89e3\u3002<\/p>\n<p>\u672c\u6b21\u5b9e\u73b0\u6211\u4eec\u91c7\u7528\u4e86Zig\u8bed\u8a00\uff0c\u7b80\u8981\u7684\u5b9e\u73b0LSM-Tree\u7684\u6838\u5fc3\u529f\u80fd\uff08\u8bfb\u5199\u3001\u6570\u636e\u538b\u7f29\u3001\u6301\u4e45\u5316\uff0c\u4e0d\u5305\u542bMVCC\u7684\u5185\u5bb9\uff09\u3002<\/p>\n<p><em>Zig\u662f\u4e00\u79cd\u65b0\u5174\u7684\u7cfb\u7edf\u7f16\u7a0b\u8bed\u8a00\uff0c\u5176\u8bbe\u8ba1\u76ee\u6807\u662f\u63d0\u4f9b\u73b0\u4ee3\u7279\u6027\u7684\u540c\u65f6\u4fdd\u6301\u4f4e\u590d\u6742\u6027\u3002<\/em><\/p>\n<p><em>\u672c\u9879\u76ee\u6781\u5927\u7684\u53d7\u5230\u4e86Mini-Lsm\u8fd9\u4e2a\u9879\u76ee\u7684\u542f\u53d1\uff0c\u5f3a\u70c8\u63a8\u8350\u5927\u5bb6\u5b66\u4e60\u8fd9\u4e2a\u9879\u76ee\uff01<\/em><\/p>\n<h2>\u4e8c\u3001LSM-Treee \u6838\u5fc3\u529f\u80fd\u6982\u8ff0<\/h2>\n<p>\u5728\u5f00\u59cb\u81ea\u5df1\u7f16\u5199\u4e4b\u524d\uff0c\u6211\u5148\u7b80\u5355\u4ecb\u7ecd\u4e00\u4e0bLSM-Tree\uff08<strong>Log-Structured Merge Tree<\/strong>\uff09\u7684\u67b6\u6784\u4ee5\u53ca\u8bfb\u5199\u6d41\u7a0b\u3002<\/p>\n<p>LSM-Tree\u5b83\u7ed3\u5408\u4e86\u65e5\u5fd7\u548c\u7d22\u5f15\u7684\u7279\u70b9\uff0c\u4f18\u5316\u4e86\u5199\u5165\u548c\u8bfb\u53d6\u6027\u80fd\u3002\u6bcf\u6b21\u5199\u5165\u90fd\u662f\u91c7\u7528append-only\u7684\u65b9\u5f0f\uff0c\u6240\u4ee5\u5199\u5165\u6027\u80fd\u5f88\u9ad8\u3002<\/p>\n<p>\u800c\u4f5c\u4e3a\u4ee3\u4ef7\uff0c\u8ffd\u52a0\u5199\u5165\u4f1a\u9020\u6210\u5b58\u50a8\u653e\u5927\uff0cLSM-Tree\u65f6\u91c7\u7528\u4e86\u591a\u5c42SSTable\u7684\u65b9\u5f0f\u5c06\u6570\u636e\u5806\u53e0\u5728\u786c\u76d8\u4e0a\u3002\u6240\u4ee5\u9700\u8981\u4e00\u4e2a\u5408\u5e76\u538b\u7f29\u7684\u8fc7\u7a0b\u6765\u56de\u6536\u8fc7\u591a\u7684\u7a7a\u95f4\u3002<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184279\" alt=\"\u5408\u5e76\u538b\u7f29\u7684\u8fc7\u7a0b.jpeg\" title=\"\u5408\u5e76\u538b\u7f29\u7684\u8fc7\u7a0b.jpeg\" loading=\"lazy\"><\/p>\n<p><strong>\u5199\u6d41\u7a0b<\/strong><\/p>\n<ul>\n<li><strong>\u9884\u5199\u65e5\u5fd7<\/strong>\uff08<strong>WAL<\/strong>\uff09 \uff1a\u5199\u64cd\u4f5c\u9996\u5148\u5199\u5165\u9884\u5199\u65e5\u5fd7\uff08WAL\uff09\uff0c\u7528\u4e8e\u8bb0\u5f55\u672a\u63d0\u4ea4\u7684\u6570\u636e\uff0c\u786e\u4fdd\u6570\u636e\u7684\u6301\u4e45\u6027\u548c\u4e00\u81f4\u6027\u3002<\/li>\n<li><strong>MemTable<\/strong>\uff1a\u968f\u540e\u5c06\u6570\u636e\u5199\u5165\u5185\u5b58\u4e2d\u7684MemTable\uff0cMemTable\u662f\u4e00\u4e2a\u5e73\u8861\u6811\uff08\u5982skiplist\uff09\uff0c\u652f\u6301\u5feb\u901f\u63d2\u5165\u548c\u5220\u9664\u64cd\u4f5c\u3002<\/li>\n<li><strong>\u89e6\u53d1Compaction<\/strong>\uff1a\u5f53MemTable\u8fbe\u5230\u4e00\u5b9a\u9608\u503c\u65f6\uff0c\u4f1a\u89e6\u53d1\u540e\u53f0\u7ebf\u7a0b\u5c06MemTable\u4e2d\u7684\u6570\u636e\u5237\u5165\u78c1\u76d8\uff0c\u751f\u6210SSTable\u6587\u4ef6\u3002<\/li>\n<li><strong>SSTable<\/strong>\uff1a\u751f\u6210\u7684SSTable\u6587\u4ef6\u662f\u4e0d\u53ef\u53d8\u7684\uff0c\u5b58\u50a8\u5728\u78c1\u76d8\u4e0a\uff0c\u7528\u4e8e\u540e\u7eed\u8bfb\u53d6\u64cd\u4f5c\u3002<\/li>\n<li><strong>\u5408\u5e76\u64cd\u4f5c<\/strong>\uff08<strong>Merge<\/strong>\uff09 \uff1a\u5f53\u591a\u4e2aSSTable\u6587\u4ef6\u8fbe\u5230\u4e00\u5b9a\u6570\u91cf\u65f6\uff0c\u4f1a\u89e6\u53d1\u5408\u5e76\u64cd\u4f5c\uff0c\u5c06\u5b83\u4eec\u5408\u5e76\u4e3a\u4e00\u4e2a\u66f4\u5927\u7684SSTable\u6587\u4ef6\uff0c\u4ee5\u51cf\u5c11\u6587\u4ef6\u6570\u91cf\u3002<\/li>\n<\/ul>\n<p><strong>\u8bfb\u6d41\u7a0b<\/strong><\/p>\n<ul>\n<li><strong>MemTable\u4f18\u5148<\/strong>\uff1a\u8bfb\u53d6\u64cd\u4f5c\u9996\u5148\u4eceMemTable\u4e2d\u67e5\u627e\u6570\u636e\uff0c\u56e0\u4e3aMemTable\u662f\u6309\u5347\u5e8f\u6392\u5217\u7684\uff0c\u67e5\u627e\u6548\u7387\u8f83\u9ad8\u3002<\/li>\n<li><strong>Block Cache<\/strong>\uff1a\u5982\u679cMemTable\u4e2d\u672a\u627e\u5230\u6570\u636e\uff0c\u5219\u4eceBlock Cache\u4e2d\u67e5\u627e\u3002Block Cache\u5b58\u50a8\u4e86\u9884\u5148\u52a0\u8f7d\u5230\u5185\u5b58\u4e2d\u7684SSTable\u5757\uff0c\u4ee5\u63d0\u9ad8\u8bfb\u53d6\u6027\u80fd\u3002<\/li>\n<li><strong>SSTable\u67e5\u627e<\/strong>\uff1a\u5982\u679cBlock Cache\u4e2d\u4e5f\u672a\u627e\u5230\u6570\u636e\uff0c\u5219\u4ece\u78c1\u76d8\u4e0a\u7684SSTable\u6587\u4ef6\u4e2d\u67e5\u627e\u3002Lsm-tree\u4f1a\u4ece\u6700\u4f4e\u5c42\uff08L0\uff09\u5f00\u59cb\u67e5\u627e\uff0c\u9010\u5c42\u5411\u4e0a\u67e5\u627e\uff0c\u76f4\u5230\u627e\u5230\u76ee\u6807\u6570\u636e\u3002<\/li>\n<li><strong>\u591a\u7248\u672c\u5e76\u53d1\u63a7\u5236<\/strong>\uff08<strong>MVCC<\/strong>\uff09 \uff1aLsm-tree\u652f\u6301\u591a\u7248\u672c\u5e76\u53d1\u63a7\u5236\uff0c\u5141\u8bb8\u540c\u65f6\u8bbf\u95ee\u4e0d\u540c\u7248\u672c\u7684\u6570\u636e\uff0c\u4ece\u800c\u63d0\u9ad8\u5e76\u53d1\u6027\u80fd\u3002<\/li>\n<\/ul>\n<h2>\u4e09\u3001\u6838\u5fc3\u529f\u80fd\u5b9e\u73b0<\/h2>\n<h3>MemTable \u5b9e\u73b0<\/h3>\n<p>\u9996\u5148\uff0c\u6211\u4eec\u5148\u5b9e\u73b0 LSM \u5b58\u50a8\u5f15\u64ce\u7684\u5185\u5b58\u7ed3\u6784\u2014Memtable\u3002\u6211\u4eec\u9009\u62e9<strong>\u8df3\u8868<\/strong>\u5b9e\u73b0\u4f5c\u4e3a Memtable \u7684\u6570\u636e\u7ed3\u6784\uff0c\u56e0\u4e3a\u5b83\u652f\u6301\u65e0\u9501\u7684\u5e76\u53d1\u8bfb\u5199\u3002\u6211\u4eec\u4e0d\u4f1a\u6df1\u5165\u4ecb\u7ecd\u8df3\u8868\u7684\u5de5\u4f5c\u539f\u7406(Redis\u7684\u540c\u5b66\u5e94\u8be5\u4e0d\u964c\u751f\u8fd9\u4e2a\u4e1c\u897f)\uff0c\u7b80\u5355\u6765\u8bf4\uff0c\u5b83\u662f\u4e00\u4e2a\u6613\u4e8e\u5b9e\u73b0\u7684\u6709\u5e8f\u952e\u503c\u6620\u5c04\u3002<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184280\" alt=\"\u6709\u5e8f\u5065\u503c.jpeg\" title=\"\u6709\u5e8f\u5065\u503c.jpeg\" loading=\"lazy\"><br \/>Skiplist\u7684\u5b9e\u73b0\u975e\u5e38\u7b80\u5355\uff0c\u8fd9\u91cc\u6211\u5229\u7528Zig\u7f16\u8bd1\u65f6\u7684\u80fd\u529b\u5b9e\u73b0\u4e86\u4e00\u4e2a\u6cdb\u578b\u7248\u672c\u7684\u8df3\u8868src\/skiplist.zig\uff0c\u6709\u5174\u8da3\u7684\u5c0f\u4f19\u4f34\u53ef\u4ee5\u76f4\u63a5\u53bb\u4ed3\u5e93\u4e2d\u53c2\u89c2\u4ee3\u7801\u3002<\/p>\n<p>\u57fa\u4e8eSkipList\u7684\u80fd\u529b\uff0c\u6211\u4eec\u5373\u53ef\u5305\u88c5\u51faMemtable\u7684\u57fa\u672c\u529f\u80fd\u3002<\/p>\n<p>\u6211\u4eec\u8fd9\u4e2aLSM\u652f\u6301WAL\u529f\u80fd\u7684\uff0c\u5373\u5199\u5165\u5185\u5b58\u8868\u4e4b\u524d\u8981\u5148\u5199\u5165\u78c1\u76d8\u65e5\u5fd7\uff0c\u65b9\u4fbf\u5728\u610f\u5916\u5b95\u673a\u91cd\u542f\u540e\u53ef\u4ee5\u6062\u590d\u6570\u636e\u3002<\/p>\n<p>WAL\u7684\u80fd\u529b\u6211\u5c31\u4e0d\u60f3\u81ea\u5df1\u518d\u5b9e\u73b0\u4e86\uff0c\u4e8e\u662f\u4ece\u7f51\u4e0a\u6252\u4e86\u4e00\u4e2aC\u7684\u5b9e\u73b0\uff08Zig\u96c6\u6210C\u8bed\u8a00\u975e\u5e38\u4fbf\u6377\uff0c\u53ef\u4ee5\u53c2\u8003\u4e0e C \u4ea4\u4e92\uff09\u3002<\/p>\n<pre><code class=\"java\">map: Map,\nlock: RwLock,\nwal: ?Wal,\nid: usize,\nallocator: std.mem.Allocator,\narena: std.heap.ArenaAllocator,\napproximate_size: atomic.Value(usize) = atomic.Value(usize).init(0),\n\nfn putToList(self: *Self, key: []const u8, value: []const u8) !void {\n    {\n        self.lock.lock();\n        defer self.lock.unlock();\n        try self.map.insert(kk, vv);\n    }\n\n    _ = self.approximate_size.fetchAdd(@intCast(key.len + value.len), .monotonic);\n}\n\nfn putToWal(self: *Self, key: []const u8, value: []const u8) !void {\n    \/\/ [key-size: 4bytes][key][value-size: 4bytes][value]\n\n    if (self.wal) |w| {\n        var buf = std.ArrayList(u8).init(self.arena.allocator());\n\n        var bw = buf.writer();\n        try bw.writeInt(u32, @intCast(key.len), .big);\n        _ = try bw.write(key);\n        try bw.writeInt(u32, @intCast(value.len), .big);\n        _ = try bw.write(value);\n        try w.append(buf.items);\n    }\n}\n\n\/\/ \u5199\u5165Memtable\uff0c\u5148\u5199WAL\uff0c\u518d\u5199skiplist table\npub fn put(self: *Self, key: []const u8, value: []const u8) !void {\n    try self.putToWal(key, value);\n    try self.putToList(key, value);\n}\n\npub fn get(self: *Self, key: []const u8, val: *[]const u8) !bool {\n    self.lock.lockShared();\n    defer self.lock.unlockShared();\n    var vv: []const u8 = undefined;\n    if (try self.map.get(key, &amp;vv)) {\n        val.* = vv;\n        return true;\n    }\n    return false;\n}\n<\/code><\/pre>\n<p>\u6ce8\u610f\u5230\u8fd9\u91cc\u6211\u4eec\u6ca1\u6709\u5b9e\u73b0\u5220\u9664\u7684\u529f\u80fd\uff0c\u8fd9\u91cc\u6211\u4eff\u7167\u4e86RocksDB\u4e2d\u7684\u5893\u7891\u673a\u5236\uff0c\u7528\u7a7a\u503c\u4ee3\u8868\u5220\u9664\uff0c\u6240\u4ee5\u5220\u9664\u88abput(key, &#8220;&#8221;)\u53d6\u4ee3\u3002<\/p>\n<h3>SSTable<\/h3>\n<p>\u63a5\u4e0b\u6765\uff0c\u6211\u4eec\u5c31\u7740\u624b\u5f00\u59cb\u5b9e\u73b0LSM\u4e2d\u53e6\u5916\u4e00\u4e2a\u91cd\u8981\u5143\u7d20 &#8212; SSTable\u3002<\/p>\n<p>*SSTable\uff08Sorted String Table\uff09\u662f\u4e00\u79cd\u4e0d\u53ef\u53d8\u7684\uff08Immutable\uff09\u78c1\u76d8\u6587\u4ef6\uff0c\u5185\u90e8\u6309Key\u6709\u5e8f\u6392\u5217\uff0c\u5b58\u50a8\u952e\u503c\u5bf9\u6570\u636e\u3002\u6bcf\u4e2aSSTable\u6587\u4ef6\u751f\u6210\u540e\u4e0d\u518d\u4fee\u6539\uff0c\u66f4\u65b0\u548c\u5220\u9664\u64cd\u4f5c\u901a\u8fc7\u8ffd\u52a0\u65b0\u8bb0\u5f55\u6216\u6807\u8bb0\u5220\u9664\uff0c\u6700\u7ec8\u901a\u8fc7\u5408\u5e76\uff08Compaction\uff09\u6e05\u7406\u5197\u4f59\u6570\u636e\u3002<br \/>\u6bcf\u5f53LSM-Tree\u4e2d\u7684MemTable\u4f53\u79ef\u8d85\u51fa\u9608\u503c\uff0c\u5c31\u4f1a\u5c06\u5185\u5b58\u4e2d\u7684\u6570\u636e\u5199\u5165SsTable\u3002*<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184281\" alt=\"\u5185\u5b58\u4e2d\u7684\u6570\u636e.jpeg\" title=\"\u5185\u5b58\u4e2d\u7684\u6570\u636e.jpeg\" loading=\"lazy\"><br \/>\u6bcf\u4e2aSSTable\u7531\u591a\u4e2aBlock\u7ec4\u6210\uff0c\u6bcf\u4e2aBlock\u662f\u4e00\u7ec4KV\u7684package\u3002<\/p>\n<p>Block\u7684<strong>\u7f16\u7801\u683c\u5f0f<\/strong>\u5982\u4e0b\uff1a<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184282\" alt=\"block\u7684\u5065\u7801\u683c\u5f0f.jpeg\" title=\"block\u7684\u5065\u7801\u683c\u5f0f.jpeg\" loading=\"lazy\"><br \/>\u4e3a\u4e86\u6784\u5efa\u4e00\u4e2aBlock\uff0c\u6211\u4eec\u5b9e\u73b0\u4e86\u4e00\u4e2a<strong>BlockBuilder<\/strong>\u7684\u6a21\u5757\uff0c\u8fd9\u90e8\u5206\u4ee3\u7801\u89c1src\/block.zig\uff1a<\/p>\n<pre><code class=\"java\">pub const Block = struct {\n    data_v: std.ArrayList(u8),\n    offset_v: std.ArrayList(u16),\n}\n\npub const BlockBuilder = struct {\n    allocator: std.mem.Allocator,\n    offset_v: std.ArrayList(u16),\n    data_v: std.ArrayList(u8),\n    block_size: usize,\n    first_key: []u8,\n    \n    pub fn add(self: *Self, key: []const u8, value: ?[]const u8) !bool {\n        std.debug.assert(key.len &gt; 0); \/\/ key must not be empty\n\n        const vSize = if (value) |v| v.len else 0;\n        \n        if ((self.estimated_size() + key.len + vSize + 3 * @sizeOf(u16) &gt; self.block_size) and !self.is_empty()) {\n            return false;\n        }\n        try self.doAdd(key, value);\n\n        if (self.first_key.len == 0) {\n            self.first_key = try self.allocator.dupe(u8, key);\n        }\n        return true;\n    }\n\n    fn doAdd(self: *Self, key: []const u8, value: ?[]const u8) !void {\n        \/\/ add the offset of the data into the offset array\n        try self.offset_v.append(@intCast(self.data_v.items.len));\n        const overlap = calculate_overlap(self.first_key, key);\n\n        var dw = self.data_v.writer();\n        \/\/ encode key overlap\n        try dw.writeInt(u16, @intCast(overlap), .big);\n        \/\/ encode key length\n        try dw.writeInt(u16, @intCast(key.len - overlap), .big);\n\n        \/\/ encode key content\n        _ = try dw.write(key[overlap..]);\n        \/\/ encode value length\n        if (value) |v| {\n            try dw.writeInt(u16, @intCast(v.len), .big);\n            \/\/ encode value content\n            _ = try dw.write(v);\n        } else {\n            try dw.writeInt(u16, 0, .big);\n        }\n    }\n\n    pub fn build(self: *Self) !Block {\n        if (self.isEmpty()) {\n            @panic(&quot;block is empty&quot;);\n        }\n        return Block.init(\n            try self.data_v.clone(),\n            try self.offset_v.clone(),\n        );\n    }\n}<\/code><\/pre>\n<p>\u53ef\u80fd\u6709\u540c\u5b66\u6ce8\u610f\u5230\uff0c\u6211\u4eec\u5199key\u7684\u65f6\u5019\u6ca1\u6709\u76f4\u63a5\u5c06key\u503c\u5199\u5165\uff0c\u800c\u4e14\u53ea\u5199\u4e86key\u4e0e\u5f53\u524dblock\u7684\u7b2c\u4e00\u4e2akey\u4e0d\u91cd\u53e0\u7684suffix\u90e8\u5206\u3002\u7531\u4e8eblock\u4e2d\u7684key\u90fd\u662f\u6709\u5e8f\u7684\uff0c\u6240\u4ee5\u4e00\u4e2ablock\u4e2d\u7684key\u6709\u5f88\u5927\u6982\u7387\u662f\u524d\u7f00\u7c7b\u4f3c\u7684\uff0c\u6240\u4ee5\u8fd9\u91cc\u662f\u4e00\u4e2a\u7a7a\u95f4\u4f18\u5316\u7684\u5c0f\u6280\u5de7\uff0c\u4f8b\u5982\uff1a<\/p>\n<p><strong>Key: foo, foo1, foo2, foo3 &#8230;.<\/strong><\/p>\n<p>\u6211\u4eec\u5199\u5165block\u65f6\uff0c\u53ea\u9700\u8981\u5199\uff1a<\/p>\n<p><strong>foo|1|2|3|&#8230;.<\/strong><br \/>\u5f88\u591a\u6709\u5e8f\u8868\u7684\u5b9e\u73b0\u4e2d\u90fd\u4f1a\u7528\u5230\u8fd9\u4e2a\u5c0f\u6280\u5de7\u3002<\/p>\n<p>\u6709\u4e86block\u7684\u5b9e\u73b0\uff0c\u6211\u4eec\u53ef\u4ee5\u8fdb\u4e00\u6b65\u6765\u5b9a\u4e49SSTable\u7684\u683c\u5f0f\u3002\u4e00\u4e2aSSTable\u7531\u591a\u4e2aBlock\u3001block\u5143\u6570\u636e\u4ee5\u53ca\u5e03\u9686\u8fc7\u6ee4\u5668\u6784\u6210\u3002<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184283\" alt=\"\u5e03\u9686\u8fc7\u6ee4\u5668.jpeg\" title=\"\u5e03\u9686\u8fc7\u6ee4\u5668.jpeg\" loading=\"lazy\"><br \/><em>\u5e03\u9686\u8fc7\u6ee4\u5668\u662f\u4e00\u79cd\u6982\u7387\u6027\u6570\u636e\u7ed3\u6784\uff0c\u7528\u4e8e\u7ef4\u62a4\u4e00\u7ec4\u952e\u3002\u60a8\u53ef\u4ee5\u5411\u5e03\u9686\u8fc7\u6ee4\u5668\u4e2d\u6dfb\u52a0\u952e\uff0c\u5e76\u4e14\u53ef\u4ee5\u77e5\u9053\u5728\u6dfb\u52a0\u5230\u5e03\u9686\u8fc7\u6ee4\u5668\u4e2d\u7684\u952e\u96c6\u4e2d\u53ef\u80fd\u5b58\u5728\u6216\u5fc5\u987b\u4e0d\u5b58\u5728\u7684\u952e\u3002<\/em><\/p>\n<p><em>\u5728SSTable\u4e2d\u6dfb\u52a0\u5e03\u9686\u8fc7\u6ee4\u5668\u53ef\u4ee5\u6709\u6548\u63d0\u5347\u67e5\u8be2key\u7684\u6548\u7387\u3002<\/em><\/p>\n<p>\u5143\u6570\u636e\u5305\u542b\u4e86block\u7684<strong>\u7b2c\u4e00\u4e2a\u4e0e\u6700\u540e\u4e00\u4e2akey\u4ee5\u53cablock\u5728sst\u4e2d\u7684offset\u4fe1\u606f<\/strong>\uff0c\u8bb0\u5f55\u5143\u6570\u636e\u4e3b\u8981\u4e3a\u4e86\u5728\u540e\u7eed\u7684\u68c0\u7d22\u4e2d\u53ef\u4ee5\u5feb\u901f\u5b9a\u4f4d\u67d0\u4e2akey\u843d\u5728\u54ea\u4e2ablock\u4e2d\u3002<\/p>\n<p>\u540c\u6837\u7684\u5957\u8def\uff0c\u4e3a\u4e86\u6784\u5efaSSTable\uff0c\u6211\u4eec\u5148\u5b9e\u73b0\u4e00\u4e2a<strong>SSTableBuilder<\/strong>\uff0c\u90e8\u5206\u4ee3\u7801\u89c1src\/ss_table.zig<\/p>\n<pre><code class=\"java\">pub const SsTableBuilder = struct {\n    allocator: std.mem.Allocator,\n    builder: BlockBuilder, \/\/ \u521a\u624d\u5b9e\u73b0\u7684block\u6784\u5efa\u88c5\u7f6e\n    first_key: ?[]const u8,\n    last_key: ?[]const u8,\n    meta: std.ArrayList(BlockMeta),\n    block_size: usize,\n    data: std.ArrayList(u8),\n    bloom: BloomFilterPtr, \/\/ \u5e03\u9686\u8fc7\u6ee4\u5668\n    \n    pub fn add(self: *Self, key: []const u8, value: []const u8) !void {\n        try self.setFirstKey(key);\n        try self.bloom.get().insert(key); \/\/ \u5199\u5165\u5e03\u9686\u8fc7\u6ee4\u5668\n\n        if (try self.builder.add(key, value)) {\n            try self.setLastKey(key);\n            return;\n        }\n        \/\/ block is full\n        try self.finishBlock();\n        std.debug.assert(try self.builder.add(key, value));\n        try self.resetFirstKey(key);\n        try self.setLastKey(key);\n    }\n    \n    \/\/ \u5199\u5165\u4e00\u4e2ablock\u7684\u6570\u636e\n    fn finishBlock(self: *Self) !void {\n        if (self.builder.isEmpty()) {\n            return;\n        }\n        var bo = self.builder;\n        \/\/ reset block\n        defer bo.reset();\n\n        self.builder = BlockBuilder.init(self.allocator, self.block_size);\n        var blk = try bo.build();\n        defer blk.deinit();\n        const encoded_block = try blk.encode(self.allocator); \/\/ block\u5e8f\u5217\u5316\n        defer self.allocator.free(encoded_block);\n        \n        \/\/ \u8bb0\u5f55block\u7684\u5143\u6570\u636e\n        try self.meta.append(.{\n            .allocator = self.allocator,\n            .offset = self.data.items.len,\n            .first_key = try self.allocator.dupe(u8, self.first_key.?),\n            .last_key = try self.allocator.dupe(u8, self.last_key.?),\n        });\n        const cksm = hash.Crc32.hash(encoded_block); \/\/ \u5199\u51654b\u7684\u6821\u9a8c\u503c\n        try self.data.appendSlice(encoded_block);\n        try self.data.writer().writeInt(u32, cksm, .big);\n    }\n    \n    \/\/ \u6784\u5efa\u4e3a\u4e00\u4e2aSSTable\n    pub fn build(\n        self: *Self,\n        id: usize,\n        block_cache: ?BlockCachePtr, \/\/ \u8bfb\u53d6block\u6570\u636e\u7684\u7f13\u5b58\uff0c\u51cf\u5c11block\u7684\u53cd\u5e8f\u5217\u5316\u6210\u672c\n        path: []const u8,\n    ) !SsTable {\n        var arena = std.heap.ArenaAllocator.init(self.allocator);\n        defer arena.deinit();\n        const allocator = arena.allocator();\n\n        try self.finishBlock();\n        const w = self.data.writer();\n        \n        \/\/ \u5199\u5165\u5143\u6570\u636e\u53ca\u5176offset\n        const meta_offset = self.data.items.len;\n        const meta_b = try BlockMeta.batchEncode(self.meta.items, allocator);\n        _ = try w.write(meta_b);\n        try w.writeInt(u32, @intCast(meta_offset), .big);\n\n        \/\/ \u5199\u5165\u5e03\u9686\u8fc7\u6ee4\u5668\u53ca\u5176offset\n        const bloom_offset = self.data.items.len;\n        const encoded_bloom = try self.bloom.get().encode(allocator);\n        _ = try w.write(encoded_bloom);\n        try w.writeInt(u32, @intCast(bloom_offset), .big);\n        \n        \n        const file = try FileObject.init(path, self.data.items);\n        errdefer file.deinit();\n\n        const fk = self.meta.items[0].first_key;\n        const lk = self.meta.getLast().last_key;\n\n        return .{\n            .allocator = self.allocator,\n            .file = file,\n            .block_metas = try self.meta.toOwnedSlice(),\n            .meta_offset = meta_offset,\n            .block_cache = block_cache,\n            .bloom = self.bloom.clone(),\n            .id = id,\n            .first_key = try self.allocator.dupe(u8, fk),\n            .last_key = try self.allocator.dupe(u8, lk),\n            .max_ts = 0,\n        };\n    }\n}\n<\/code><\/pre>\n<h3>Write<\/h3>\n<p>\u6709\u4e86SSTable\u548cMemTable\uff0c\u6211\u4eec\u5c31\u6709\u4e86LSM-Tree\u9700\u8981\u7684\u4e24\u4e2a\u6700\u91cd\u8981\u7684\u6750\u6599\uff0c\u540e\u7eed\u7684\u8bfb\u5199\u4e0d\u8fc7\u662f\u5bf9\u8fd9\u4e24\u7c7b\u6750\u6599\u7684\u7ec4\u5408\u62fc\u88c5\u3002<\/p>\n<p>\u5728\u5b9e\u73b0\u5199\u64cd\u4f5c\u4e4b\u524d\uff0c\u6211\u4eec\u5148\u5047\u60f3\u4e00\u4e0bLSM-Tree\u7684\u6570\u636e\u7ed3\u6784:<br \/><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184284\" alt=\"lsmtree\u7684\u6570\u636e\u7ed3\u6784.jpeg\" title=\"lsmtree\u7684\u6570\u636e\u7ed3\u6784.jpeg\" loading=\"lazy\"><\/p>\n<ul>\n<li>\u9996\u5148\u6211\u4eec\u9700\u8981\u4e00\u4e2a\u6570\u636e\u7ed3\u6784\u5b58\u50a8\u5f53\u524dMemTable\u3001\u51b7MemTables\u548c\u591a\u5c42\u7684SST\uff0c\u5982\u4e0b\u56fe\u6240\u793a\u3002<br \/>\u56fe\u7247<\/li>\n<li>\u5176\u6b21\u6211\u4eec\u9700\u8981\u4e00\u4e2a\u9501\u7528\u4e8e\u540c\u6b65\u4e0a\u8ff0\u6570\u636e\u7ed3\u6784\u7684\u8bfb\u5199\u884c\u4e3a\u3002<\/li>\n<li>\u6211\u4eec\u8fd8\u9700\u8981\u4e00\u4e2aSSTable\u7684\u81ea\u589eid\u3002<\/li>\n<li>\u6700\u540e\u8fd8\u9700\u8981\u4e00\u4e9b\u5fc5\u8981\u7684\u914d\u7f6e\uff0c\u4f8b\u5982\u5b58\u50a8\u8def\u5f84\u3001\u7ebf\u7a0b\u7ba1\u7406\u5668\u7b49\u3002<\/li>\n<\/ul>\n<p>\u6700\u7ec8\uff0c\u6211\u4eec\u5b9e\u73b0\u7684LSM\u6570\u636e\u7ed3\u6784\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"java\">pub const StorageState = struct {\n    allocator: std.mem.Allocator,\n    mem_table: MemTablePtr, \/\/ \u5f53\u524d\u6b63\u5728\u5199\u7684MemTable\n    imm_mem_tables: std.ArrayList(MemTablePtr), \/\/ \u51b7MemTable\u6570\u7ec4\n    l0_sstables: std.ArrayList(usize), \/\/ \u7b2c\u4e00\u5c42\u7684SSTable\u6570\u7ec4\n    levels: std.ArrayList(std.ArrayList(usize)), \/\/ \u540e\u7eed\u591a\u5c42\u7684SSTable\u6570\u7ec4\n    sstables: std.AutoHashMap(usize, SsTablePtr), \/\/ sst_id =&gt; SSTable\n}\n\npub const StorageInner = struct {\n    const Self = @This();\n\n    allocator: std.mem.Allocator,\n    state: StorageState,\n    state_lock: std.Thread.RwLock = .{},\n    next_sst_id: atomic.Value(usize),\n    path: []const u8,\n    options: StorageOptions,\n    compaction_controller: CompactionController,\n    block_cache: BlockCachePtr,\n    terminate: std.Thread.ResetEvent = .{},\n    wg: std.Thread.WaitGroup = .{},\n}<\/code><\/pre>\n<p>\u5148\u4e0d\u8003\u8651\u9010\u5c42\u538b\u7f29\u7684\u903b\u8f91\uff0c\u53ea\u8003\u8651\u4e00\u5c42SSTable\u7684\u7b80\u5355\u60c5\u51b5\uff0c\u5199\u903b\u8f91\u53ef\u4ee5\u7b80\u5316\u4e3a\u5982\u4e0b\u6d41\u7a0b\uff1a<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184285\" alt=\"\u7b80\u5316\u4e3a\u5982\u4e0b\u6d41\u7a0b.jpeg\" title=\"\u7b80\u5316\u4e3a\u5982\u4e0b\u6d41\u7a0b.jpeg\" loading=\"lazy\"><\/p>\n<ul>\n<li>\n<p>\u5199\u5165State\u4e2d\u7684MemTable<\/p>\n<pre><code class=\"java\">pub fn writeBatch(self: *Self, records: []const WriteBatchRecord) !void {\n for (records) |record| {\n     switch (record) {\n         .put =&gt; |pp| {\n             try self.state.getMemTable().put(pp.key, pp.value);\n         },\n         .delete =&gt; |dd| {\n             \/\/ we use &quot;&quot; as the tombstone value\n             try self.state.getMemTable().put(dd, &quot;&quot;);\n         },\n     }\n     \/\/ \u5c1d\u8bd5\u628a\u5f53\u524dMemTable\u538b\u5165\u51b7\u6570\u636e\n     try self.tryFreeze(self.state.getMemTable().getApproximateSize());\n }\n}<\/code><\/pre>\n<\/li>\n<li>\u5f53MemTable\u4f53\u79ef\u8d85\u51fa\u9608\u503c\uff0c\u538b\u5165\u51b7MemTable\u6570\u7ec4\uff0c\u91cd\u7f6e\u5f53\u524dMemTable<\/li>\n<\/ul>\n<pre><code class=\"java\">fn forceFreezeMemtable(self: *Self) !void {\n    const next_sst_id = self.getNextSstId();\n    \n    \/\/ \u751f\u6210\u4e00\u4e2a\u65b0\u7684MemTable\n    var new_mm: MemTable = undefined;\n    {\n        if (self.options.enable_wal) {\n            const mm_path = try pathOfWal(self.allocator, self.path, next_sst_id);\n            defer self.allocator.free(mm_path);\n            new_mm = MemTable.init(next_sst_id, self.allocator, mm_path);\n        } else {\n            new_mm = MemTable.init(next_sst_id, self.allocator, null);\n        }\n    }\n    errdefer new_mm.deinit();\n\n    var old_mm: *MemTable = undefined;\n    {\n        self.state_lock.lock();\n        defer self.state_lock.unlock();\n        var old_mm_ptr = self.state.mem_table;\n        old_mm = old_mm_ptr.get();\n        defer old_mm_ptr.release();\n        self.state.mem_table = try MemTablePtr.create(self.allocator, new_mm);\n        \n        \/\/ \u5c06\u5199\u6ee1\u7684MemTable\u538b\u5165\u51b7\u6570\u636e\n        try self.state.imm_mem_tables.append(old_mm_ptr.clone()); \/\/ newer memtable is inserted at the end\n    }\n    \/\/ TIPS\uff1a\u628a\u78c1\u76d8\u540c\u6b65\u653e\u5728\u9501\u7684\u8303\u56f4\u5916\u9762\uff0c\u964d\u4f4e\u9501\u7684\u8986\u76d6\n    try old_mm.syncWal();\n}<\/code><\/pre>\n<ul>\n<li>\u5f53\u51b7MemTable\u6570\u7ec4\u5927\u5c0f\u8d85\u51fa\u914d\u7f6e\u9608\u503c\uff0c\u89e6\u53d1SSTable\u843d\u76d8\uff0c\u5f39\u51fa\u6700\u51b7\u7684MemTable\uff0c\u5199\u5165\u78c1\u76d8SSTable\uff0c\u5e76\u8bb0\u5f55\u5728L0\u7684SSTable\u6570\u7ec4\u4e2d\u3002\u8fd9\u4e00\u8fc7\u7a0b\u662f\u5728\u4e00\u4e2a\u7ebf\u7a0b\u4e2d\u5b9a\u65f6\u89e6\u53d1<\/li>\n<\/ul>\n<pre><code class=\"java\">pub fn flushNextMemtable(self: *Self) !void {\n    std.debug.assert(self.state.imm_mem_tables.items.len &gt; 0);\n    var to_flush_table: *MemTable = undefined;\n    {\n        self.state_lock.lockShared();\n        defer self.state_lock.unlockShared();\n        \/\/ oldest memtable is at the index 0\n        to_flush_table = self.state.imm_mem_tables.items[0].load();\n    }\n\n    \/\/ \u5c06\u6700\u51b7\u7684MemTable\u6784\u5efa\u4e3aSSTable\n    var builder = try SsTableBuilder.init(self.allocator, self.options.block_size);\n    defer builder.deinit();\n\n    const sst_id = to_flush_table.id;\n    try to_flush_table.flush(&amp;builder);\n\n    const sst_path = try self.pathOfSst(sst_id);\n    defer self.allocator.free(sst_path);\n    var sst = try builder.build(sst_id, self.block_cache.clone(), sst_path);\n    errdefer sst.deinit();\n\n    \/\/ add the flushed table to l0_sstables\n    {\n        self.state_lock.lock();\n        defer self.state_lock.unlock();\n\n        var m = self.state.imm_mem_tables.orderedRemove(0);\n        defer m.deinit();\n        std.debug.assert(m.load().id == sst_id);\n\n        \/\/ newest sstable is at the end\n        try self.state.l0_sstables.append(sst_id);\n        try self.state.sstables.put(sst.id, try SsTablePtr.create(self.allocator, sst));\n    }\n}<\/code><\/pre>\n<p>\u5f53\u7136\uff0c\u8fd9\u91cc\u53ea\u5b9e\u73b0\u4e86\u4e00\u534a\u7684\u5199\u903b\u8f91\uff0c\u6570\u636e\u505c\u7559\u5728L0\u7684SST\u4e2d\uff0c\u540e\u7eed\u7684\u591a\u5c42SST\u8fd8\u6ca1\u6709\u4f7f\u7528\u3002<\/p>\n<p>\u5269\u4e0b\u4e00\u534a\u7684\u5199\u903b\u8f91\u4f1a\u5728\u6570\u636e\u538b\u7f29\u7684\u7ae0\u8282\u4e2d\u4ecb\u7ecd\u3002<\/p>\n<h3>Iterators<\/h3>\n<p>\u5199\u5165\u7684\u8fc7\u7a0b\u6bd4\u8f83\u597d\u7406\u89e3\uff0c\u4f46\u662f\u8bfb\u5c31\u7565\u5fae\u590d\u6742\u4e86\uff0c\u4ee5\u4e0a\u9762\u6211\u4eec\u5b9e\u73b0\u7684\u5199\u7ed3\u679c\u4e3a\u4f8b\u5b50\uff0c\u6700\u7ec8\u6211\u4eec\u7684\u6570\u636e\u6c89\u6dc0\u5728\u4e00\u4e2a3\u5c42\u7684\u6570\u636e\u7ed3\u6784\u4e2d\uff0c\u8981\u5982\u4f55\u9ad8\u6548\u7684\u4ece\u5176\u4e2d\u68c0\u7d22\u6570\u636e\u5462\uff1f<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184286\" alt=\"\u9ad8\u6548\u68c0\u7d22\u6570\u636e.jpeg\" title=\"\u9ad8\u6548\u68c0\u7d22\u6570\u636e.jpeg\" loading=\"lazy\"><br \/>\u5982\u540c\u5199\u8fc7\u7a0b\u4e00\u822c\uff0c\u8bfb\u8fc7\u7a0b\u4e5f\u662f\u5bf9\u5404\u4e2a\u57fa\u7840\u5355\u5143(MemTable\u3001SSTable\u3001Block)\u8bfb\u8fc7\u7a0b\u7684\u7ec4\u5408\uff0c\u4e3a\u4e86\u65b9\u4fbf\u7ec4\u5408\u903b\u8f91\uff0c\u6211\u4eec\u8981\u5148\u7edf\u4e00\u5404\u4e2a\u6a21\u5757\u7684\u8bfb\u884c\u4e3a\u3002<\/p>\n<p>\u5728LSM-Tree\u4e2d\uff0c\u6240\u6709\u7684\u8bfb\u884c\u4e3a\u90fd\u5b9a\u4e49\u4e3a\u4e86\u5982\u4e0b\u7684Interface\uff08Zig\u4e2d\u6ca1trait\u6216\u8005Interface\uff0c\u6240\u4ee5\u8fd9\u91cc\u5b9e\u4f8b\u4ee3\u7801\u6211\u7528Rust\u63cf\u8ff0\uff09\uff1a<\/p>\n<pre><code class=\"java\">pub trait StorageIterator {\n    \/\/\/ Get the current value.\n    fn value(&amp;self) -&gt; &amp;[u8];\n\n    \/\/\/ Get the current key.\n    fn key(&amp;self) -&gt; &amp;[u8];\n\n    \/\/\/ Check if the current iterator is empty.\n    fn is_empty(&amp;self) -&gt; bool;\n\n    \/\/\/ Move to the next position.\n    fn next(&amp;mut self) -&gt; anyhow::Result&lt;()&gt;;\n\n    \/\/\/ Number of underlying active iterators for this iterator.\n    fn num_active_iterators(&amp;self) -&gt; usize {\n        1\n    }\n}<\/code><\/pre>\n<p>\u6211\u4eec\u9996\u5148\u5bf9MemTable\u3001SSTable\u3001Block\u8fd9\u4e9b\u6a21\u5757\u5b9e\u73b0\u8bfb\u63a5\u53e3\uff0c\u4ee3\u7801\u53ef\u89c1\uff1asrc\/MemTable.zig\uff0csrc\/block.zig\uff0csrc\/ss_table.zig\uff0c\u8fd9\u91cc\u5355\u72ec\u7b80\u5355\u4ecb\u7ecd\u4e0bSSTable\u7684\u8bfb\u63a5\u53e3\u5b9e\u73b0\u601d\u8def\uff0c\u5176\u4ed6\u7684\u6a21\u5757\u5b9e\u73b0\u601d\u8def\u7c7b\u4f3c\uff0c\u611f\u5174\u8da3\u7684\u76f4\u63a5\u9605\u8bfb\u6e90\u7801\u5373\u53ef\u3002<\/p>\n<pre><code class=\"java\">pub const SsTableIterator = struct {\n    allocator: std.mem.Allocator,\n    table: SsTablePtr,\n    blk: BlockPtr,\n    blk_iterator: BlockIteratorPtr,\n    blk_idx: usize,\n\n    const Self = @This();\n\n\n    pub fn initAndSeekToFirst(allocator: std.mem.Allocator, table: SsTablePtr) !Self {\n        const s = try seekToFirstInner(allocator, table);\n        return .{\n            .allocator = allocator,\n            .table = table,\n            .blk_iterator = s.blk_iter,\n            .blk = s.blk,\n            .blk_idx = 0,\n        };\n    }\n\n    pub fn initAndSeekToKey(allocator: std.mem.Allocator, table: SsTablePtr, k: []const u8) !Self {\n        const b = try seekToKeyInner(allocator, table, k);\n        return .{\n            .allocator = allocator,\n            .table = table,\n            .blk_iterator = b.blk_iter,\n            .blk_idx = b.blk_idx,\n            .blk = b.blk,\n        };\n    }\n\n    fn seekToFirstInner(allocator: std.mem.Allocator, table: SsTablePtr) !struct {\n        blk: BlockPtr,\n        blk_iter: BlockIteratorPtr,\n    } {\n        var blk = try table.get().readBlockCached(0, allocator); \/\/ \u8bfb\u53d6\u7b2c\u4e00\u4e2ablock\n        errdefer blk.release();\n        var blk_iter = try BlockIterator.createAndSeekToFirst(allocator, blk.clone());\n        errdefer blk_iter.deinit();\n\n        return .{\n            .blk = blk,\n            .blk_iter = try BlockIteratorPtr.create(allocator, blk_iter), \/\/ \u4eceSSTable\u7684\u8bfb\u63a5\u53e3\u8f6c\u6362\u4e3aBlock\u7684\u8bfb\u63a5\u53e3\n        };\n    }\n\n    fn seekToKeyInner(allocator: std.mem.Allocator, table: SsTablePtr, k: []const u8) !struct {\n        blk_idx: usize,\n        blk: BlockPtr,\n        blk_iter: BlockIteratorPtr,\n    } {\n        const table_ptr = table.get();\n        var blk_idx = try table_ptr.findBlockIndex(k);\n        var blk = try table_ptr.readBlockCached(blk_idx, allocator);\n        errdefer blk.deinit();\n        var blk_iter = try BlockIterator.createAndSeekToKey(allocator, blk.clone(), k);\n        errdefer blk_iter.deinit();\n        var blk_iter_ptr = try BlockIteratorPtr.create(allocator, blk_iter);\n        errdefer blk_iter_ptr.release();\n\n        \/\/ \u5982\u679c\u5f53\u524dblock\u8bfb\u5b8c\u4e86\uff0c\u8df3\u5230\u4e0b\u4e00\u4e2ablock\uff0c\u5e76\u751f\u6210block\u7684\u8bfb\u63a5\u53e3\n        if (blk_iter.isEmpty()) {\n            blk_idx += 1;\n            if (blk_idx &lt; table_ptr.numBlocks()) {\n                {\n                    blk.deinit();\n                    blk_iter.deinit();\n                }\n                var blk2 = try table_ptr.readBlockCached(blk_idx, allocator);\n                errdefer blk2.deinit();\n                var blk_iter2 = try BlockIterator.createAndSeekToFirst(allocator, blk2.clone());\n                errdefer blk_iter2.deinit();\n\n                return .{\n                    .blk_idx = blk_idx,\n                    .blk_iter = try BlockIteratorPtr.create(allocator, blk_iter2),\n                    .blk = blk2,\n                };\n            }\n        }\n        return .{\n            .blk_idx = blk_idx,\n            .blk_iter = blk_iter_ptr,\n            .blk = blk,\n        };\n    }\n\n    pub fn key(self: Self) []const u8 {\n        return self.blk_iterator.get().key();\n    }\n\n    pub fn value(self: Self) []const u8 {\n        return self.blk_iterator.get().value();\n    }\n\n    pub fn isEmpty(self: Self) bool {\n        return self.blk_iterator.get().isEmpty();\n    }\n\n    pub fn next(self: *Self) !void {\n        try self.blk_iterator.get().next();\n        \/\/ \u82e5\u5f53\u524d\u7684Block\u8bfb\u5b8c\u4e86\uff0c\u5c31\u8df3\u5230\u4e0b\u4e00\u4e2ablock\uff0c\u5e76\u751f\u6210Block\u8bfb\u63a5\u53e3\u3002\n        if (self.blk_iterator.get().isEmpty()) {\n            self.blk_idx += 1;\n            if (self.blk_idx &lt; self.table.get().numBlocks()) {\n                self.reset();\n                const blk = try self.table.get().readBlockCached(self.blk_idx, self.allocator);\n                const blk_iter = try BlockIterator.createAndSeekToFirst(self.allocator, blk.clone());\n                self.blk = blk;\n                self.blk_iterator = try BlockIteratorPtr.create(self.allocator, blk_iter);\n            }\n        }\n    }\n};\n<\/code><\/pre>\n<p>\u6709\u4e86\u51e0\u4e2a\u57fa\u672c\u5143\u7d20\u7684\u8bfb\u63a5\u53e3\u4e4b\u540e\uff0c\u6211\u4eec\u4fbf\u9047\u5230\u7b2c\u4e00\u4e2a\u95ee\u9898\uff1a<strong>\u6211\u4eec\u5982\u4f55\u5bf9\u591a\u4e2aMemTable\u505a\u8bfb\u68c0\u7d22\uff1f<\/strong><\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184287\" alt=\"\u5982\u4f55\u5bf9\u591a\u4e2am\u505a\u68c0\u7d22.jpeg\" title=\"\u5982\u4f55\u5bf9\u591a\u4e2am\u505a\u68c0\u7d22.jpeg\" loading=\"lazy\"><br \/>\u8fd9\u4e2a\u65f6\u5019\uff0c\u6211\u4eec\u9700\u8981\u4e00\u4e2a\u65b0\u7684\u6570\u636e\u7ed3\u6784\u6765\u5b9e\u73b0\u591a\u4e2a\u8bfb\u5b9e\u4f8b\u7684\u5408\u5e76\u68c0\u7d22&#8212;- <strong>MergeIterator<\/strong><\/p>\n<p>MergeIterator\u5728\u5185\u90e8\u7ef4\u62a4\u4e00\u4e2a\u4e8c\u53c9\u5806\u3002\u5806\u4e2d\u6570\u636e\u7684\u4f18\u5148\u7ea7\u5982\u4e0b\uff1a<\/p>\n<p><strong>\u5f53\u5404\u4e2a\u8fed\u4ee3\u5668key\u4e0d\u540c\u65f6\uff0c\u5177\u6709\u6700\u5c0fkey\u7684\u8fed\u4ee3\u5668\u6700\u4f18\u3002\u5f53\u591a\u4e2a\u8fed\u4ee3\u5668\u6709\u76f8\u540c\u7684\u5f53\u524dkey\u65f6\uff0c\u6700\u65b0\u7684\u8fed\u4ee3\u5668\u4e00\u4e2a\u6700\u4f18\u3002<\/strong><\/p>\n<p>\u5047\u8bbe\u6211\u4eec\u6709\u5982\u4e0bMemTable\uff08iter1\u6700\u65b0\uff0citer3\u6700\u65e7\uff09:<\/p>\n<p>*iter1: b-&gt;del, c-&gt;4, d-&gt;5<br \/>iter2: a-&gt;1, b-&gt;2, c-&gt;3<br \/>iter3: e-&gt;4*<\/p>\n<p>\u7ecf\u8fc7\u5408\u5e76\u540e\u8fed\u4ee3\u5668\u7ed3\u679c\u5e94\u8be5\u4e3a\uff1a<\/p>\n<p>*a\u6700\u5c0f\uff0citer2\u4f18\u5148\u8fed\u4ee3<br \/>iter2\u8fed\u4ee3\u4e00\u6b21\u540e\uff0citer1\u4e0eiter2 key\u76f8\u540c\uff0citer1\u4f18\u5148\u8fed\u4ee3\uff0cb-&gt;2\u8df3\u8fc7<br \/>c\u6700\u5c0f\uff0citer1\u4f18\u5148\u8fed\u4ee3\uff0citer2\u4e2dc-&gt;3\u8df3\u8fc7<br \/>d\u6700\u5c0f\uff0citer1\u4f18\u5148\u8fed\u4ee3<br \/>\u53ea\u5269iter3\uff0c\u8fed\u4ee3iter3*<\/p>\n<p>\u6700\u7ec8\u7ed3\u679c\uff1aa-&gt;1, b-&gt;del, c-&gt;4, d-&gt;5, e-&gt;4<\/p>\n<p>\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"java\">\/\/ \u6807\u51c6\u5e93\u4e2d\u6709\u4e8c\u53c9\u5806\u5b9e\u73b0\nconst IteratorHeap = std.PriorityQueue(*HeapWrapper, Comparer.Context, Comparer.cmp);\n\nallocator: std.mem.Allocator,\nq: IteratorHeap,\ncurrent: ?*HeapWrapper,\n\npub fn init(allocator: std.mem.Allocator, iters: std.ArrayList(StorageIteratorPtr)) !Self {\n    var q = IteratorHeap.init(allocator, .{});\n    if (iters.items.len == 0) {\n        return Self{\n            .allocator = allocator,\n            .q = q,\n            .current = null,\n        };\n    }\n\n    \/\/ PS: the last iter has the highest priority\n    \/\/ \u6309\u987a\u5e8f\u5199\u5165\u4e8c\u53c9\u5806\n    for (iters.items, 0..) |sp, i| {\n        if (!sp.load().isEmpty()) {\n            const hw = try allocator.create(HeapWrapper);\n            errdefer allocator.destroy(hw);\n            hw.* = HeapWrapper.init(i, sp.clone());\n            try q.add(hw);\n        }\n    }\n\n    const cc = q.removeOrNull();\n    return Self{\n        .allocator = allocator,\n        .q = q,\n        .current = cc,\n    };\n}\n\npub fn key(self: Self) []const u8 {\n    return self.current.?.key();\n}\n\npub fn value(self: Self) []const u8 {\n    return self.current.?.value();\n}\n\npub fn isEmpty(self: Self) bool {\n    if (self.current) |cc| {\n        return cc.isEmpty();\n    }\n    return true;\n}\n\npub fn next(self: *Self) !void {\n    const cc = self.current.?;\n    while (true) {\n        if (self.q.peek()) |ii| {\n            std.debug.assert(!ii.isEmpty());\n            \/\/ \u5982\u679c\u4f18\u5148\u5806\u5934\u90e8\u8fed\u4ee3\u5668A\u548c\u5f53\u524d\u6b63\u5728\u751f\u6548\u7684\u8fed\u4ee3\u5668B\u7684key\u76f8\u540c\uff0c\u8ba9\u8fed\u4ee3\u5668A\u8df3\u8fc7\u91cd\u590dkey\n            if (std.mem.eql(u8, cc.key(), ii.key())) {\n                try ii.next();\n                if (ii.isEmpty()) {\n                    _ = self.q.remove();\n                    ii.deinit();\n                    self.allocator.destroy(ii);\n                }\n            } else {\n                break;\n            }\n        }\n        break;\n    }\n\n    try cc.next(); \/\/ \u8fed\u4ee3\u5f53\u524d\u8fed\u4ee3\u5668\n\n    \/\/ \u5982\u679c\u5f53\u524d\u4f18\u5148\u8fed\u4ee3\u5668\u8fed\u4ee3\u5b8c\u4e86\uff0c\u5c31\u4ece\u5806\u4e2d\u5f39\u51fa\u6700\u4f18\u8fed\u4ee3\u5668\n    if (cc.isEmpty()) {\n        defer {\n            cc.deinit();\n            self.allocator.destroy(cc);\n        }\n        if (self.q.removeOrNull()) |h| {\n            self.current = h;\n        } else {\n            self.current = null;\n        }\n        return;\n    }\n\n    \/\/ \u5c06\u5f53\u524d\u8fed\u4ee3\u5668\u5199\u56de\u4e8c\u53c9\u5806\uff0c\u91cd\u65b0\u8ba1\u7b97\u6700\u4f18\u8fed\u4ee3\u5668\n    try self.q.add(cc); \n    self.current = self.q.removeOrNull();\n}<\/code><\/pre>\n<p>\u6709\u4e86MergeIterator\u8fd9\u4e2a\u5de5\u5177\uff0c\u6211\u4eec\u5177\u5907\u4e86\u5728\u591a\u4e2aMemTable\u548c\u591a\u4e2aSSTable\u4e2d\u8fed\u4ee3\u68c0\u7d22\u7684\u80fd\u529b\uff0c\u4f46\u662f\u8fd8\u6709\u4e2a\u95ee\u9898\uff0c\u6211\u4eec\u5f53\u524d\u6709\u4e24\u4e2aMergeIterator\uff0c\u5e94\u8be5\u5982\u4f55\u5728\u4e24\u4e2a\u8fed\u4ee3\u5668\u4e2d\u6267\u884c\u8fed\u4ee3\u4efb\u52a1\uff1f<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184288\" alt=\"\u6267\u884c\u8fed\u4ee3\u4efb\u52a1.jpeg\" title=\"\u6267\u884c\u8fed\u4ee3\u4efb\u52a1.jpeg\" loading=\"lazy\"><br \/>\u6b64\u65f6\uff0c\u6211\u4eec\u518d\u5f15\u5165\u4e00\u4e2a\u65b0\u7684\u6570\u636e\u7ed3\u6784\uff1a<strong>TwoMergeIterator<\/strong>\uff0c\u8fd9\u4e2a\u662fMergeIterator\u5728\u5143\u7d20\u53ea\u6709\u4e24\u4e2a\u7684\u60c5\u51b5\u4e0b\u7684\u7b80\u5316\u7248\u3002<\/p>\n<p>TwoMergeIterator\u7531\u4e24\u4e2a\u8fed\u4ee3\u5668\u6784\u6210\uff0c\u4e00\u4e2a\u9ad8\u4f18\u4e00\u4e2a\u4f4e\u4f18\uff0c\u6bcf\u6b21\u8fed\u4ee3\u4f18\u5148\u8fed\u4ee3\u9ad8\u4f18\uff0c\u5f53key\u76f8\u540c\u65f6\uff0c\u4f18\u5148\u8fed\u4ee3\u9ad8\u4f18\u3002\u5b9e\u73b0\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"java\">pub const TwoMergeIterator = struct {\n    a: StorageIteratorPtr,\n    b: StorageIteratorPtr,\n    choose_a: bool,\n\n    \/\/ \u9009\u62e9\u4e24\u4e2a\u8fed\u4ee3\u5668\u4e2dkey\u66f4\u5c0f\u7684\u8fed\u4ee3\u5668\n    fn chooseA(a: *StorageIterator, b: *StorageIterator) bool {\n        if (a.isEmpty()) {\n            return false;\n        }\n        if (b.isEmpty()) {\n            return true;\n        }\n        return std.mem.lessThan(u8, a.key(), b.key());\n    }\n\n    \/\/ key\u76f8\u540c\u65f6\uff0c\u8df3\u8fc7\u4f4e\u4f18\u4e2d\u7684key\n    fn skipB(self: *TwoMergeIterator) !void {\n        const ap = self.a.load();\n        const bp = self.b.load();\n        if (!ap.isEmpty() and !bp.isEmpty() and std.mem.eql(u8, ap.key(), bp.key())) try bp.next();\n    }\n\n    pub fn init(a: StorageIteratorPtr, b: StorageIteratorPtr) !TwoMergeIterator {\n        var iter = TwoMergeIterator{\n            .a = a,\n            .b = b,\n            .choose_a = false,\n        };\n        try iter.skipB();\n        iter.choose_a = chooseA(iter.a.load(), iter.b.load());\n        return iter;\n    }\n\n    pub fn deinit(self: *TwoMergeIterator) void {\n        self.a.release();\n        self.b.release();\n    }\n\n    pub fn key(self: TwoMergeIterator) []const u8 {\n        if (self.choose_a) {\n            std.debug.assert(!self.a.load().isEmpty());\n            return self.a.load().key();\n        }\n        std.debug.assert(!self.b.load().isEmpty());\n        return self.b.load().key();\n    }\n\n    pub fn value(self: TwoMergeIterator) []const u8 {\n        if (self.choose_a) {\n            std.debug.assert(!self.a.load().isEmpty());\n            return self.a.load().value();\n        }\n        std.debug.assert(!self.b.load().isEmpty());\n        return self.b.load().value();\n    }\n\n    pub fn isEmpty(self: TwoMergeIterator) bool {\n        if (self.choose_a) {\n            return self.a.load().isEmpty();\n        }\n        return self.b.load().isEmpty();\n    }\n\n    pub fn next(self: *TwoMergeIterator) !void {\n        if (self.choose_a) {\n            try self.a.load().next();\n        } else {\n            try self.b.load().next();\n        }\n        try self.skipB();\n        self.choose_a = chooseA(self.a.load(), self.b.load());\n    }\n};\n<\/code><\/pre>\n<p>\u81f3\u6b64\uff0c\u6211\u4eec\u8bfb\u884c\u4e3a\u6240\u9700\u8981\u7684\u6b66\u5668\u5c31\u5b8c\u5907\u4e86\uff01<\/p>\n<h3>Read\/Scan<\/h3>\n<p>\u8ba9\u6211\u4eec\u518d\u6765\u770b\u770bLSM\u7684\u67b6\u6784\u56fe\uff1a<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184289\" alt=\"LSM\u7684\u67b6\u6784\u56fe.jpeg\" title=\"LSM\u7684\u67b6\u6784\u56fe.jpeg\" loading=\"lazy\"><br \/>\u6211\u4eec\u5c06\u6bcf\u4e2a\u6570\u636e\u5c42\u4e2d\u7684\u6570\u636e\u6807\u4e0a\u4f18\u5148\u7ea7\uff0c\u7531\u4e8eLSM-Tree\u662fappend-only\u7684\uff0c\u6240\u4ee5\u4f18\u5148\u7ea7\u8d8a\u9ad8\u7684\u6570\u636e\u5c42\u4e2d\u6570\u636e\u8d8a\u65b0\u3002<\/p>\n<p>\u6240\u4ee5\u6211\u4eec\u7684\u8bfb\u7b56\u7565\u4e5f\u5f88\u660e\u663e\uff1a\u6309\u7167\u4e0a\u56fe\u4e2dP0\u81f3P2\u4f9d\u6b21\u68c0\u7d22\uff0c\u8fd9\u90e8\u5206\u4ee3\u7801\u5b9e\u73b0\u89c1src\/storage.zig\u3002<\/p>\n<ul>\n<li>\u8bfbMemTable<\/li>\n<\/ul>\n<pre><code class=\"java\">\/\/ search in memtable\nif (try self.state.getMemTable().get(key, value)) {\n    if (value.*.len == 0) {\n        \/\/ tomestone\n        return false;\n    }\n    return true;\n}<\/code><\/pre>\n<ul>\n<li>\u8bfbImmutable MemTable<\/li>\n<\/ul>\n<pre><code class=\"java\">\/\/ search in imm_memtables\n\nself.state_lock.lockShared();\ndefer self.state_lock.unlockShared();\nfor (self.state.imm_mem_tables.items) |imm_table| {\n    if (try imm_table.load().get(key, value)) {\n        if (value.*.len == 0) {\n            \/\/ tomestone\n            return false;\n        }\n        return true;\n    }\n}<\/code><\/pre>\n<ul>\n<li>\u8bfbLV0~LVmax SSTables<\/li>\n<\/ul>\n<pre><code class=\"java\">\/\/ \u6536\u96c6L0\u4e2d\u7684\u8fed\u4ee3\u5668\nvar l0_iters = std.ArrayList(StorageIteratorPtr).init(self.allocator);\ndefer {\n    for (l0_iters.items) |iter| {\n        var ii = iter;\n        ii.release();\n    }\n    l0_iters.deinit();\n}\n{\n    self.state_lock.lockShared();\n    defer self.state_lock.unlockShared();\n    for (self.state.l0_sstables.items) |sst_id| {\n        const sst = self.state.sstables.get(sst_id).?;\n        if (try sst.load().mayContain(key)) {\n            var ss_iter = try SsTableIterator.initAndSeekToKey(self.allocator, sst.clone(), key);\n            errdefer ss_iter.deinit();\n            try l0_iters.append(try StorageIteratorPtr.create(self.allocator, .{ .ss_table_iter = ss_iter }));\n        }\n    }\n}\n\n\/\/ \u6536\u96c6Levels\u4e2d\u7684\u8fed\u4ee3\u5668\nvar level_iters: std.ArrayList(StorageIteratorPtr) = undefined;\n{\n    self.state_lock.lockShared();\n    defer self.state_lock.unlockShared();\n    level_iters = try std.ArrayList(StorageIteratorPtr).initCapacity(\n        self.allocator,\n        self.state.levels.items.len,\n    );\n    for (self.state.levels.items) |level| {\n        var level_ssts = try std.ArrayList(SsTablePtr).initCapacity(self.allocator, level.items.len);\n        errdefer level_ssts.deinit();\n        for (level.items) |sst_id| {\n            const sst = self.state.sstables.get(sst_id).?;\n            if (try mayWithinTable(key, sst)) {\n                try level_ssts.append(sst.clone());\n            }\n        }\n        if (level_ssts.items.len &gt; 0) {\n            var level_iter = try SstConcatIterator.initAndSeekToKey(\n                self.allocator,\n                level_ssts,\n                key,\n            );\n            errdefer level_iter.deinit();\n            try level_iters.append(try StorageIteratorPtr.create(self.allocator, .{ .sst_concat_iter = level_iter }));\n        }\n    }\n}\n\n\/\/ \u5c06\u591a\u4e2a\u8fed\u4ee3\u5668\u5408\u5e76\u4e3a\u4e00\u4e2aTwoMergeIterator\nvar l0_merge_iter = try MergeIterators.init(self.allocator, l0_iters);\nerrdefer l0_merge_iter.deinit();\n\nvar levels_merge_iter = try MergeIterators.init(self.allocator, level_iters);\nerrdefer levels_merge_iter.deinit();\n\nvar iter = try TwoMergeIterator.init(\n    try StorageIteratorPtr.create(self.allocator, .{ .merge_iterators = l0_merge_iter }),\n    try StorageIteratorPtr.create(self.allocator, .{ .merge_iterators = levels_merge_iter }),\n);\ndefer iter.deinit();\n\nif (iter.isEmpty()) {\n    return false;\n}\n\nif (std.mem.eql(u8, iter.key(), key) and iter.value().len &gt; 0) {\n    value.* = iter.value();\n    return true;\n}\n<\/code><\/pre>\n<h3>\u538b\u7f29<\/h3>\n<p>\u5728\u4e0a\u4e00\u8282\u7684\u5199\u8fc7\u7a0b\u4e2d\uff0c\u6211\u4eec\u5b9e\u73b0\u4e86\u4ece\u5185\u5b58\u8868\u5230Level0\u7684SSTable\u5806\u53e0\u3002<\/p>\n<p>\u968f\u7740\u5199\u5165\u7684\u6301\u7eed\uff0cLv0\u7684SSTable\u4f1a\u8d8a\u6765\u8d8a\u591a\uff0c\u8fd9\u4e2a\u65f6\u5019\u5c31\u9700\u8981\u6211\u4eec\u5c06Lv0\u4e2d\u7684\u6570\u636e\u5408\u5e76\u5199\u5165\u81f3Lv2\uff0c\u5e76\u4f9d\u6b21\u7c7b\u63a8\u91cd\u590d\u8fd9\u4e2a\u8fc7\u7a0b\uff0c\u76f4\u5230\u5806\u53e0\u5230\u6700\u6df1\u7684\u5c42\u6570\uff0c\u8fd9\u4e2a\u9010\u5c42\u5408\u5e76\u6570\u636e\u7684\u8fc7\u7a0b\u5c31\u662f<strong>\u6570\u636e\u538b\u7f29<\/strong>\u3002<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184290\" alt=\"\u6570\u636e\u538b\u7f29.jpeg\" title=\"\u6570\u636e\u538b\u7f29.jpeg\" loading=\"lazy\"><br \/>LSM-Tree\u4e2d\u6570\u636e\u538b\u7f29\u7684\u8fc7\u7a0b\u5927\u81f4\u5982\u4e0b\uff1a<\/p>\n<p><img decoding=\"async\"   referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000046184291\" alt=\"\u8fc7\u7a0b\u5927\u81f4\u5982\u4e0b.jpeg\" title=\"\u8fc7\u7a0b\u5927\u81f4\u5982\u4e0b.jpeg\" loading=\"lazy\"><br \/>\u5177\u4f53\u7684\u5b9e\u73b0\u4ee3\u7801\u53ef\u89c1src\/compact.zig\uff0csrc\/storage.zig\u3002<\/p>\n<p>\u7b80\u5355\u5206\u5c42\u538b\u7f29\u4e0e\u539f\u59cb LSM \u8bba\u6587\u4e2d\u7684\u538b\u7f29\u7b56\u7565\u76f8\u4f3c\u3002\u5b83\u4e3a LSM \u6811\u7ef4\u62a4\u591a\u4e2a\u5c42\u7ea7\u3002\u5f53\u4e00\u4e2a\u5c42\u7ea7\u592a\u5927\u65f6\uff0c\u5b83\u4f1a\u5c06\u6b64\u5c42\u7ea7\u7684\u6240\u6709 SST \u4e0e\u4e0b\u4e00\u5c42\u5408\u5e76\u3002\u538b\u7f29\u7b56\u7565\u7531 3 \u4e2a\u53c2\u6570\u63a7\u5236\uff1a<\/p>\n<ul>\n<li>size_ratio_percent\uff1a\u3010\u6587\u4ef6\u4f4e\u7ea7\u6570\u91cf\/\u6587\u4ef6\u9ad8\u7ea7\u6570\u91cf\u3011\uff0c\u5f53\u5b9e\u9645\u8ba1\u7b97\u7684\u503c\u4f4e\u4e8e\u6b64\u9608\u503c\u65f6\u89e6\u53d1\u538b\u7f29\u3002\u5047\u8bbe\u8fd9\u91cc\u6211\u4eec\u8bbe\u7f6e\u4e3a60%\uff0c\u5f53L0\u4e2dSST\u6570\u91cf\u4e3a2\uff0cL1\u4e2dSST\u6570\u91cf\u4e3a1\uff0c\u6b64\u65f6ratio\u4e3a1\/2 = 50% &lt; 60%\uff0c\u6b64\u65f6\u6211\u4eec\u5e94\u8be5\u5c06L0\u538b\u7f29\u5408\u5e76\u81f3L1\u3002<\/li>\n<li>level0_file_num_compaction_trigger: \u7b2c\u4e00\u5c42SSTable\u8fbe\u5230\u591a\u5c11\u540e\u89e6\u53d1\u538b\u7f29\u3002\u56e0\u4e3a\u8fd9\u662f\u6700\u9ad8\u5c42\uff0c\u6ca1\u6cd5\u4e0e\u66f4\u9ad8\u5c42\u6bd4\u8f83\uff0c\u53ea\u80fd\u56fa\u5b9a\u89e6\u53d1\u538b\u7f29\u3002<\/li>\n<li>max_levels: \u987e\u540d\u601d\u4e49\uff0c\u6700\u5927\u7684\u5c42\u6570\u9650\u5236\u3002<\/li>\n<\/ul>\n<p>\u505a\u597d\u8fd9\u4e9b\u51c6\u5907\u5de5\u4f5c\uff0c\u6211\u4eec\u53ef\u4ee5\u9010\u6b65\u5b9e\u73b0\u538b\u7f29\u903b\u8f91\uff1a<\/p>\n<ul>\n<li>\u751f\u6210\u538b\u7f29\u4efb\u52a1\uff1a<\/li>\n<\/ul>\n<pre><code class=\"java\">pub const SimpleLeveledCompactionController = struct {\n    options: SimpleLeveledCompactionOptions,\n\n    pub fn generateCompactionTask(self: SimpleLeveledCompactionController, state: *storage.StorageState) !?SimpleLeveledCompactionTask {\n        if (self.options.max_levels == 1) {\n            return null;\n        }\n\n        var level_sizes = std.ArrayList(usize).init(state.allocator);\n        defer level_sizes.deinit();\n\n        try level_sizes.append(state.l0_sstables.items.len);\n        for (state.levels.items) |level| {\n            try level_sizes.append(level.items.len);\n        }\n\n        \/\/ \u5982\u679cLv0\u4e2dSST\u6570\u91cf\u8d85\u51fa\u9608\u503c\uff0c\u89e6\u53d1L0\u7ea7\u522b\u538b\u7f29\n        if (state.l0_sstables.items.len &gt;= self.options.level0_file_num_compaction_trigger) {\n            std.debug.print(&quot;compaction of L0 to L1 because L0 has {d} SSTS &gt;= {d}\/n&quot;, .{ state.l0_sstables.items.len, self.options.level0_file_num_compaction_trigger });\n            return .{\n                .upper_level = null,\n                .upper_level_sst_ids = try state.l0_sstables.clone(),\n                .lower_level = 1,\n                .lower_level_sst_ids = try state.levels.items[0].clone(),\n                .is_lower_level_bottom = false,\n            };\n        }\n\n        \/\/ \u8ba1\u7b97Lv[n+1]\/lv[n]\uff0c\u5982\u679c\u6bd4\u4f8b\u5c0f\u4e8e\u9608\u503c\uff0c\u89e6\u53d1Lv[n]\u7ea7\u522b\u538b\u7f29\n        for (1..self.options.max_levels) |level| {\n            const lower_level = level + 1;\n            if (level_sizes.items[level] == 0) {\n                continue;\n            }\n            const size_ration = level_sizes.items[lower_level] * 100 \/ level_sizes.items[level];\n            if (size_ration &lt; self.options.size_ration_percent) {\n                std.debug.print(&quot;compaction of L{d} to L{d} because L{d} size ratio {d} &lt; {d}\/n&quot;, .{ level, lower_level, level, size_ration, self.options.size_ration_percent });\n                return .{\n                    .upper_level = level,\n                    .upper_level_sst_ids = try state.levels.items[level - 1].clone(),\n                    .lower_level = lower_level,\n                    .lower_level_sst_ids = try state.levels.items[lower_level - 1].clone(),\n                    .is_lower_level_bottom = lower_level == self.options.max_levels,\n                };\n            }\n        }\n\n        return null;\n    }\n}<\/code><\/pre>\n<ul>\n<li>\u6267\u884c\u538b\u7f29\u4efb\u52a1\uff1a<\/li>\n<\/ul>\n<p>\u6709\u4e86\u4e0a\u4e00\u5c0f\u8282\u4e2d\u8bfb\u8fc7\u7a0b\u7684\u4ecb\u7ecd\uff0c\u591a\u5c42\u6570\u636e\u7684\u538b\u7f29\u8fc7\u7a0b\u5c31\u5f88\u597d\u7406\u89e3\u4e86\u3002<\/p>\n<p>\u4f8b\u5982\u6211\u4eec\u60f3\u5c06L1\u4e0eL2\u7684SSTable\u5408\u5e76\u538b\u7f29\u81f3L2\uff0c\u6211\u4eec\u53ea\u9700\u8981\u628aL1\u548cL2\u7684\u6570\u636e\u653e\u5728\u4e00\u8d77\u521b\u9020\u4e00\u4e2a\u8fed\u4ee3\u5668\uff0c\u518d\u6301\u7eed\u4ece\u8be5\u8fed\u4ee3\u5668\u4e2d\u8bfb\u51fa\u6570\u636e\u5199\u5165\u65b0\u7684SSTable\u4e2d\uff0c\u8fd9\u4e2a\u8fc7\u7a0b\u4fdd\u8bc1\u4e86\u65b0\u7684SSTable\u4e2d\u6570\u636e\u4e0d\u91cd\u590d\u4e14\u6709\u5e8f\u3002<\/p>\n<pre><code class=\"java\">fn compactSimple(self: *Self, task: SimpleLeveledCompactionTask) !std.ArrayList(SsTablePtr) {\n    if (task.upper_level) |_| {\n        var upper_ssts = try std.ArrayList(SsTablePtr).initCapacity(\n            self.allocator,\n            task.upper_level_sst_ids.items.len,\n        );\n        var lower_ssts = try std.ArrayList(SsTablePtr).initCapacity(\n            self.allocator,\n            task.lower_level_sst_ids.items.len,\n        );\n\n        self.state_lock.lockShared();\n        for (task.upper_level_sst_ids.items) |sst_id| {\n            const sst = self.state.sstables.get(sst_id).?;\n            try upper_ssts.append(sst.clone());\n        }\n        for (task.lower_level_sst_ids.items) |sst_id| {\n            const sst = self.state.sstables.get(sst_id).?;\n            try lower_ssts.append(sst.clone());\n        }\n        self.state_lock.unlockShared();\n\n        var upper_iter = try SstConcatIterator.initAndSeekToFirst(self.allocator, upper_ssts);\n        errdefer upper_iter.deinit();\n\n        var lower_iter = try SstConcatIterator.initAndSeekToFirst(self.allocator, lower_ssts);\n        errdefer lower_iter.deinit();\n\n        var iter = try TwoMergeIterator.init(\n            try StorageIteratorPtr.create(self.allocator, .{ .sst_concat_iter = upper_iter }),\n            try StorageIteratorPtr.create(self.allocator, .{ .sst_concat_iter = lower_iter }),\n        );\n        defer iter.deinit();\n        return self.compactGenerateSstFromIter(&amp;iter, task.is_lower_level_bottom);\n    } else {\n        \/\/ compact l0_sstables to l1_sstables\n        \/\/ ..... \u4ee3\u7801\u903b\u8f91\u5927\u81f4\u4e0e\u4e0a\u9762LvN\u5c42\u538b\u7f29\u4e00\u81f4\uff0c\u53ea\u662fLv0\u5c42\u7684SSTable\u662f\u65e0\u5e8f\u7684\u9700\u8981\u7279\u6b8a\u8003\u8651\n        return self.compactGenerateSstFromIter(&amp;iter, task.is_lower_level_bottom);\n    }\n}\n\n\nfn compactGenerateSstFromIter(self: *Self, iter: *TwoMergeIterator, compact_to_bottom_level: bool) !std.ArrayList(SsTablePtr) {\n    var builder: SsTableBuilder = try SsTableBuilder.init(self.allocator, self.options.block_size);\n    defer builder.deinit();\n    var new_ssts = std.ArrayList(SsTablePtr).init(self.allocator);\n    \n    \/\/ \u6301\u7eed\u8fed\u4ee3\u6b64\u8fed\u4ee3\u5668\n    while (!iter.isEmpty()) {\n        \/\/ \u5982\u679c\u538b\u7f29\u81f3\u6700\u540e\u4e00\u5c42\uff0c\u53ef\u4ee5\u4e0d\u4fdd\u7559\u5893\u7891\u503ckey\u4e86\n        if (compact_to_bottom_level) {\n            if (iter.value().len &gt; 0) {\n                try builder.add(iter.key(), iter.value());\n            }\n        } else {\n            try builder.add(iter.key(), iter.value());\n        }\n        \/\/ \u5f53\u5199\u6ee1\u4e00\u4e2aSSTable\u540e\uff0c\u5c31\u6e05\u7a7abuilder\uff0c\u628a\u5199\u6ee1\u7684SSTable\u5165\u5217\n        if (builder.estimatedSize() &gt;= self.options.target_sst_size) {\n            \/\/ reset builder\n            defer builder.reset() catch unreachable;\n            const sst_id = self.getNextSstId();\n            const path = try self.pathOfSst(sst_id);\n            defer self.allocator.free(path);\n            var sst = try builder.build(sst_id, self.block_cache.clone(), path);\n            errdefer sst.deinit();\n\n            var sst_ptr = try SsTablePtr.create(self.allocator, sst);\n            errdefer sst_ptr.deinit();\n\n            try new_ssts.append(sst_ptr);\n        }\n        try iter.next();\n    }\n    \/\/ \u5269\u4f59\u7684\u6570\u636e\u5355\u72ec\u4e00\u4e2aSSTable\n    if (builder.estimatedSize() &gt; 0) {\n        const sst_id = self.getNextSstId();\n        const path = try self.pathOfSst(sst_id);\n        defer self.allocator.free(path);\n        var sst = try builder.build(sst_id, self.block_cache.clone(), path);\n        errdefer sst.deinit();\n        var sst_ptr = try SsTablePtr.create(self.allocator, sst);\n        errdefer sst_ptr.deinit();\n        try new_ssts.append(sst_ptr);\n    }\n    return new_ssts;\n}\n<\/code><\/pre>\n<ul>\n<li>\u66ff\u6362\u538b\u7f29\u540e\u7684SST<\/li>\n<\/ul>\n<p>\u8fd9\u90e8\u5206\u903b\u8f91\u5e76\u4e0d\u590d\u6742\uff0c\u5373\u5220\u9664\u6b64\u6b21\u538b\u7f29\u4efb\u52a1\u4e2d\u7684\u539f\u6709\u4e24\u5c42\u6570\u636e\uff0c\u7528\u65b0\u5408\u5e76\u7684SSTable\u66ff\u6362\u81f3\u8f83\u4f4e\u5c42\u6570\u636e\u3002<\/p>\n<p><em>\u8fd9\u91cc\u6709\u4e2a\u9700\u8981\u6ce8\u610f\u7684\u70b9\uff0c\u5373\u538b\u7f29\u8fc7\u7a0b\u662f\u5728\u4e00\u4e2a\u7ebf\u7a0b\u4e2d\u5355\u72ec\u6267\u884c\u7684\uff0c\u538b\u7f29\u8fc7\u7a0b\u4e2dLSM-Tree\u7684\u539f\u6570\u636e\u53ef\u80fd\u53d1\u751f\u4e86\u6539\u53d8\uff0c\u6240\u4ee5\u8fd9\u91cc\u6267\u884cSSTable\u5220\u9664\u65f6\u8981\u6ce8\u610f\u8fc7\u6ee4\u6389\u65b0\u6570\u636e\uff0c\u4e0d\u80fd\u8986\u76d6\u4e86\u6709\u6548\u6570\u636e\u3002<\/em><\/p>\n<p><em>\u5e76\u53d1\u95ee\u9898\u662f\u8f6f\u4ef6\u4e2d\u7684Bug\u96c6\u6563\u5730\uff01<\/em><\/p>\n<pre><code class=\"java\">pub fn applyCompactionResult(\n    _: SimpleLeveledCompactionController,\n    state: *storage.StorageState,\n    task: SimpleLeveledCompactionTask,\n    output: []usize,\n) !std.ArrayList(usize) {\n    var files_to_remove = std.ArrayList(usize).init(state.allocator);\n    errdefer files_to_remove.deinit();\n\n    if (task.upper_level) |upper_level| {\n        \/\/ \u5220\u9664\u9ad8\u5c42SSTable\u6570\u636e\uff0c\u8fd9\u5c42\u6570\u636e\u4e0d\u4f1a\u5728\u538b\u7f29\u8fc7\u7a0b\u4e2d\u53d8\u66f4\uff0c\u653e\u5fc3\u5220\n        std.debug.assert(sliceEquals(\n            task.upper_level_sst_ids.items,\n            state.levels.items[upper_level - 1].items,\n        ));\n        try files_to_remove.appendSlice(task.upper_level_sst_ids.items);\n        state.levels.items[upper_level - 1].clearAndFree();\n    } else {\n        \/\/ \u5220\u9664L0\u6570\u636e\uff0c\u9700\u8981\u5c0f\u5fc3\n        try files_to_remove.appendSlice(task.upper_level_sst_ids.items);\n        var new_l0_sstables = std.ArrayList(usize).init(state.allocator);\n        errdefer new_l0_sstables.deinit();\n\n        {\n            var l0_sst_compacted = std.AutoHashMap(usize, struct {}).init(state.allocator);\n            defer l0_sst_compacted.deinit();\n            for (task.upper_level_sst_ids.items) |sst_id| {\n                try l0_sst_compacted.put(sst_id, .{});\n            }\n\n            for (state.l0_sstables.items) |sst_id| {\n                if (!l0_sst_compacted.remove(sst_id)) { \/\/ \u4e0d\u5728\u538b\u7f29\u4efb\u52a1\u4e2d\u7684SST\u4e0d\u80fd\u5220\u9664\n                    try new_l0_sstables.append(sst_id);\n                }\n            }\n            std.debug.assert(l0_sst_compacted.count() == 0);\n        }\n        state.l0_sstables.deinit();\n        state.l0_sstables = new_l0_sstables;\n    }\n    \/\/ \u4f4e\u5c42SSTable\u6570\u636e\uff0c\u76f4\u63a5\u5220\u9664\n    try files_to_remove.appendSlice(task.lower_level_sst_ids.items);\n    state.levels.items[task.lower_level - 1].clearAndFree();\n    try state.levels.items[task.lower_level - 1].appendSlice(output);\n\n    return files_to_remove;\n}\n\n\n\/\/ sst to remove\nvar ssts_to_remove = std.ArrayList(SsTablePtr).init(self.allocator);\n\n{\n    var new_sst_ids = std.ArrayList(usize).init(self.allocator);\n    defer new_sst_ids.deinit();\n\n    self.state_lock.lock();\n    defer self.state_lock.unlock();\n\n    for (sstables.items) |sst| {\n        const id: usize = @intCast(sst.get().sstId());\n        try new_sst_ids.append(id);\n        try self.state.sstables.put(id, sst.clone());\n    }\n\n    var file_to_remove = try self.compaction_controller.applyCompactionResult(\n        &amp;self.state,\n        task,\n        output.items,\n    );\n    defer file_to_remove.deinit();\n\n    for (file_to_remove.items) |id| {\n        if (self.state.sstables.fetchRemove(id)) |kv| {\n            try ssts_to_remove.append(kv.value);\n        }\n    }\n    try self.syncDir();\n}\n\nfor (ssts_to_remove.items) |sst| {\n    const path = try self.pathOfSst(sst.get().sstId());\n    defer self.allocator.free(path);\n    try std.fs.cwd().deleteFile(path);\n}\ntry self.syncDir();<\/code><\/pre>\n<h2>\u56db\u3001\u603b\u7ed3<\/h2>\n<p>\u6211\u4eec\u4f7f\u7528Zig\u8bed\u8a00\u5b9e\u73b0\u4e86\u4e00\u4e2aLSM-Tree\u7684\u6838\u5fc3\u529f\u80fd\uff0c\u5305\u62ecMemTable\u3001SSTable\u3001\u5199\u6d41\u7a0b\u3001\u5404\u7c7bIterator\u4e0e\u6570\u636e\u538b\u7f29\u80fd\u529b\u3002\u901a\u8fc7\u8fd9\u4e2a\u9879\u76ee\uff0c\u6211\u6536\u83b7\u4e86\u5f88\u591a\u5fc3\u5f97\u4f53\u4f1a\u3002<\/p>\n<h4>\u4e86\u89e3\u4e86LSM-Tree\u7684\u6838\u5fc3\u6d41\u7a0b<\/h4>\n<p>\u4ee5\u5f80\u5bf9LSM\u8fd9\u4e2a\u6570\u636e\u7ed3\u6784\u7684\u591a\u5c42SST\u8bbe\u8ba1\u4e0e\u5199\u8fc7\u7a0b\u65e9\u6709\u8033\u95fb\uff0c\u4f46\u662f\u8bfb\u6d41\u7a0b\u7684\u5b9e\u73b0\u4e0d\u592a\u7406\u89e3\u3002\u8fd9\u4e2a\u9879\u76ee\u89e3\u7b54\u4e86\u6211\u7591\u60d1\u5f88\u4e45\u7684\u8bfb\u6d41\u7a0b\u7684\u5b9e\u73b0\uff0c\u7279\u522b\u662fMergeIterator\u7684\u7b97\u6cd5\u8bbe\u8ba1\u975e\u5e38\u5de7\u5999\u3002<\/p>\n<h4>\u6478\u7d22\u4e86\u4e2azig\u8bed\u8a00\u7684\u667a\u80fd\u6307\u9488<\/h4>\n<p>Zig\u8bed\u8a00\u6ca1\u6709\u5185\u5b58\u5b89\u5168\u7684\u4fdd\u8bc1\uff0c\u4e3a\u4e86\u4e0d\u60f3\u6307\u9488\u4e71\u98de\u5230\u5904\u6cc4\u9732\uff0c\u5728Deepseek\u7684\u5e2e\u52a9\u4e0b\u5b9e\u73b0\u4e86\u4e00\u4e2a\u7b80\u5355\u7684\u667a\u80fd\u6307\u9488\uff0c\u6781\u5927\u964d\u4f4e\u4e86\u5185\u5b58\u7ba1\u7406\u7684\u5fc3\u667a\u8d1f\u62c5\u3002<\/p>\n<h4>\u5de5\u7a0b\u7ecf\u9a8c<\/h4>\n<ul>\n<li>\u5c3d\u53ef\u80fd\u591a\u7684\u505aassertion\u7684\u5de5\u4f5c\uff0c\u53ef\u4ee5\u63d0\u524d\u66b4\u9732\u5f88\u591abug\u3002<\/li>\n<li>\u5927\u578b\u591a\u6a21\u5757\u7684\u9879\u76ee\uff0c\u4e00\u5b9a\u8981\u5199\u5355\u5143\u6d4b\u8bd5\uff0c\u4e0d\u7136\u51fa\u4e86bug\u65e0\u6cd5\u5206\u5757\u5b9a\u4f4d\u95ee\u9898\u3002<\/li>\n<li>\u5343\u4e07\u4e0d\u8981\u628aIO\u8fc7\u7a0b\u653e\u5728\u9501\u7684\u8303\u56f4\u91cc\uff0c\u6781\u5927\u7684\u5f71\u54cd\u6027\u80fd\uff01<\/li>\n<\/ul>\n<p>\u6587 \/ \u9152\u7c73<\/p>\n<p>\u5173\u6ce8\u5f97\u7269\u6280\u672f\uff0c\u6bcf\u5468\u66f4\u65b0\u6280\u672f\u5e72\u8d27<\/p>\n<p>\u8981\u662f\u89c9\u5f97\u6587\u7ae0\u5bf9\u4f60\u6709\u5e2e\u52a9\u7684\u8bdd\uff0c\u6b22\u8fce\u8bc4\u8bba\u8f6c\u53d1\u70b9\u8d5e\uff5e<\/p>\n<p>\u672a\u7ecf\u5f97\u7269\u6280\u672f\u8bb8\u53ef\u4e25\u7981\u8f6c\u8f7d\uff0c\u5426\u5219\u4f9d\u6cd5\u8ffd\u7a76\u6cd5\u5f8b\u8d23\u4efb\u3002<\/p>\n<p><a href=\"https:\/\/segmentfault.com\/a\/1190000046184275\">https:\/\/segmentfault.com\/a\/1190000046184275<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4e00\u3001\u5f15 \u8a00 LSM-Tree\uff08Log-Structured Merge Tree\uff09\u662f\u4e00\u79cd\u9ad8\u6548\u7684\u952e\u503c\u5b58\u50a8\u6570\u636e\u7ed3\u6784 [&hellip;]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-10020665","post","type-post","status-publish","format-standard","hentry","category-share"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10020665","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10020665"}],"version-history":[{"count":0,"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10020665\/revisions"}],"wp:attachment":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10020665"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10020665"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10020665"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}