TL；博士：四年前，我离开Goog​​le时，有了一个用于监视服务器的新工具的想法。 这个想法是将通常隔离的功能（ 收集和分析日志，收集指标， 警报和仪表板）组合到一项服务中。 原则之一-服务应该真正快速 ，为开发人员提供轻松，互动，愉快的工作。 这就需要在一秒钟内处理数GB的数据集，而又不会超出预算。 现有的用于处理日志的工具通常很慢且笨拙，因此我们面临着一项艰巨的任务：正确开发一种工具，使用户从工作中获得新的感觉。

本文介绍了Scalyr我们如何通过应用传统方法，蛮力方法，消除冗余层并避免复杂的数据结构来解决此问题。 您可以将这些课程应用于自己的工程任务。

老派的实力

日志分析通常从搜索开始：查找与特定模板匹配的所有消息。 在Scalyr中，这些是来自许多服务器的数十或数百GB的日志。 通常，现代方法涉及构建一些针对搜索优化的复杂数据结构。 当然，我在Google上看到了这一点，他们在这些方面非常擅长。 但是我们决定采用一种更为粗糙的方法：对日志进行线性扫描。 它确实有效-我们提供的搜索界面比竞争对手快一个数量级（请参见最后的动画）。

关键的见解是，现代处理器在简单，直接的操作中确实非常快。 在依赖于I / O速度和网络操作的复杂的多层系统中，这一点很容易被忽略，并且这种系统在当今非常普遍。 因此，我们开发了一种设计，该设计可最大程度地减少层数和多余的垃圾。 并行使用多个处理器和服务器，搜索速度达到每秒1 TB。

本文的主要发现：

• 粗略搜索是解决实际大规模问题的可行方法。
  
• 蛮力是一种设计技术，不是从工作中解放出来。 与任何技术一样，它比某些技术更适用于某些问题，并且实施效果不佳。
  
• 蛮力对于稳定性能特别好。
  
• 有效使用暴力需要代码优化和及时使用足够的资源。 如果您的服务器承受着大量的非用户工作量并且用户操作仍然是优先事项，则这是合适的。
  
• 性能取决于整个系统的设计，而不仅取决于内部循环算法。

（本文介绍了如何在内存中搜索数据。在大多数情况下，当用户搜索日志时，Scalyr服务器已经将其缓存了。在下一篇文章中，我们将讨论通过未缓存的日志进行搜索。相同的原理适用于：高效代码，具有大量计算能力的蛮力方法资源）。

蛮力法

传统上，在大型数据集中使用关键字索引进行搜索。 应用于服务器日志时，这意味着搜索日志中的每个唯一单词。 对于每个单词，您需要列出所有包含的内容。 这使得查找带有该词的所有消息变得容易，例如“错误”，“ firefox”或“ transaction_16851951”-只需在索引中查找即可。

我在Google上使用了这种方法，效果很好。 但是在Scalyr中，我们逐字节查看日志。

怎么了 从抽象算法的角度来看，关键字索引比粗略搜索有效得多。 但是，我们不出售算法；我们出售性能。 性能不仅是算法，而且是系统工程。 我们必须考虑所有因素：数据量，搜索类型，可用的硬件和软件环境。 我们认为对于我们的特定问题，像“ grep”这样的选项比索引更好。

索引很棒，但是有局限性。 一个字很容易找到。 但是查找带有几个单词的消息（例如“ googlebot”和“ 404”）已经非常复杂。 搜索“未捕获的异常”之类的短语需要一个更麻烦的索引，该索引不仅会记录该单词的所有消息，而且还会记录该单词的特定位置。

当您不寻找单词时，真正的困难就来了。 假设您想查看来自机器人的流量。 首先想到的是在日志中搜索单词“ bot”。 因此，您会发现一些机器人：Googlebot，Bingbot和许多其他机器人。 但是这里的“机器人”不是一个词，而是其中的一部分。 如果我们在索引中搜索“机器人”，则不会找到带有“ Googlebot”一词的邮件。 如果您检查索引中的每个单词，然后在索引中扫描找到的关键字，则搜索速度将大大降低。 结果，某些用于处理日志的程序不允许搜索单词的一部分，或者（最多）允许使用性能较低的特殊语法。 我们要避免这种情况。

