Algolia的分布式搜索网络架构

Algolia是一家做离线移动搜索引擎的公司，两年时间构建了世界范围的分布式网络。今天为世界12个区域每月20亿用户查询，平均服务器时间为6.7ms，90%的查询应答<15ms，不可用率低于十的负六次方，及每月宕机时间<3s……

本文是Algolia对其REST API建立和扩展经验的总结，其中包括如何在全世界不同位置保障数据的高可用和一致，以及如何通过Anycast DNS将查询路由到离用户地理位置最近的服务器。它的架构有哪些独到之处，本文进行了详细解析。

以下为译文

Algolia创建于2012年，其业务是为移动设备提供一个离线搜索引擎SDK。Julien 表示，在公司创建时，他们从未想过能建立一个为全世界使用的分布式搜索网络。

当下，Algolia每月需要支撑来自全世界12个地区用户产生的20亿次以上搜索。如此规模下，Algolia仍然可以将服务器响应时间控制在6.7毫秒，并在15毫秒内为用户返回结果。Algolia服务的不可用比率低于十的负六次方，也就是服务每个月宕机时间被控制在3秒以内。

基于移动的性质，其离线移动SDK所面临的技术限制被放大。同时，因为无法使用传统服务器端的一些设计理念，Algolia必须制定独特的策略来应对这些挑战。

数据体积的误解

在架构设计之前，我们必须准确定位我们业务的使用场景。在考虑业务扩展需求时，这么做尤其重要。我们必须充分了解用户需要索引的数据体积，GB、TB或者是PB。取决于需要支撑的用例，架构将变得完全不同。

在提到搜索时，人们首先想到的就是一些非常大的用例，比如Google的网页索引，又或是Facebook基于数万亿post的索引。冷静下来，并思考每天所见到的各种搜索框，你就会发现，它们中大部分都不是基于一个规模很大的大数据集。举个例子，Netflix的搜索建立在大约1万个标题之上，而Amazon美国数据库则包含了2亿个左右的商品。到这里，你就会发现，针对上述用例，只需要使用1台服务器就可以支撑所有数据！当然，这里并不是说将数据储存在一台主机上是一个很好的思路，但是必须考虑到的是，跨主机同步将造成大量的复杂性和性能损耗。

高可用性打造途

在SaaS API建立时，高可用是个需要重点关注的领域，因为移除单点故障（SPOF）确实非常困难。经过数个星期的头脑风暴，我们终于设计出了属于我们自己的最佳架构，一个面向用户的搜索架构。

主从 vs. 主主

不妨临时缩小一下使用场景，将用例看成“索引只储存在1台主机上”，那么可用性打造将简化为“将服务器放到不同的数据中心”。通过这个设置，我们可以想到的第一个解决方案就是使用主从的架构，主服务器负责接收所有索引操作，随后在1个或多个从服务器上备份。通过这个途径，我们可以很便捷地在所有服务器上做负载均衡。

然后，问题出现了，这种架构设计只保障了搜索查询的高可用。对于一个服务公司来说，将所有索引操作传输到主服务器这种架构隐藏着非常大的风险。因为一旦主服务器宕机，所有客户端都会出现索引错误。

因此，我们必须实现一个主主架构，而主主架构设计的关键元素就是如何在一组服务器进行结果同步。这样一来，我们需要做的就是在任何情况下系统的一致性，即使在主机之间存在网络分割。

引入分布式一致性

对于一个搜索引擎来说，想实现分布式一致性就必须将写入操作串连成一个独特的有序操作流。如果在同一时间出现数个操作进入的情况，系统必须为每个操作分配一个sequence ID（序列化的ID）。通过这些ID，系统可以保障所有的备份上都在执行正确的操作序列。

而想要得到一个sequence ID（每个作业流入都会增加1），我们必须在主机间下一个sequence ID 上拥有一个共享的全局状态。在这里，开源软件ZooKeeper是个常用的选择，我们开始时也通过下述几个步骤使用了ZooKeeper：

Step 1：当某台主机接收到一个作业时，它会使用一个临时名称将作业复制到所有的副本。

Step 2：主机获取分布式锁。

Step 3：在所有主机上从ZooKeeper中读取最新的sequence ID，并发送一个命令来拷贝临时文件作为“sequence ID + 1”操作。这个步骤等同于一个二阶段提交。

