SlimTrie: 单机百亿文件的极致索引-设计篇

15 分钟读完

Github: SlimTrie

背景

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

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

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

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

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

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

巨人的肩膀: 主流索引设计

存储系统的架构主要由两方面构成: 数据的存储 数据的定位 .

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

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

在讨论我们的索引设计之前,首先我们来回顾一下已知的几种索引设计, 分析它们的优劣, 以及为什么我们不能选择其中一个常规的设计, 而必须站在这些巨人的肩膀上更进一步。

存储体系

在分布式领域,管理大量索引数据时,一般会采用分层的思路(非常类似于两层的b+tree 的实现), 如果不是超大规模的系统, 两层最为常见:

  • 上层索引主要负责sharding, 将查询路由到一个独立的服务器
  • 下层负责具体的查询

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

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

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

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

方案-0: 消灭问题: 在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 没有业务上的规律而变得复杂.

标准方案: 解决”数据的定位”问题

标准的方案都是 客户端指定URL  的方式:

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

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

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

明确问题: 定义索引

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

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

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

存储系统中的索引需要:

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

方案-1: 基于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 的无序.

  • 内存开销: O(k * n)
  • 查询效率: O(k)

方案-2: 基于Tree 的索引