另一个问题是标点符号。 是否想要查找来自50.168.29.7所有请求？ 如何调试包含[error]日志？ 索引通常跳过标点符号。

最后，工程师喜欢强大的工具，有时问题只能用正则表达式解决。 关键字索引不太适合此操作。

另外，索引很复杂 。 每条消息必须添加到几个关键字列表中。 这些列表应始终以易于搜索的格式保存。 必须将具有短语，单词片段或正则表达式的查询转换为具有多个列表的操作，然后对结果进行扫描和合并以获得结果集。 在大规模多用户服务的情况下，这种复杂性会导致性能问题，而这些问题在分析算法时是不可见的。

关键字索引也占用大量空间，而存储是日志管理系统中的主要成本项目。

另一方面，每次搜索会花费大量计算能力。 我们的用户重视对独特查询的高速搜索，但是这种查询相对较少。 对于典型的搜索查询，例如对于仪表板，我们使用特殊的技术（我们将在下一篇文章中对其进行描述）。 其他查询很少见，因此您一次不需要处理多个查询。 但这并不意味着我们的服务器并不忙：它们忙于接收，分析和压缩新消息，评估警报，压缩旧数据等工作。 因此，我们有大量可用于满足请求的处理器。

如果您遇到蛮力问题（蛮力），蛮力就可以工作

蛮力在具有较小内部循环的简单任务上效果最佳。 通常，您可以优化内循环以使其以很高的速度工作。 如果代码很复杂，优化起来就困难得多。

最初，我们的搜索代码具有相当大的内部循环。 我们将邮件存储在4K页面上； 每个页面包含一些消息（以UTF-8格式）和每个消息的元数据。 元数据是一种对值的长度，内部消息ID和其他字段进行编码的结构。 搜索循环如下所示：



与实际代码相比，这是一个简化的选项。 但是即使在这里，您也可以看到几个对象放置，数据副本和函数调用。 JVM很好地优化了函数调用并分配了临时对象，因此此代码的工作效果比我们应得的更好。 在测试期间，客户非常成功地使用了它。 但最终，我们迈上了一个新台阶。

（您可能会问，为什么我们以这种格式存储包含4K页，文本和元数据的消息，而不是直接使用日志？原因很多，为什么内部Scalyr引擎更像是分布式数据库，而不是分布式数据库。文件系统日志分析后，文本搜索通常与字段中的DBMS样式过滤器结合使用我们可以同时搜索成千上万的日志，而简单的文本文件不适合我们的事务性，复制性和分布式控制 数据）。

最初，这种代码似乎不太适合在蛮力方法下进行优化。 String.indexOf()的“实际作业”甚至没有支配CPU配置文件。 即，仅对该方法的优化不会带来明显的效果。

碰巧我们将元数据存储在每一页的开头，而所有消息的文本都以UTF-8打包在另一端。 利用这一点，我们一次重写了整个页面的搜索循环：



此版本直接在raw byte[]视图上工作，并一次在整个4K页面上搜索所有消息。

优化暴力破解要容易得多。 内部搜索周期是针对整个4K页面同时调用的，而不是针对每条消息单独调用的。 没有数据复制，没有对象选择。 使用元数据进行更复杂的操作只会得到肯定的结果，而不是针对每条消息。 因此，我们消除了大量的开销，而其余的负载则集中在一个小的内部搜索周期中，这非常适合进一步优化。

我们的实际搜索算法基于Leonid Volnitsky的出色思想 。 它与Boyer-Moore算法相似，只是在每个步骤中略过搜索字符串的长度。 主要区别在于，它一次检查两个字节以最小化错误匹配。

我们的实现要求为每个搜索创建一个64K的查询表，但是与我们要寻找的GB数据相比，这是毫无意义的。 内部循环在单个内核上每秒处理几GB。 实际上，每个内核的稳定性能约为每秒1.25 GB，并且有改进的潜力。 您可以消除内部循环之外的一些开销，并且我们计划在C而不是Java中尝试内部循环。

施力

