lightcloud、hash_ring分析
最近看了lightcloud和hash ring的實現，基於TokyoTyrant，以下是原理圖
下面結合原理圖分析其實現：
lightcloud採用了兩個環，一個用於存儲真正的數據，一個用於尋找（存儲key對應的在storage上的存儲節點）。環上的每個節點都可能有多臺服務器（一般爲兩臺，互爲備份，這也是利用了TT本身的優勢，解決consistent問題），這樣比amazon的實現簡單了很多很多。
下面一個實例爲例來說明具體的原理：
require 'rubygems'
require 'lightcloud'
LIGHT_CLOUD = {
'lookup1_A' => ['127.0.0.1:41401', '127.0.0.1:41402'], #尋找環（lookup ring），這上名有一個節點，
'storage1_A' => ['192.168.0.2:51401', '192.168.0.2:51402']
}
lookup_nodes, storage_nodes = LightCloud.generate_nodes(LIGHT_CLOUD)
cloud = LightCloud.new(lookup_nodes, storage_nodes)
cloud.set("hello", "world")
print cloud.get("hello") # => world
cloud.delete("hello")
首先：
'lookup1_A' => ['127.0.0.1:41401', '127.0.0.1:41402'], 表示尋找環（lookup ring）上有一個節點，而且這個節點上有兩個TT數據庫，互爲備份，所以 當需要 有多個 節點時，應該再增加類似的指定，如：'lookup1_A' => ['127.0.0.1:41401', '127.0.0.1:41402'],'lookup1_B' => ['127.0.0.1:41403', '127.0.0.1:41404']，這樣 這個環上就有兩個節點A,B
同理storage環也是一樣。
lookup_nodes, storage_nodes = LightCloud.generate_nodes(LIGHT_CLOUD)，這是生成lookup和storage兩組節點，只是歸類了下，通過'lookup'和'storage'兩個前綴匹配，所以指定時一定要有這兩個關鍵字，不能隨便取名。
cloud = LightCloud.new(lookup_nodes, storage_nodes)，這條語句按照兩組節點，生成兩個環，並且記錄，每個節點上名字對應的TT服務
cloud.set("hello", "world")，這條語句怎麼執行的嗎？原理很關鍵哦
首先，cloud找到lookup_ring，通過lookup_ring，找到對應的存儲節點，如果沒找到，則初始化存儲節點，即把'hello'這個key通過hash算法設置到相應的節點，並存儲，同時在lookup_ring上也通過同樣的hash算法，找到相應的節點，記錄這個key對應的storage_ring上的存儲節點。還有一點，在存儲的時候，前面提到，一個節點一般有兩個TT，因此，他這裏又 用類似的hash算法，通過'hello'這個key計算出一個hash值，找到相應的TT，存儲進去，因此，在存儲的時候，節點上的TT都可能用到，同時存儲後TT再自動進行備份。這樣整個寫入過程就OK拉。
cloud.get("hello")，這條語句又是怎麼執行的呢？
首先，直接到storage_ring上去找這個key的存儲節點，如果找到，那就返回，OK結束，但是，如果沒找到（這種情況，在增加節點，刪除節點後就會發生），那麼就先到lookup_ring上通過這個key找到所有可能的節點，再從第1－3個節點（即如果第一個節點上沒有這個key對應的值，就按順時針繼續找下一個節點，直到找到第3個爲止。） 找到對應的存儲節點，最後在存儲節點上找到key對應的值並返回。
下面說說，增加storage_ring上的節點，和lookup_ring上的節點的情況
當在storage_ring上增加一個節點後，如'hello'原來通過hash算法後是在節點B上的，當增加節點A後，'hello'通過hash算法後在節點A上，那麼在get的時候，就會找不到，所以要到lookup_ring去先得到'hello'的存儲節點（B），然後在到存儲節點（B）上去找到'hello'對應的值，其實lookup_ring充當了記錄的角色。
那麼當 lookup_ring上增加了一個節點呢？如'hello'原來通過hash算法後是在lookup_ring上的節點B上的，當在lookup_ring上增加了節點A後，'hello'通過hash算法後也在節點A上，那麼當在lookup_ring上找'hello'的存儲節點時，A上面是沒有記錄'hello'對應的存儲節點的，所以要找下一個（B），這時就找到了'hello'的存儲節點，然後到存儲節點上取得'hello'對應的值。在hash_ring上，其實是把'hello'所有可能的節點都通過hash算法按照順序找出來，然後從第一個開始找直到找到存儲節點，或找了3個以後還沒有找到就返回NIL,當不在第一個上找到時，會把'hello'這個key和對應的存儲節點記錄到第一個節點，並將找到的那個節點上的這個key刪除，這樣下次找的時候在第一個節點上就能找到。
這樣lightcloud通過兩個hash環解決了節點的增加，而且在兩個hash環上都可以增加節點，同時，刪除節點也隻影響刪除的節點上的key，其他節點上都不影響。