从零实现Bitcask存储引擎：日志结构哈希表、Hint文件与崩溃恢复
在上一篇文章中，我们从零实现了一个HNSW向量索引，覆盖了分层图结构、贪婪搜索与启发式邻居选择。那篇文章聚焦的是高维空间的近似最近邻检索。这一次我们回到存储引擎的领域，目标是一个完整的Bitcask存储模型。
LSM-Tree和B-Tree是存储引擎领域最常被讨论的两种结构。LSM-Tree通过将随机写转化为顺序写来优化写入吞吐，B-Tree通过原地更新和平衡树结构优化读取延迟。但还有一种结构在工业界被广泛使用却很少被讨论：Bitcask。
Bitcask是Riak的默认存储后端，它的设计极其简单：所有写入追加到一个日志文件，内存中维护一个键到文件位置的哈希表。读取时先查哈希表定位文件偏移，再读取对应位置的值。写入时只做追加，不做原地修改。删除时写入一个墓碑标记。这个简单的设计带来了极高的写入吞吐和可预测的读取延迟。
但Bitcask也有代价。所有键的索引必须驻留内存，这限制了单机可存储的键数量。日志文件会持续增长，需要定期合并（Compaction）来回收空间。崩溃后需要重建索引，启动时间与日志大小成正比——直到Hint文件的引入解决了这个问题。
本文用纯前端JavaScript从零实现一个完整的Bitcask存储引擎，不依赖任何库。完整链路是：数据文件格式 → 内存键目录 → 写入路径 → 读取路径 → 删除与墓碑 → 合并压缩 → Hint文件加速启动 → 崩溃恢复。最后会讨论Bitcask与LSM-Tree、B-Tree的适用场景差异。
一、Bitcask的核心设计
Bitcask的数据模型可以概括为一句话：日志结构哈希表。
它结合了两种技术的优点。日志结构（Log-Structured）来自LSM-Tree——所有写入顺序追加到文件末尾，充分利用顺序I/O的高吞吐。哈希表（Hash Table）来自传统键值存储——内存中的哈希索引提供O(1)的键查找。
数据文件（Data File）是Bitcask的唯一持久化结构。每个写入操作对应一条记录，追加到当前活跃数据文件的末尾。记录包含四个字段：键、值、时间戳、标志位。标志位区分普通写入和墓碑（删除标记）。
内存中维护一个键目录（Keydir），将每个键映射到其最新值在数据文件中的位置。键目录的结构是Map<key, {fileId, offset, size, timestamp}>。读取时先查键目录，得到文件位置，然后从对应位置读取值。
这个设计的关键约束是：所有键必须能放入内存。对于单机存储数百万到数千万个键的场景，这个约束是可以接受的。如果需要存储数十亿个键，Bitcask就不适合了，应该选择LSM-Tree或B-Tree。
二、数据文件格式
数据文件由一系列变长记录组成。每条记录的结构如下：
javascript
// 记录格式（字节布局）：
// [keySize: 4字节][valueSize: 4字节][timestamp: 8字节][flags: 1字节][key: keySize字节][value: valueSize字节]
//
// flags: 0x00 = 普通写入, 0x01 = 墓碑（删除）
class Record {
constructor(key, value, timestamp, flags = 0) {
this.key = key;
this.value = value;
this.timestamp = timestamp;
this.flags = flags;
}
// 计算记录的总字节大小
get size() {
const keyBytes = Buffer.byteLength(this.key, 'utf8');
const valueBytes = this.value ? Buffer.byteLength(this.value, 'utf8') : 0;
// 4 + 4 + 8 + 1 + keySize + valueSize
return 17 + keyBytes + valueBytes;
}
// 序列化为 Buffer
serialize() {
const keyBytes = Buffer.byteLength(this.key, 'utf8');
const valueBytes = this.value ? Buffer.byteLength(this.value, 'utf8') : 0;
const buf = Buffer.alloc(17 + keyBytes + valueBytes);
let offset = 0;
buf.writeUInt32BE(keyBytes, offset); offset += 4;
buf.writeUInt32BE(valueBytes, offset); offset += 4;
buf.writeBigUInt64BE(BigInt(this.timestamp), offset); offset += 8;
buf.writeUInt8(this.flags, offset); offset += 1;
buf.write(this.key, offset, 'utf8'); offset += keyBytes;
if (this.value) {
buf.write(this.value, offset, 'utf8');
}
return buf;
}
// 从 Buffer 反序列化
static deserialize(buf, offset = 0) {
const keySize = buf.readUInt32BE(offset); offset += 4;
const valueSize = buf.readUInt32BE(offset); offset += 4;
const timestamp = Number(buf.readBigUInt64BE(offset)); offset += 8;
const flags = buf.readUInt8(offset); offset += 1;
const key = buf.toString('utf8', offset, offset + keySize); offset += keySize;
const value = valueSize > 0
? buf.toString('utf8', offset, offset + valueSize)
: null;
return {
record: new Record(key, value, timestamp, flags),
bytesRead: 17 + keySize + valueSize
};
}
}
在浏览器环境中，没有Node.js的Buffer，可以用DataView和TextEncoder/TextDecoder替代。序列化格式的设计有一个关键权衡：固定长度的头部（17字节）让反序列化可以快速定位字段，变长的键和值放在后面。如果键的长度是固定的，可以进一步优化头部大小。
三、内存键目录
键目录是Bitcask的核心索引结构。它不存储值本身，只存储值的位置信息。
javascript
class KeyDir {
constructor() {
this.map = new Map(); // key -> { fileId, offset, size, timestamp }
}
// 设置键的位置
set(key, fileId, offset, size, timestamp) {
this.map.set(key, { fileId, offset, size, timestamp });
}
// 获取键的位置
get(key) {
return this.map.get(key);
}
// 删除键
delete(key) {
return this.map.delete(key);
}
// 检查键是否存在
has(key) {
return this.map.has(key);
}
// 获取所有键
keys() {
return [...this.map.keys()];
}
get size() {
return this.map.size;
}
}
键目录的内存占用取决于键的数量和键的平均长度。假设有1000万个键，平均键长32字节，每个键目录条目的开销约64字节（键字符串+位置对象），总内存约640MB。这是Bitcask的单机容量上限——如果键目录超过可用内存，性能会急剧下降。
四、数据文件管理
Bitcask维护一组数据文件，每个文件有递增的ID。当前活跃文件（Active File）接收所有写入，已关闭文件（Closed File）只读。当活跃文件达到大小阈值时，创建新的活跃文件，旧的转为只读。
javascript
class DataFileManager {
constructor(directory, options = {}) {
this.directory = directory;
this.maxFileSize = options.maxFileSize || 64 * 1024 * 1024; // 64MB
this.files = new Map(); // fileId -> { fd, size, readonly }
this.activeFileId = 0;
this.activeFileSize = 0;
}
// 初始化：扫描目录，加载所有数据文件
async init() {
// 在浏览器中，这里会用 IndexedDB 或 OPFS 扫描文件
// 简化实现：用内存 Map 模拟文件系统
const fileIds = [...this.files.keys()].sort((a, b) => a - b);
if (fileIds.length === 0) {
this.activeFileId = 0;
this.activeFileSize = 0;
} else {
this.activeFileId = fileIds[fileIds.length - 1];
this.activeFileSize = this.files.get(this.activeFileId).size;
}
}
// 追加数据到活跃文件
async append(buffer) {
// 检查是否需要滚动到新文件
if (this.activeFileSize + buffer.length > this.maxFileSize) {
await this.rollover();
}
const fileId = this.activeFileId;
const offset = this.activeFileSize;
// 写入数据
if (!this.files.has(fileId)) {
this.files.set(fileId, { fd: [], size: 0, readonly: false });
}
this.files.get(fileId).fd.push(buffer);
this.files.get(fileId).size += buffer.length;
this.activeFileSize += buffer.length;
return { fileId, offset, size: buffer.length };
}
// 滚动到新文件
async rollover() {
// 标记当前文件为只读
if (this.files.has(this.activeFileId)) {
this.files.get(this.activeFileId).readonly = true;
}
// 创建新文件
this.activeFileId++;
this.activeFileSize = 0;
this.files.set(this.activeFileId, { fd: [], size: 0, readonly: false });
}
// 从指定位置读取
async read(fileId, offset, size) {
const file = this.files.get(fileId);
if (!file) throw new Error(`文件 ${fileId} 不存在`);
// 从模拟的文件数据中提取
const allData = Buffer.concat(file.fd);
return allData.slice(offset, offset + size);
}
// 获取所有文件ID
getFileIds() {
return [...this.files.keys()].sort((a, b) => a - b);
}
}
在浏览器环境中，数据文件的持久化可以用IndexedDB或Origin Private File System（OPFS）。OPFS提供了类似文件系统的API，支持随机读写，比IndexedDB更适合存储引擎场景。
五、写入路径
写入路径是Bitcask最简单的部分：序列化记录、追加到数据文件、更新键目录。
javascript
class BitcaskEngine {
constructor(options = {}) {
this.keyDir = new KeyDir();
this.fileManager = new DataFileManager(options.directory, options);
this.writeLock = Promise.resolve(); // 串行化写入
}
async open() {
await this.fileManager.init();
await this.rebuildKeyDir();
}
// 写入键值对
async put(key, value) {
return this._enqueueWrite(async () => {
const record = new Record(key, value, Date.now(), 0x00);
const buf = record.serialize();
// 1. 追加到数据文件
const { fileId, offset, size } = await this.fileManager.append(buf);
// 2. 更新键目录
this.keyDir.set(key, fileId, offset, size, record.timestamp);
return { key, fileId, offset };
});
}
// 删除键（写入墓碑）
async delete(key) {
return this._enqueueWrite(async () => {
const record = new Record(key, null, Date.now(), 0x01);
const buf = record.serialize();
const { fileId, offset, size } = await this.fileManager.append(buf);
// 从键目录中删除（墓碑不会进入键目录）
this.keyDir.delete(key);
return { key, fileId, offset };
});
}
// 串行化写入，避免并发写入导致的数据文件交错
async _enqueueWrite(fn) {
const previous = this.writeLock;
let resolve;
this.writeLock = new Promise(r => { resolve = r; });
try {
await previous;
const result = await fn();
resolve();
return result;
} catch (err) {
resolve();
throw err;
}
}
}
写入路径的关键设计是串行化。虽然JavaScript是单线程的，但异步操作（如文件写入）会交错执行。如果两个put操作同时执行，它们的记录可能交错写入同一个文件，导致键目录指向错误的偏移。writeLock保证同一时刻只有一个写入操作在执行。
六、读取路径
读取路径分两步：查键目录定位位置，从数据文件读取值。
javascript
class BitcaskEngine {
// ... 之前的代码
async get(key) {
// 1. 查键目录
const entry = this.keyDir.get(key);
if (!entry) return null;
// 2. 从数据文件读取
const buf = await this.fileManager.read(entry.fileId, entry.offset, entry.size);
// 3. 反序列化
const { record } = Record.deserialize(buf);
// 4. 检查是否是墓碑（理论上不会出现，因为墓碑不会进入键目录）
if (record.flags === 0x01) return null;
return record.value;
}
async has(key) {
return this.keyDir.has(key);
}
}
读取路径的复杂度是O(1)的哈希查找加上一次磁盘I/O。磁盘I/O的延迟取决于文件是否在操作系统的页缓存中。对于热数据，读取延迟在微秒级；对于冷数据，延迟在毫秒级。
七、崩溃恢复与键目录重建
崩溃恢复是Bitcask的关键环节。系统重启后，内存中的键目录丢失，需要从数据文件重建。重建过程是：遍历所有数据文件，按顺序读取每条记录，用最新的记录更新键目录。
javascript
class BitcaskEngine {
// ... 之前的代码
// 从数据文件重建键目录
async rebuildKeyDir() {
this.keyDir = new KeyDir();
const fileIds = this.fileManager.getFileIds();
let totalRecords = 0;
for (const fileId of fileIds) {
const file = this.fileManager.files.get(fileId);
const allData = Buffer.concat(file.fd);
let offset = 0;
while (offset < allData.length) {
try {
const { record, bytesRead } = Record.deserialize(allData, offset);
if (record.flags === 0x01) {
// 墓碑：从键目录删除
this.keyDir.delete(record.key);
} else {
// 普通记录：更新键目录
this.keyDir.set(
record.key,
fileId,
offset,
bytesRead,
record.timestamp
);
}
offset += bytesRead;
totalRecords++;
} catch (err) {
// 记录不完整（崩溃时写入了一半），停止读取该文件
console.warn(`文件 ${fileId} 在偏移 ${offset} 处损坏，停止读取`);
break;
}
}
}
console.log(`键目录重建完成: ${this.keyDir.size} 个键, 共读取 ${totalRecords} 条记录`);
}
}
重建过程有一个重要的细节：只读取每个键的最新版本。由于数据文件是追加写的，同一个键可能有多个版本分布在不同位置。重建时按时间顺序遍历，后出现的版本覆盖先出现的版本。墓碑记录会从键目录中删除对应的键。
重建的时间复杂度是O(N)，N是数据文件中的总记录数。对于一个包含1000万条记录的数据文件，重建可能需要数秒到数十秒。这在生产环境中是不可接受的——服务重启后不能等待几十秒才能响应请求。
八、Hint文件：加速启动
Hint文件是Bitcask解决启动慢问题的方案。它在数据文件关闭（或滚动）时生成一个辅助文件，记录每个键的最新位置。启动时只需要读取Hint文件，不需要遍历整个数据文件。
Hint文件的格式与数据文件类似，但只包含键和位置信息，不包含值。每个Hint记录是：[keySize][valueSize][timestamp][flags][key][fileId][offset]。
javascript
class HintFile {
constructor(fileId) {
this.fileId = fileId;
this.entries = [];
}
// 添加一条Hint记录
add(key, valueSize, timestamp, flags, offset) {
this.entries.push({ key, valueSize, timestamp, flags, offset });
}
// 序列化Hint文件
serialize() {
const buffers = [];
for (const entry of this.entries) {
const keyBytes = Buffer.byteLength(entry.key, 'utf8');
const buf = Buffer.alloc(4 + 4 + 8 + 1 + keyBytes + 4 + 4);
let offset = 0;
buf.writeUInt32BE(keyBytes, offset); offset += 4;
buf.writeUInt32BE(entry.valueSize, offset); offset += 4;
buf.writeBigUInt64BE(BigInt(entry.timestamp), offset); offset += 8;
buf.writeUInt8(entry.flags, offset); offset += 1;
buf.write(entry.key, offset, 'utf8'); offset += keyBytes;
buf.writeUInt32BE(this.fileId, offset); offset += 4;
buf.writeUInt32BE(entry.offset, offset); offset += 4;
buffers.push(buf);
}
return Buffer.concat(buffers);
}
// 反序列化Hint文件
static deserialize(buf, fileId) {
const hint = new HintFile(fileId);
let offset = 0;
while (offset < buf.length) {
const keySize = buf.readUInt32BE(offset); offset += 4;
const valueSize = buf.readUInt32BE(offset); offset += 4;
const timestamp = Number(buf.readBigUInt64BE(offset)); offset += 8;
const flags = buf.readUInt8(offset); offset += 1;
const key = buf.toString('utf8', offset, offset + keySize); offset += keySize;
const dataFileId = buf.readUInt32BE(offset); offset += 4;
const dataOffset = buf.readUInt32BE(offset); offset += 4;
hint.entries.push({
key, valueSize, timestamp, flags, offset: dataOffset
});
}
return hint;
}
}
有了Hint文件后，启动流程变为：优先读取Hint文件重建键目录；如果Hint文件不存在（比如崩溃导致未生成），回退到全量遍历数据文件。这大幅缩短了正常关闭后的启动时间。
javascript
class BitcaskEngine {
// ... 之前的代码
async rebuildKeyDirWithHint() {
this.keyDir = new KeyDir();
const fileIds = this.fileManager.getFileIds();
for (const fileId of fileIds) {
const hint = await this.loadHintFile(fileId);
if (hint) {
// 从Hint文件加载
for (const entry of hint.entries) {
if (entry.flags === 0x01) {
this.keyDir.delete(entry.key);
} else {
this.keyDir.set(
entry.key, fileId, entry.offset,
17 + Buffer.byteLength(entry.key) + entry.valueSize,
entry.timestamp
);
}
}
} else {
// 没有Hint文件，回退到全量扫描
await this._rebuildFromDataFile(fileId);
}
}
}
async loadHintFile(fileId) {
// 在浏览器中，从 OPFS 或 IndexedDB 读取
try {
const hintData = await this.fileManager.readHintFile(fileId);
if (!hintData) return null;
return HintFile.deserialize(hintData, fileId);
} catch {
return null;
}
}
}
Hint文件在数据文件关闭时生成。当活跃文件滚动到新文件时，旧文件被标记为只读，同时生成对应的Hint文件。这保证了Hint文件始终与数据文件同步。
九、合并压缩
随着写入的进行，同一个键会在数据文件中留下多个版本。旧版本占用空间但不再被读取。合并压缩（Compaction）的目标是：将多个数据文件合并为一个，只保留每个键的最新版本。
javascript
class Compactor {
constructor(engine) {
this.engine = engine;
}
// 合并一组数据文件
async compact(fileIds) {
const engine = this.engine;
const merged = new Map(); // key -> { value, timestamp, flags }
// 1. 遍历所有文件，收集每个键的最新版本
for (const fileId of fileIds) {
const file = engine.fileManager.files.get(fileId);
if (!file) continue;
const allData = Buffer.concat(file.fd);
let offset = 0;
while (offset < allData.length) {
const { record, bytesRead } = Record.deserialize(allData, offset);
const existing = merged.get(record.key);
if (!existing || record.timestamp > existing.timestamp) {
merged.set(record.key, {
value: record.value,
timestamp: record.timestamp,
flags: record.flags
});
}
offset += bytesRead;
}
}
// 2. 创建新的合并文件
const newFileId = engine.fileManager.activeFileId + 1000; // 避免冲突
const hint = new HintFile(newFileId);
const newFileData = [];
for (const [key, entry] of merged) {
// 跳过墓碑（如果该键已被删除，且没有被重新创建）
if (entry.flags === 0x01) {
const keyDirEntry = engine.keyDir.get(key);
if (!keyDirEntry) continue; // 已删除且未重建
}
const record = new Record(key, entry.value, entry.timestamp, entry.flags);
const buf = record.serialize();
const offset = newFileData.reduce((sum, b) => sum + b.length, 0);
newFileData.push(buf);
if (entry.flags === 0x00) {
hint.add(key, Buffer.byteLength(entry.value || '', 'utf8'),
entry.timestamp, entry.flags, offset);
}
}
// 3. 持久化新文件和Hint文件
engine.fileManager.files.set(newFileId, {
fd: newFileData,
size: newFileData.reduce((sum, b) => sum + b.length, 0),
readonly: true
});
await engine.fileManager.writeHintFile(newFileId, hint.serialize());
// 4. 更新键目录，指向新文件
let offset = 0;
for (const [key, entry] of merged) {
if (entry.flags === 0x01) {
engine.keyDir.delete(key);
continue;
}
const record = new Record(key, entry.value, entry.timestamp, 0);
engine.keyDir.set(key, newFileId, offset, record.size, entry.timestamp);
offset += record.size;
}
// 5. 删除旧文件
for (const fileId of fileIds) {
engine.fileManager.files.delete(fileId);
await engine.fileManager.deleteHintFile(fileId);
}
console.log(`合并完成: ${fileIds.length} 个文件 -> 1 个文件, ${merged.size} 个键`);
return newFileId;
}
// 自动选择需要合并的文件
async autoCompact() {
const fileIds = this.engine.fileManager.getFileIds();
// 排除活跃文件
const candidates = fileIds.filter(id => id !== this.engine.fileManager.activeFileId);
// 策略：合并所有已关闭的文件
if (candidates.length >= 2) {
return this.compact(candidates);
}
return null;
}
}
合并压缩的策略有多种。最简单的是全量合并——合并所有已关闭文件。更精细的策略是分层合并（类似LSM-Tree），按文件大小或年龄分级，只合并大小相近的文件。对于Bitcask，全量合并通常就足够了，因为键目录已经包含了所有键的位置信息，合并只需要遍历一次所有文件。
十、完整测试与性能特征
把所有部分串联起来，测试一个完整的读写流程：
javascript
async function testBitcask() {
const engine = new BitcaskEngine({
directory: '/tmp/bitcask',
maxFileSize: 1024 * 1024 // 1MB，方便触发滚动
});
await engine.open();
// 写入测试
console.log('=== 写入测试 ===');
const writeStart = performance.now();
for (let i = 0; i < 10000; i++) {
await engine.put(`key_${i}`, `value_${i}`);
}
const writeTime = performance.now() - writeStart;
console.log(`写入 10000 条耗时: ${writeTime.toFixed(2)}ms`);
console.log(`平均: ${(writeTime / 10000).toFixed(3)}ms/条`);
console.log(`键目录大小: ${engine.keyDir.size}`);
// 读取测试
console.log('\n=== 读取测试 ===');
const readStart = performance.now();
let found = 0;
for (let i = 0; i < 10000; i++) {
const val = await engine.get(`key_${i}`);
if (val === `value_${i}`) found++;
}
const readTime = performance.now() - readStart;
console.log(`读取 10000 条耗时: ${readTime.toFixed(2)}ms`);
console.log(`平均: ${(readTime / 10000).toFixed(3)}ms/条`);
console.log(`正确读取: ${found}/10000`);
// 更新测试
console.log('\n=== 更新测试 ===');
for (let i = 0; i < 1000; i++) {
await engine.put(`key_${i}`, `updated_${i}`);
}
console.log(`更新后 key_0 = ${await engine.get('key_0')}`);
// 删除测试
console.log('\n=== 删除测试 ===');
await engine.delete('key_0');
console.log(`删除后 key_0 = ${await engine.get('key_0')}`);
// 合并压缩
console.log('\n=== 合并压缩 ===');
const compactor = new Compactor(engine);
await compactor.autoCompact();
console.log(`合并后键目录大小: ${engine.keyDir.size}`);
// 验证合并后数据仍然正确
let correct = 0;
for (let i = 0; i < 10000; i++) {
const val = await engine.get(`key_${i}`);
if (i < 1000) {
if (val === `updated_${i}`) correct++;
} else {
if (val === `value_${i}`) correct++;
}
}
console.log(`合并后验证: ${correct}/10000`);
}
testBitcask();
Bitcask的性能特征非常清晰。写入路径是O(1)的哈希表插入加上一次顺序追加，单条写入延迟在微秒级（不考虑磁盘I/O）。读取路径是O(1)的哈希查找加上一次随机读取，延迟取决于数据是否在页缓存中。合并压缩是后台操作，不影响在线读写。
Bitcask的局限性也很明确。键目录必须全部驻留内存，这限制了单机可存储的键数量。对于键数量在千万级以内的场景，Bitcask是极佳的选择。对于键数量在亿级以上的场景，应该考虑LSM-Tree（键目录可以部分存储在磁盘）或B-Tree（支持更大的键空间）。
十一、Bitcask与LSM-Tree、B-Tree的对比
维度 Bitcask LSM-Tree B-Tree
写入路径 追加日志 追加日志+后台合并 原地更新
读取路径 哈希表+一次I/O 多层查找+Bloom Filter 树查找
写入吞吐 极高 极高 中等
读取延迟 低（热数据） 中（需检查多层） 低（稳定）
内存占用 键目录驻留内存 索引部分驻留 索引部分驻留
键数量上限 受内存限制 亿级 十亿级
范围查询 不支持 支持 支持
实现复杂度 低 高 中
Bitcask不支持范围查询，因为键目录是哈希表，没有顺序结构。如果需要范围查询，需要在Bitcask之上构建额外的索引，或者选择LSM-Tree/B-Tree。
十二、总结
从数据文件格式到内存键目录，从写入路径到读取路径，从崩溃恢复到Hint文件，从合并压缩到性能测试——这个Bitcask存储引擎的核心代码不到500行，但覆盖了日志结构哈希表的全部关键机制。
Bitcask的设计哲学是极简主义。它不做原地更新，不建复杂的索引结构，不维护多层文件。它只做两件事：把写入追加到文件末尾，把键的位置记在内存里。这种简单性带来了可预测的性能和极低的实现复杂度。
理解了这套最小内核，再去看Riak的Bitcask实现、Datomic的存储层、或者各种嵌入式键值存储的源码，会发现它们在架构上遵循的是同一套思路——日志追加、内存索引、定期合并。差异只在工程细节：文件系统的选择、并发控制的粒度、合并策略的调度。Bitcask是这一切的起点。
- 点赞
- 收藏
- 关注作者
评论（0）