我们讨论了日志搜索可以“大致”实现，但是我们拥有多少“功能”？ 很多

1核 ：如果正确使用，现代处理器的一个核本身就非常强大。

8个核心 ：我们目前正在使用Amazon hi1.4xlarge和i2.4xlarge SSD服务器，每个服务器都有8个核心（16个线程）。 如上所述，通常这些内核忙于后台操作。 当用户执行搜索时，后台操作将暂停，将所有8个内核释放出来进行搜索。 搜索通常在瞬间完成，然后继续进行后台工作（控制器程序确保一系列搜索查询不会干扰重要的后台工作）。

16个核心 ：为了提高可靠性，我们将服务器分为主/从组。 每个主服务器都有一台SSD服务器和一个EBS下属。 如果主服务器崩溃，则SSD上的服务器将立即取代其位置。 几乎所有时间，主服务器和从服务器都能正常工作，因此可以在两个不同的服务器上搜索每个数据块（从EBS服务器的处理器较弱，因此我们不考虑）。 我们在它们之间划分任务，因此我们总共有16个内核。

许多核心 ：在不久的将来，我们将在服务器之间分发数据，以便它们都参与每个非平凡请求的处理。 每个核心都会工作。 [注意： 我们实施了该计划，并将搜索速度提高到1 TB / s，请参阅文章末尾的注释 ]。

简单性提供可靠性

蛮力的另一个优点是其相对稳定的性能。 通常，搜索对任务和数据集的细节不太敏感（我认为这就是为什么它被称为“粗鲁”）。

关键字索引有时会产生令人难以置信的快速结果，但在其他情况下却不会。 假设您有50 GB的日志，其中“ customer_5987235982”一词恰好出现了3次。 通过该词进行的搜索直接从索引中计算出三个位置，并立即结束。 但是复杂的通配符搜索可以扫描成千上万个关键字，并花费大量时间。

另一方面，对任何查询的蛮力搜索都以大致相同的速度执行。 搜索长字更好，但是即使搜索单个字符也足够快。

蛮力法的简单性意味着它的生产率接近理论最大值。 对于意外的磁盘过载，锁冲突，指针追逐以及成千上万的其他失败原因，有较少的选择。 我只是在上周最忙的服务器上查看了Scalyr用户提出的请求。 有14,000个请求。 恰好有八个人花了超过一秒钟的时间； 99％的代码在111毫秒内执行了（如果您还没有使用日志分析工具，请相信我： 这很快 ）。

稳定，可靠的性能对于使用服务的便利性很重要。 如果它定期变慢，用户会认为它不可靠并且不愿意使用它。

进行日志搜索

这是一个小动画，显示了Scalyr的搜索操作。 我们有一个模拟帐户，可以在其中将每个公共Github存储库中的每个事件导入。 在此演示中，我研究了本周的数据：大约600 MB的原始日志。

该视频未经特别准备就在我的台式机（距服务器约5000公里）上实时录制。 您将看到的性能很大程度上是由于Web客户端的优化以及快速可靠的后端。 只要有没有“正在加载”指示灯的暂停，我都会暂停它，以便您可以阅读要点击的内容。

总结

在处理大量数据时，选择一个好的算法很重要，但是“好的”并不意味着“花哨的”。 考虑一下您的代码在实践中将如何工作。 在现实世界中可能非常重要的一些因素不在算法的理论分析范围之内。 更简单的算法更容易优化，并且在临界情况下更稳定。

还考虑代码将在其中执行的上下文。 就我们而言，我们需要足够强大的服务器来管理后台任务。 用户相对很少启动搜索，因此我们可以在完成每个搜索所需的短时间内借用一整组服务器。

我们使用蛮力对一组日志进行了快速，可靠，灵活的搜索。 我们希望这些想法对您的项目有用。

编辑： 标题和文本从“每秒20 GB搜索”更改为“每秒1 TB搜索”，以反映过去几年性能的提高。 速度的提高主要归因于我们今天为服务于不断增长的客户群而提高的EC2服务器的类型和数量。 在不久的将来，预计将发生变化，这将进一步提高工作效率，我们期待有机会对此进行介绍。