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 拥有。2010 年还没有 LevelDB，而 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，我们了解了列存储数据库如何处理非聚合数据的临时分析任务。如果您能够从非聚合数据中检索任何报表，那么就会引发一个问题，即数据是否需要像我们对 Metrage 所做的那样提前聚合。

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

• 您需要提前拥有用户需要的报表列表；换句话说，用户无法创建自定义报表。
• 当聚合大量键时，数据量不会减少，聚合毫无用处；当报表很多时，聚合选项过多（组合爆炸）。
• 当聚合高基数键（例如 URL）时，由于此原因，数据量不会大幅减少（减少不到一半），因此数据量可能不会减少，反而会在聚合过程中增加。
• 用户不会查看我们为他们计算的所有报表（换句话说，很多计算都证明是无用的）。
• 在存储大量不同聚合时，难以维护逻辑一致性。

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

因此，如果我们预先聚合数据，那么我们应该持续（实时）进行聚合，但相对于用户查询而言是异步的。我们确实应该实时聚合数据；收到的报表很大一部分应该由准备好的数据组成。

如果数据没有预先聚合，那么所有工作都必须在用户请求时完成（即他们在等待报表页面加载时）。这意味着需要处理数十亿行数据以响应用户的查询；处理速度越快越好。

为此，您需要一个良好的列存储数据库。市场上没有任何列存储数据库能够很好地处理 Runet（俄罗斯互联网）规模的互联网分析任务，并且许可证费用不会过高。

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

在 Yandex，我们开发了，后来开源了我们自己的列存储数据库——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，您可以获得关系数据库的便利性。

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

ClickHouse 非常适合创建各种分析工具。请考虑：如果系统能够应对 Yandex.Metrica 的挑战，那么您可以确定 ClickHouse 将能够处理其他任务，并有大量的性能冗余。

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

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

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

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

在传统系统中，数据就像一个死重，比喻地说。您可以操作它，但这需要花费很多时间并且很不方便。但是，如果您的数据位于 ClickHouse 中，它会更具可塑性：您可以从不同的横截面研究它，并深入到单个数据行。

Yandex.Metrica 已成为全球第二大 Web 分析系统。Metrica 接收的数据量从 2009 年的每天 2 亿次事件增长到 2016 年的超过 250 亿次。为了在满足日益增长的工作负载的同时为用户提供各种选择，我们不得不不断修改我们的数据存储方法。

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

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

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