搜索速度达到20GB/秒的日志管理平台实践要素

日志管理 算法

作者：Steve Newman。本文的翻译和发布已获授权，点击这里阅读英文原文。

四年前，我怀揣打造一种全新服务器监控工具的想法离开了Google。当时我的想法是将日志探索、日志汇总和分析、指标收集、警报，以及仪表盘等传统的，相互独立的功能结合在一起，打造一个一体式服务。这种服务必须足够快速，为运维团队提供一种轻巧、交互式的“愉快”体验。这就要求该服务必须能在不到一秒的时间内分析数GB数据集，同时实现这一切的成本必须足够低。现有的日志管理工具通常又慢又笨重，因此我们当时面临了不小的挑战。好在这对我们也是一次机会，可以通过自己的努力打造一种全新用户体验。

本文介绍了我们是如何使用“老派”的暴力方法消除不必要的软件层，避免处理复杂的数据结构，以应对这一挑战的。我们学到的一些经验也可以帮你应对开发过程中遇到的挑战。

老派做法的强大之处

日志探索通常从搜索开始的的，借此找出符合某种模式的所有信息。对于Scalyr来说，这一过程可能需要处理从多台服务器收集的数十甚至上百GB日志。解决这一问题的现代化方式通常需要构建一些复杂的，专门针对搜索进行优化的数据结构。我在Google工作时他们就是这样做的，他们都很擅长做这种工作。但Scalyr采取了一种更为暴力的方法：对整个日志进行线性扫描。这种方法同样有效，我们通过这种方式提供了丰富的日志探索体验，而这种方法的速度足以让竞争对手汗颜。（如想知道这个工具长什么样，请查看文末嵌入的视频。）

这里的关键在于，面对简单直接的线性操作，现代化处理器可以用非常非常快的速度处理。但面对目前十分普遍的，对I/O和网络有一定要求的复杂分层式系统就有些力不从心了。因此我们采用了一种可以将分层和各种晦涩需求降至最低的系统设计。通过并行使用多个处理器和服务器，现实环境中我们已实现20GB/s的搜索速度，注意，数据量的单位是GB，而非Gb！预计很快将实现100GB/s的速度，这套系统的速度还有很大的提升空间。

本文希望体现的一些重点包括：

• 在现实世界中，暴力法是解决一些大规模问题切实可行的方法。
• 暴力法是一种工程技术，但并不能帮你自动解决所有问题。与其他任何技术类似，这种方法有适合的场合，也有不适合的场合，应用后的效果可能也各不相同。
• 在提供一致的性能过程中，暴力法的效果非常好。
• 若要高效率地使用暴力法，需要对代码进行精简，并且必须能以及时的方式提供足够多的“暴力”。如果你的服务器上运行了大量无需面向用户的工作负载，并能让所有面向用户的操作获得更高优先级，此时就适合使用这种方法。在为每个用户请求提供服务时，我们会尽量使用服务器的所有运算能力。
• 用户最终可以获得的性能取决于整个系统的设计，而不仅仅取决于内循环算法（Inner-loop algorithm）。

（本文介绍了内存中数据的搜索。大部分时候当用户搜索日志时，Scalyr服务器已经将相关日志缓存在内存中。随后我们将另外发布一篇文章介绍如何搜索未缓存的日志。但总的原则是相似的：用精简的暴力搜索代码处理海量资源。）

暴力法的选择

以往，大规模数据集的搜索是通过关键字索引进行的。服务器日志的搜索也是如此，这意味着需要找出日志中出现的每个单字。对于每个字，我们会通过列表列出包含这个字的所有日志信息。这样就可以很容易地找到包含这个字的所有信息，例如“错误”或“Firefox”，或“transaction_16851951”，读取该字对应的列表即可。

我在Google从事的一些项目也使用了这样的方法，效果还不错。但在Scalyr，当用户需要搜索日志时，我们会用逐个字节的方式搜索他的日志。

为什么要这样做？从抽象算法的角度来看，关键字索引的效率远远超过暴力法搜索。然而我们销售的并不是算法而是性能。性能不光是算法决定的，而是系统工程所决定的。我们的考虑必须面面俱到：要搜索的数据量有多少，用户执行的搜索属于什么类型，可用硬件资源有多少，进行搜索的软件上下文环境如何。针对遇到的具体问题，我们认为类似“字符串搜索（Grep）”的技术比关键字索引更适合。

关键字索引技术很棒，但也存在局限。通过这种技术搜索单字很简单，搜索多个字，例如搜索同时包含“googlebot”和“404”的信息也不太难，但短语，例如“uncaught exception”的搜索就比较棘手了，需要事先准备略为笨重的索引，不仅要追踪包含单字的信息，而且要了解这些字在信息中出现的位置。

