Facebook是怎么做到每秒索引数百万条记录的？

数据库 facebook| 2016-09-08

编者按：作者Pedro Eugênio Rocha 现任Facebook系统工程师，2016年毕业于巴西巴拉那州联邦大学信息学专业，研究兴趣包括数据库与存储系统，尤其是与分布式系统和大数据相关的数据库与存储系统。

作者在文章中介绍了Cubrick：一种多维内存数据管理系统。Cubrick是由Facebook开发的新型分布式多维内存数据库管理系统，其目的在于解决大量数据资源并行运行所存在的问题。为达到交互式分析高度动态数据集这一目的，Cubrick运用一种用于管理柱形内存数据的新策略，这种策略允许在数据集的每一个维度中进行索引过滤，并有效地实时更新。

大数据集实时分析已经成为众多互联网公司的广泛需求。最大限度缩小数据生成与数据分析之间的时间差使得数据驱动的互联网公司能够及时形成见解，做出决策，最终能够促进自身快速发展。为了实现实时分析，需要构建一个数据库系统，保证该系统能够连续不断地获取由网络日志生成的数据流，在数据生成几秒后应答查询需求。鉴于有一些实时数据流每秒钟能够释放出几百万条记录，大规模获取这些高动态化数据集将面临越来越多的挑战。

此外，所有的数据库查询需要在数百毫秒内完成，为用户提供一种真实的交互式体验，以便充分挖掘数据的利用价值，但是，事实上，在如此短的时间内浏览大型数据集要求大量并行运行，因而庞大的数据资源成为必须的硬件条件。但是，在Facebook过去几年的工作中，我们观察过一些实用案例，在这些案例中所有的查询都经过过度过滤，此外，我们只关注一种超大型数据集中的小部分特定子集。例如，一项查询可能只对某一特定人口统计学中的一种度量方法感兴趣，例如，限定于住在美国的人群，或来自某一特定性别的人群，测定会话量，查询某一特定群体，或提及某一特定标签。考虑到应用哪些过滤条件取决于数据分析师对数据集中哪些部分感兴趣，这类过滤条件多为点对点模式，使得传统的一维预定义的索引变得不那么有效。

程序员专属礼品：编程水杯

Cubrick是由Facebook开发的新型分布式多维内存数据库管理系统，其目的在于解决大量数据资源并行运行所存在的问题。为了交互式分析高度动态数据集，Cubrick运用一种用于管理柱形内存数据的新策略，这种策略允许在数据集的每一个维度中进行索引过滤，并有效地实时更新。这种数据管理策略与一种特殊式且经过优化的查询引擎相结合使得Cubrick成为唯一一种适合交互式实时分析的数据管理系统，并且使得Cubrick达到目前数据库解决方案尚未实现的数据管理规模。

本周印度新德里国际顶级数据库会议(VLDB)上我们即将呈现的论文Cubrick: Indexing Millions of Records per second for Interactive Analytics一文中，我们描述了被命名为Granular Partitioning 的Cubrick新型数据管理技术，详细介绍了Cubrick的内部数据结构，分布式模型与查询执行引擎，并将宣布目前Facebook对这种新型数据管理系统的应用情况。

Cubrick的应用现状

通过跳过非必要数据来提高过滤性能的传统数据库技术要么是基于维护索引（辅助数据结构），要么是基于对数据集进行预整理。通过维护辅助索引（如B+Trees）来提高获取特定记录的效率是一种为大多数数据管理系统运用的众所周知的技术，且几乎每一种OLTP数据管理系统均运用这种数据库技术。但是，在OLAP负载中，维护更新索引的对数开销由于被视为表的大小和获取数据速率的度量而被禁止。在存储痕迹中，大多数类型的索引（著名的是二级索引）通过增大所占据的存储空间来存储中等结点和数据指示值，以便于在每一栏建立索引可能会致使存储使用率成倍增长。此外，如何准确地确定索引栏是点对点查询面临的一项挑战。