Step 4：如果从大多数（法定）主机中收到确定信息，即把 Zookeeper中将sequence ID + 1。

Step 5：释放分布式锁。

Step 6：最终，发送作业的客户端将收到结果。大部分情况下，都可以得到理想的结果。

不幸的是，这种序列化并不能运用到生产环境中，如果获取分布式锁的主机崩溃，或者在执行步骤3、4时重启，我们很可能面临这样一个情况：作业在部分主机上提交成功。这样一来，我们需要一个更复杂的序列解决方案。

通过TCP连接将 ZooKeeper打包成一个外部服务的方式无形中提高了ZooKeeper的使用门槛，同时还需要使用一个非常大的timeout（默认设置是4秒）。

因此，任何故障发生时，不管是因为硬件还是软件，在整个timeout设置的时间内，系统将被冻结。看起来似乎可以接受，但是在Algolia的场景下，我们需要一个频度很高的生产环境故障测试（类似Netflix的Monkey测试方法）。

Raft一致性算法

幸运的是，当我们遭遇这些问题时，Raft一致性算法发布了。很明显，这个算法非常适合我们的用例。RAFT的状态机就是我们的索引，而日志则是待执行的索引作业列表。在PAXOS协议和它的变体上我已经有了一定的了解，但是并没有深刻到有足够的信心去亲自实现，而RAFT则更加的清晰明了。虽然当时RAFT还没有稳定的开源实现，但是很清楚的是它可以完美地匹配我们需求，而我也有足够的信心基于它来设计我们的架构

对于一致性算法实现来说，其最难的部分就是保证系统中不存在任何bug。为了保障这一点，我选择了monkey方法进行测试，在重新启动之前使用sleep来随机kill一个进程。为了更进一步地测试，我甚至通过防火墙来模拟网络中断和降级（degradation）。这种类型的测试帮助我们发现了很多bug，而在连续多天无故障运行后，我非常确认这个实现没有问题。

应用程序还是文件系统等级复制？

取代在文件系统上复制最终结果，我们决定将写入操作分配到所有主机上本地执行。做这个选择主要基于以下两个原因：

• 这样做更快。索引在所有主机上并行进行，显然快于复制体积可能会很大的结果（二进制文件）。
• 与多个区域策略兼容。如果在索引后复制，我们需要一个进程重写全部的索引。这意味我们可能需要传输非常大的数据，而在全球不同地理位置做大规模数据传输显然是没有效率的，比如从伦敦到新加坡。

每台主机都会使用一个正确的顺序接收所有写入操作作业，并立刻独立处理。也就是说，所有的机器最终都会在一个相同的状态，但是同一时刻的状态可能不同。

一致性上的妥协

在分布式计算环境下，CAP定理表示分布式系统不可能同时满足以下3个特性：

• Consistency（一致性)：同一时刻所有节点上的数据都相同。
• Availability（可用性）：保证每个请求都会收到其成功与否的响应。
• Partition tolerance（分区容错性）：任何消息丢失，或者系统的任何部分发生故障，系统都可以持续良好运行。

在这里，我们在一致性上做出了让步。我们不保证同一时刻所有节点上的数据相同，但是它们最后必然得到更新。换句话说，我们允许小型场景中节点不同步的情况。事实上这并不会造成问题，因为当一个用户执行一个写入操作时，我们会在所有主机上执行这个作业。在更新时间上，最先更新的主机与最后更新的主机之间不会超过1秒，因此通常情况下终端用户根本感受不到。唯一不一致的可能就是最新收到的更新是否已经被执行，然而这与我们的用例并不矛盾。

总体架构

集群的定义

在主机间保持分布式一致性是高可用基础设施打造的必备条件，然而不幸的是，这正是系统性能的一大瓶颈所在。一致性保障需要主机间的多次交互，因此每秒能达成的一致性保障数量与主机间存在的延时戚戚相关。也就是说，主机必须尽可能近才能获得每秒更高数量的一致性保障。这样一来，为了支撑多个不同的地理位置，同时还不会降低写入操作的性能，我们需要搭建多个集群，每个集群都拥有3台主机来充当备份机。

对于一致性来说，每个地区最少拥有1个集群，但是这显然并不如人意：