当你想搜索的内容不是字词的时候，真正的困难出现了。假设你想知道自己网站的多少流量来自机器人（Bot），首先你可能会尝试在访问日志中搜索“Bot”，也许无法借此找到所有机器人产生的流量，但至少Googlebot、Bingbot，以及其他大部分机器人产生的流量都是可以看到的。然而“Bot”在这个语境中不是一个单词，而是一个单词片段。如果在关键字索引中查询“Bot”这个词，根本找不到包含“Googlebot”这个词的信息。虽然关键字索引也可以通过一定的方法找到所有包含“Bot”的内容，但速度将会非常慢：必须先在索引中查询每个词才能知道哪些词中包含“Bot”字样，随后针对找到的每个单词扫描整个索引。因此一些日志管理器不允许用户搜索某些特定词汇，或（顶多）让用户使用特殊的语法耗费更多时间找到想要的结果。我们不希望自己的工具也是这样。

标点符号则是另一个挑战。想找到所有来自50.168.29.7的请求？想找到所有包含[error]字样的调试日志？关键字索引通常会忽略标点符号。

最后，所有工程师都喜欢功能强大的工具，无法通过其他方式实现时就只能使用正则表达式。对关键字索引使用正则表达式虽然困难，但至少可以做到。

抛开能力不谈，关键字索引还很复杂。每条信息都需要加入到多个关键字列表中，这些列表必须用一种易于查找的方式定期收集整理并保存在磁盘上。涉及短语、单词片段，或正则表达式的查询必须针对多个关键字列表转换为多种操作，随后还需要对结果列表进行扫描与合并才能生成最终结果。在大规模多租户服务中，这样的复杂性会造成算法分析过程中无法体现的性能问题。

关键字索引还需要占用大量存储空间，存储可能是决定日志管理系统成本的关键。

反过来讲，我们负担得起为每次搜索提供足够的处理能力。用户很喜欢我们提供的高速、即席（ad-hoc）日志探索服务，但用户并不经常需要进行即席探索。我们对需要经常执行的搜索应用了一些特殊技巧，例如将其包含在仪表板内。（日后我们将专门撰文介绍这一功能）。在我们的整个服务中，其他执行频率不够高的搜索通常很少会同时进行，大部分时候一次只需要处理一个这样的搜索。但这并不是说我们的服务器很闲：服务器始终忙于新日志信息的摄入、解析和压缩操作，还需要对旧数据执行评估和压缩等操作。为了让查询的执行更快速，我们在CPU方面进行了相当大的投资。（下文将详细介绍这方面内容）

“残酷”的问题要用（大量）“暴力”的方法解决

暴力的方法最适合包含小规模内循环（Inner loop）的简单任务。通常通过对内循环进行优化既可以极高速度运行。如果代码太复杂，通常更难以进行极端的优化。

最初我们搜索代码的内循环规模非常大。我们会用4K的页存储日志信息，每个页包含一些（UTF-8格式的）信息，以及每条信息的某些元数据。元数据使用了一种字节包装（Byte-packed）结构，其中封装了值长度、信息的内部ID，以及其他多种字段信息。此时搜索的循环看起来是这样的：

这是实际代码简化后的结果。尽管如此，这一过程依然涉及多个对象分配、数据副本和函数调用。JVM很适合用于对函数的调用进行优化以及暂存对象（Ephemeral object）的分配，因此这些代码的效果甚至超出了我们的预期。我们的试用客户对这样的技术很满意。但最终我们的服务以此为基础实现了更完善的效果。

（你可能想知道我们为什么通过4K页，以元数据和文本的格式存储日志信息，而不是直接存储原始日志文件。原因有很多，最终可归结于我们系统内部的Scalyr日志引擎实际上更像是一种分布式数据库，而非文件系统。在对日志字段进行解析时，通常会将文本搜索与数据库形式的筛选器配合使用，我们一次可以搜索数千条日志，简单的文本文件无法胜任我们这种事务型、可复制的分布式数据管理系统。）

在最初的形态下，这种代码不适合针对暴力法进行优化。String.indexOf()中的“实际代码”甚至不是CPU配置文件的主要部分。单纯对这种方法进行多少优化也无法实现显著的效果。

巧的是，在每个4K页中，我们可以将元数据存储在页头，随后将所有日志信息以UTF-8文本的方式封装并存储在页尾。为此我们还重写了搜索循环，以便能同时搜索整个页：

这个版本可直接处理原始格式保存的数据，同时搜索4K页中包含的所有信息。

这种方法更适合针对暴力法进行优化。我们的内部搜索循环会一次调用4K数据，而不是分别调用每条信息，不涉及数据复制或对象分配。更复杂的元数据操作针对每次匹配只需要进行一次，而无须对每条日志信息分别执行。这样系统工作量大幅降低，可将更多资源用于小规模的内部搜索循环，因此还有进一步优化的空间。

实际使用的搜索算法基于Leonid Volnitsky提出的一种绝妙想法。该想法类似于Boyer-Moore搜索，但每个步骤使用了大致相同长度的搜索字符串，因此更先进一些。这两者最大的差异在于，我们的方法可以同时检查两个字节，借此可将错误匹配的情况降至最低。

我们的实现需要为每个搜索构建一个64K的查询表，相对于要搜索的数GB数据，这样的成本已经很低了。这样的内循环可以通过一个CPU内核每秒搜索数GB内容。在实际运用中，系统整体性能稳定在大约1.25GB/秒/内核的水平上，并且依然有改善的空间。目前我们还需要消除一些剩余的非内循环开销，同时还打算将内循环从Java迁移为C。

