Yandex.Metrica 中数据结构的演变

Yandex.Metrica 接收代表网站或应用程序上发生的事件的数据流。我们的任务是保存这些数据，并以可分析的形式呈现出来。真正的挑战在于确定处理后的结果应该以何种形式保存，以便于使用。在开发过程中，我们不得不彻底改变了数据存储组织的方案数次。我们从 MyISAM 表开始，然后使用了 LSM 树，最终提出了列式数据库 ClickHouse。

Metrica 在成立之初被设计为 Yandex.Direct（搜索广告服务）的分支。Direct 中使用带有 MyISAM 引擎的 MySQL 表来存储统计数据，因此很自然地在 Metrica 中使用了相同的方法。最初，网站的 Yandex.Metrica 拥有 40 多种“固定”报告类型（例如，访问者地理报告）、几种页面内分析工具（如点击地图）、Webvisor（用于非常详细地研究个人用户行为的工具）以及单独的报告构建器。但随着时间的推移，为了跟上业务目标，系统必须变得更加灵活，并为客户提供更多的自定义机会。如今，Metrica 不再使用固定报告，而是允许自由添加新的维度（例如，在关键字报告中，您可以进一步按着陆页细分数据）、分段和比较（例如，所有访问者的流量来源与来自莫斯科的访问者之间的比较）、更改您的指标集等。这些功能需要与我们使用 MyISAM 时完全不同的数据存储方法，我们将在下文中从技术角度讨论这种转变。

大多数用于获取报告数据的 SELECT 查询都带有条件 WHERE CounterID = AND Date BETWEEN min_date AND max_date。有时还会有按区域筛选的条件，因此使用复合主键将此转换为主键范围读取是有意义的。因此，Metrica 的表模式如下所示：CounterID、Date、RegionID -> Visits、SumVisitTime 等。现在我们来看看当数据进入时会发生什么。

MyISAM 表由数据文件和索引文件组成。如果表中没有任何内容被删除，并且在更新期间行长度没有改变，则数据文件将由按添加顺序连续排列的序列化行组成。索引（包括主键）是一棵 B 树，其中叶子包含数据文件中的偏移量。当我们读取索引范围数据时，会从索引中获取数据文件中的大量偏移量。然后，针对数据文件中的这组偏移量发出读取操作。

让我们看看实际情况，当索引在 RAM 中（MySQL 中的键缓存或系统页面缓存），但表数据未缓存时。假设我们正在使用 HDD。读取数据所需的时间取决于需要读取的数据量以及需要运行多少次 Seek 操作。Seek 的次数由数据在磁盘上的局部性决定。

数据局部性图示：

Metrica 事件的接收顺序几乎与它们实际发生的顺序相同。在这个传入的数据流中，来自不同计数器的数据完全随机地分散。换句话说，传入的数据在时间上是局部的，但在 CounterID 上不是局部的。当写入 MyISAM 表时，来自不同计数器的数据也相当随机地放置。这意味着要读取数据报告，您将需要执行的随机读取次数与表中所需的行数大致相同。

典型的 7200 rpm 硬盘每秒可以执行 100 到 200 次随机读取。如果使用得当，RAID 可以处理的数量是其磁盘数量的倍数。一块五年新的 SSD 每秒可以执行 30,000 次随机读取，但我们无法负担将数据保存在 SSD 上。因此，在这种情况下，如果我们需要读取 10,000 行报告，则需要 10 秒以上，这是完全不可接受的。

InnoDB 更适合读取主键范围，因为它使用了聚集主键（即，数据按主键有序存储）。但是，由于 InnoDB 的写入速度慢，因此无法使用它。如果这让您想起了TokuDB，请继续阅读。

为了使 Yandex.Metrica 在 MyISAM 上正常工作，需要进行大量的技巧，例如定期表排序、复杂的手动分区方案以及将数据保存在世代中。这种方法也有许多操作上的缺点，例如复制速度慢、一致性、恢复不可靠等。尽管如此，截至 2011 年，我们在 MyISAM 表中存储了超过 5800 亿行数据。

Metrage 是LSM 树的实现，这是一种相当常见的数据结构，非常适合具有密集写入流和主要主键读取的工作负载，例如 Yandex.Metrica。LevelDB 在 2010 年尚不存在，而 TokuDB 当时是专有的。

