墓碑（Tombstone）

一、为什么需要墓碑#

一个 LSM 树存储引擎，数据按层级写入只追加的 SSTable。你不能原地修改或删除一条记录，SSTable 是不可变的。那删除一条数据怎么办？直接跳过不管的话，读取时还会找到旧值。

分布式数据库中，删除操作需要传播到所有副本。如果节点 A 删除了一条数据，节点 B 还没收到删除消息，B 仍然会返回旧值。更危险的是：如果节点 C 宕机期间发生了删除，C 恢复后可能把旧数据当作 “新发现” 重新传播到整个集群，已删除的数据死而复生。

墓碑给出的方案是：不直接删除数据，而是写入一条特殊的 “墓碑” 记录来覆盖原始数据。读取时检查墓碑标记，将已标记的条目视为已删除。后台压缩进程随后物理删除墓碑和被覆盖的数据，真正回收空间。

二、现实类比#

图书馆里贴了「已下架」贴纸但还在书架上的书。读者看到就知道不能借了，图书管理员在月度整理时统一收走下架的书。不需要每本书一决定下架就立刻跑去书架抽出来，标记和清理是两步独立的操作。

三、核心思想#

墓碑将删除操作分为快速路径（标记删除）和慢速路径（回收空间），两者解耦。写入墓碑是 O(1) 的追加操作，不影响写入性能。空间回收由后台压缩进程异步完成。

flowchart TD subgraph 写入路径 D["delete('B')"] --> L["追加墓碑标记"] end subgraph 读取路径 G["get('B')"] --> Q["查找"] Q --> F["找到: B = tomb"] F --> N["返回 NOT FOUND"] end subgraph 压缩 L --> C["后台压缩"] C --> R["物理删除墓碑 + 原始数据"] end

属性	值	说明
删除	O(1)	仅追加墓碑标记
空间回收	延迟	后台压缩
读开销	需检查墓碑	每次读取需判断是否被标记
一致性	墓碑必须传播到所有副本	才能安全移除

墓碑累积问题：如果压缩落后或删除率很高，墓碑会在各层级堆积。读取时必须逐层检查墓碑，范围扫描尤其受影响，1000 万个墓碑意味着扫描要读取 1000 万条记录，逐一评估，最后返回零结果。解决方案包括更积极地触发压缩、使用范围墓碑（RocksDB 的 DeleteRange）或独立索引。

四、变体与对比#

模式	与墓碑的关系	适用场景
LSM 树	LSM 树大量使用墓碑，压缩时清理	只追加的存储引擎
MVCC	MVCC 用墓碑标记旧版本以供垃圾回收	多版本并发控制
空闲链表	墓碑清理后，释放的槽位由空闲链表管理	固定大小槽位的回收
引用计数	引用计数确定何时可以安全回收被墓碑标记的对象	共享资源的延迟回收
LRU 缓存	分布式 LRU 缓存用墓碑标记已删除的条目	分布式缓存一致性

五、多语言实现#

1
package tombstone
2

3
import (
4
    "sync"
5
    "time"
6
)
7

8
// Entry 存储条目，支持墓碑标记
9
type Entry struct {
10
    Value     string
11
    Deleted   bool
12
    Timestamp int64
13
}
14

15
// TombstoneStore 带墓碑删除的键值存储
16
type TombstoneStore struct {
17
    mu              sync.RWMutex
18
    store           map[string]*Entry
19
    tombstoneCount  int
20
}
21

22
func NewTombstoneStore() *TombstoneStore {
23
    return &TombstoneStore{
24
        store: make(map[string]*Entry),
25
    }
26
}
27

28
// Put 写入键值对
29
func (s *TombstoneStore) Put(key, value string) {
30
    s.mu.Lock()
31
    defer s.mu.Unlock()
32
    s.store[key] = &Entry{
33
        Value:     value,
34
        Deleted:   false,
35
        Timestamp: time.Now().UnixMilli(),
36
    }
37
}
38

39
// Get 读取值，墓碑标记的条目视为不存在
40
func (s *TombstoneStore) Get(key string) (string, bool) {
41
    s.mu.RLock()
42
    defer s.mu.RUnlock()
43
    entry, ok := s.store[key]
44
    if !ok || entry.Deleted {
45
        return "", false
46
    }
47
    return entry.Value, true
48
}
49

50
// Delete 墓碑删除：标记而非物理删除
51
func (s *TombstoneStore) Delete(key string) bool {
52
    s.mu.Lock()
53
    defer s.mu.Unlock()
54
    entry, ok := s.store[key]
55
    if !ok || entry.Deleted {
56
        return false
57
    }
58
    entry.Deleted = true
59
    entry.Value = ""       // 释放值引用
60
    entry.Timestamp = time.Now().UnixMilli()
61
    s.tombstoneCount++
62
    return true
63
}
64

