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，其他节点上都不影响。

评论

1 楼 totothink 2010-07-05  

不错的文章。LightCloud作为Plurk团队开源的轻量级云存储项目，实现非常简单实用。 它底层采用的是TokyoCabinet和TokyoTyrant，TC和TT是日本最大社交网站mixi的开源项目。 LightCloud利用TT本身的主主复制解决单点故障的问题，利用hash_ring实现分布式调度。  应该说LightCloud用简单的方法解决复杂的问题，非常不错的思路。