我们的用户在不知道疲劳的情况下互相写消息。
这是相当多的。 如果你打算读取所有用户的所有消息，则需要超过 150 万年。 前提是您是一位相当高级的读者，并且在每条消息上花费的时间不超过一秒钟。
对于如此大量的数据，以最佳方式构建存储和访问数据的逻辑至关重要。 否则，在某个不那么美妙的时刻，一切可能很快就会出问题。
对我们来说，这一刻已经是一年半前的事了。 我们是如何走到这一步以及最终发生了什么 - 我们按顺序告诉您。
病历
在第一个实现中，VKontakte 消息在 PHP 后端和 MySQL 的组合上运行。 对于小型学生网站来说，这是完全正常的解决方案。 然而，该网站的增长不受控制，并开始要求优化自身的数据结构。
2009 年底，编写了第一个文本引擎存储库，并于 2010 年将消息传输到其中。
在文本引擎中，消息存储在列表中 - 一种“邮箱”。 每个这样的列表都由一个 uid 确定 - 拥有所有这些消息的用户。 消息具有一组属性：对话者标识符、文本、附件等。 “盒子”内的消息标识符是 local_id，它永远不会改变，并为新消息按顺序分配。 这些“盒子”是独立的，引擎内部彼此不同步；它们之间的通信发生在 PHP 级别。 可以从内部看一下text-engine的数据结构和能力 .
这对于两个用户之间的通信来说已经足够了。 你猜接下来发生了什么？
2011 年 XNUMX 月，VKontakte 引入了与多个参与者的对话——多重聊天。 为了与他们合作，我们提出了两个新的集群——member-chats 和 chat-members。 第一个存储有关用户聊天的数据，第二个存储有关用户聊天的数据。 除了列表本身之外，这还包括邀请用户以及他们添加到聊天中的时间等。
“PHP，让我们向聊天室发送一条消息，”用户说。
“来吧，{用户名}，”PHP 说。
该方案也有缺点。 同步仍然是 PHP 的责任。 大型聊天和同时向他们发送消息的用户是一个危险的故事。 由于文本引擎实例取决于 uid，因此聊天参与者可能会在不同时间收到相同的消息。 如果进展停滞不前，人们可以忍受这一点。 但这不会发生。
2015年底，我们推出了社区消息，2016年初，我们推出了社区消息API。 随着社区中大型聊天机器人的出现，人们可能会忘记均匀的负载分配。
一个好的机器人每天会生成数百万条消息 - 即使是最健谈的用户也无法夸耀这一点。 这意味着此类机器人赖以生存的某些文本引擎实例开始受到最大程度的影响。
2016 年的消息引擎包括 100 个聊天成员和成员聊天实例，以及 8000 个文本引擎。 它们托管在 64 台服务器上，每台服务器都有 32 GB 内存。 作为第一个紧急措施，我们将内存再增加了 XNUMX GB。 我们估计了预测。 如果没有重大变化，这大约还够再用一年。 您需要获取硬件或优化数据库本身。
由于架构的性质，只有成倍增加硬件才有意义。 也就是说，至少将汽车数量增加一倍——显然，这是一条相当昂贵的道路。 我们会优化。
新概念
新方法的核心本质是聊天。 聊天有一个与其相关的消息列表。 用户有一个聊天列表。
至少需要两个新数据库：
- 聊天引擎。 这是聊天向量的存储库。 每个聊天都有一个与其相关的消息向量。 每条消息在聊天中都有一个文本和一个唯一的消息标识符 - chat_local_id。
- 用户引擎。 这是用户向量的存储-用户的链接。 每个用户都有一个peer_id向量（对话者-其他用户、多聊天或社区）和一个消息向量。 每个peer_id都有一个与其相关的消息向量。 每条消息都有一个 chat_local_id 和该用户的唯一消息 ID - user_local_id。
新集群使用 TCP 相互通信 - 这可以确保请求的顺序不会改变。 请求本身及其确认记录在硬盘上 - 因此我们可以在引擎发生故障或重新启动后随时恢复队列的状态。 由于用户引擎和聊天引擎各有 4 个分片，因此集群之间的请求队列将均匀分布（但实际上根本没有 - 而且运行速度非常快）。
在大多数情况下，我们数据库中的磁盘操作是基于二进制更改日志 (binlog)、静态快照和内存中的部分映像的组合。 白天的更改会写入二进制日志，并定期创建当前状态的快照。 快照是为我们的目的而优化的数据结构的集合。 它由一个标头（图像的元索引）和一组元文件组成。 标头永久存储在 RAM 中，并指示从快照中查找数据的位置。 每个图元文件都包含在接近的时间点可能需要的数据，例如与单个用户相关的数据。 当您使用快照头查询数据库时，将读取所需的图元文件，然后考虑创建快照后发生的二进制日志中的更改。 您可以阅读有关此方法优点的更多信息 .
同时，硬盘驱动器上的数据每天只更改一次 - 在莫斯科的深夜，此时负载最小。 由于这一点（知道磁盘上的结构全天保持不变），我们可以用固定大小的数组替换向量 - 因此，可以增加内存。
在新方案中发送消息如下所示：
- PHP 后端联系用户引擎并请求发送消息。
- 用户引擎将请求代理到所需的聊天引擎实例，该实例返回到用户引擎 chat_local_id - 此聊天中新消息的唯一标识符。 然后，chat_engine 将消息广播给聊天中的所有收件人。
- 用户引擎从聊天引擎接收 chat_local_id 并将 user_local_id 返回给 PHP - 该用户的唯一消息标识符。 然后使用该标识符，例如通过 API 处理消息。
但除了实际发送消息之外，您还需要实现一些更重要的事情：
- 例如，子列表是您打开对话列表时看到的最新消息。 未读消息、带有标签的消息（“重要”、“垃圾邮件”等）。
- 在聊天引擎中压缩消息
- 在用户引擎中缓存消息
- 搜索（通过所有对话框并在特定对话框中）。
- 实时更新（长轮询）。
- 保存历史记录以在移动客户端上实现缓存。
所有子列表的结构都在快速变化。 为了与他们合作，我们使用 。 这种选择的解释是，我们有时在树的顶部存储快照中的一整段消息 - 例如，在每晚重新索引之后，树由一个顶部组成，其中包含子列表的所有消息。 Splay 树可以轻松插入到此类顶点的中间，而无需考虑平衡。 另外，Splay不会存储不必要的数据，这节省了我们的内存。
消息涉及大量信息，其中大部分是文本，能够进行压缩非常有用。 重要的是我们能够准确地取消存档，即使是一封单独的邮件。 用于压缩消息 通过我们自己的启发法 - 例如，我们知道在消息中单词与“非单词”（空格、标点符号）交替出现 - 而且我们还记得使用俄语符号的一些特殊性。
由于用户比聊天少得多，为了在聊天引擎中保存随机访问磁盘请求，我们将消息缓存在用户引擎中。
消息搜索被实现为从用户引擎到包含该用户聊天的所有聊天引擎实例的对角查询。 结果在用户引擎本身中组合。
好吧，所有细节都已考虑在内，剩下的就是切换到新方案 - 最好是在用户没有注意到的情况下。
数据迁移
因此，我们有一个按用户存储消息的文本引擎，以及两个集群 chat-member 和 member-chats，它们存储有关多聊天室及其中用户的数据。 如何从这个转移到新的用户引擎和聊天引擎？
旧方案中的member-chats主要用于优化。 我们迅速将必要的数据从它转移到聊天成员，然后它就不再参与迁移过程。
聊天成员排队。 它包括 100 个实例，而 chat-engine 有 4 个实例。 要传输数据，您需要使其合规 - 为此，聊天成员被分为相同的 4 个副本，然后在聊天引擎中启用聊天成员 binlog 的读取。
现在聊天引擎知道来自聊天成员的多聊天，但它还不知道与两个对话者的对话。 此类对话位于与用户相关的文本引擎中。 在这里，我们“正面”获取数据：每个聊天引擎实例询问所有文本引擎实例是否有所需的对话。
太棒了 - 聊天引擎知道有哪些多聊天聊天，并且知道有哪些对话。
您需要合并多聊天中的消息，以便最终在每个聊天中得到一个消息列表。 首先，聊天引擎从文本引擎检索此聊天中的所有用户消息。 在某些情况下，它们的数量相当多（多达数亿），但除了极少数例外，聊天完全适合 RAM。 我们有无序的消息，每个消息都有多个副本 - 毕竟，它们都是从与用户相对应的不同文本引擎实例中提取的。 目标是对邮件进行排序并删除占用不必要空间的副本。
每条消息都有一个时间戳，其中包含发送时间和文本。 我们使用时间进行排序 - 我们将指针放置在多聊天参与者最旧的消息上，并比较目标副本文本中的哈希值，从而增加时间戳。 副本具有相同的哈希值和时间戳是合乎逻辑的，但实际上情况并非总是如此。 您还记得，旧方案中的同步是由 PHP 执行的 - 在极少数情况下，不同用户发送同一消息的时间会有所不同。 在这些情况下，我们允许自己编辑时间戳——通常在一秒钟内。 第二个问题是不同收件人的消息顺序不同。 在这种情况下，我们允许创建额外的副本，为不同的用户提供不同的订购选项。
此后，有关多聊天中的消息的数据将发送到用户引擎。 导入消息有一个令人不快的功能。 在正常操作中，到达引擎的消息严格按照 user_local_id 升序排列。 从旧引擎导入到用户引擎的消息失去了这个有用的属性。 同时，为了测试的方便，您需要能够快速访问它们，在其中查找内容并添加新内容。
我们使用特殊的数据结构来存储导入的消息。
它表示一个大小的向量 大家在哪里 - 不同且按降序排列，具有特殊的元素顺序。 在每个带有索引的段中 元素已排序。 在这样的结构中搜索元素需要时间 通过 二分搜索。 增加的元素摊销 .
因此，我们找到了如何将数据从旧引擎传输到新引擎的方法。 但这个过程需要几天的时间——在这些天里我们的用户不太可能放弃互相写信的习惯。 为了在这段时间不丢失消息，我们切换到同时使用新旧集群的工作方案。
数据被写入聊天成员和用户引擎（而不是文本引擎，如根据旧方案的正常操作）。 用户引擎将请求代理到聊天引擎 - 这里的行为取决于该聊天是否已经被合并。 如果聊天尚未合并，则聊天引擎不会将消息写入自身，并且其处理仅在文本引擎中进行。 如果聊天已合并到聊天引擎中，则会将 chat_local_id 返回到用户引擎并将消息发送给所有收件人。 用户引擎将所有数据代理到文本引擎 - 这样，如果发生问题，我们可以随时回滚，将所有当前数据保留在旧引擎中。 text-engine 返回 user_local_id，用户引擎存储该 ID 并将其返回到后端。
因此，转换过程如下所示：我们连接空的用户引擎和聊天引擎集群。 chat-engine 读取整个 chat-members binlog，然后根据上述方案启动代理。 我们传输旧数据并获得两个同步集群（旧的和新的）。 剩下的就是将读取从文本引擎切换到用户引擎并禁用代理。
结果
由于采用了新方法，引擎的所有性能指标都得到了改进，数据一致性问题也得到了解决。 现在我们可以快速在消息中实现新功能（并且已经开始这样做 - 我们增加了聊天参与者的最大数量，实现了对转发消息的搜索，启动了固定消息并提高了每个用户消息总数的限制） 。
逻辑上的变化确实是巨大的。 我想指出的是，这并不总是意味着需要一个庞大的团队和无数行代码进行多年的开发。 聊天引擎和用户引擎以及所有附加故事（例如用于消息压缩的 Huffman、Splay 树和导入消息的结构）不到 20 万行代码。 它们是由 3 位开发人员在短短 10 个月内编写的（但是，值得记住的是 - 世界冠军 ).
此外，我们没有将服务器数量增加一倍，而是将其数量减少了一半——现在用户引擎和聊天引擎运行在 500 台物理机器上，而新方案有很大的负载空间。 我们在设备上节省了大量资金 - 大约 5 万美元 + 每年 750 万美元的运营费用。
我们努力为最复杂和大规模的问题找到最佳解决方案。 我们有很多这样的人 - 这就是我们在数据库部门寻找有才华的开发人员的原因。 如果您热爱并知道如何解决此类问题，并且对算法和数据结构有丰富的了解，我们邀请您加入我们的团队。 联系我们的 了解详情。
即使这个故事与您无关，请注意，我们重视推荐。 告诉朋友 ，如果他成功完成试用期，您将获得100万卢布的奖金。
来源： habr.com