65
// Compact 压缩：物理删除过期的墓碑
66
func (s *TombstoneStore) Compact(maxAgeMs int64) int {
67
    s.mu.Lock()
68
    defer s.mu.Unlock()
69
    cutoff := time.Now().UnixMilli() - maxAgeMs
70
    removed := 0
71
    for key, entry := range s.store {
72
        if entry.Deleted && entry.Timestamp < cutoff {
73
            delete(s.store, key)
74
            removed++
75
            s.tombstoneCount--
76
        }
77
    }
78
    return removed
79
}
80

81
// Size 返回活跃条目数量（不含墓碑）
82
func (s *TombstoneStore) Size() int {
83
    s.mu.RLock()
84
    defer s.mu.RUnlock()
85
    count := 0
86
    for _, entry := range s.store {
87
        if !entry.Deleted {
88
            count++
89
        }
90
    }
91
    return count
92
}
93

94
// PendingTombstones 返回待压缩的墓碑数量
95
func (s *TombstoneStore) PendingTombstones() int {
96
    s.mu.RLock()
97
    defer s.mu.RUnlock()
98
    return s.tombstoneCount
99
}

1
interface Entry<V> {
2
  value: V | null;
3
  deleted: boolean;
4
  timestamp: number;
5
}
6

7
class TombstoneStore<V> {
8
  private store = new Map<string, Entry<V>>();
9
  private tombstoneCount = 0;
10

11
  // 写入键值对
12
  put(key: string, value: V): void {
13
    this.store.set(key, {
14
      value,
15
      deleted: false,
16
      timestamp: Date.now(),
17
    });
18
  }
19

20
  // 读取：墓碑标记的条目视为不存在
21
  get(key: string): V | undefined {
22
    const entry = this.store.get(key);
23
    if (!entry || entry.deleted) return undefined;
24
    return entry.value!;
25
  }
26

27
  // 墓碑删除：标记而非物理删除
28
  delete(key: string): boolean {
29
    const entry = this.store.get(key);
30
    if (!entry || entry.deleted) return false;
31
    entry.deleted = true;
32
    entry.value = null;
33
    entry.timestamp = Date.now();
34
    this.tombstoneCount++;
35
    return true;
36
  }
37

38
  // 压缩：物理删除过期的墓碑
39
  compact(maxAge: number): number {
40
    const cutoff = Date.now() - maxAge;
41
    let removed = 0;
42
    for (const [key, entry] of this.store) {
43
      if (entry.deleted && entry.timestamp < cutoff) {
44
        this.store.delete(key);
45
        removed++;
46
        this.tombstoneCount--;
47
      }
48
    }
49
    return removed;
50
  }
51

52
  get size(): number {
53
    let count = 0;
54
    for (const entry of this.store.values()) {
55
      if (!entry.deleted) count++;
56
    }
57
    return count;
58
  }
59

60
  get pendingTombstones(): number {
61
    return this.tombstoneCount;
62
  }
63
}

六、生产验证#

项目	源码位置	用途
LevelDB	dbformat.h#L39-L43	`kTypeDeletion`（值 0x0）在预写日志和 SSTable 中标记键已删除。压缩期间，当没有更早的快照引用该键时，墓碑被丢弃
Apache Cassandra	DeletionTime.java#L37-L99	`DeletionTime` 用 `markedForDeleteAt` 时间戳表示墓碑。墓碑在 `gc_grace_seconds`（默认 10 天）期间传播到各副本，之后压缩才清除
RocksDB	kTypeDeletion	`kTypeDeletion` 和 `kTypeSingleDeletion` 墓碑，可配置压缩触发器，支持 `DeleteRange` 范围墓碑

七、小结#

何时使用：

LSM 树存储引擎，LevelDB、RocksDB、Cassandra 追加墓碑，压缩负责清理
分布式数据库，墓碑在物理删除前将删除意图传播到所有副本
应用层软删除，标记记录为已删除但保留审计记录，保留期后清除
不可变/只追加日志，无法修改现有条目，删除需要影子记录
并发数据结构，标记节点已删除以避免并发读取期间不安全的指针操作

何时不用：

可原地修改的存储，哈希表、可变数组可以直接删除条目
内存受限系统，墓碑在压缩前占用空间，空间紧张时立即删除更好
无后台处理能力，压缩需要后台线程/进程，如不可用，墓碑会无限积累

八、参考资料#

LevelDB dbformat - LevelDB 墓碑类型定义和压缩逻辑
Cassandra DeletionTime - Cassandra 墓碑时间戳和 gc_grace_seconds 机制
RocksDB DeleteRange - RocksDB 范围墓碑优化，解决墓碑扫描问题
CockroachDB MVCC 墓碑 - CockroachDB 用于范围删除的 MVCC 墓碑，由后台任务 GC

目录

tsukimi 示例博客