暴力法的运用

至此已经介绍了如何使用“暴力”的方法解决日志搜索过程中遇到的问题，那么到底能运用多“暴力”的方法？很多！

1个内核：现代化CPU的一个内核，只要妥善运用就已经相当强大。

8个内核：我们目前使用了Amazon提供的，基于SSD的hi1.4xlarge和i2.4xlarge服务器，每个服务器包含8个内核（通过超线程技术可使用16个内核）。通常情况下，这些内核都在忙于处理上文提到的后台操作。当用户执行搜索时，会暂停所有后台操作，将所有8个内核用于执行搜索。搜索通常会在不到1秒的时间里完成，随后会继续进行后台操作。（我们会通过一个调度器确保杂乱的搜索不会影响重要的后台操作的执行。）

16个内核：考虑到可靠性，我们将服务器分为主/从组。每个主服务器搭配一个使用SSD的从服务器，以及一个基于EBS的从服务器。如果主服务器故障，SSD从服务器可以立刻接手工作。几乎所有时间里，主从服务器都可以正常运转，这意味着每个数据块都可以通过两台服务器进行搜索。（EBS从服务器配置了最小规模的CPU，因此此处描述的用途中不予考虑。）我们会将一半搜索任务分配给从服务器，因此总共有16个CPU内核可供使用。

更多内核：在不远的未来，我们会用某种方式将数据分散在多台服务器上，让所有服务器均可参与每个重要查询。这样我们所使用的每个内核都可以参与到搜索的处理中。在提高每个内核的搜索性能后，预计搜索性能将进一步提升，达到100GB/秒甚至更高速度，跟随我们的业务一起增长。

简单即可靠

这种简单的暴力式解决方案所提供的另一个收益是，可以始终提供近乎一致的性能。暴力法通常不会过渡专注于任务和数据集本身的具体特征。（我猜这也是将其称之为“暴力法”的原因。）

关键字索引在某些情况下可以用非常快的速度提供结果，但有些情况可能会很慢。假设你有50GB日志，其中“customer_5987235982”这串字符一共出现了三次。搜索“customer_5987235982”需要直接从索引中三个相匹配的位置读取数据，这一过程可以瞬间完成。但包含通配符的复杂搜索可能需要扫描数千个关键字，需要很长时间才能完成。

然而暴力搜索的方法运行任何查询所需的时间都差不多。该方法更适合搜索较长的内容，但就算只搜索一个字也能实现极快的响应速度。

抛开算法的复杂度不谈，暴力搜索方法更简单的实现方式意味着实际性能与理论性能更接近。预期外的磁盘颠簸（Disk thrashing）、锁争用（Lock contention）、未缓存的指针跟踪（Uncached pointer chasing），以及软件代码中继承而来的所有数千个小瑕疵产生的影响也可以进一步降低。我刚刚查看了Scalyr用户上周在我们最繁忙服务器上执行查询的数量，共执行查询14000次，其中只有八个查询的执行时间超过一秒，99%的查询在111毫秒内完成。（如果你以前没用过日志分析工具，那么可以直接听听我们的意见：这速度真的很快。）

一致可靠的性能是用户体验的关键。如果服务的性能会时不时降低，用户会认为有问题并不愿意继续使用。

日志搜索的实际效果如何

下面的视频短片演示了Scalyr的日志探索过程。我们提供了一个演示账户，其中导入了我们每个公用GitHub代码库产生的每个事件。在这个演示中，我导入了一周的数据，大约600MB原始日志。

这个视频是通过我的台式机（距离服务器大约3000英里）实时录制的，没有进行任何特殊的事先准备。你所看到的性能归功于我们在Web客户端所做的诸多努力，同时也要归功于快速可靠的后端系统。你看到的所有未显示“正在加载”字样的停顿都是我有意为之，是为了让你能够有充分的时间看到我要点击的内容。

结论

在处理海量数据时，一定要选择最适合的算法，但“适合”并不总是意味着“花哨”。一定要考虑实际运用中代码的执行方式。“Big O”分析逐渐取消了常量因素（Constant factor），但在现实世界中依然举足轻重。算法越简单，就越容易优化，面对糟糕的边界用例行为（Edge-case behavior）漏洞也会越少。

此外还要考虑运行代码的上下文情境。在我们的用例中，需要用相当强大的服务器管理管理后台任务。用户发起的搜索相对较少见，因此必要时可以短时间征用整组服务器执行每个搜索。

这是有关Scalyr系统工程和性能的系列文章中的一篇。若想了解前端性能，请参阅优化AngularJS：从1200毫秒到35毫秒。

通过使用暴力方法，我们可以针对汇总后的日志进行极为快速可靠灵活的搜索。希望你能将这样的想法用在自己的项目中。如果想自行感受Scalyr的性能，你可以免费试用或详细了解我们的日志监控工具。

另外：Scalyr正在招人！如果你想加入到此类系统的开发工作中，或者想要加入一个能够让你大展宏图的团队，请立刻访问：scalyr.com/careers。