各位同仁，各位技术爱好者，大家好！
今天，我们将深入探讨一个在高性能存储系统，特别是基于SSD的系统中至关重要且常常被误解的概念：写放大（Write Amplification, WA）。我们不仅会剖析它的成因、影响，更会聚焦于如何通过Compaction（数据压缩/合并）策略来权衡SSD的寿命与性能。作为一名编程专家，我希望通过这次讲座，将理论与实践相结合，辅以代码示例，帮助大家建立起对这一复杂主题的深刻理解。
序章：闪存与固态硬盘的根基
在深入写放大之前，我们必须先了解SSD（固态硬盘）的物理特性。它与传统的HDD（机械硬盘）有着本质的区别。
NAND Flash 存储单元的特性
SSD的核心是NAND闪存芯片。NAND闪存的存储单元（Cell）有以下几个关键特性：
- 页（Page）是最小的读写单元： 通常为4KB、8KB或16KB。数据写入必须以页为单位进行。
- 块（Block）是最小的擦除单元： 一个块通常包含几十到几百个页（例如，128页，即512KB或1MB）。在写入任何数据到一个已经被写过的页之前，该页所属的整个块必须先被擦除。而擦除操作只能将整个块的所有位都置为1。
- 写入限制： NAND闪存单元的擦除-写入循环次数是有限的（P/E Cycles）。这直接决定了SSD的寿命。SLC（单层单元）闪存的寿命最长（约10万次P/E），MLC（多层单元）次之（约3000-10000次P/E），TLC（三层单元）更短（约500-3000次P/E），QLC（四层单元）最短（约100-1000次P/E）。
闪存转换层（Flash Translation Layer, FTL）
为了模拟传统硬盘的块设备接口，并隐藏NAND闪存的复杂性（如擦除前写入、坏块管理、磨损均衡等），SSD内部实现了一个复杂的软件层，称为FTL。
FTL的核心功能是：
- 逻辑地址到物理地址的映射： 操作系统请求写入一个逻辑地址的数据，FTL会将这个逻辑地址映射到一个可用的物理页。
- 磨损均衡（Wear Leveling）： 确保所有闪存块被擦写的次数大致相同，从而延长SSD寿命。
- 垃圾回收（Garbage Collection, GC）： 这是导致写放大的主要因素之一。
当一个逻辑页的数据被更新时，FTL并不会直接在原物理页上修改。相反，它会将新数据写入到一个新的空闲物理页，然后更新逻辑地址到物理地址的映射表，并将旧的物理页标记为“无效”（Stale）。由于闪存的“擦除前写入”特性，这些被标记为无效的页并不能立即回收。只有当一个块中所有页都被标记为无效，或者有效页比例低于某个阈值时，FTL才会执行垃圾回收。
垃圾回收（Garbage Collection, GC）
GC过程大致如下：
- 选择一个“受害者”块（Victim Block）： 通常是包含最多无效页的块，以最大化回收效率。
- 拷贝有效页： 将“受害者”块中所有仍然有效的页读取出来。
- 重新写入有效页： 将这些有效页写入到新的空闲块中。这一步就是写放大的直接来源，因为这些数据并没有被应用程序更新，但却被SSD内部重新写入了。
- 擦除“受害者”块： 将整个“受害者”块擦除，使其成为一个全新的空闲块，可用于后续写入。
这个过程中，应用程序只进行了一次逻辑写入，但SSD内部可能进行了多次物理写入（原始数据写入 + GC过程中有效数据的重新写入）。
第一章：写放大（Write Amplification, WA）的深层剖析
什么是写放大？
写放大（Write Amplification, WA）是指应用程序向SSD写入的数据量与SSD控制器实际向NAND闪存芯片写入的数据量之比。
WA = 实际写入NAND闪存的数据总量 / 应用程序逻辑写入的数据总量
例如，如果你的应用程序写入了1GB数据，但SSD控制器最终向NAND闪存写入了4GB数据，那么写放大系数就是4。
写放大的成因
写放大是一个综合性的指标，受到多种因素的影响，这些因素可以分为SSD内部因素和应用层因素。
1. SSD内部因素（FTL和GC）
这是最直接的WA来源，我们在序章中已经提及。
- 擦除前写入： 每次数据更新，旧数据页变为无效，新数据写入新页。旧数据页所在的块必须等到GC才能被擦除和回收。
- 垃圾回收（GC）： 为了回收空间，FTL必须将受害者块中的有效数据拷贝到新的块中。这些被拷贝的数据并非应用程序的“新”写入，但却增加了物理写入量。
代码示例：模拟SSD控制器中的垃圾回收引起的写放大
我们来构建一个简化的SSD控制器模型，模拟页写入、块擦除和垃圾回收过程，并计算写放大。
import random
import collections
# 定义SSD的物理特性
PAGE_SIZE_KB = 4 # 页面大小 (KB)
PAGES_PER_BLOCK = 16 # 每个块包含的页面数
BLOCK_SIZE_KB = PAGE_SIZE_KB * PAGES_PER_BLOCK # 块大小 (KB)
TOTAL_BLOCKS = 100 # SSD总块数
class Page:
"""模拟一个数据页"""
def __init__(self, logical_id, data_content=None):
self.logical_id = logical_id
self.data_content = data_content or f"Data for LPN {logical_id}"
self.is_valid = True # 标记页是否有效
self.physical_address = None # (block_id, page_offset)
def __repr__(self):
return f"Page(LPN={self.logical_id}, Valid={self.is_valid})"
class Block:
"""模拟一个NAND闪存块"""
def __init__(self, block_id):
self.block_id = block_id
self.pages = [None] * PAGES_PER_BLOCK # 存储Page对象
self.valid_page_count = 0
self.next_write_offset = 0 # 下一个可写入的页偏移
self.erasure_count = 0 # 擦除次数，用于磨损均衡统计
def write_page(self, page_obj):
"""将一个页写入块中"""
if self.next_write_offset >= PAGES_PER_BLOCK:
raise Exception(f"Block {self.block_id} is full.")
page_obj.physical_address = (self.block_id, self.next_write_offset)
self.pages[self.next_write_offset] = page_obj
self.valid_page_count += 1
self.next_write_offset += 1
return True
def invalidate_page(self, page_offset):
"""将块中的一个页标记为无效"""
if self.pages[page_offset] and self.pages[page_offset].is_valid:
self.pages[page_offset].is_valid = False
self.valid_page_count -= 1
return True
return False
def is_full(self):
return self.next_write_offset >= PAGES_PER_BLOCK
def get_valid_page_ratio(self):
return self.valid_page_count / PAGES_PER_BLOCK
def erase(self):
"""擦除整个块"""
self.pages = [None] * PAGES_PER_BLOCK
self.valid_page_count = 0
self.next_write_offset = 0
self.erasure_count += 1
# print(f"--- Block {self.block_id} erased. Erasure count: {self.erasure_count}")
class SSDController:
"""模拟SSD控制器，包含FTL和GC逻辑"""
def __init__(self, total_blocks=TOTAL_BLOCKS, over_provisioning_ratio=0.07):
self.blocks = [Block(i) for i in range(total_blocks)]
self.logical_to_physical_map = {} # LPN -> (block_id, page_offset)
self.free_blocks = collections.deque(range(total_blocks)) # 空闲块队列
# 模拟预留空间 (Over-provisioning)
self.op_blocks = int(total_blocks * over_provisioning_ratio)
if self.op_blocks > 0:
for _ in range(self.op_blocks):
self.free_blocks.pop() # 预留块不给用户使用，但可用于GC
self.active_block_id = self._get_new_active_block()
self.total_writes_to_nand = 0 # 实际写入NAND的总页数
self.total_logical_writes = 0 # 应用程序逻辑写入的总页数 (不含GC拷贝)
print(f"SSD initialized with {TOTAL_BLOCKS} blocks, {self.op_blocks} blocks for over-provisioning.")
print(f"Usable blocks: {TOTAL_BLOCKS - self.op_blocks}")
def _get_new_active_block(self):
"""获取一个新的活动块用于写入"""
if not self.free_blocks:
# 如果没有空闲块，则必须执行GC
if not self.garbage_collect():
raise Exception("CRITICAL: No free blocks and GC failed to free any!")
new_block_id = self.free_blocks.popleft()
return new_block_id
def write_logical_page(self, logical_page_id, data_content=None, is_gc_copy=False):
"""
模拟应用程序写入一个逻辑页数据。
is_gc_copy: 标记是否为GC过程中拷贝的页，不计入total_logical_writes。
"""
if not is_gc_copy:
self.total_logical_writes += 1 # 仅统计用户发起的逻辑写入
new_page = Page(logical_page_id, data_content)
# 1. 查找并使旧物理页无效
if logical_page_id in self.logical_to_physical_map:
old_block_id, old_page_offset = self.logical_to_physical_map[logical_page_id]
self.blocks[old_block_id].invalidate_page(old_page_offset)
# 2. 写入新数据到活动块
current_active_block = self.blocks[self.active_block_id]
if current_active_block.is_full():
# 如果活动块已满，需要切换到新块，并可能触发GC
self.active_block_id = self._get_new_active_block()
current_active_block = self.blocks[self.active_block_id]
current_active_block.write_page(new_page)
self.logical_to_physical_map[logical_page_id] = new_page.physical_address
self.total_writes_to_nand += 1 # 每次物理写入都计数
def garbage_collect(self, victim_selection_strategy="most_stale"):
"""
执行垃圾回收，选择一个受害者块，拷贝有效页，然后擦除。
返回True如果成功回收，否则False。
"""
victim_block = None
if victim_selection_strategy == "most_stale":
# 策略1: 选择有效页最少的块 (即stale data最多的块)
min_valid_pages = PAGES_PER_BLOCK + 1
for block in self.blocks:
if block.block_id == self.active_block_id:
continue # 不对当前写入的活动块进行GC
# 只考虑已满的块进行GC
if block.is_full() and block.valid_page_count < min_valid_pages:
victim_block = block
min_valid_pages = block.valid_page_count
# 如果没有找到合适的受害者块，或者受害者块是空的，则无法进行GC
if not victim_block or victim_block.valid_page_count == 0:
# print("No suitable victim block found for GC or victim is empty.")
return False
# print(f"--- Starting GC for Block {victim_block.block_id} (Valid pages: {victim_block.valid_page_count})")
# 拷贝有效页
pages_to_copy = []
for page in victim_block.pages:
if page and page.is_valid:
pages_to_copy.append(page)
# 模拟将有效页重新写入到新的位置 (这会增加total_writes_to_nand)
for page_to_copy in pages_to_copy:
# 注意: 这里使用is_gc_copy=True，表示这些写入不是用户发起的逻辑写入
self.write_logical_page(page_to_copy.logical_id, page_to_copy.data_content, is_gc_copy=True)
# 擦除受害者块
victim_block.erase()
self.free_blocks.append(victim_block.block_id) # 将擦除后的块加入空闲队列
# print(f"--- GC: Block {victim_block.block_id} erased. Copied {len(pages_to_copy)} valid pages.")
return True
def calculate_wa(self):
"""计算写放大系数"""
if self.total_logical_writes == 0:
return 1.0 # 如果没有逻辑写入，假设WA为1
return self.total_writes_to_nand / self.total_logical_writes
def get_free_blocks_count(self):
return len(self.free_blocks)
def get_valid_pages_in_blocks(self):
return sum(block.valid_page_count for block in self.blocks)
# --- 模拟WA的场景 ---
print("--- SSD Write Amplification Simulation ---")
ssd = SSDController(total_blocks=TOTAL_BLOCKS, over_provisioning_ratio=0.1) # 10% OP
num_initial_writes = (TOTAL_BLOCKS - ssd.op_blocks) * PAGES_PER_BLOCK # 填充可用空间
num_overwrites = num_initial_writes // 2 # 覆盖一半的数据
num_churn_writes = num_initial_writes * 2 # 大量数据更新和GC触发
print(f"nPhase 1: Initial writes ({num_initial_writes} pages)")
for i in range(num_initial_writes):
ssd.write_logical_page(i) # 写入新的逻辑页
print(f"Logical writes: {ssd.total_logical_writes}, Physical writes: {ssd.total_writes_to_nand}, WA: {ssd.calculate_wa():.2f}")
print(f"Free blocks: {ssd.get_free_blocks_count()}")
print(f"nPhase 2: Overwrites ({num_overwrites} pages) - Triggers invalidations")
for i in range(num_overwrites):
logical_id_to_overwrite = random.randint(0, num_initial_writes - 1)
ssd.write_logical_page(logical_id_to_overwrite, f"New data for {logical_id_to_overwrite}")
print(f"Logical writes: {ssd.total_logical_writes}, Physical writes: {ssd.total_writes_to_nand}, WA: {ssd.calculate_wa():.2f}")
print(f"Free blocks: {ssd.get_free_blocks_count()}")
print(f"nPhase 3: High data churn ({num_churn_writes} pages) - Forces GC")
for i in range(num_churn_writes):
logical_id_to_write = random.randint(0, num_initial_writes + num_overwrites - 1) # 写入现有或新页
ssd.write_logical_page(logical_id_to_write, f"Churn data {i}")
# 在实际SSD中，GC是持续在后台运行的。这里我们模拟在写入过程中间歇性触发GC
if ssd.get_free_blocks_count() < (TOTAL_BLOCKS * 0.05): # 如果空闲块低于5%
ssd.garbage_collect()
print(f"nFinal State after high churn:")
print(f"Total Logical Writes: {ssd.total_logical_writes} pages")
print(f"Total Physical Writes to NAND: {ssd.total_writes_to_nand} pages")
print(f"Final Write Amplification: {ssd.calculate_wa():.2f}")
print(f"Total block erasures (sum of all blocks): {sum(b.erasure_count for b in ssd.blocks)}")
print(f"Average block erasures: {sum(b.erasure_count for b in ssd.blocks) / TOTAL_BLOCKS:.2f}")
运行上述代码，你会观察到随着数据的不断写入和覆盖，特别是当空闲块不足以满足新写入时，垃圾回收会被频繁触发，导致 total_writes_to_nand 远大于 total_logical_writes，从而WA值显著上升。
2. SSD控制器设计和预留空间（Over-provisioning）
- 预留空间： SSD厂商通常会在出厂时预留一部分NAND闪存空间不提供给用户使用。这部分空间被称为“预留空间”或“OP空间”。OP空间越大，FTL在进行GC时就拥有更多的空闲块，可以更灵活地选择受害者块，从而降低WA，提高性能。但代价是用户可用容量减少。
- FTL算法： FTL内部的映射粒度（页映射、块映射、混合映射）、GC触发阈值、受害者块选择策略等都会影响WA。
3. 应用程序/文件系统层因素
这些因素与SSD内部的GC机制无关，而是由上层存储引擎或文件系统的数据组织方式引起。
- 写入模式：
- 随机小块写入： 会导致大量页失效，GC效率低下，WA高。
- 顺序大块写入： 能够有效利用整个页和块，WA低。
- 删除操作： 应用程序删除数据时，文件系统通常只是标记文件为已删除，并不会立即擦除对应的物理块。这些块最终会在GC时被回收。如果一个文件被删除，但其所在的块中还有很多有效数据，那么这些有效数据就需要被拷贝，产生WA。
- 文件系统元数据： 文件系统自身的元数据更新也会产生写入，并影响WA。
- 数据库/存储引擎的Compaction： 这是我们接下来要重点讨论的。在LSM-tree（Log-Structured Merge-tree）等结构中，为了合并和清理数据，存储引擎会主动读取旧文件、合并新旧数据、写入新文件，这个过程本身就会产生大量的写放大。
写放大的影响
写放大对SSD的核心影响体现在两个方面：
- 寿命缩短： 闪存单元的P/E循环次数有限。WA越高，每次逻辑写入都会导致更多的物理写入，从而更快地耗尽SSD的P/E循环次数，缩短SSD的寿命。
- *SSD寿命（TBW）= 用户可用容量 闪存P/E循环次数 / WA**
- 性能下降：
- 写入性能： GC操作需要读取、擦除、写入，这些都会占用SSD内部资源，与应用程序的写入请求竞争I/O带宽，导致写入延迟增加，吞吐量下降。WA越高，GC越频繁，性能影响越大。
- 读取性能： 虽然WA主要影响写入，但GC操作在后台进行时，也可能影响读取请求的响应时间。
第二章：Compaction 策略与写放大
在高性能的键值存储系统和数据库中（如RocksDB, LevelDB, Cassandra等），为了提供高效的写入和查询，常常采用Log-Structured Merge-tree (LSM-tree) 架构。LSM-tree通过将所有写入操作首先追加到内存中的Memtable，然后周期性地将Memtable刷写成不可变的SSTable（Sorted String Table）文件到磁盘，从而将随机写入转化为顺序写入，极大地提高了写入性能。
然而，这种设计也引入了新的挑战：磁盘上会存在大量包含重复键、过期键和删除标记（Tombstones）的SSTable文件。为了解决这些问题，LSM-tree引入了Compaction（压缩/合并）机制。
Compaction 的主要目标包括：
- 减少读放大（Read Amplification）： 当查询一个键时，可能需要在多个SSTable中查找，直到找到最新版本。Compaction通过合并文件，将最新数据集中，减少查询所需扫描的文件数量。
- 减少空间放大（Space Amplification）： 清理过期数据和删除标记，回收存储空间。
- 减少写放大（Write Amplification）： （是的，Compaction本身也会导致WA，但好的Compaction策略旨在优化整体WA，包括GC引起的WA）。通过合并和重写数据，可以减少重复数据，并以更优的方式组织数据，从而间接帮助SSD的GC。
LSM-tree 架构简介
一个典型的LSM-tree包含：
- Memtable： 内存中的写缓冲区，所有新的写入都在这里进行。
- Immutable Memtables： 当Memtable达到一定大小时，变为不可变，并在后台刷写到磁盘。
- SSTables (Sorted String Tables)： 存储在磁盘上的有序键值对文件。它们通常组织成多个层（Levels）。
Compaction就是将磁盘上的SSTable文件进行合并、去重、清理，并生成新的SSTable文件，通常在不同的层之间进行。
核心 Compaction 策略
LSM-tree 中最常见的两种 Compaction 策略是：Size-Tiered Compaction (STCS) 和 Leveled Compaction (LCS)。
1. Size-Tiered Compaction (STCS) / 大小分层合并
工作原理：
STCS将SSTable文件组织成不同的层（或称为“Tier”）。每个层中的文件大小大致相同。当一个层中的文件数量达到某个阈值时，所有这些文件会被合并成一个更大的文件，并提升到下一个层。下一个层的文件大小通常是前一个层的数倍。
- 写入路径： 新的Memtable刷写到L0（最上层），通常作为独立的小文件。
- 合并过程： 当L0中的文件数量达到N个时，它们会被合并成一个更大的文件，放到L1。当L1中的文件数量达到N个时，它们会被合并成一个更大的文件，放到L2，以此类推。每个合并操作都会读取所有待合并的文件，合并其中的键值对（处理更新和删除），然后写入一个新的更大的文件。
特点：
- 写放大 (WA)： STCS的写放大通常较低，因为它倾向于批量处理大量文件，并且只在必要时进行合并。然而，它的一个显著缺点是写放大峰值可能非常高。当一个大层触发合并时，需要读取和重写大量数据。
- 读放大 (RA)： 读放大较高。因为在查询一个键时，可能需要在每个层中都查找一遍，直到找到最新版本。最坏情况下，需要扫描所有层的所有文件。
- 空间放大 (SA)： 空间放大较高。由于文件只在达到阈值时才合并，旧版本的数据会在磁盘上存留很长时间，直到被大合并清理。这会导致磁盘空间利用率较低。
适用场景： 写入吞吐量高、对读取延迟不敏感、对存储空间不敏感的场景。例如，Apache Cassandra默认使用STCS。
代码示例：模拟Size-Tiered Compaction
我们模拟SSTable文件及其合并过程，并跟踪Compaction产生的写放大。
import collections
import random
import time
class SSTable:
"""模拟一个SSTable文件"""
def __init__(self, table_id, keys, level=0):
self.table_id = table_id
self.keys = sorted(list(set(keys))) # 模拟有序且去重的键
self.size = len(self.keys) * 100 # 简化文件大小，每个键100字节
self.level = level
self.min_key = self.keys[0] if self.keys else None
self.max_key = self.keys[-1] if self.keys else None
def __repr__(self):
return f"SSTable(ID={self.table_id}, L={self.level}, Size={self.size/1024:.2f}KB, Keys={len(self.keys)})"
def merge(self, other_table):
"""模拟两个SSTable的合并过程"""
# 在实际中，这里会处理键的冲突、删除标记等，只保留最新版本
# 为了简化，我们只是合并键集
merged_keys = sorted(list(set(self.keys + other_table.keys)))
return SSTable(f"{self.table_id}_{other_table.table_id}", merged_keys, self.level)
class SizeTieredCompactionSimulator:
"""模拟Size-Tiered Compaction策略"""
def __init__(self, merge_threshold=4, tier_size_ratio=10):
self.tiers = collections.defaultdict(list) # {tier_level: [SSTable, ...]}
self.next_table_id = 0
self.merge_threshold = merge_threshold # 当一个层的文件数达到此阈值时触发合并
self.tier_size_ratio = tier_size_ratio # 每一层的大小是前一层的多少倍 (STCS不严格遵循，但在某些变体中可能使用)
self.total_logical_writes_bytes = 0 # 应用程序写入的总字节数
self.total_compaction_writes_bytes = 0 # Compaction过程中的物理写入总字节数
def _add_sstable_to_tier(self, sstable):
"""将SSTable添加到相应的层级，并尝试触发合并"""
self.tiers[sstable.level].append(sstable)
self.compact()
def add_memtable(self, new_keys_bytes):
"""模拟Memtable刷写成新的SSTable"""
self.total_logical_writes_bytes += new_keys_bytes
num_keys = new_keys_bytes // 100 # 假设每个键100字节
keys = [f"key_{random.randint(0, 100000)}" for _ in range(num_keys)]
new_sstable = SSTable(self.next_table_id, keys, level=0)
self.next_table_id += 1
self._add_sstable_to_tier(new_sstable)
print(f" Memtable flushed: {new_sstable}")
def compact(self):
"""执行Compaction"""
while True:
compacted_in_cycle = False
for tier_level in sorted(self.tiers.keys()):
if len(self.tiers[tier_level]) >= self.merge_threshold:
# 达到合并阈值，合并当前层的所有文件
tables_to_merge = sorted(self.tiers[tier_level], key=lambda x: x.size) # 排序不是必须的，但有助于理解
if not tables_to_merge:
continue
print(f" --- STCS: Triggering merge for Tier {tier_level} with {len(tables_to_merge)} tables ---")
# 模拟读取所有待合并文件
read_bytes = sum(t.size for t in tables_to_merge)
# 执行合并操作
merged_table = tables_to_merge[0]
for i in range(1, len(tables_to_merge)):
merged_table = merged_table.merge(tables_to_merge[i])
# 模拟写入新的合并文件
# 注意：合并后的文件大小可能小于所有源文件之和（去重）
# 但为了简化WA计算，我们假设写入量至少是合并后文件的大小
# 实际WA可能更高，因为合并过程也会有临时文件等
self.total_compaction_writes_bytes += merged_table.size
merged_table.table_id = self.next_table_id
self.next_table_id += 1
merged_table.level = tier_level + 1 # 提升到下一层
self.tiers[tier_level] = [] # 清空当前层
self._add_sstable_to_tier(merged_table) # 将合并后的文件添加到下一层
print(f" STCS: Merged into {merged_table}. Moving to Tier {tier_level+1}")
compacted_in_cycle = True
break # 从头开始检查，因为层级结构可能已改变
if not compacted_in_cycle:
break # 没有更多合并可进行
def calculate_compaction_wa(self):
"""计算Compaction引起的写放大"""
if self.total_logical_writes_bytes == 0:
return 0.0
return self.total_compaction_writes_bytes / self.total_logical_writes_bytes
def get_current_state(self):
state = {}
for level in sorted(self.tiers.keys()):
state[level] = [(t.table_id, t.size) for t in self.tiers[level]]
return state
# --- STCS 模拟示例 ---
print("--- Size-Tiered Compaction (STCS) Simulation ---")
stcs_sim = SizeTieredCompactionSimulator(merge_threshold=3) # 3个文件就合并
# 模拟多次Memtable刷写
for i in range(1, 10):
print(f"n--- Cycle {i}: Adding Memtable (approx 10KB) ---")
stcs_sim.add_memtable(10 * 1024) # 每次写入10KB数据
current_state = stcs_sim.get_current_state()
print(f"Current Tier State: {current_state}")
print(f"Logical writes (total): {stcs_sim.total_logical_writes_bytes / 1024:.2f} KB")
print(f"Compaction writes (total): {stcs_sim.total_compaction_writes_bytes / 1024:.2f} KB")
print(f"Compaction WA: {stcs_sim.calculate_compaction_wa():.2f}")
time.sleep(0.1) # 稍作延迟，方便观察输出
print("n--- Final STCS State ---")
print(f"Total Logical Writes: {stcs_sim.total_logical_writes_bytes / 1024:.2f} KB")
print(f"Total Compaction Writes: {stcs_sim.total_compaction_writes_bytes / 1024:.2f} KB")
print(f"Final Compaction WA: {stcs_sim.calculate_compaction_wa():.2f}")2. Leveled Compaction (LCS) / 分层合并
工作原理：
LCS将SSTable文件严格地组织成多个层（Levels），每个层都有一个目标大小限制。L0层（最上层）是Memtable刷写下来的文件。当L0层的文件数量或总大小超过阈值时，L0的文件会与L1层的部分或全部重叠文件进行合并。然后，L1层如果超过其大小限制，会选出一个文件与L2层的重叠文件进行合并，依此类推。
- 写入路径： Memtable刷写到L0。
- 合并过程：
- L0 -> L1 合并： L0中的文件与L1中所有键范围重叠的文件进行合并。由于L0文件可能与L1中大量文件重叠，这通常是一个大的合并操作。
- Li -> Li+1 合并 (i > 0)： 从Li层选择一个文件，与Li+1层所有键范围重叠的文件进行合并。Li+1层的文件总大小通常是Li层的数倍（例如10倍）。这个过程通常是“一对多”的合并。
特点：
- 写放大 (WA)： LCS的写放大通常较高，因为它需要频繁地从一个层合并到下一个层，数据会被多次重写。然而，它的写放大是相对稳定和可预测的，没有STCS那种巨大的峰值。
- 读放大 (RA)： 读放大非常低。因为除了L0，其他层中的文件通常是完全去重且有序的，并且键范围不重叠（或重叠非常少）。查询一个键通常只需要扫描L0和每个层中的一个文件。
- 空间放大 (SA)： 空间放大非常低。通过频繁的合并，过期数据和删除标记可以被迅速清理，磁盘空间利用率高。
适用场景： 对读取延迟敏感、对存储空间利用率有要求、对写入延迟平稳性有要求的场景。例如，RocksDB, LevelDB默认使用LCS。
代码示例：模拟Leveled Compaction
import collections
import random
import time
# 假设SSTable类和SSTable的merge方法与STCS示例相同
class LeveledCompactionSimulator:
"""模拟Leveled Compaction策略"""
def __init__(self, level_size_multiplier=10, l0_threshold_files=4, l0_size_threshold_bytes=40*1024):
self.levels = collections.defaultdict(list) # {level_num: [SSTable, ...]}
self.next_table_id = 0
self.level_size_multiplier = level_size_multiplier # Li+1层的大小是Li层的倍数
self.l0_threshold_files = l0_threshold_files # L0文件数阈值
self.l0_size_threshold_bytes = l0_size_threshold_bytes # L0总大小阈值
# 预设每层的最大字节数
self.level_max_bytes = {
0: self.l0_size_threshold_bytes,
1: self.l0_size_threshold_bytes * self.level_size_multiplier
}
self.total_logical_writes_bytes = 0
self.total_compaction_writes_bytes = 0
def _get_level_max_bytes(self, level):
"""动态计算指定层的最大字节数"""
if level not in self.level_max_bytes:
# 简化计算，通常L1有固定大小，L2及以后按倍数增长
# 在实际中，L0->L1的合并逻辑更复杂，L1及以后是基于Li的大小
if level == 0: return self.l0_size_threshold_bytes
self.level_max_bytes[level] = self._get_level_max_bytes(level - 1) * self.level_size_multiplier
return self.level_max_bytes[level]
def add_memtable(self, new_keys_bytes):
self.total_logical_writes_bytes += new_keys_bytes
num_keys = new_keys_bytes // 100
keys = [f"key_{random.randint(0, 100000)}" for _ in range(num_keys)]
new_sstable = SSTable(self.next_table_id, keys, level=0)
self.next_table_id += 1
self.levels[0].append(new_sstable)
print(f" Memtable flushed: {new_sstable}")
self.compact()
def _get_overlapping_tables(self, source_table, target_level_tables):
"""
查找目标层中与源SSTable键范围重叠的所有SSTable。
这里简化为只要有键重叠就认为是重叠。实际LSM-tree有更精确的范围查找。
"""
overlapping = []
source_key_set = set(source_table.keys)
for target_table in target_level_tables:
# 简化：检查是否存在任何共同的键，实际应检查键范围
if source_table.max_key >= target_table.min_key and
source_table.min_key <= target_table.max_key:
overlapping.append(target_table)
return overlapping
def compact(self):
"""执行Leveled Compaction"""
while True:
compacted_in_cycle = False
# 优先处理L0的Compaction (L0 -> L1)
l0_current_size = sum(t.size for t in self.levels[0])
if len(self.levels[0]) >= self.l0_threshold_files or l0_current_size > self.l0_size_threshold_bytes:
# 选取L0的所有文件进行合并 (RocksDB L0 Compaction通常是这样)
tables_to_merge_l0 = list(self.levels[0])
if not tables_to_merge_l0:
break
print(f" --- LCS: Triggering L0 -> L1 Compaction with {len(tables_to_merge_l0)} tables from L0 ---")
# 合并L0文件
merged_l0_table = tables_to_merge_l0[0]
for i in range(1, len(tables_to_merge_l0)):
merged_l0_table = merged_l0_table.merge(tables_to_merge_l0[i])
# 查找L1中与合并后的L0文件重叠的文件
overlapping_l1_tables = self._get_overlapping_tables(merged_l0_table, self.levels[1])
# 将L0合并结果和所有重叠的L1文件一起合并
all_tables_for_l1_compaction = [merged_l0_table] + overlapping_l1_tables
if not all_tables_for_l1_compaction:
break # 应该不会发生
final_merged_table = all_tables_for_l1_compaction[0]
for i in range(1, len(all_tables_for_l1_compaction)):
final_merged_table = final_merged_table.merge(all_tables_for_l1_compaction[i])
self.total_compaction_writes_bytes += final_merged_table.size # 计入写放大
final_merged_table.table_id = self.next_table_id
self.next_table_id += 1
final_merged_table.level = 1 # 结果写入L1
self.levels[0] = [] # 清空L0
# 从L1中移除被合并的旧文件
self.levels[1] = [t for t in self.levels[1] if t not in overlapping_l1_tables]
self.levels[1].append(final_merged_table) # 添加新合并的文件
print(f" LCS: L0->L1 Merged. New table: {final_merged_table}. Removed {len(overlapping_l1_tables)} from L1.")
compacted_in_cycle = True
# 处理Li -> Li+1 Compaction (i > 0)
# 简化：一次只从Li中选择一个文件进行合并
if not compacted_in_cycle: # 如果L0->L1没有发生，再检查其他层
for level_num in sorted(self.levels.keys()):
if level_num == 0: continue # L0已处理
current_level_size = sum(t.size for t in self.levels[level_num])
if current_level_size > self._get_level_max_bytes(level_num) and self.levels[level_num]:
# 选取当前层的一个文件进行合并
table_to_compact = self.levels[level_num][0] # 简单选择第一个
print(f" --- LCS: Triggering L{level_num} -> L{level_num+1} Compaction for {table_to_compact} ---")
overlapping_next_level_tables = self._get_overlapping_tables(table_to_compact, self.levels[level_num+1])
all_tables_for_next_level_compaction = [table_to_compact] + overlapping_next_level_tables
if not all_tables_for_next_level_compaction:
break
final_merged_table = all_tables_for_next_level_compaction[0]
for i in range(1, len(all_tables_for_next_level_compaction)):
final_merged_table = final_merged_table.merge(all_tables_for_next_level_compaction[i])
self.total_compaction_writes_bytes += final_merged_table.size # 计入写放大
final_merged_table.table_id = self.next_table_id
self.next_table_id += 1
final_merged_table.level = level_num + 1
self.levels[level_num].remove(table_to_compact) # 移除被合并的文件
# 从Li+1中移除被合并的旧文件
self.levels[level_num+1] = [t for t in self.levels[level_num+1] if t not in overlapping_next_level_tables]
self.levels[level_num+1].append(final_merged_table) # 添加新合并的文件
print(f" LCS: L{level_num}->L{level_num+1} Merged. New table: {final_merged_table}. Removed {len(overlapping_next_level_tables)} from L{level_num+1}.")
compacted_in_cycle = True
break # 一次只执行一个Li->Li+1的合并
if not compacted_in_cycle:
break # 没有更多合并可进行
def calculate_compaction_wa(self):
if self.total_logical_writes_bytes == 0:
return 0.0
return self.total_compaction_writes_bytes / self.total_logical_writes_bytes
def get_current_state(self):
state = {}
for level in sorted(self.levels.keys()):
state[level] = [(t.table_id, t.size) for t in self.levels[level]]
return state
# --- LCS 模拟示例 ---
print("n--- Leveled Compaction (LCS) Simulation ---")
lcs_sim = LeveledCompactionSimulator(level_size_multiplier=3, l0_threshold_files=2) # 降低倍数和阈值以便更快看到效果
for i in range(1, 10):
print(f"n--- Cycle {i}: Adding Memtable (approx 10KB) ---")
lcs_sim.add_memtable(10 * 1024) # 每次写入10KB数据
current_state = lcs_sim.get_current_state()
print(f"Current Level State: {current_state}")
print(f"Logical writes (total): {lcs_sim.total_logical_writes_bytes / 1024:.2f} KB")
print(f"Compaction writes (total): {lcs_sim.total_compaction_writes_bytes / 1024:.2f} KB")
print(f"Compaction WA: {lcs_sim.calculate_compaction_wa():.2f}")
time.sleep(0.1)
print("n--- Final LCS State ---")
print(f"Total Logical Writes: {lcs_sim.total_logical_writes_bytes / 1024:.2f} KB")
print(f"Total Compaction Writes: {lcs_sim.total_compaction_writes_bytes / 1024:.2f} KB")
print(f"Final Compaction WA: {lcs_sim.calculate_compaction_wa():.2f}")Compaction 策略对比
| 特性 | Size-Tiered Compaction (STCS) | Leveled Compaction (LCS) |
|---|---|---|
| 写放大 (WA) | 较低（但有高峰值），通常在 2-10x 之间。 | 较高且稳定，通常在 5-30x 之间（取决于层数和倍数）。 |
| 读放大 (RA) | 较高，查询时可能需要扫描所有层。 | 较低，查询通常只需扫描L0和每个层的一个文件。 |
| 空间放大 (SA) | 较高，旧数据和删除标记可能存留较久。 | 较低，过期数据和删除标记清理迅速。 |
| 写入性能 | 写入延迟低且稳定，但Compaction峰值可能导致间歇性卡顿。 | 写入延迟相对稳定，但每个写入操作最终都会触发多次Compaction重写。 |
| 读取性能 | 较差，随机读和范围读性能受文件数量影响大。 | 较好，随机读和范围读性能稳定且高效。 |
| 实现复杂度 | 相对简单。 | 相对复杂，需要精细的键范围管理。 |
| 典型应用 | Apache Cassandra, ElasticSearch（某些版本）。 | RocksDB, LevelDB, Apache HBase (部分模式)。 |
总写放大：LSM-tree WA 与 SSD GC WA 的结合
需要注意的是，我们讨论的 Compaction WA 仅仅是应用程序层面的写放大。SSD的实际总写放大是 LSM-tree Compaction WA 与 SSD 内部 GC WA 的乘积。
*总 WA = (1 + Compaction WA) (1 + GC WA)**
其中 Compaction WA 是指应用层合并数据重写的总数据量与用户逻辑写入数据量之比。GC WA 是指SSD内部因磨损均衡和垃圾回收额外写入的数据量与SSD控制器接收到的总数据量（包括应用层Compaction重写的数据）之比。
因此，选择 Compaction 策略时，不仅要考虑其自身的读写放大特性，还要考虑其对SSD内部GC的影响。例如：
- LCS 往往会产生更稳定且更高的 Compaction WA。 这意味着更多的数据会被写入SSD，从而给SSD的GC带来更大的压力。然而，LCS产生的文件通常更规整、更新更频繁，这可能有助于SSD的GC更有效地回收空间，因为无效页的比例更高。
- STCS 尽管Compaction WA可能较低，但其碎片化的文件组织和长生命周期的旧数据可能导致SSD的GC更难找到“干净”的块，从而提高GC WA。 尤其是在删除操作频繁的场景下，STCS可能导致大量无效数据长期占据物理空间，迫使GC拷贝更多有效数据。
第三章：在 SSD 寿命限制下权衡 Compaction 策略
现在，我们来到了核心问题：如何在SSD寿命限制下，权衡 Compaction 策略的选择？这并非一个简单的非黑即白的问题，而是需要根据具体工作负载、性能目标、成本预算和数据持久性要求进行多维度考量。
核心权衡维度
-
工作负载特性：
- 写入密集型 vs. 读取密集型： 如果写入非常频繁且随机，那么需要一个能有效处理写入的策略。如果读取延迟是瓶颈，则需要一个读放大低的策略。
- 更新/删除频率： 大量更新和删除会产生大量无效数据（tombstones），需要Compaction机制及时清理。
- 数据生命周期： 数据是长期存储还是短期活跃？
- 数据大小： 大键值对还是小键值对？
- 访问模式： 顺序访问还是随机访问？点查询还是范围查询？
-
SSD 寿命（DWPD / TBW）：
- DWPD (Drive Writes Per Day)： 每天可写入整个盘容量的次数。
- TBW (Terabytes Written)： 总写入字节数。
这些指标直接与WA相关。WA越高，SSD寿命消耗越快。
-
性能目标：
- 写入吞吐量和延迟： 是否能接受偶尔的写入延迟尖峰？
- 读取吞吐量和延迟： 对读取响应时间有多严格的要求？
- QoS (Quality of Service)： 是否需要保证稳定的P99/P99.9延迟？
-
存储成本：
- SSD类型： 不同类型的NAND闪存（SLC/MLC/TLC/QLC）具有不同的P/E循环次数和成本。如果应用WA较高，可能需要选择更昂贵的、耐久性更好的SSD。
- 存储容量： 空间放大高的策略需要更多的物理存储空间。
具体的权衡考量和优化方向
1. LCS vs. STCS 的选择
-
选择 LCS 的场景：
- 读取性能是首要目标： 例如在线事务处理（OLTP）、需要低延迟点查询和范围查询的应用。
- 存储空间利用率要求高： 需要及时回收过期数据，减少空间浪费。
- 删除操作频繁： LCS能更快速地清理Tombstones，避免它们在多个层级中累积。
- 可以接受较高的但稳定可预测的写放大： 愿意牺牲一部分SSD寿命来换取读取性能和空间效率。
- SSD具备足够预留空间： 高WA会给SSD GC带来压力，足够的OP空间有助于缓解。
-
选择 STCS 的场景：
- 写入吞吐量是首要目标，且对读取延迟不敏感： 例如日志收集、消息队列、数据导入等。
- 数据生命周期短，或者大部分数据是追加写入： 如果数据很少更新或删除，STCS的低WA优势更明显。
- 可以容忍写入延迟的偶发性尖峰： 接受大Compaction带来的间歇性卡顿。
- SSD寿命是绝对瓶颈，需要尽可能降低总WA： 在某些特定条件下，STCS可能提供更低的总WA，尤其是在其工作负载下GC效率较高时。
2. 优化 Compaction 策略以降低 WA
无论选择哪种基本策略，都可以通过以下方式进行优化：
-
Compaction 触发阈值：
- LCS： 调整
level_size_multiplier(层级大小倍数) 和L0_file_num_compaction_trigger(L0文件合并阈值)。减小倍数或提高L0阈值会增加WA，但可能减少Compaction的频率。 - STCS： 调整
merge_threshold(合并文件数阈值)。提高阈值会减少Compaction频率，但增加读放大和空间放大。 - 目标： 找到一个平衡点，既能及时清理数据，又不会过于频繁地触发Compaction。
- LCS： 调整
-
写入缓冲和批处理：
- Memtable 大小： 增大Memtable可以允许更多的数据在内存中合并，减少刷写到磁盘的SSTable文件数量，从而减少后续Compaction的次数和WA。但会增加恢复时间。
- 写入批次： 将逻辑写入打包成更大的批次，可以使SSD控制器进行更高效的顺序写入，降低GC的WA。
-
数据压缩：
- 数据压缩率： 在数据写入SSTable之前进行压缩，可以减少实际写入磁盘的数据量，从而直接降低Compaction WA和GC WA。
- 权衡： 压缩会增加CPU开销，并在读取时需要解压，增加读取延迟。选择合适的压缩算法（如Snappy、LZ4、Zstd）至关重要。
代码示例：在SSTable中加入压缩的简要概念
import zlib # 使用zlib作为示例压缩库 class SSTableWithCompression(SSTable): def __init__(self, table_id, keys, level=0, compression_ratio=0.5): super().__init__(table_id, keys, level) self.compression_ratio = compression_ratio # 模拟压缩后的实际存储大小 self.compressed_size = int(self.size * compression_ratio) # 存储压缩后的数据（这里仅为概念，实际会存储压缩后的字节流） # self.compressed_data = zlib.compress(str(keys).encode()) def __repr__(self): return f"SSTable(ID={self.table_id}, L={self.level}, OrigSize={self.size/1024:.2f}KB, CompSize={self.compressed_size/1024:.2f}KB, Keys={len(self.keys)})" # 合并方法也需要考虑压缩，合并后重新压缩 def merge(self, other_table): merged_keys = sorted(list(set(self.keys + other_table.keys))) # 假设合并后的压缩率保持不变 return SSTableWithCompression(f"{self.table_id}_{other_table.table_id}", merged_keys, self.level, self.compression_ratio) # 模拟Compaction时计算WA使用compressed_size # compaction_writes_bytes += merged_table.compressed_size -
Tombstone 处理：
- 过期时间（TTL）： 为数据设置过期时间，Compaction可以更早地清理过期数据，减少无效数据积累。
- Tombstone Compaction： RocksDB等系统有专门的Tombstone Compaction，确保删除标记不会长时间存活并影响读写性能。
-
**Bloom