在 Metrage 中，任意数据结构（在编译时固定）可以用作其中的“行”。每一行都是键值对。键是一个具有用于相等和不等比较操作的结构。值是一个任意结构，具有更新（添加某些内容）和合并（聚合或与另一个值组合）的操作。简而言之，它是一个 CRDT。数据在硬盘上相当局部地存储，因此主键范围读取速度很快。即使使用快速算法，数据块也能有效地压缩，因为是有序的（2010 年我们使用了 QuickLZ，自 2011 年以来使用了 LZ4）。以系统的方式存储数据使我们能够使用稀疏索引。

由于读取不是很频繁地执行（即使在执行时读取大量行），因此由于有许多块和解压缩数据块而导致的延迟增加并不重要。由于索引稀疏性而读取额外的行也没有什么影响。

在将报告从 MyISAM 转移到 Metrage 后，我们立即看到了 Metrica 界面速度的提升。以前 90% 的页面标题报告加载时间为 26 秒，而使用 Metrage 后，加载时间为 0.8 秒（总时间，包括处理所有数据库查询和后续数据转换的时间）。根据百分比，Metrage 本身处理查询（对于所有报告）所花费的时间如下：平均值 = 6 毫秒，90 分位数 = 31 毫秒，99 分位数 = 334 毫秒。

我们已经使用 Metrage 五年了，事实证明它是一个可靠的解决方案。截至 2015 年，我们在 Metrage 中存储了 3.37 万亿行数据，并为此使用了 39 * 2 台服务器。

它的优点是简单性和有效性，这使其成为比 MyISAM 更好的数据存储选择。尽管该系统仍然存在一个巨大的缺点：它实际上只在固定报告下有效工作。Metrage 聚合数据并保存聚合数据。但是为了做到这一点，您必须提前列出所有您想要聚合数据的方式。因此，如果我们以 40 种不同的方式进行此操作，则意味着 Metrica 将包含 40 种类型的报告，仅此而已。

为了缓解这种情况，我们不得不暂时保留一个用于自定义报表向导的单独存储，称为 OLAPServer。它是列式数据库的一个简单且非常有限的实现。它只支持编译时设置的一个表——会话表。与 Metrage 不同，数据不是实时更新的，而是在每天更新几次。唯一支持的数据类型是 1-8 字节的定长数字，因此它不适合包含其他类型数据（例如 URL）的报告。

通过使用 OLAPServer，我们了解了列式 DBMS 如何很好地处理带有非聚合数据的即席分析任务。如果您可以从非聚合数据中检索任何报告，那么就会引出一个问题，即是否甚至需要像我们使用 Metrage 那样提前聚合数据。

一方面，预聚合数据可以减少在加载报告页面时使用的数据量。另一方面，聚合数据并不能解决所有问题。以下是原因：

• 您需要提前准备好用户需要的报告列表；换句话说，用户无法组合自定义报告
• 当聚合大量键时，数据量不会减少，聚合是无用的；当有很多报告时，聚合选项太多（组合爆炸）
• 当聚合高基数键（例如 URL）时，由于这个原因，数据量不会减少太多（减少不到一半），数据量可能不会减少，而实际上会在聚合期间增长
• 用户不会查看我们为他们计算的所有报告（换句话说，许多计算证明是无用的）
• 当存储大量不同的聚合时，很难维护逻辑一致性

如您所见，如果没有任何聚合，并且我们使用非聚合数据，那么计算量甚至可能会减少。但是，仅使用非聚合数据对执行查询的系统的效率提出了非常高的要求。

因此，如果我们提前聚合数据，那么我们应该不断地（实时地）进行聚合，但相对于用户查询异步进行。我们真的应该只是实时聚合数据；接收到的报告的很大一部分应该由准备好的数据组成。

如果数据没有提前聚合，则所有工作都必须在用户请求时完成（即在他们等待报告页面加载时）。这意味着需要处理数百亿行数据才能响应用户的查询；越快完成越好。

为此，您需要一个好的列式 DBMS。市场上没有任何列式 DBMS 能够很好地处理 Runet（俄罗斯互联网）规模的互联网分析任务，并且许可成本也不会高得令人望而却步。

最近，作为商业列式 DBMS 的替代方案，用于分布式计算系统中数据高效即席分析的解决方案开始出现：Cloudera Impala、Spark SQL、Presto 和 Apache Drill。尽管此类系统可以有效地处理内部分析任务的查询，但很难想象它们会成为可供外部用户访问的分析系统的 Web 界面的后端。

在 Yandex，我们开发并后来开源了我们自己的列式 DBMS — ClickHouse。让我们回顾一下我们在开始开发之前考虑的基本要求。

