KV断线恢复：Write-Ahead Log、完整前缀与持久ACK

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练string KV、单writer、set/delete，文件系统提供正常fsync语义；进程崩溃模型为日志持久前缀，完整记录内容损坏另作错误。
• 二进制frame=4字节大端body长度+UTF-8 JSON操作+SHA256；JSON用于本训练记录格式，题目未给具体codec。最大record1MiB，sequence从1严格连续。
• 代码实际打开文件，不提供多进程锁；I/O失败后实例不得继续服务，必须关闭/重开recover。故障注入不证明所有硬件掉电/存储损坏场景。

解题路线

1. 写入操作先编码(sequence,op,key,value)，append/flush/fsync成功后才更新内存并返回成功。若先更新内存ACK再写日志，崩溃会丢已承诺写入。新建WAL还要fsync parent目录，确保文件名持久。
2. 恢复逐条读length/body/hash，完整校验后apply。尾部不足header/body/hash视未完成记录停止；完整记录hash错误、超预算length、非法op或sequence不连续报错，不当作可随意忽略的尾部。
3. 恢复得last_complete_offset后truncate残尾并fsync，再append；不截断会把新记录接在旧半条后面，使后续恢复混淆。重放set覆盖和delete幂等，但sequence防日志段重复拼接。
4. fsync成功后ACK丢失，用户不知道是否成功，可能重试；本地WAL持久化不等于客户端请求去重。生产需在同条持久事务保存request ID/结果，用稳定key避免重复非幂等操作。
5. 长日志用一致checkpoint：保存KV与last sequence，fsync数据、原子发布manifest并fsync目录，确认可恢复后才清理旧WAL。并发更新需snapshot/version边界，不能随便dump当前map再删日志。

手动走一遍

记录set a=1完整、set a=2只写一半，重启恢复a=1并截断尾部；后续set b=3可正常再恢复。日志完整但字节翻转，拒绝启动而非悄悄漏掉已ACK写；checksum检测损坏不是修复或授权。枚举每个字节cut，与独立完整frame边界状态比对，再用临时文件真实重开验证。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

import hashlib,json,os,struct
from pathlib import Path
MAX_RECORD=1_048_576

def encode(sequence,op,key,value=None):
    body=json.dumps([sequence,op,key,value],ensure_ascii=False,separators=(',',':')).encode('utf-8')
    if len(body)>MAX_RECORD:raise ValueError('record budget')
    return struct.pack('>I',len(body))+body+hashlib.sha256(body).digest()

def recover(data):
    values={};position=0;sequence=0
    while position<len(data):
        if len(data)-position<4:break
        length=struct.unpack('>I',data[position:position+4])[0]
        if length>MAX_RECORD:raise ValueError('invalid record length')
        end=position+4+length+32
        if end>len(data):break
        body=data[position+4:position+4+length];digest=data[position+4+length:end]
        if hashlib.sha256(body).digest()!=digest:raise ValueError('corrupt complete record')
        record=json.loads(body.decode('utf-8'))
        if not isinstance(record,list) or len(record)!=4:raise ValueError('record shape')
        seq,op,key,value=record
        if type(seq) is not int or seq!=sequence+1 or not isinstance(key,str) or op not in ('set','delete'):raise ValueError('sequence/op/key')
        if op=='set':
            if not isinstance(value,str):raise ValueError('string value')
            values[key]=value
        elif value is not None:raise ValueError('delete value')
        else:values.pop(key,None)
        sequence=seq;position=end
    return values,sequence,position

class KV:
    # One writer, existing durable parent directory, static file path.
    def __init__(self,path):
        self.path=Path(path);created=not self.path.exists();self.file=open(self.path,'a+b');self.file.seek(0);data=self.file.read()
        self.values,self.sequence,end=recover(data)
        self.file.truncate(end);self.file.flush();os.fsync(self.file.fileno());self.file.seek(0,2)
        if created:
            descriptor=os.open(self.path.parent,os.O_RDONLY)
            try:os.fsync(descriptor)
            finally:os.close(descriptor)
    def _write(self,op,key,value=None):
        if not isinstance(key,str) or (op=='set' and not isinstance(value,str)):raise ValueError('string key/value')
        blob=encode(self.sequence+1,op,key,value)
        # I/O failure makes this instance unusable; reopen/recover before retry.
        self.file.write(blob);self.file.flush();os.fsync(self.file.fileno())
        self.sequence+=1
        if op=='set':self.values[key]=value
        else:self.values.pop(key,None)
    def set(self,key,value):self._write('set',key,value)
    def delete(self,key):self._write('delete',key)
    def close(self):self.file.close()

复杂度

恢复O(日志bytes+操作数)时间，内存O(KV大小+完整data读取)，示例一次read整个日志不是流式恢复。写每条fsync延迟主导吞吐，group commit可提升但需在持久后批量ACK；checkpoint减少恢复时间。

易错点与追问

容易失分的边界

• 进程buffer flush不等于fsync。
• 恢复后未截断半条尾记录，新的append使日志不可读。
• 完整checksum坏记录当未完成tail忽略，可能静默丢已持久操作。

继续深挖

• 并发writer与group commit怎样保序、定义ACK和关闭状态？
• 多文件WAL轮转如何原子发布段序列并保留checkpoint可恢复性？