# 搜索技術剖析：blekko 的 NoSQL 數據庫 > 原文： [http://highscalability.com/blog/2012/4/25/the-anatomy-of-search-technology-blekkos-nosql-database.html](http://highscalability.com/blog/2012/4/25/the-anatomy-of-search-technology-blekkos-nosql-database.html)  *這是 blekko 的首席技術官 Greg Lindahl 的來賓帖子（[第 2 部分](http://highscalability.com/blog/2012/5/28/the-anatomy-of-search-technology-crawling-using-combinators.html)，[第 3 部分](http://highscalability.com/blog/2012/7/9/data-replication-in-nosql-databases.html)），該網站是垃圾郵件免費搜索引擎，3 月的獨立訪問者超過 350 萬。 Greg Lindahl 是 PathScale 的創始人兼杰出工程師，當時他是 InfiniPath 低延遲 InfiniBand HCA 的架構師，該架構用于構建緊密耦合的超級計算集群。* 想象一下，您已經瘋狂到足以考慮構建搜索引擎了。 這是一項艱巨的任務：回答大多數查詢所需的最小索引大小是數十億個網頁。 要對數十億個網頁進行爬網和建立索引，就需要一個群集，其中包含幾 PB 的可用磁盤（即幾千個 1 TB 的磁盤），并且產生的索引大小約為 100 TB。 快速提供查詢結果涉及將大多數索引放在 RAM 或固態（閃存）磁盤上。 如果您可以以 3,000 美元的價格購買具有 100 GB RAM 的服務器，那么這 1,000 臺服務器的資本成本為 300 萬美元，加上每年服務器托管成本（電源/散熱/空間）約為 100 萬美元。SSD 替代方案需要 更少的服務器，但是每秒提供更少的查詢，因為 SSD 比 RAM 慢得多。 您可能會認為，亞馬遜的 AWS 云將是降低啟動搜索引擎成本的好方法。 不是，原因有四個： 1. 爬網和建立索引一直需要大量資源； 您有時無法僅通過租用大多數服務器來省錢。 2. 亞馬遜目前不出租帶有 SSD 的服務器。 將索引放入 Amazon 的 RAM 中非常昂貴，并且僅對擁有幾％市場份額的搜索引擎有意義。 3. 亞馬遜僅出租有限數量的磁盤 I / O 與內存大小與核心數量的比率。 事實證明，相對于其他所有產品，我們需要大量的磁盤 I / O，這使 Amazon 的成本效益降低。 4. 在某種集群規模下，一家初創公司具有足夠的規模經濟優勢，可以超過亞馬遜的成本+利潤率。 在發布時（2010 年 11 月），blekko 擁有 700 臺服務器，而我們目前有 1,500 臺。 這遠遠超出了收支平衡點。 ## 軟件 那僅僅是硬件：我們還需要一個軟件系統來管理存儲以及對集群中 Web 爬網和索引數據的訪問。 我們的目標之一是設計一種存儲體系結構，當在搜索引擎環境中使用 Web 大小的數據集時，將為程序員帶來生產力上的優勢。 我們的目標是： * 一種將數據存儲在類似于數據庫表的系統中 * 同一集群中的實時（查詢服務）和批處理（爬網和索引）處理 * 添加對倒排索引的直接支持的能力，該索引非常適合系統的其余部分 * 出色的程序員生產力，包括： * 無縫集成主要實現語言的數據存儲和數據結構 * 抵抗常見的數據庫和群集數據庫問題，例如熱點和死鎖/活鎖 * 數據存儲區，可實現常規數據庫操作（如 BASE 和 CRUD），并有效地實現并協助并行編程結構（如工作隊列）。 * 支持快速完成初始批處理作業結果的周轉時間，從而使程序員可以快速發現其批處理作業做錯了什么 * 可擴展到數千個磁盤設備： * 磁盤故障是將群集擴展到大尺寸時最常見且令人討厭的問題 * 面對故障逐漸退化 * 理想情況下，群集故障 1％只會使處理能力和存儲量減少 1％。 例如，在節點上重建 RAID 卷期間，服務器上 RAID 的使用不當會導致吞吐量降低超過 1％。 此外，磁盤故障在大型集群中非常常見，以至于我們希望在準備好一次，一周或一個月后修復多個節點之前就不需要人工干預。 * 由于可用性的原因，我們希望使用群體算法來實現盡可能多的子系統，而不是使用 Paxos 來選擇主節點。 [https://zh.wikipedia.org/wiki/Paxos_algorithm](https://en.wikipedia.org/wiki/Paxos_algorithm) ## 組合器 在傳統的數據庫系統中，對數據庫的更新是在事務中完成的，其中程序鎖定數據庫的一行或多行，進行一些更改，然后提交或中止整個事務。 大多數 NoSQL 數據庫都將事務限制為鎖定&來修改單個行，并限制可以在事務內完成的計算類型。 在 blekko 的數據存儲區中，我們嚴重依賴于稱為合并器的構造在數據庫單元級別進行處理。 組合器是對數據庫單元進行的原子操作，該操作是關聯的，最好是可交換的。 “ Add（n）”是一個簡單組合器的示例； 它將 n 加到單元格中的任何數字上。 至關重要的是，它不會將總和返回給調用方。 它只是啟動加法。 如果一堆數據庫節點想在數據庫的同一單元中加 1，而又不了解該單元的最終值是什么，則可以將這些操作組合到集群中的層次結構中，從而進行最終的磁盤操作 是一個將初始增量之和相加的操作。  加法是關聯和可交換的事實意味著我們（最終）將在此單元格的所有 3 個副本中獲得相同的答案。 組合的層次結構意味著與天真的實現相比，事務總數大大減少了，因為天真的實現每個過程都直接與單元的 3 個副本進行對話，而每個加法操作都會導致 3 個立即事務。 ### 日志計數組合器 搜索引擎經常需要計算一組中的唯一項。 示例包括計算網站的鏈接數，鏈接到該網站的唯一地理區域的數量以及鏈接到該網站的唯一的 C 類 IP 網絡的數量等等。 盡管我們總是可以運行 MapReduce 作業來獲得這些項目的準確計數，但我們希望在任何時間點都知道這些計數。 保持完美的計數將需要保留大量數據，因此我們發明了一種**近似方法**，該方法僅用 16 個字節就可以對多達十億個事物進行計數，精度為±50％。 該組合器（我們稱為對數計數）以可交換和關聯的方式實現-您可以將其中兩個的位與進行組合以合并其計數。 它還具有以下屬性：如果您多次計數任何字符串，則最多只能更改一次答案。 最后一個屬性意味著它是可重新運行的，即如果在數據庫中進行了兩次相同的事務，則答案不會改變。 ### TopN 組合器 搜索引擎的另一種常見操作是記住集合中最重要的 N 個項目。 這用于我們不想記住集合中的所有項目以減小尺寸的情況。 例如，我們可能希望經常將最重要的 2500 個傳入 URL 的[錨文本]( https://en.wikipedia.org/wiki/Anchor_text)訪問到我們曾經抓取過的每個 URL。 TopN 組合器可以在適合數據庫的單個單元格的有限大小的數組中表示前 N 個 URL：  隨著我們抓取新的網頁，可以對 TopN 組合器進行增量更新，并且這些更新的價格不昂貴。 可以在單個磁盤操作中讀取它，而無需索引或排序或讀取不位于前 N 個位置的 URL 的任何數據。感謝用于決定哪個 URL 最適合 N 的行列，它是可交換的 和關聯。 而且它可以重新運行。 如果我們使用時間作為排名，則可能會有其他技巧。 這使我們能夠有效地記住最近的 N 個事物或最早的 N 個事物。 到目前為止，我們已經在數據庫表中將組合器用作單個單元格。 也可以在我們程序中的變量中使用**； 它們的實現將它們存儲為字符串，讀取值需要調用“ finalize”函數。 例如，此功能將日志計數中的 16 個字節的位字段轉換為整數的近似項目數。** ### 元組合器：哈希組合器 如果數據庫中的一個單元格包含（鍵，值）對的哈希，則哈希元組合器可用于原子地僅更新一些（鍵，值）對，其余的保持不變。 這給了我們極大的自由，可以將數據庫中的列設置為對程序員有意義的列，而不必為了使原子地進行更改而必須將多余的內容提升為列。 ### 減少地圖/縮小 由于我們用組合器表示數據庫表，為什么不使用組合器來改組并減少 MapReduce 作業的輸出？ 然后我們可以編寫遍歷數據庫中某個表的 MapJob，然后使用組合器將其輸出寫回到數據庫中。 讓我們對網絡進行字數統計： > “ / crawl / url”中的 foreach 行 > > html 列中的 foreach 單詞 > > comb_add（“ / wordcount”，word，1） 在此偽代碼中，我們遍歷表/ crawl / url 中的所有 html 文檔，對于找到的每個單詞，我們在表“ / wordcount”中增加相應的行。 編程人員不再需要考慮改組/減少步驟應以哪種**中間形式**作為輸入，或指定減少功能。 這種單詞計數方法的第二個特點是，上述功能還可以在流上下文中使用**，將新抓取的文檔的單詞計數添加到表“ / wordcount”中的現有計數。 表示 MapReduce 計算的通常方法不能在流計算中使用相同的代碼。** 第三個功能是該 MapJob 的第一個輸出在 MapJob 啟動后的幾分鐘后出現在/ wordcount 表中。 大多數 MapReduce 系統直到每個分片完成后才開始隨機播放和還原。 具有**快速，部分答案**可使程序員更快地找到其 MapJob 中的錯誤。 ## 我們是否實現了所有要求？ 現在，我們已經在這個本地數據存儲上擁有近 3 年的運營經驗，現在很高興回頭看看，我們基本上滿足了我們預先設定的所有要求。 在本文的初始篇中，我們僅討論了數據存儲的部分功能，但是我們在這里討論的內容已廣為人知。 我們的數據存儲區： * 看起來像表格數據庫 * 在同一集群中支持實時和批處理 * 支持高程序員效率 在本系列的下一部分中，我們將更詳細地研究 Web 爬網，并使用組合器實現爬網程序。 這篇文章中的所有內容看起來都很簡單容易。 我希望人們不要錯過這里介紹的算法和數據庫調用的類型具有可伸縮性。 經驗法則（我剛剛完成）是只要您將數據存儲區調用的大部分都考慮為可交換的，您做對了，它就會擴展并可以期望。 我敢打賭，該系統不僅可以在水平方向上很好地縮放，而且可以在單臺機器上高效地運行，并且在垂直方向上也可以很好地縮放。 這個系統不僅是 BIG-DATA，它還是 EFFICIENT-BIG-DATA，這更重要，因為它的大小:)不錯的文章，加上 plus100 也可避免沉迷于流行詞的不必要使用:) >快速提供查詢結果涉及將大多數索引放在 RAM 或固態（閃存）磁盤上。 僅當查詢在查詢空間之間均勻分布時，這才是正確的。 在現實生活中，查詢空間由一小部分“熱”（經常請求）查詢和一長串“冷”（很少請求）查詢組成。 因此，在從 I / O 綁定存儲中服務“冷”查詢的同時，可以在 RAM 中僅緩存一小部分索引，這對應于“熱”查詢。 這可以顯著減少索引所需的 RAM 量，同時保持良好的 qps。 搜索查詢往往有一個“長尾巴”，因此專用于僅服務于頭部的 ram 會使大多數查詢脫離緩存。 我們努力在所有查詢的 95/99％上實現目標延遲-我們在辦公室的大型狀態監視器上具有跟蹤此延遲的圖形，以及在我們掉線時會喚醒人們的操作警報。 對于主流搜索服務而言，在 50％的查詢上實現合理的延遲是不夠的。 具有 SLA 的合作伙伴也不會接受該級別的性能。 日志計數組合器上的準確性是否正確？ 那么，100,000 意味著 50,000 至 150,000 之間的東西？ 如果是這樣，我很好奇具有這種準確性的計數將達到什么目的。 另外，我應該首先說這看起來很酷。 是否有計劃實施后續文章，還是 Blekko 秘密調味醬過多？ 謝謝。 讓我們做簡單的數學。 100Tb 索引對應于 50 x 2Tb HDD。 每個 HDD 可以執行 100 IOPS（10 毫秒隨機搜尋延遲）。 因此 50 個 HDD 可以執行 5K qps。 這意味著該應用程序可以輕松地每秒處理 5K 個“冷”索引查詢，每個查詢具有 10ms 的延遲，而無需計算從 RAM 執行的數百萬個“熱”索引查詢。 如果將 HDD 替換為 SSD，則“冷”索引查詢的性能可以輕松提高到 500K qps 甚至更高。 日志計數示例：計算到 URL 的入站鏈接數。 在 0 和 1（合格）入站鏈接之間的差值中大約有與在 128 和 256 之間相同的信號。對于像這樣的對數分布上出現的現象，用兩個作品的漸進冪中的誤差進行近似計數。 實際上，我們有一個新的組合器，該組合器在我們的系統中大部分已替換為 logcount，稱為 adapcount。 您以字節為單位指定要使用的空間量，使用的空間越多，精度越好。 因此，對于 2k，您可以有+/- 5％的值（我忘了細節）。 噢，是的，我完全忘記提及 logcount 有很多朋友，這些朋友更大，更精確。 最不精確的版本用于我們擁有大量統計數據的地方，就像我們為 180 億個網頁所保留的統計數據一樣，我們已經看到了鏈接但尚未抓取。 當第一句話包含“無垃圾郵件搜索引擎”時，我差點彎腰閱讀。 但是哎呀，我束手無策： http://blekko.com/ws/site:bigresource.com 這是一個非常有趣的帖子。 您是否會碰巧有更多關于組合器和系統技術細節的文章/白皮書或其他資源？ 聽起來很有趣:) 感謝分享 藝術 聽起來像一個有趣的小項目。 如果要為職位實施垂直搜索引擎，應該使用哪個數據庫？