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的網頁索引，又或是非死book基于數萬億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 ）。在所有測試都通過之后，我們就會逐步的部署到集群。
對于服務供應商來說，我們的測試應該做到生產環境的零影響，并對用戶透明。同時，我們還期望在一致性確認過程中營造主機故障的場景，并檢查所有事情是否如按預期進行。為了實現這兩個目標，我們獨立部署集群中的每臺主機，并遵循以下步驟：
- 獲取新的nginx和builder二進制文件
- 重啟nginx網絡服務器，并且在零用戶查詢丟失的情況下重新發布新的nginx。
- 關閉并發布新的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 （譯者/薛童陽 責編/錢曙光）