能够处理大型数据集。在当前的网站 Yandex.Metrica 中，ClickHouse 用于存储所有报告数据。截至 2016 年 11 月，该数据库由 18.3 万亿行组成。它由非聚合数据组成，用于实时检索报告。最大表中的每一行都包含 200 多个列。

系统应线性扩展。ClickHouse 允许您根据需要添加新服务器来增加集群的大小。例如，Yandex.Metrica 的主集群在三年内从 60 台服务器增加到 426 台服务器。为了实现容错，我们的服务器分布在不同的数据中心。ClickHouse 可以使用所有硬件资源来处理单个查询。这样，每秒可以处理超过 2 TB 的数据。

高效率。我们特别为我们数据库的高性能感到自豪。根据内部测试结果，ClickHouse 处理查询的速度比我们能获得的任何其他系统都快。例如，ClickHouse 的工作速度平均比 Vertica 快 2.8-3.4 倍。ClickHouse 没有什么灵丹妙药能使系统如此快速地工作。

功能应足以满足 Web 分析工具的需求。该数据库支持 SQL 语言方言、子查询和 JOIN（本地和分布式）。有许多 SQL 扩展：用于 Web 分析的函数、数组和嵌套数据结构、高阶函数、用于使用草图进行近似计算的聚合函数等。通过使用 ClickHouse，您可以获得关系型 DBMS 的便利性。

ClickHouse 最初由 Yandex.Metrica 团队开发。此外，我们能够使系统足够灵活和可扩展，以便它可以成功地用于不同的任务。尽管该数据库可以在大型集群上运行，但它也可以安装在一台服务器甚至虚拟机上。我们公司内部现在有十几个不同的 ClickHouse 应用程序。

ClickHouse 非常适合创建各种分析工具。试想一下：如果该系统能够应对 Yandex.Metrica 的挑战，您可以确信 ClickHouse 将能够胜任其他任务，并具有充足的性能余量。

ClickHouse 作为时间序列数据库运行良好；在 Yandex，它通常用作 Graphite 的后端，而不是 Ceres/Whisper。这使我们能够在单个服务器上处理超过 1 万亿个指标。

ClickHouse 被分析部门用于内部任务。根据我们在 Yandex 的经验，ClickHouse 的性能比传统数据处理方法（MapReduce 上的脚本）高出约三个数量级。但这不仅仅是一个简单的数量差异。事实是，通过拥有如此高的计算速度，您可以负担得起采用完全不同的问题解决方法。

如果分析师必须制作报告，并且他们胜任他们的工作，他们不会只是继续构建一份报告。相反，他们将首先检索数十份其他报告，以更好地了解数据的性质并测试各种假设。从不同的角度查看数据以提出和检查新假设通常很有用，即使您没有明确的目标。

只有当数据分析速度允许您进行在线研究时，这才有可能实现。查询执行速度越快，您可以测试的假设就越多。使用 ClickHouse，人们甚至会感觉到他们能够更快地思考。

在传统系统中，数据就像一块沉重的负担，比喻来说。您可以操作它，但这需要大量时间并且很不方便。但是，如果您的数据在 ClickHouse 中，它会更具延展性：您可以研究不同的横截面并向下钻取到各个数据行。

Yandex.Metrica 已成为世界第二大 Web 分析系统。Metrica 接收的数据量从 2009 年的每天 2 亿个事件增长到 2016 年的超过 250 亿个事件。为了在跟上不断增加的工作负载的同时为用户提供广泛的选择，我们不得不不断修改我们的数据存储方法。

有效的硬件利用率对我们非常重要。根据我们的经验，当您拥有大量数据时，最好不要太担心系统扩展性如何，而是专注于如何有效地利用每个资源单元：每个处理器核心、磁盘和 SSD、RAM 和网络。毕竟，如果您的系统已经使用了数百台服务器，并且您必须提高十倍的效率，那么无论您的系统可扩展性如何，您都不太可能只是继续安装数千台服务器。

为了最大限度地提高效率，重要的是定制您的解决方案以满足特定类型工作负载的需求。没有一种数据结构可以很好地应对完全不同的场景。例如，很明显，键值数据库不适用于分析查询。系统负载越大，所需的专业化程度就越窄。不应害怕为不同的任务使用完全不同的数据结构。

我们能够将 Yandex.Metrica 的硬件设置得相对便宜。这使我们能够为非常大的网站和移动应用程序（甚至比 Yanex 自己的网站和应用程序更大）免费提供服务，而竞争对手通常开始要求付费订阅计划。