• 我们不可以将所有用户请求塞进同一台主机里。
• 用户数量越多，每个用户每秒可以执行的写入操作越少，这是因为每秒能达成的一致操作数量是固定的。

为了解决这一问题，我们决定在地区等级上使用相同的概念：每个地区都拥有多个由3台主机组成的集群。每个集群可以处理1个以上的客户，数量由客户的数据体积决定。这个观念类似于在物理机上做虚拟化，我们可以将多个客户放到同一个集群中，除下某个用户出现动态增长或者改变其使用率。为了实现这个目标，我们需要提升或自动化下面几个操作：

• 当某个集群上数据或者写入操作数量过多时，将其中的一个客户迁移到另一个集群。
• 如果查询的体积过大，为集群添加新主机。
• 如果客户的数据量过大，改变分区数量，或者将其跨多集群切分。

在使用了上述策略后，一个客户不可能永远分配给一个集群。分配取决于个人使用情况和集群使用情况。这样一来，我们需要一个方案将客户分配给指定的集群。

将一个客户分配给一个集群

通常情况下，为客户分配集群的方法是为每个客户都配置一个唯一的DNS入口，类似Amazon Cloudfront的工作方式，每个客户通过customerID.cloudfront.net表格获得一个唯一的DNS条目（DNS entry），随后根据客户被分配到不同集合的主机上。

我们也决定使用这个方法。每个客户被分配一个唯一的应用程序ID，对应APPID.algolia.io表格中的DNS记录。DNS记录会指定特定的集群，因为该集群中所有主机都属于该DNS记录的一部分，所以这里存在一个通过DNS完成的负载均衡。我们同样使用健康检查机制来检测主机故障，一旦发现即会将故障机从DNS解析中移除。

单靠健康检查机制并不能提供一个很好的SLA，即使在DNS记录上配置一个很低的TTL（TTL是客户被允许缓存的DNS answer时间）。这里存在的问题是在主机发生故障时，用户仍然可能缓存这台主机。在缓存期满前，用户仍然会不停地给这台主机发送查询。在很多情况下，系统可能不遵守TTL设置。在实际操作中，我们看到1分钟的TTL可能会被某些DNS服务器修改成30分钟的TTL。

为了进一步提高可用性，以及避免主机故障对用户的影响，我们为每个客户生成了另一组DNS记录，APPID-1.algolia.io、APPID-2.algolia.io以及APPID-3.algolia.io。这么做是为了当TCP连接超时后，API客户端可以重新尝试其他的DNS记录。我们的实现是对DNS记录进行shuffle，然后按照顺序重试。

对比使用一个专业的负载均衡器，严格地控制重试配合API客户端中的超时逻辑，系统获得了一个更健壮及开销更小的客户分配机制。

随后，我们发现流行的.IO TLD在性能方面表现并不如人意。对比.IO，在anycast network情景下，.NET可以拥有更多的DNS服务器。为了解决.IO因为大量超时导致的域名解析变慢，我们切换到了algolia.net域名，同时向后兼容algolia.io域名。

集群的可扩展性如何？

在不会潜在影响现有客户的情况下，因为多了集群间的隔离，多集群允许服务支撑更多的客户。但单集群所面临的扩展性问题仍需考虑。

基于写的一致性保障，每秒写入操作数量成为集群扩展性的首要限制因素。为了移除这个限制，在保证一致性确认正常进行的基础上，我们在API中添加了大量的方法将一组写入操作压缩成一个操作。但是这里仍然存在问题，一些客户仍然不使用批量的方式执行写入操作，从而影响到集群中其他用户的索引速度。

为了减少这种情况下的性能下降，我们对架构做如下两个改变：

• 添加一个批量策略，在一致性确认产生争用时，会以一致性确认为前提，自动将每个客户的写入操作整合成一个。在实际操作中，这么做意味着重置作业的顺序，但是并不会影响到操作的语义。举个例子，如果有1000个作业在争夺一致性确认资源，其中990个都来自同一个客户，我们会将这990个写入操作合并成一个，即使在顺序上这990个作业中间可能会穿插一些其他用户的作业。
• 基于应用程序ID，增加一个一致性调度器（consensus scheduler）来控制每秒需要做一致性确认的写入操作数量，这样可以避免某个客户占用所有带宽的情况。

