一. 背景    

当下信息社会每天都产生大量需要保存的数据，这些数据在刺激海量存储技术发展的同时也带来了新的挑战。比如，海量数据为存储系统增加了大量的小文件，这些小文件的元数据如何管理？如何控制定位某个文件的时间和空间开销？

随着对数据实时性要求的提高, 文件也越来越趋于碎片化，像短视频、直播类业务, 往往一个视频只有几百KB, 甚至几十KB大小。可以说, 一个成熟的对象存储系统最后都会面临巨量元数据管理的挑战, 如HDFS, openstack-swift等, 在软件整体进入相对成熟的阶段, 小文件成为最头疼的问题。

以100TB数据（大约是日常的单机容量）为例，若全部存储10KB的文件（文件名<=1KB），仅是管理这些文件所需的索引数据就将需要约10,000GB的内存空间。这是任何成（sheng）熟（qian）的存储系统都无法接受的巨大压（cheng）力（ben）。

为了应对当前环境给存储带来的挑战，经过不懈研究和探索，白山云存储在两个方面进行了优化:

• 整体上对元数据管理采用无中心的设计，索引采用分层的思想，抛弃中心化元数据管理的策略, 将元数据分散到每个单机存储服务器。
• 单机上,  我们部署了一套全新的索引数据结构SlimTrie，对索引数据进行了裁剪、压缩和聚合，将索引进行了极大的优化, 逼近空间利用率的理论极限。以单机100TB数据为例, 如果文件都是10KB小文件, 那么就有100亿个文件，我们的SlimTrie算法最终只需10GB内存空间。

今天我们就主要聊聊如何能在单机上实现百亿文件的索引。

 

二. 巨人的肩膀：主流索引设计

存储系统的架构主要由数据的存储和数据的定位 两方面构成。数据的存储更多关注文件布局、复制、故障检测、修复等环节，它主要决定系统的可靠性；而数据的定位是最具挑战的, 尤其是面对海量数据时，一个存储系统中索引的设计，直接决定了这个系统的读写效率、可扩展能力和成熟度。

然而，索引的设计面临着各种挑战和难题。比如，当存储的数据量越来越大，如何权衡索引数据的格式、算法、达到最高的空间利用率和查询效率等问题, 就成为系统设计的关键。

在讨论SlimTrie索引设计之前，我们来回顾一下已知的几种索引设计。

 

1.存储体系

在分布式领域，管理大量索引数据时，一般会采用分层的思路（非常类似于两层b+tree的实现）, 如果不是超大规模的系统, 两层最为常见，上层索引主要负责sharding, 将查询路由到一个独立的服务器，下层负责具体的查询。

 

一般来说，单集群规模可能有是几百到几千个服务器组成, 这时上层sharding部分的数据可能只有几千条（或上百万条，如果使用虚拟bucket等策略, 虚拟节点可能是物理节点的几百倍）, 所以上层索引会很小，大部分问题集中在底层索引上。

在我们的设计中, 上层是一个百万级别的sharding, 下层直接是存储服务器, 存储服务器负责索引整机的文件。这样, 上层sharding的量级不会很大, 整个系统设计的核心问题就落在了单机的文件索引设计上。

Tips：

• 一般很少有千台服务器以上的集群，不是受限于技术，而是为了简化运维。 几百到几千个服务器已经具备了不错的容量、负载弹性和单点故障容错能力, 而且几百个服务器的小集群管理相对容易。
• 如果集群规模大到需要3层索引, 多一次索引访问, 性能也会降低。
• 类Haystack的设计在对象存储中很常见: Haystack是一个关于单机存储设计的实现, 为了提升IO性能, 降低文件系统Inode的读写开销, 将小文件合并成一个大文件存储, 并在内存中存储所有文件的元信息（meta）, 这样直接将每个文件读取的2次IO（inode+data）转变成一次内存操作和一次IO操作。

剥去系统架构层面的组件, 剩下的就是单机上文件定位的问题。

 

2.消灭问题，在URL中嵌入定位信息

这一类方案可以称之为服务器端URL生成。

每次上传时, 存储服务器负责生成一个用于下载的URL，如FastDFS的实现:

http://192.168.101.5/group1/M00/00/00/wKhlBVVY2M-AM_9DAAAT7-0xdqM485_big.png

其中, group1, M00, 00, 00是分组和定位信息。

当服务器接到一个URL时,直接从其中解析出文件位置, 然后定位到文件所在的服务器、 磁盘、目录和文件名，不再需要额外的索引数据。

