TL;DR：四年前，我离开 Google 时想到了一个新的服务器监控工具。 这个想法是将通常孤立的功能组合成一项服务 以及日志分析、指标收集、 和仪表板。 原则之一是服务必须真实 快速地，为开发人员提供简单、互动、愉快的体验。 这需要在几分之一秒内处理数千兆字节的数据集，同时保持在预算之内。 现有的日志管理工具通常缓慢且笨重，因此我们面临着一个很好的挑战：巧妙地设计一个工具来为用户提供新的体验。
本文介绍了 Scalyr 如何通过应用老式方法（暴力方法）、消除不必要的层并避免复杂的数据结构来解决这个问题。 您可以将这些经验教训应用于您自己的工程问题。
老派力量
日志分析通常从搜索开始：查找与特定模式匹配的所有消息。 在 Scalyr 中，这些是来自许多服务器的数十或数百 GB 的日志。 现代方法通常涉及构建一些针对搜索而优化的复杂数据结构。 我当然在谷歌上看到过这一点，他们在这类事情上非常擅长。 但我们选择了一种更为原始的方法：对日志进行线性扫描。 它起作用了 - 我们提供了一个可搜索的界面，比我们的竞争对手快几个数量级（请参见最后的动画）。
关键的见解是，现代处理器在简单、直接的操作中确实非常快。 在依赖 I/O 速度和网络操作的复杂、多层系统中，这一点很容易被忽视，而且此类系统如今非常常见。 因此，我们开发了一种设计，可以最大限度地减少层数和多余碎片。 多个处理器和服务器并行，搜索速度达到每秒 1 TB。
本文的要点：
- 蛮力搜索是解决现实世界的大规模问题的可行方法。
- 蛮力是一种设计技术，而不是一种无需工作的解决方案。 与任何技术一样，它比其他技术更适合某些问题，并且可能实施得不好或很好。
- 蛮力特别适合实现 稳定 表现。
- 有效使用暴力需要优化代码并在正确的时间应用足够的资源。 如果您的服务器承受着沉重的非用户负载并且用户操作仍然是优先事项，那么它是合适的。
- 性能取决于整个系统的设计，而不仅仅是内循环算法。
（本文描述的是在内存中搜索数据。大多数情况下，当用户执行日志搜索时，Scalyr服务器已经缓存了它。下一篇文章将讨论搜索未缓存的日志。同样的原则适用：高效代码，暴力破解具有大量的计算资源）。
蛮力法
传统上，使用关键字索引来搜索大型数据集。 当应用于服务器日志时，这意味着搜索日志中的每个唯一单词。 对于每个单词，您需要列出所有包含的内容。 这样可以轻松查找包含该单词的所有消息，例如“error”、“firefox”或“transaction_16851951” - 只需查看索引即可。
我在谷歌使用过这种方法，效果很好。 但在 Scalyr 中，我们逐字节搜索日志。
为什么？ 从抽象算法的角度来看，关键词索引比暴力搜索要高效得多。 然而，我们不卖算法，我们卖性能。 而性能不仅仅关乎算法，还关乎系统工程。 我们必须考虑一切：数据量、搜索类型、可用的硬件和软件环境。 我们认为，对于我们的特定问题，“grep”之类的东西比索引更适合。
索引很棒，但也有局限性。 一个词很容易找到。 但搜索包含多个单词（例如“googlebot”和“404”）的消息要困难得多。 搜索像“未捕获的异常”这样的短语需要一个更麻烦的索引，该索引不仅记录带有该单词的所有消息，还记录该单词的具体位置。
当你不寻找词语时，真正的困难就来了。 假设您想查看有多少流量来自机器人。 第一个想法是在日志中搜索“机器人”一词。 您可以通过这种方式找到一些机器人：Googlebot、Bingbot 等等。 但这里的“机器人”不是一个词，而是它的一部分。 如果我们在索引中搜索“bot”，我们将找不到任何包含“Googlebot”一词的帖子。 如果你检查索引中的每个单词，然后扫描索引查找找到的关键字，搜索速度会大大减慢。 因此，某些日志程序不允许部分单词搜索或（最多）允许性能较低的特殊语法。 我们想避免这种情况。
另一个问题是标点符号。 您想查找来自以下位置的所有请求吗 50.168.29.7？ 包含以下内容的调试日志怎么样？ [error]？ 下标通常会跳过标点符号。
最后，工程师喜欢强大的工具，有时问题只能通过正则表达式来解决。 关键字索引不太适合这个。
此外，指数 复杂的。 每条消息都需要添加到多个关键字列表中。 这些列表应始终以易于搜索的格式保存。 包含短语、单词片段或正则表达式的查询需要转换为多列表操作，并对结果进行扫描和组合以生成结果集。 在大规模、多租户服务的背景下，这种复杂性会产生在分析算法时不可见的性能问题。
关键字索引也占用大量空间，存储是日志管理系统的主要成本。
另一方面，每次搜索都会消耗大量的计算能力。 我们的用户喜欢对独特查询进行高速搜索，但此类查询相对较少。 对于典型的搜索查询，例如仪表板，我们使用特殊技术（我们将在下一篇文章中描述它们）。 其他请求并不频繁，因此您很少需要一次处理多个请求。 但这并不意味着我们的服务器不忙：它们忙于接收、分析和压缩新消息、评估警报、压缩旧数据等工作。 因此，我们有相当多的处理器可用于执行查询。
如果你有一个蛮力问题（并且需要很大的力量），那么蛮力就有效
蛮力对于具有小内部循环的简单问题最有效。 通常，您可以优化内部循环以非常高的速度运行。 如果代码很复杂，优化起来就会困难得多。
我们的搜索代码最初有一个相当大的内部循环。 我们将消息存储在 4K 的页面上； 每个页面包含一些消息（UTF-8 格式）和每条消息的元数据。 元数据是一种对值的长度、内部消息 ID 和其他字段进行编码的结构。 搜索周期如下所示：
这是实际代码的简化版本。 但即使在这里，多个对象放置、数据副本和函数调用也是可见的。 JVM 在优化函数调用和分配临时对象方面非常擅长，因此这段代码的效果比我们应得的要好。 在测试过程中，客户使用得相当成功。 但最终我们将其提升到了一个新的水平。
（你可能会问为什么我们以这种4K页面、文本和元数据的格式存储消息，而不是直接使用日志。原因有很多，归结为这样一个事实：Scalyr引擎在内部更像是一个分布式数据库，而不是一个分布式数据库。文件系统。文本搜索通常在日志解析后与 DBMS 风格的过滤器结合起来。我们可以同时搜索数千条日志，而简单的文本文件不适合我们的事务性、复制性、分布式数据管理）。
最初，似乎这样的代码不太适合暴力优化。 “真正的工作”在 String.indexOf() 甚至没有主导CPU配置文件。 也就是说，单独优化这个方法并不会带来明显的效果。
碰巧我们将元数据存储在每个页面的开头，而所有消息的文本以 UTF-8 格式打包在另一端。 利用这一点，我们重写了循环以一次搜索整个页面：
该版本直接在视图上运行 raw byte[] 并在整个 4K 页面上一次搜索所有消息。
这对于蛮力方法来说更容易优化。 内部搜索循环是针对整个 4K 页面同时调用的，而不是针对每个帖子单独调用。 没有数据复制，没有对象分配。 仅当结果为正时才会调用更复杂的元数据操作，而不是针对每条消息。 通过这种方式，我们消除了大量的开销，其余的负载集中在一个小的内部搜索循环中，这非常适合进一步优化。
我们实际的搜索算法是基于 。 它类似于 Boyer-Moore 算法，在每一步中跳过大约搜索字符串的长度。 主要区别在于它一次检查两个字节以最大限度地减少错误匹配。
我们的实现需要为每次搜索创建一个 64K 的查找表，但这与我们正在搜索的千兆字节数据相比根本不算什么。 内部循环在单个核心上每秒处理数千兆字节。 实践中，每个核心的稳定性能约为每秒 1,25 GB，并且还有改进的空间。 消除内部循环之外的一些开销是可能的，我们计划用 C 而不是 Java 来试验内部循环。
我们使用武力
我们讨论过日志搜索可以“大致”实现，但是我们有多少“力量”呢？ 非常多。
1 核：如果使用得当，现代处理器的单核本身就非常强大。
8核：我们目前在 Amazon hi1.4xlarge 和 i2.4xlarge SSD 服务器上运行，每个服务器都有 8 个核心（16 个线程）。 如上所述，这些核心通常忙于后台操作。 当用户执行搜索时，后台操作会暂停，从而释放所有 8 个内核用于搜索。 搜索通常会在一瞬间完成，然后后台工作就会恢复（限制程序可确保大量搜索查询不会干扰重要的后台工作）。
16核：为了可靠性，我们将服务器分为主/从组。 每个Master麾下有一台SSD和一台EBS服务器。 如果主服务器崩溃，SSD服务器会立即接替。 几乎所有时候，master和slave都工作得很好，这样每个数据块在两个不同的服务器上都是可搜索的（EBS从服务器的处理器很弱，所以我们不考虑它）。 我们将任务分配给它们，这样我们总共就有 16 个可用核心。
多核：在不久的将来，我们将在服务器之间分配数据，让它们都参与处理每个重要的请求。 每个核心都会工作。 [笔记： 我们实施了该计划，并将搜索速度提高到 1 TB/s，请参阅文章末尾的注释].
简单性确保可靠性
蛮力方法的另一个优点是其相当一致的性能。 通常，搜索对问题和数据集的细节不是很敏感（我想这就是为什么它被称为“粗略”）。
关键字索引有时会产生令人难以置信的快速结果，而有时却不会。 假设您有 50 GB 的日志，其中术语“customer_5987235982”恰好出现了 XNUMX 次。 对该术语的搜索直接从索引中计算三个位置，并将立即完成。 但复杂的通配符搜索可能会扫描数千个关键字，并且需要很长时间。
另一方面，对于任何查询，暴力搜索的执行速度都或多或少相同。 搜索长单词更好，但即使搜索单个字符也相当快。
蛮力方法的简单性意味着其性能接近其理论最大值。 对于意外磁盘过载、锁争用、指针追逐以及数千种其他失败原因的选择较少。 我刚刚查看了 Scalyr 用户上周在我们最繁忙的服务器上提出的请求。 有 14 个请求。 其中有八个花了超过一秒的时间； 000% 在 99 毫秒内完成（如果你没有使用过日志分析工具，相信我： 它很快).
稳定、可靠的性能对于服务的易用性非常重要。 如果它周期性地滞后，用户会认为它不可靠并且不愿意使用它。
运行中的日志搜索
这是一个简短的动画，展示了 Scalyr 搜索的实际情况。 我们有一个演示帐户，我们可以在其中导入每个公共 Github 存储库中的每个事件。 在此演示中，我检查了一周的数据：大约 600 MB 的原始日志。
视频是现场录制的，无需特殊准备，就在我的桌面上（距离服务器约5000公里）。 您将看到的性能很大程度上取决于 ，以及快速可靠的后端。 每当出现没有“正在加载”指示器的暂停时，都是我暂停，以便您可以阅读我要按的内容。
总之
在处理大量数据时，选择好的算法很重要，但“好”并不意味着“花哨”。 考虑一下您的代码在实践中将如何工作。 算法的理论分析遗漏了一些在现实世界中可能非常重要的因素。 更简单的算法更容易优化并且在边缘情况下更稳定。
还要考虑执行代码的上下文。 在我们的例子中，我们需要足够强大的服务器来管理后台任务。 用户发起搜索的频率相对较低，因此我们可以在完成每次搜索所需的短时间内借用整组服务器。
使用强力方法，我们在一组日志中实现了快速、可靠、灵活的搜索。 我们希望这些想法对您的项目有用。
编辑： 标题和文本已从“每秒 20 GB 搜索”更改为“每秒 1 TB 搜索”，以反映过去几年的性能提升。 速度的提高主要是由于我们今天为服务不断增加的客户群而安装的 EC2 服务器的类型和数量发生了变化。 即将发生的变化将进一步显着提高运营效率，我们迫不及待地想分享这些变化。
来源： habr.com