340 lines
14 KiB
TypeScript
340 lines
14 KiB
TypeScript
/**
|
||
* AriaEngine SSTable Builder + Reader 单元测试
|
||
*/
|
||
import { SSTableBuilder } from '../../src/engine/aria/index/sstable_builder';
|
||
import { SSTableReader } from '../../src/engine/aria/index/sstable';
|
||
import type { SSTableMeta } from '../../src/engine/aria/types';
|
||
|
||
// ===================================================================
|
||
// SSTable Builder + Reader
|
||
// ===================================================================
|
||
describe('AriaEngine — SSTable Builder + Reader', () => {
|
||
const makeMeta = (data: Uint8Array): SSTableMeta => ({
|
||
id: 1, level: 0, minKey: '', maxKey: '\uffff',
|
||
blockCount: 1, totalSize: data.byteLength, bloomData: null,
|
||
});
|
||
|
||
it('构建单条目 SSTable 并精确读取', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
builder.add('key1', { name: 'Alice', age: 30 });
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
const result = reader.get('key1');
|
||
expect(result).not.toBeNull();
|
||
expect(result!.name).toBe('Alice');
|
||
expect(result!.age).toBe(30);
|
||
});
|
||
|
||
it('构建多条 SSTable 并全部读取', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
const items: [string, Record<string, unknown>][] = [];
|
||
for (let i = 0; i < 100; i++) {
|
||
const key = `user-${String(i).padStart(3, '0')}`;
|
||
const value = { idx: i, name: `User${i}` };
|
||
items.push([key, value]);
|
||
builder.add(key, value);
|
||
}
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
for (const [key, value] of items) {
|
||
const result = reader.get(key);
|
||
expect(result).not.toBeNull();
|
||
expect(result!.idx).toBe(value.idx);
|
||
}
|
||
});
|
||
|
||
it('get — 不存在的 key 返回 null', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
builder.add('a', { v: 1 });
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
expect(reader.get('nonexistent')).toBeNull();
|
||
});
|
||
|
||
it('rangeScan — 范围查询', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
for (let i = 0; i < 20; i++) {
|
||
builder.add(`k-${String(i).padStart(2, '0')}`, { v: i });
|
||
}
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
const results: [string, Record<string, unknown>][] = [];
|
||
reader.rangeScan('k-05', 'k-10', (k, v) => results.push([k, v]));
|
||
expect(results).toHaveLength(6);
|
||
expect(results[0][0]).toBe('k-05');
|
||
expect(results[results.length - 1][0]).toBe('k-10');
|
||
});
|
||
|
||
it('scanAll — 遍历所有条目', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
const count = 50;
|
||
for (let i = 0; i < count; i++) {
|
||
builder.add(`item-${i}`, { idx: i });
|
||
}
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
const items: [string, Record<string, unknown>][] = [];
|
||
reader.scanAll((k, v) => items.push([k, v]));
|
||
expect(items).toHaveLength(count);
|
||
});
|
||
|
||
// v0.6.1-fix(P0): 索引键是"块内最后一个 key"，locateBlockLE 排除尾 key 越界的
|
||
// 下一块会导致范围扫描漏读尾部数据（二级索引 5 万行查询丢 106~219 条）。
|
||
it('v0.6.1-fix — 范围扫描跨前缀边界不漏尾部数据', () => {
|
||
// 小块强制多块；t5 数据分散在多块中，最后一个 t5 块之后紧跟 t6 块（尾 key 越界）
|
||
const builder = new SSTableBuilder(120);
|
||
for (let i = 0; i < 30; i++) {
|
||
builder.add(`t5:k${String(i).padStart(5, '0')}`, { pk: `k${i}` });
|
||
}
|
||
for (let i = 0; i < 30; i++) {
|
||
builder.add(`t6:k${String(i).padStart(5, '0')}`, { pk: `k${i}` });
|
||
}
|
||
for (let i = 0; i < 30; i++) {
|
||
builder.add(`t7:k${String(i).padStart(5, '0')}`, { pk: `k${i}` });
|
||
}
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
const t5: [string, Record<string, unknown>][] = [];
|
||
reader.rangeScan('t5', 't5\uffff', (k, v) => t5.push([k, v]));
|
||
expect(t5).toHaveLength(30);
|
||
expect(t5[0][0]).toBe('t5:k00000');
|
||
expect(t5[t5.length - 1][0]).toBe('t5:k00029');
|
||
});
|
||
|
||
it('v0.6.1-fix — 范围扫描 endKey 恰在块尾（不越界不丢、不多扫错数据）', () => {
|
||
const builder = new SSTableBuilder(150);
|
||
for (let i = 0; i < 40; i++) {
|
||
builder.add(`p-${String(i).padStart(3, '0')}`, { v: i });
|
||
}
|
||
for (let i = 0; i < 20; i++) {
|
||
builder.add(`q-${String(i).padStart(3, '0')}`, { v: i });
|
||
}
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
// endKey 恰等于某条存在的 key：结果必须包含它且不含 p 之外的 key
|
||
const results: [string, Record<string, unknown>][] = [];
|
||
reader.rangeScan('p-000', 'p-039', (k, v) => results.push([k, v]));
|
||
expect(results).toHaveLength(40);
|
||
expect(results[39][0]).toBe('p-039');
|
||
});
|
||
|
||
it('v0.6.1-fix — 范围扫描 endKey 超出全部数据（返回全量）', () => {
|
||
const builder = new SSTableBuilder(100);
|
||
for (let i = 0; i < 25; i++) {
|
||
builder.add(`z-${String(i).padStart(3, '0')}`, { v: i });
|
||
}
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
const results: [string, Record<string, unknown>][] = [];
|
||
reader.rangeScan('z-000', '\uffff\uffff', (k, v) => results.push([k, v]));
|
||
expect(results).toHaveLength(25);
|
||
});
|
||
|
||
it('v0.6.1-fix — 多前缀数据 rangeScan 与 scanAll 结果一致', () => {
|
||
// 模拟索引混合写入：t0..t9 交叉 + 尾部跨块（flush 路径先排序再构建）
|
||
const items: [string, Record<string, unknown>][] = [];
|
||
for (let i = 0; i < 120; i++) {
|
||
const tag = `t${i % 10}`;
|
||
items.push([`${tag}:k${String(i).padStart(5, '0')}`, { pk: `k${i}` }]);
|
||
}
|
||
items.sort((a, b) => (a[0] < b[0] ? -1 : 1));
|
||
const builder = new SSTableBuilder(200);
|
||
for (const [k, v] of items) builder.add(k, v);
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
for (let t = 0; t < 10; t++) {
|
||
const keys: string[] = [];
|
||
reader.rangeScan(`t${t}`, `t${t}\uffff`, (k) => keys.push(k));
|
||
expect(keys).toHaveLength(12);
|
||
}
|
||
});
|
||
|
||
|
||
it('边界 — 空 SSTable 不抛异常', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
expect(reader.get('any')).toBeNull();
|
||
const results: [string, Record<string, unknown>][] = [];
|
||
reader.scanAll((k, v) => results.push([k, v]));
|
||
expect(results).toHaveLength(0);
|
||
});
|
||
|
||
it('带特殊字符的 key', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
// 必须按键排序添加（按 ASCII 排序：空格 < 短横 < 点号）
|
||
builder.add('key with space', { v: 3 });
|
||
builder.add('key-with-dash', { v: 1 });
|
||
builder.add('key.with.dot', { v: 2 });
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
expect(reader.get('key-with-dash')!.v).toBe(1);
|
||
expect(reader.get('key.with.dot')!.v).toBe(2);
|
||
expect(reader.get('key with space')!.v).toBe(3);
|
||
});
|
||
|
||
it('getEntryCount 返回正确条目数', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
builder.add('a', { v: 1 });
|
||
builder.add('b', { v: 2 });
|
||
builder.add('c', { v: 3 });
|
||
expect(builder.getEntryCount()).toBe(3);
|
||
});
|
||
});
|
||
|
||
// ===================================================================
|
||
// v0.4.5: 整文件 CRC-32 校验
|
||
// ===================================================================
|
||
describe('AriaEngine — SSTable CRC-32 校验', () => {
|
||
const makeMeta = (data: Uint8Array): SSTableMeta => ({
|
||
id: 1, level: 0, minKey: '', maxKey: '\uffff',
|
||
blockCount: 1, totalSize: data.byteLength, bloomData: null,
|
||
});
|
||
|
||
it('新构建的 SSTable 写入真实非零 checksum', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
builder.add('key1', { name: 'Alice' });
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
// footer 最后 4 字节为真实 checksum（非 0）
|
||
const stored = new DataView(sstableData.buffer, sstableData.byteOffset + sstableData.byteLength - 4, 4).getUint32(0, false);
|
||
expect(stored).not.toBe(0);
|
||
expect(reader.verifyChecksum()).toBe(true);
|
||
});
|
||
|
||
it('正常文件校验通过后可正常读取', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
for (let i = 0; i < 50; i++) builder.add(`k-${i}`, { v: i });
|
||
const { sstableData } = builder.build();
|
||
|
||
const reader = new SSTableReader(sstableData, makeMeta(sstableData));
|
||
expect(reader.verifyChecksum()).toBe(true);
|
||
expect(reader.get('k-30')).toEqual({ v: 30 });
|
||
});
|
||
|
||
it('数据块字节篡改 → 校验失败', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
for (let i = 0; i < 50; i++) builder.add(`k-${i}`, { v: i, pad: 'x'.repeat(64) });
|
||
const { sstableData } = builder.build();
|
||
|
||
// 篡改数据区中部一个字节（非 footer）
|
||
const corrupted = new Uint8Array(sstableData);
|
||
corrupted[Math.floor(corrupted.length / 2)] ^= 0xff;
|
||
|
||
const reader = new SSTableReader(corrupted, makeMeta(corrupted));
|
||
// 结构仍可解析（长度一致），但 CRC 必须失败
|
||
const stored = new DataView(corrupted.buffer, corrupted.byteOffset + corrupted.byteLength - 4, 4).getUint32(0, false);
|
||
expect(stored).not.toBe(0);
|
||
expect(reader.verifyChecksum()).toBe(false);
|
||
});
|
||
|
||
it('索引块字节篡改 → 校验失败', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
for (let i = 0; i < 20; i++) builder.add(`k-${i}`, { v: i });
|
||
const { sstableData } = builder.build();
|
||
|
||
// 从 footer 反推索引块位置并篡改
|
||
const footerOffset = sstableData.byteLength - 32;
|
||
const view = new DataView(sstableData.buffer, sstableData.byteOffset, sstableData.byteLength);
|
||
const indexOffset = view.getUint32(footerOffset, false);
|
||
const corrupted = new Uint8Array(sstableData);
|
||
corrupted[indexOffset + 8] ^= 0x01;
|
||
|
||
const reader = new SSTableReader(corrupted, makeMeta(corrupted));
|
||
expect(reader.verifyChecksum()).toBe(false);
|
||
});
|
||
|
||
it('旧版文件（checksum=0）跳过校验，保持兼容', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
builder.add('legacy', { v: 1 });
|
||
const { sstableData } = builder.build();
|
||
|
||
// 手工把 checksum 字段清零，模拟旧版写入产物
|
||
const legacy = new Uint8Array(sstableData);
|
||
new DataView(legacy.buffer).setUint32(legacy.byteLength - 4, 0, false);
|
||
|
||
const reader = new SSTableReader(legacy, makeMeta(legacy));
|
||
const stored = new DataView(legacy.buffer, legacy.byteOffset + legacy.byteLength - 4, 4).getUint32(0, false);
|
||
expect(stored).toBe(0);
|
||
expect(reader.verifyChecksum()).toBe(true); // 跳过校验
|
||
expect(reader.get('legacy')).toEqual({ v: 1 }); // 数据仍可读
|
||
});
|
||
|
||
it('v1 旧格式文件（magic SSTB，checksum=0）校验通过且可读', () => {
|
||
// 手工构造 v1 格式最小文件：单条记录 + 索引 + footer（magic SSTB, checksum 0）
|
||
const encoder = new TextEncoder();
|
||
const keyBytes = encoder.encode('old-key');
|
||
const valBytes = encoder.encode(JSON.stringify({ v: 42 }));
|
||
|
||
// data block: entryCount(u32)=1 + keyLen(u16)+key + valLen(u16)+val
|
||
const block = new ArrayBuffer(4 + 2 + keyBytes.length + 2 + valBytes.length);
|
||
const bv = new DataView(block);
|
||
let off = 0;
|
||
bv.setUint32(off, 1, false); off += 4;
|
||
bv.setUint16(off, keyBytes.length, false); off += 2;
|
||
new Uint8Array(block).set(keyBytes, off); off += keyBytes.length;
|
||
bv.setUint16(off, valBytes.length, false); off += 2;
|
||
new Uint8Array(block).set(valBytes, off); off += valBytes.length;
|
||
|
||
// index block: entryCount(u32)=1 + keyLen(u16)+key + blockOffset(u32) + blockSize(u32)
|
||
const blockSize = block.byteLength;
|
||
const idxKey = encoder.encode('old-key');
|
||
const idxBlock = new ArrayBuffer(4 + 2 + idxKey.length + 4 + 4);
|
||
const iv = new DataView(idxBlock);
|
||
let ioff = 0;
|
||
iv.setUint32(ioff, 1, false); ioff += 4;
|
||
iv.setUint16(ioff, idxKey.length, false); ioff += 2;
|
||
new Uint8Array(idxBlock).set(idxKey, ioff); ioff += idxKey.length;
|
||
iv.setUint32(ioff, 0, false); ioff += 4; // blockOffset = 0
|
||
iv.setUint32(ioff, blockSize, false); ioff += 4;
|
||
|
||
const footerSize = 32;
|
||
const total = block.byteLength + idxBlock.byteLength + footerSize;
|
||
const file = new ArrayBuffer(total);
|
||
const fv = new DataView(file);
|
||
new Uint8Array(file).set(new Uint8Array(block), 0);
|
||
new Uint8Array(file).set(new Uint8Array(idxBlock), block.byteLength);
|
||
const fo = block.byteLength + idxBlock.byteLength;
|
||
fv.setUint32(fo, block.byteLength, false); // index_offset
|
||
fv.setUint32(fo + 4, idxBlock.byteLength, false);
|
||
fv.setUint32(fo + 8, 0, false); // bloom_offset
|
||
fv.setUint32(fo + 12, 0, false); // bloom_size
|
||
fv.setUint32(fo + 16, 0, false); // bloom_hash_count
|
||
fv.setUint32(fo + 20, 1, false); // entry_count
|
||
fv.setUint32(fo + 24, 0x53535442, false); // magic "SSTB" (v1)
|
||
fv.setUint32(fo + 28, 0, false); // checksum = 0（旧版无校验）
|
||
|
||
const data = new Uint8Array(file);
|
||
const reader = new SSTableReader(data, makeMeta(data));
|
||
const stored = new DataView(data.buffer, data.byteOffset + data.byteLength - 4, 4).getUint32(0, false);
|
||
expect(stored).toBe(0);
|
||
expect(reader.verifyChecksum()).toBe(true);
|
||
expect(reader.get('old-key')).toEqual({ v: 42 });
|
||
});
|
||
|
||
it('footer checksum 字段自身篡改 → 校验失败', () => {
|
||
const builder = new SSTableBuilder(4096);
|
||
builder.add('a', { v: 1 });
|
||
const { sstableData } = builder.build();
|
||
|
||
const tampered = new Uint8Array(sstableData);
|
||
const view = new DataView(tampered.buffer);
|
||
view.setUint32(tampered.byteLength - 4, view.getUint32(tampered.byteLength - 4, false) ^ 0x000000ff, false);
|
||
|
||
const reader = new SSTableReader(tampered, makeMeta(tampered));
|
||
expect(reader.verifyChecksum()).toBe(false);
|
||
});
|
||
});
|