这种方案实际上是将”数据的定位”绕开了, 交给外层逻辑, 也就是存储的使用方来处理, 而自己只处理”数据的存储”。

优势：

• 简化了问题, 在实际生成环境中, 有不少应用是倾向于这种策略的，它们对url的组织形式不关心, 只要求能下载到, 例如 “图床” 类应用

劣势：

• 缺少通用性, 存储的使用方必须负责管理每个URL
• 一般不适合删除文件
• 按照规则自动清理、授权等需求,也会因为URL没有业务上的规律而变得复杂

 

3.解决“数据的定位”问题，客户端指定URL

客户端指定URL是比较通用的方式， 它允许用户在上传时指定下载的URL, 因此它不仅要管理”数据的存储”问题, 同时也关心”数据的定位”问题。存储系统负责记录每个URL到文件数据位置的信息， 相当于一个分布式的key-value map。

类似aws S3和其他大部分公有云对象存储服务, 都属于第二类, 是通用的存储。

提到 key-value map, 分布式领域和单机领域有颇多相似, 分布式存储系统的”数据的定位”问题, 也就是索引的构建, 基本上也分为两个思路: 无序的hash map类结构, 和有序的tree 类结构。

接下来我们分别分析两类索引的优劣。

 

3.1 明确问题: 定义索引

提出一个好问题永远比解决问题更重要:

索引可以被认为是一些"额外"的数据, 在这些额外数据的帮助下, 可以从大量数据中快速找到自己想要的内容。

就像一本书, 一般包括1个"索引"—— 目录, 它让读者只翻阅几页的目录后就可以定位到某个章节的页码。

存储系统中的索引需要做到:

• 足够小: 如果目录过于详细, 翻阅目录的时间成本就会变高
• 缩小查询范围: 目录的作用不是精确的定位到某一页某一行某个字, 而是定位到一个足够小的范围（几页）
• 足够准确: 对较小的文件, 访问一个文件开销为1次磁盘IO操作
• 全内存: 索引信息必须全部在内存中, 访问一个文件分为2步——访问索引、访问磁盘。 访问索引的过程中不能访问磁盘, 否则延迟变得不可控（这也是为什么leveldb或其他db在我们的设计中没有作为索引的实现来考虑）

 

3.2基于Hash map的索引

Hash 类索引例图

 

Hash map类索引首先利用hash函数的计算，将要存储的key映射到一个新的hash值，然后再建立索引。查找定位时也需要这一步来定位到真正数据存储的位置。上面的例图简单展示了其结构和工作原理。

它的优点很明显:

• 一次检索定位数据. 即, 每个key都可以通过一步计算找到所需的值的位置.
• 查找的时间复杂度是 O（k）（k是key的长度）。这个特点非常适合用来做单条数据的定位，然而它有一个前提是查找的key必须是等值匹配的，不支持“>”、“<”的操作

范围查找在存储系统中也是一个非常重要的特性, 在数据清理、合并等操作时, 是必须要支持的一个API

从图中我们能明显看到它的几个天然缺陷:

• 无序。当进行查找操作时，如果不是等值的匹配而是范围查询，比如，想要顺序列出索引中全部的key，最优时间复杂度也需要O（k * n * log（n）），这样的操作消耗的空间和时间代价都是索引系统不可接受的。
• 内存开销大。 Hash map 要求在内存中保存完整的key, 也就是说内存开销是O（k*n）, 这对单机百亿文件级别的目标来说无疑是致命的缺陷。

有一种优化方式是: 使用MD5（key）的前8字节作为索引的key, 可以将任意长度key缩减到8字节, 并在一定范围内把碰撞几率控制到很小。

但我们没有选择这种方案的原因还是因为hash的无序。

 

3.3 基于Tree 的索引

Tree 类索引例图

 

Tree 类索引利用树的中间节点和分支将全量的key分成一个个更小的部分。上图是一个典型的B+Tree实现，其中间节点只保存了key，数据部分全部保存在叶子节点里。这样的结构在查询时，通过树的中间节点一步步缩小查找范围，从而找到要查找的key。

Tree 类中代表性的数据结构有:

• B+tree、 RBTree、SkipList、LSM Tree ： 一般以平衡性最优为特点, 适用于数据库中实现索引等场合。
• 排序数组: 也可以认为是Tree类的数据结构, 它的空间开销、查询性能都跟平衡树相当。

Tree 类索引的特点也很明显:

• 优势: 对保存的key是排序的。如例图所示，通过一个顺序访问数据的指针，就能够方便地顺序列出全部数据，这弥补了Hash类索引不能够范围查询的缺点。