在查询时间内有效跳过数据的另一途径是预整理数据集。基于C-STROE架构建立的以栏为导向的数据库能够维护按照关键字排序的数据集的多种复制版本——也被称为映射——也能够被用于有效评估按照关键字排序的每一栏中的过滤器性能。尽管一种与LSM-Tree（日志结构的合并树）相似的结构被用于摊还插入所带来的计算成本，随着所获取数据的规模不断扩大，仍然需要大量的数据重组来保证映射结果的实时更新。此外，我们得预先决定要创建哪些映射机器相对应的排序关键字，这些在由点对点查询构成的数据集中难以定义。最后，由于每一次新的映射都是对整个数据集的复制，这种方式不适用于数据管理系统的内存设置，这种数据管理系统试图在其内存中拟合尽可能多的数据集，以避免对硬盘进行繁重访问。

一种新方法

我们已经采用一种新方法而非通过预整理数据集或维护二级索引数据结构这两种方法，来解决如何跳过非必要数据以提高过滤器性能这一问题。假定系统中所有的表格都是被每一维度列进行分区排列的，我们对传统的数据库分区概念进行扩展。同时，能够预先获取每一维度列的基数，这允许我们将数据集理解为一个有更小的超立方体构成的大立方体，在一定程度上更像一个n维魔方。每一个较小的超立方体（或brick,Cubrick的一种术语表达法）代表基数函数分配的一个标识符，以一种无序且附注的形式在每一列中零散地存储数据。最后，我们假定，所有的字符串值都是经过代码编码的，内部是由单调递增的整数表示的。该假设便于我们开发一种仅在原始数据层面运行的经过优化的，精细的数据库引擎。

与其他多维数据库系统相似，Cubrick的每一列均以一种度量或一种维度进行定义，这些维度通常被用于过滤和分组，每一种度量被用于聚合函数中。图1阐释了：在一个由两个维度——区间和性别，基数为4，变化尺寸为2和1，与两种度量——喜好和评论，构成的一个数据集例子中，如何为每一模块分配数据记录。

Facebook是怎么做到每秒索引数百万条记录的？

鉴于有一种连续性的时间函数将每一条记录映射到与之相匹配的目标模块中，而且每一模块中的数据都是无序排列的，这种简单却有效的数据管理方法考虑到非常有效的记录插入。此外，如果在搜索空间内没有插入记录，在查询时间段内，每一模块都能够轻松地与查询过滤器相匹配，并得到梳理。

实验结果

为了评估Cubrick获取记录的速率与获取记录通道所占用的CPU，图8所示为：与CPU占用量相比，每个单一结点簇每秒获取的记录数量。本实验得出以下结论：即使每秒获取的记录数量达到100万，每个单一结点簇所占用的CPU依然处于低水平（20%以下）。

Facebook是怎么做到每秒索引数百万条记录的？

注：当获取不同容量大小的记录时，每个单一结点簇的CPU占用情况

图7所示为在一个72个结点簇处运行的10TB数据集存在的多种潜在查询，旨在评估我们的索引策略是否有效。X轴代表应用过滤器的列，颜色标尺为这种过滤器的局限性，或该数据集与过滤器之间的匹配百分比。实验结果显示，Y轴上的颜色与位置存在明显关联性，与X轴上的位置不相关。换句话来讲，不论处于哪一列，当运用过滤器时，查询速率将得到很大程度的提升。

Facebook是怎么做到每秒索引数百万条记录的？

注：在一个72个结点簇处运行的10TB数据集经不同维度过滤后存在的多种潜在查询

请参考我们在2016年国际顶级数据库会议上发表的论文，获得完整的实验方法与结果。

瞻望未来

在过去几年内，Facebbook曾在多个实时（批量）交互式分析应用实例中采用Cubrick，Cubrick正在迅速成长为一个更为成熟的全功能数据管理系统。关于如何更加有效地处理具有不同数据分布特征的数据集与使这种立方体图式更具动态化，我们还要进行大量的研究求证。我们相信，Cubrick的研发是我们朝向这一目标迈进的第一步，不过，目前该研究领域还存在几个尚未探索且有趣的主题等待我们开展研究。

本文文字及图片出自雷锋网