在实现这些提升之前，我们通过返回一个429 HTTP 状态码来控制速率限制。但是很快就被证明这个处理方式会大幅度影响用户体验，客户不得不等待它的响应，随后再进行重试。当下，我们最大的客户在一个3主机的集群上每天执行10亿次的写入操作，平均下来每秒1.15万次，最高峰值每秒可达15万。

第二个问题则是选择最合适的硬件设置，从而避免类似CPU/IO等潜在的瓶颈，以避免对集群扩展性产生影响。自开始起，我们就选择了使用自己的实体服务器，从而可以完全控制服务的性能，并避免资源的浪费。而长久以来，我们在选择合适硬件的过程中不停碰壁。

在2012年底，我们从一个较低的配置开始：Intel Xeon E3 1245v2、2x Intel SSD 320 series 120GB in raid 0以及32GB of RAM。这个配置的价格非常合理，也比云平台更加强大，同时允许我们在Europe和US-East提供服务。

这个配置允许我们针对I/O调度来调整内核及虚拟化内存，这对硬件资源的最佳利用至关重要。即使如此，我们很快发现服务受到内存和I/O限制。在那个时候，我们使用10GB的内存做索引，因此只剩下20GB的内存来缓存文件用于搜索查询。鉴于提供毫秒级响应时间的服务指标，客户索引必须放在内存中，而20GB的容量实在太小了。

在第一个配置之后，我们尝试使用不同的硬件主机，比如单/双CPU、128GB及256GB内存，以及不同大小和型号的SSD。

在多次尝试之后，我们终于找到了最佳设置：Intel Xeon E5 1650v2、128GB内存以及 2x400GB Intel S3700 SSD。在持久性上，SSD的型号非常重要。在发现正确的型号之前，多年使用中我们损坏了大量的SSD。

最终，我们建立的架构允许我们在任何地区进行良好的扩展，只要满足一个条件：在任何时候都需要拥有可用资源。也许你会感觉很奇怪，在2015年的当下我们还在考虑维护实体服务器，但如果聚焦服务质量和价格就会发现这一切都是值得的。对比使用AWS，我们可以将搜索引擎在3个不同的地理位置备份，完全置于内存，从而获得一个更好的性能。

复杂性

控制进程的数量

每台主机只包含3个进程。第一个是将所有查询解释代码嵌入到一个模块的nginx服务器。为了响应一个查询，我们在内存中映射了索引文件，并在nginx工作者进程内部直接执行查询，从而避免与任何进程或者主机通信。唯一罕见的例外情况就是客户数据无法在同一台主机上保存。

第二个进程是redis键值存储，我们使用它来检查速度和限制，并使用它为每个应用程序ID存储实时日志和计数器。这些计数器被用于建立我们的实时仪表盘，当用户连接到账号时就可以被查看，在做最近一次API调用可视化及debug上很有帮助。

最后一个进程就是生成器（builder）。这个进程负责处理所有的写入操作。当nginx进程收到一个写入操作时，它会将操作转发到生成器来执行一致性检查。同时，它还负责建立索引，并包含了大量用于检查服务错误的监视代码，比如崩溃、索引缓慢、索引错误等。基于问题的严重性，有些会通过Twilio的API以SMS告知，而有些则直接报告给PagerDuty。一旦在生产环境中发现某个错误，而这个错误并没有得到相应的报告，那么随后我们就会将之记录用于以后该种类型错误的处理。

易于部署

简单的堆栈可以非常便捷地部署。在代码部署之前，我们进行了大量的单元测试以及非回归测试（Non-Regression Test ）。在所有测试都通过之后，我们就会逐步的部署到集群。

对于服务供应商来说，我们的测试应该做到生产环境的零影响，并对用户透明。同时，我们还期望在一致性确认过程中营造主机故障的场景，并检查所有事情是否如按预期进行。为了实现这两个目标，我们独立部署集群中的每台主机，并遵循以下步骤：

1. 获取新的nginx和builder二进制文件
2. 重启nginx网络服务器，并且在零用户查询丢失的情况下重新发布新的nginx。
3. 关闭并发布新的builder。这将在主机的部署上触发一个RAFT故障，可以让我们确保故障转移是否如预期进行。

在架构衍变过程中，减少系统管理复杂性同样是一个坚持不懈的目标。我们不期望部署被架构约束。