此外，Tree类索引有许多成熟的实现，如B树、B+树的设计在查询性能方面也有很好的表现，MySQL的默认索引类型就是B+树。

• 劣势: 跟Hash map一样, 用Tree做索引的时候, map.set（key = key, value = （offset, size）） 内存中必须保存完整的key, 内存开销为O（k * n），也很大。

 

4.小结

以上是两种经典的索引结构设计案例，它们都存在一个无法避免的问题：首先这两种索引结构首先都会存储全量的key信息，当key的数量快速增长时，它们对内存空间的需求会变的非常巨大。

小文件索引数据量大的困境，导致以上的经典索引结构无法支持在索引海量数据的同时，将索引缓存在内存中。而一旦索引数据需要磁盘IO，时间消耗会增大几个量级，存储系统的性能将因索引效率低而大打折扣。

优化索引结构以提高存储性能，才是解决这个问题的唯一出路。

对此，目前业界也有自己的一些方案， 比如LevelDB采用skiplist建立索引，但skiplist内存占用太大，需要2n个指针的开销，而且无法做前缀压缩。仔细研究过这些已有方案后，我们认为都不太理想。

是否有一种数据结构能够索引海量数据，并且占用空间不大，能够缓存在内存中呢？

 

三. 鱼和熊掌我都要: 低内存, 高性能的 SlimTrie 索引

1.理论极限

如果要索引n个key, 那至少需要为每个key提供log2（n） 个bit, 才能区分出n个不同的key。

如果一共有n个key, 因此理论上所需的内存空间最低是log2（n） * n, 这就是我们空间优化的目标。

在这个极限中, key的长度不会影响空间开销, 而仅仅依赖于key的数量, 这也是我们要达到的一个目标——允许很长的key出现在索引中而不需要增加额外的内存。

实际上我们在实现时限制了n的大小, 将整个key的集合拆分成多个指定大小的子集, 这样有2个好处:

• n 和 log2（n） 都比较确定, 容易进行优化
• 占用空间更小, 因为: a * log（a） + b * log（b） < （a+b） * log（a+b）

最终达到每个文件的索引均摊内存开销与key的长度无关:

每条索引一共10 byte, 其中6 byte是key的信息、4 byte是value: offset。

 

2.SlimTrie 的前辈: Trie

Tree的顺序性、查询效率都可以满足预期, 但空间开销仍然很大。

在以字符串为key的索引结构中, Trie的特性刚好可以优化key存储的问题。

Trie 是一个前缀树, 例如:

保存了8个key的trie结构

"A", "to", "tea", "ted", "ten", "i", "in", and "inn"

 

Trie的特点在于原生的前缀压缩, 而Trie上的节点数最少为O（n）, 但Trie的空间开销比较大, 因为每个节点都要保存若干个指针（指针单独要占8字节）, 导致它的空间复杂度虽然是O（n）, 但实际内存开销很大。

如果能将Trie的空间开销降到足够低, 它就是我们想要的东西!

 

3.SlimTrie的设计

• 静态数据索引

数据生成之后在使用阶段不修改。依赖于这个假设我们可以对索引进行更多的优化: 预先对所有的key进行扫描, 提取特征, 大大降低索引信息的量。

在存储系统中, 需要被索引的数据大部分是静态的，数据的更新是通过Append 和 Compact这2个操作完成的， 一般不需要随机插入一条记录。

• SlimTrie保证存在的key被正确定位, 但被索引到的key不一定存在

索引的目的在于快速定位一个对象所在的位置范围, 但不保证定位到的对象一定存在，就像Btree的中间节点, 用来确定key的范围, 但要查找的key是否真的存在, 需要在Btree的叶子节点（真实数据）上来确定。

• SlimTrie支持顺序查找和遍历key

索引很多情况下需要支持范围查询，SlimTrie 作为索引的数据结构，一定是支持顺序遍历的特点。SlimTrie 在结构上与树形结构有相似点，顺序遍历的实现并不难。

• SlimTrie的内存开销只与key的个数n相关，不依赖于key的长度k
• SlimTrie支持最大16KB的key
• SlimTrie查询速度要非常快

  假设n个key，每个key的长度为k，各数据结构的特性如下表：

 

4.生成SlimTrie的三个步骤

1）用所有的key创建一个标准的Trie树, 然后在标准Trie树基础上做裁剪。

裁剪掉标准Trie中无效的节点，即Trie树中的单分支节点，对索引key没有任何的帮助，将索引数据的量级从O（n * k）降低到O（n）。

