Crash recovery — scan or hint

1def rebuild_keydir(data_dir):
2    keydir = {}  # empty — RAM is gone
3    files = sorted(data_dir.list('*.data'))
4    for f in files:
5        hint = data_dir.path(f.id + '.hint')
6        if hint.exists():
7            entries = read_hints(hint)        # metadata only
8        else:
9            entries = scan_data_file(f)       # full crawl
10        for e in entries:
11            # later tstamp wins on overwrite
12            if e.key not in keydir or e.tstamp > keydir[e.key].tstamp:
13                keydir[e.key] = (f.id, e.vsz, e.vpos, e.tstamp)
14    return keydir

1def scan_data_file(f):
2    pos = 0
3    while pos < f.size:
4        header = f.pread(pos, HEADER_SIZE)
5        crc, tstamp, ksz, vsz = unpack(header)
6        kv = f.pread(pos + HEADER_SIZE, ksz + vsz)
7        if crc32(header[4:] + kv) != crc:
8            f.truncate(pos)               # drop torn tail
9            return                        # stop, log ends here
10        key = kv[:ksz]
11        vpos = pos + HEADER_SIZE + ksz
12        yield Entry(key, tstamp, vsz, vpos)
13        pos += HEADER_SIZE + ksz + vsz

1# Data record — written by every put() to the active file:
2data_record = struct(
3    crc:    u32,    # checksum over (tstamp..value)
4    tstamp: u64,
5    ksz:    u32,
6    vsz:    u32,
7    key:    bytes[ksz],
8    value:  bytes[vsz],   # the value bytes themselves
9)
10 
11# Hint record — written by merge alongside each merged data file:
12hint_record = struct(
13    tstamp: u64,
14    ksz:    u32,
15    vsz:    u32,
16    vpos:   u64,    # where the value lives in the .data file
17    key:    bytes[ksz],
18    # no value bytes — that is the entire point
19)