实现全球覆盖

服务变得越来越全球化，在地球上某个区域支撑所有区域的查询显然是不切实际的。举个例子，如果把服务托管在US-East的主机肯定会对其他地区用户的可用性产生影响。在这种情况下，US-East的用户延时可能只有几毫秒，而亚洲客户的延时却可能达到数百毫秒，这还是没有计算海外光纤饱和所带来的带宽限制。

在这个问题的解决上，我们看到许多公司都为搜索引擎搭载了CDN。对于我们来说，对比得到的好处，这么做将造成更多的问题：在改善被频繁提交的那么一小部分查询的同时，却带来了无效缓存这个噩梦。对于我们来说，最实际的方法就是在不同的地理位置进行备份，并将之加载到内存中以提升查询效率。

这里我们需求的是一个在已有集群备份上的区域内复制。副本可以储存在一台主机上，因为这个副本将只负责搜索查询。所有写入操作将仍然传输到客户的原始集群上。

每个客户都可以选择数据备份托管的数据中心，因此某个区域中的备份机可以从多个集群中接收数据，并拥有集群将数据发送到多个备份。

基于操作流，这个机制同样被用于一致性。在一致性确认之后，每个集群负责转换自己的写入操作流到一个版本，从而每台备份机都可以使用空作业替换掉与这次复制无关的作业。随后，这个操作流会被发送到所有副本做批量操作，以尽可能地避免延时。单个发送作业会造成备份机之间的太多交互确认操作。

在集群上，写入操作会一直保存在主机上，直到它被所有的备份机确认。

DNS的最后一部分处理是将用户重定向到离自己最近的地理位置，为了保证这一点，我们在APPID-dsn.algolia.net 表格中加了另一条DNS记录以处理最近数据中心问题。最初我们使用的是Route53 DNS，但是不久后就碰到了限制。

基于延时的路由机制受限于AWS regions，因为我们有很多AWS未覆盖的地理位置，比如印度、香港、加拿大和俄罗斯。

基于地理位置的路由很糟糕，你需要为每个国家指出DNS解析是什么。许多托管DNS提供商都使用了这个传统途径，但是在我们用例中很难支持这点，也无法提供足够的相关性。举个例子，我们在美国就拥有了多个数据中心。

在做了大量的基准测试和讨论后，我们基于以下几个原因考虑使用NSOne：

对于我们来说，他们的Anycast网络非常适合，负载均衡性也做的更好。举个例子，他们在印度和非洲都拥有一个POP。

他们的过滤逻辑非常好。我们可以为每个用户指定与之相关的主机（包括备份机），并通过地理过滤器根据距离将他们分类。

他们支持EDNS客户端子网。同时，我们使用终端用户的IP而不是他们DNS服务器的IP。

在性能方面，我们实现了全球范围内的秒级同步，你可以在Product Hunt's search（托管在US-East、US-West、India、Australia和Europe）或者。Hacker News' search (托管在US-East、US-West、India和Europe)进行测试。

总结

我们花费了大量时间以打造一个分布式、可扩展的架构，也遭遇了各种不同的问题。我希望通过本文让你对我们处理问题的途径有一定的了解，并为读者打造服务提供一定的指导。

在这段时间里，我们看到越来越多开发者面临与我们类似的问题，他们使用多区域数据中心来支撑世界各地的用户，同时也拥有需要在全球范围内做一致性保障的业务，比如登陆或内容，而多区域数据中心已经成为拥有良好用户体验的必然条件。

关于作者：Julien Lemoine，Algolia的联合创始人兼CTO，Algolia是一个开发者友好的搜索即服务API，可以在毫秒级提供数据库搜索结果。

原文链接： The Architecture of Algolia’s Distributed Search Network （译者/薛童阳 责编/钱曙光） 

OpenCloud 2015将于2015年 4月16-18日在北京召开。大会包含“2015 OpenStack技术大会”、“2015 Spark技术峰会”、“2015 Container技术峰会”三大技术峰会及多场深度行业实战培训，主题聚焦技术创新与应用实践，荟萃国内外真正的云计算技术的大牛讲师。这里都是一线接地气的干货，扎实的产品、技术、服务和平台。OpenCloud 2015，懂行的人都在这里！