2）Trie的压缩, 通过一个compacted array来存储整个Trie的数据结构, 在实现上将内存开销降低。

接下来还要在实现上压缩Trie实际的内存开销。树形结构在内存中多以指针的形式来实现, 但指针在64位系统上占用8个字节, 相当于最差情况下, 内存开销至少为 8*n，这样的内存开销还是太大了，所以我们使用compacted array来压缩内存开销。

3）对小文件进行优化, 将多个相邻的小文件用1条索引来标识, 平衡IO开销和内存开销。

索引的设计以降低IO和降低内存开销为目的，这两方面有矛盾的地方, 如果要降低IO就需要索引尽可能准确, 这将带来索引的容量增加；如果要减小索引的内存开销, 则可能带来对磁盘上文件定位的不准确而导致额外的IO。在做这个设计时, 有一个假设是, 磁盘的一次IO, 开销是差不多的, 跟这次IO的读取的数据量大小关系不大，所以可以在一次IO中读取更多的数据来有效利用IO。

 

四.实测 SlimTrie 索引

使用 SlimTrie 数据结构的索引相比于使用其他类索引 ，在保证索引功能的情况下压缩了索引中的 key 所占用的空间。理论上讲，使用 SlimTrie 做索引可以极大的节约内存占用。

现在我们来看看实际测试的结果。

 

1.内存的低开销

首先我们用一个基本的实验来证明我们的实现和上文说到的理论是相符的。实验选取Hash 类数据结构的 map 和 Tree 类数据结构的B-Tree 与 SlimTrie 做对比，计算在同等条件下，各个数据结构建立索引所耗费的内存空间。

实验在go语言环境下进行，map 使用 golang 的 map 实现，B-Tree使用Google的BTree implementation for Go （github.com/google/btre… ） 。 key 和 value 都是 string 类型（我们更多关心它的大小）。

实验的结果数据如下：

1）索引内存占用对比

可以得出明显结论：

• SlimTrie 作为索引在内存的节省上碾压 map 和 B-Tree。
• SlimTrie 作为索引其内存占用的决定因素是 value 的大小，与key的大小无关。

在此实验的基础上我们再做一个理论上的计算：1PB 的数据量，使用 SlimTrie 做索引，小文件合并到 1MB，索引的 value 是每一个 1MB 数据块的起始位置，4 byte 的 int 足够，根据测试，索引的 key 在 SlimTrie 中占的空间不会超过 6 Byte。

那么，1GB内存便可建立 100TB 数据量的索引:

100TB / 1M * （4+6） = 1GB

 

2）SlimTrie 在通用场景中的表现

因为这次测试所有的数据结构都保存了完整的key和value信息，所以我们只看memory overhead即可比较出谁的空间占用小。测试得到的数据，见下面的图表：

两者进行对比，可以明显看出，SlimTrie 所占用的空间额外开销仍然远远小于 map 和 B-Tree 所占的内存，每个 key 能够节省大约 50 Byte。

内存占用空间大获全胜之后，我们还对 SlimTrie 的查询进行了测试，同时和 map 、Btree 进行了比较，在与内存测试相同的go语言环境下进行实验。

 

2.查询的高性能

1）测量查询相同的、确定存在的 key 的查询时间比较结果如下图

 

存在的key的查找耗时对比图（越小越优）

 

2）查询相同的、确定不存在的 key 的查询时间比较结果如下图

不存在的key的查找耗时对比图（越小越优）

 

SlimTrie的查询效率远好于Btree, 也非常接近Hash map的性能。

• 上面两个图中，前半段key的长度k=1000保持不变，随着key的个数n的增长， SlimTrie 查询耗时随之上涨
• 后半段key的个数保持不变，长度减小，SlimTrie 的查询耗时基本维持不变

从查询效率上也反应了SlimTrie的内部结构只与n相关的特性.

另一方面，在上图中，我们也能够看到，SlimTrie 的实际查询耗时在 150ns 左右，加上优秀的空间占用优化，作为存储系统的索引依然有非常强的竞争力。

 

3.小结

作为索引，SlimTrie 的优势巨大，可以在1GB内存中建立100TB数据量的索引，空间节约惊人，令以往的索引结构望尘莫及；时间消耗上，SlimTrie 的查找性能与 sorted Array 接近，超过经典的B-Tree。抛下索引这个身份，SlimTrie 在各项性能方面表现依旧不俗，作为一个通用 Key-Value 的数据结构，内存额外开销仍远远小于经典的 map 和 Btree。