稀疏文件 LRU 缓存

Source: Hacker News

稀疏文件概述

几年前我遇到的一个有趣的文件系统特性是 稀疏文件。简而言之，许多文件系统允许你创建一个逻辑上包含“空”（全零）块的文件，这些块在实际写入之前并不会在磁盘上占用物理空间。

该文件在磁盘上实际占用 0 字节，尽管逻辑大小为 512 MB。在 16 MB 偏移处写入一些非零字节后，系统只会物理分配一个块（4 KB）。文件系统会维护元数据，记录文件的哪些块在磁盘上有实际表示，哪些块没有。对普通读取者而言，稀疏性是透明的——它完全由文件系统管理。

Amplitude 的使用案例

在 Amplitude，所有数据都以耐久的冷存储（Amazon S3）形式保存，使用一种用于分析查询的列式数据格式。每次查询都从 S3 获取数据既低效又昂贵，因此数据会被缓存到本地 NVMe SSD（例如来自 r7gd 实例系列 的 SSD）上。

这些本地 SSD 的成本是冷存储的十倍以上，所以制定良好的缓存策略至关重要。

为什么列式格式很重要

分析查询通常只涉及少量列（在可能成千上万列中只需 5–10 列）。由于每列在文件中以连续的范围存储，读取速度很快。连续的范围也非常契合我们的本地缓存方式——我们不需要在文件中挑选散落的细小片段。

传统缓存方法

1. 缓存整个文件 – 简单且需要的元数据最少，但会在很少或根本不使用的列上浪费大量 SSD 空间。
2. 将每列缓存为单独的文件 – 减少了空间浪费，但会导致文件数量激增，增加文件系统元数据开销。小列会被向上取整到文件系统块大小，而在数十万客户的情况下，绝大多数文件/列都很小（Pareto principle）。

稀疏文件作为折中方案

稀疏文件让我们能够缓存整个文件，同时只在物理上保留包含所需列的逻辑块。这种方式：

• 保持消费者端读取逻辑简单（仍然是单个文件）。
• 减少磁盘使用，因为未使用的列保持未分配。
• 降低文件系统元数据开销。
• 将小列合并到共享的文件系统块中，减少 S3 GET 请求的次数。

消费者必须在读取之前向缓存声明他们需要的列。

管理稀疏文件元数据

我们在本地的 RocksDB 实例中存储哪些列被缓存的元数据。具体来说，我们跟踪稀疏文件的逻辑块：

• 哪些块在本地存在。
• 每个块最近一次被读取的时间。

利用这些信息，我们近似实现了 LRU 策略 来在 SSD 空间耗尽时驱逐数据。

块布局

逻辑块是可变大小的：

• 在文件头部有几个较小的块（仍然大于文件系统块大小），用于保存文件格式元数据头（类似于 Parquet）。
• 其余数据使用更大的块。

这种布局利用了这样一个事实：必须始终读取头部才能解释列的位置。

稀疏文件 LRU 缓存的优势

• 更少的 S3 GET – 仅获取所需的列。
• 降低文件系统元数据 – 更少的单独文件以及更低的块分配开销。
• 降低块开销 – 小列共享块，最大限度减少空间浪费。
• 更少的 IOPS – 缓存管理操作更少。

稀疏文件 LRU 缓存同时改进了查询系统的多个方面，展示了底层文件系统特性如何对整体系统设计产生显著影响。