## 引子 如何能實現全文檢索的功能呢？ 可以使用SQL的like 數據量小的時候Like還湊合，但是數據量大了，效率就非常低了 那么可以使用inverted index ## Inverted Index Inverted Index被翻譯成倒排索引 比如有兩篇文檔： * 文檔1：A computer is a device that can execute operations * 文檔2：Early computers are big devices 把這兩篇文章中的單詞都抽取出來，并且記錄下這個單詞出現在哪個文檔中。  通過這個 “倒排索引”，只要給出一個單詞，就可以迅速地定位到它在哪個文檔中。 用來做全文搜素非常合適。 這個倒排索引有些粗糙，可以精化一下 1. 對于 a, is , to ,that ,can ,the,are 這些詞對搜索來說沒什么意義，用戶幾乎不會用他們搜索，可以過濾掉。 2. 用戶搜索的時候雖然輸入了 computer，但是也希望搜出 computers 出來，所以需要把復數單詞，過去式單詞等做還原。 3. 用戶雖然輸入了 device , 但是也希望搜索出 Device 出來，所以需要把大寫都改成小寫。 經過這番轉換，文檔 1 和文檔 2 的關鍵字變成了這樣： 文檔 1：[computer] [device] [execute] [operation] 文檔 2：[early] [computer] [big] [device]  為了更好的統計和高亮顯示搜索結果，還可以記錄關鍵詞在文章中出現的次數和位置（例如：是第幾個單詞）  ## 架構 只要把那些書籍的標題，介紹，作者等信息給提取出來，形成 inverted index，不就可以做關鍵字檢索了嗎？ 這個需求應該是個通用的需求，不僅是圖書館有，很多互聯網應用，例如網上商城也需要， 我完全可以設計一個類庫出來  不管你是什么類型的文檔，HTML， PDF， Word，甚至是數據庫的數據，只要能從中抽取出文本，就可以當作我的數據源，對文本做了分析以后，就可以存入索引庫。 用戶可以發出各種查詢，不僅僅是單個關鍵字，還支持關鍵字的組合： keyword1 AND keyword2 等，對索引庫進行搜索以后，把結果返回給用戶。 ## 抽象 接下來就是API設計了。 軟件設計就是一個不斷抽象的過程。既然有 HTML,PDF, Word 文檔， 很自然，你可以做一個 Document 的抽象 但是如果數據源是數據庫，怎么變成 Document，比如一行數據可以映射到一個Document，當然，這個轉化必須得有程序員來完成。程序員決定什么東西是 Document Document有什么東西？ Document 可以有很多屬性，每個屬性都有名稱和值， 我可以把屬性叫做 Field。 比如一個 HTML 文檔，可能有 path, title，content 等多個 Field，其中 path 可以唯一地標志這個文檔, title 和 content 需要做進行分詞，形成倒排索引，讓用戶搜索  用戶創建了 Document 和 Field 以后，就可以進行分析了，原始的內容劃分成一個個 Term，這樣，我可以定義一個 Analyzer 的抽象類，讓別的程序可以擴展它 分析的結果可以加入索引庫，這個操作可以讓一個單獨的類，比如 IndexWriter 類來完成。 可是 IndexWriter 如何知道索引應該存在什么地方？ 內存？ 文件系統 那就再來一個抽象的概念：Directory，表示索引文件的存儲  對于對于用戶搜索來說，肯定得有個叫做 Query 的東西，用來表達用戶的搜索要求。當然，這個 Query 也應該允許擴展。  但是這些類使用起來還是比較麻煩， 最好是支持用戶輸入字符串來表達搜索的意圖：(computer or phone) and price 所以必須得有個解析器來完成從字符串到 Query 的轉化，然后我們讓 IndexSearcher 來接收 Query，就可以實現搜索的功能了  有個叫做 Lucene 的開源系統，和我們的設計很像啊，功能更加強大 ## 三年之后 人們發現Lucene用起來太低級了，比如想搜索一下我的商品描述，現在還得理解什么 “Directory”,"Analyzer","Query"，實在是太復雜了！ 還有我們的數據越來越多，索引也越來占的空間也越來越大，怎么才能實現分布式的存儲啊 是時候對 Lucene 做一層封裝，提供一個簡單的 API 了...... ## Lucene的問題 * Lucene做搜索很強大，但是**API用起來太低級**，想搜索一下我的產品描述，現在還得理解什么 “Directory”,"Analyzer","IndexWriter" * 互聯網的數據是海量的，僅僅是單機存儲索引是遠遠不夠的。 俗話說：軟件開發中遇到的所有問題，都可以通過增加一層抽象而得以解決 ## Java API -> Web API Web 開發面對的都是領域模型，比如 User,Product, Blog，Account 之類。用戶想做的無非就是搜索產品的描述， 搜索 Blog 的標題，內容等等 如果能圍繞領域模型的概念進行搜索的各種操作就好了。 Web 時代中，程序員都喜歡采用 RESTful 的方式來描述一個 Web 資源， 對于搜索而言，完全可以借鑒一下 /coolspace/blog/1001 : 表示一個編號為 1001 的博客 /coolspace/user/u3876：表示一個 ID 為 u3876 的用戶 * /coolspace 表示一個 “索引庫” * /blog ,/user 表示 “索引的類型”（可以理解為編程中的領域模型）。 1001， u3876 表示數據的 ID，格式是 /<index>/<type>/<id> 如果和關系數據庫做個類比的話： > 索引庫 <---> 數據庫 > 索引的類型 <---> 數據庫的表 用戶看到的就是領域模型， 當用戶想去操作時候，用 HTTP 的 GET, PUT 等操作就好了，交互的數據可以使用 JSON 這個簡單的格式。 ## 基本操作 * 把文檔加入索引庫 把一個 blog 的 “文檔” 加入索引庫，這個文檔的數據是 JSON 格式，其中的每個字段將來都可以被搜索： ~~~ PUT /coolspace/blog/1001 { "title" : "xxxxxxx", "content" : "xxxxxxxxxxxx", "author" : "xxxxx", "create_date": "xxxxxx" ... } ~~~ * 把一個blog文檔刪除 ~~~ DELETE /coolspace/blog/1001 ~~~ * 用戶搜索 用戶想搜索的時候也很簡單，發起一個這樣的請求就行： ~~~ GET /coolspace/blog/_search ~~~ 但是如何表達查詢的具體需求呢，這時候必須得定義一個規范了，例如：想查詢一個內容字段（content) 包含 “java" 的 blog。 ~~~ GET /coolspace/blog/_search { "query" : { "match" : { "content" : "java" } } } ~~~ 也就是query可以增加更加復雜的條件，表示用戶的查詢需求，因為是JSON格式的，可以非常的靈活，返回值也是JSON  通過這樣一個抽象層， Lucene 那些復雜的 API 全部被隱藏了 ## 分布式 如果索引太大，我們把它切割一下，分成一片一片的，存儲到各個機器上不就得了  那么怎么要去保存索引和搜索索引呢？ 首先要保存每個分片(shard)和機器之間的對應關系， ~~~ 分片 1 ：node1 分片 2 ：node2 分片 3 ：node3 ~~~ 可以用余數算法來確定一個‘文檔’到底保存在哪個 shard 中。 **shard 編號 = hash(文檔的 ID) % shard 總數** 這樣對于任意一個文檔，對它的 ID 做 hash 計算，然后對總分片數量求余， 就可以得到 shard 的編號，然后就可以找到對應的機器了 但是如果用戶想增加shard數的時候余數算法就不能用了。 比如原來 shard 總數是 3， hash 值是 100， shard 編號 = 100 % 3 = 1 假設用戶又增加了兩臺機器，shard 總數變成了 5， 此時 shard 編號 = 100 % 5 = 0 ， 如果去 0 號機器上去找索引，肯定是找不到的。 要不采用分布式一致性算法， 嗯，它會減少出錯的情況，還是無法避免，這該怎辦 我們可以立下一個規矩： 用戶在創建索引庫的時候，必須要指定 shard 數量，并且一旦指定，就不能更改了 ~~~ PUT /coolspace { "settings" : { "number_of_shards" : 3 } } ~~~ 雖然對用戶來說有點不爽， 但余數算法的高效和簡單確實太吸引人了 索引數據分布了，如果某個節點壞掉了，數據就會丟失，我們得做個備份才行 可以用新的node來做replica，也可以為了節省空間，復用現有的node來做replica。 之前的分片叫做主分片，primary shard  ~~~ PUT /coolspace/_settings { "number_of_replicas" : 2 } ~~~ 雖然主分片的數目在創建 “索引庫” 的時候已經確定，但是副本的數目是可以任意增減的，這依賴于硬件的情況：性能和數量。 “現在每個主分片都有兩個副本， 如果某個節點掛了也不怕，比如節點 1 掛了，我們可以位于節點 3 上的副本 0 提升為 主分片 0， 只不過每個主分片的副本數不夠兩個了  等到節點1再次啟動的時候，還可以恢復副本 ## 集群 現在我們建立了一個集群， 這個集群中可以包含若干 node ， 有數據的備份，能實現高可用性。 那么另一個問題出現了對于客戶端來說，通過哪個 node 來讀寫‘文檔’呢 可以讓請求發送到集群的任意一個節點，每個節點都具備處理任何請求的能力 具體為： （1）假設用戶把請求發給了節點 1 （2）系統通過余數算法得知這個'文檔'應該屬于主分片 2，于是請求被轉發到保存該主分片的節點 3 （3）系統把文檔保存在節點 3 的主分片 2 中，然后將請求轉發至其他兩個保存副本的節點。副本保存成功以后，節點 3 會得到通知，然后通知節點 1， 節點 1 再通知用戶。  如果是做查詢呢？ 比如說用戶查詢一個文檔： GET /coolspace/blog/1001 查詢的請求也可以分發到任意一個節點，然后該節點可以找到主分片或者任意一個副本，返回即可 （1） 請求被發給了節點 1 （2）節點 1 計算出該數據屬于主分片 2，這時候，有三個選擇，分別是位于節點 1 的副本 2， 節點 2 的副本 2，節點 3 的主分片 2， 假設節點 1 為了負載均衡，采用輪詢的方式，選中了節點 2，把請求轉發。 （3） 節點 2 把數據返回給節點 1， 節點 1 最后返回給客戶端。  這種方式比較靈活，但是要求各個節點互通有無。 對于一個集群來說，還得有一個主節點（master node），這個主節點在處理數據請求上和其他節點是平等的，但是它還有更重要的工作，需要維護整個集群的狀態，增加移除節點，創建 / 刪除索引庫，維護主分片和集群的關系等等 如果這個主節點掛了，就只好從剩下的節點中重新選舉了 就涉及到分布式系統的各種問題了，什么一致性，腦裂 所以我們可以只選取一個Master， 比如一個Bully 的算法， 改進一下應該就可以用了