海量存储系列之十

可以看到，在客户机到服务器端，有这么几个东西 一，规则引擎 二，数据节点间的同步 抽象的来看，分布式K-V系统和传统的单机k-v系统的差别，也就只在于上面的两个地方的选择。 今天先来谈规则引擎 抽象的来看，规则引擎面向的场景应该被这样的描述：对于有状态的数据，需要一套机制以保证其针对同一个数据的多次请求，应该物理上被发送到同一个逻辑区块内的同一个数据上。 举例子来说，一个人进行了三笔交易，每笔交易都是这个人给其他人100元。那么，这三比交易的更新(update set money = money – 100 where userid = ?) 必须被发到同一台机器上执行，才能拿到正确的结果。【不考虑读性能的gossip模型除外】 这种根据一个userid 找到其对应的机器的过程，就是规则引擎所要处理的事情。 我们对于规则引擎的需求，一般来说也就是要查的快，第二个是要能尽可能的将数据平均的分配到所有的节点中去。第三个，如果新的节点加入进去，希望能够只移动那些需要移动的数据，不需要移动的数据则不要去移动他。 那么一想到“根据xxx找到xxx”相信大家第一个想到的一定又是以前说过的K-V了。所以我们就再复习一遍: ) Hash O(1)效率 不支持范围查询（时间这样的查询条件不要考虑了） 不需要频繁调整数据分布 顺序 主要是B-Tree O(logN)效率 支持范围查询 需要频繁调整节点指针以适应数据分布 这也就是我们最常用的两种分布式k-value所使用的数据结构了 首先来看HASH的方法。Hash其实很容易理解，但我跟不少人交流，发现大家可能对一致性hash的理解有一定的误解。下面请允许我给大家做个简单的介绍。 简单取模: 最简单的HASH 就是取mod,user_id % 3 。这样，会将数据平均的分配到0,1,2 这三台机器中。 这也是我们目前最常用的，最好用的方案。但这套方案也会有一个问题，就是如果id % 3 -> id % 4 总共会有75%的数据需要变动hash桶，想一想，只增加了一台机器，但75%的数据需要从一个机器移动到另外一个机器，这无疑是不够经济的，也是对迁移不友好的方案。 不过，虽然增加一台机器，会发生无谓的数据移动，但取模的方案在一些特殊的场景下，也能很好的满足实际的需要，如id % 3 -> id % 6，这种情况下，只需要有50%的数据移动到新的机器上就可以了。这也就是正常的hash取模最合适的扩容方式—–> 倍分扩容。我们一般把这种扩容的方式叫做”N到2N”的扩容方案。 取模Hash还有个无法解决的问题，就是无法处理热点的问题，假设有一个卖家有N个商品。如果按照卖家ID进行切分，那么就有可能会造成数据不均匀的问题。有些卖家可能有10000000个商品，而有些卖家只会有10个。这种情况下如果有大量商品的卖家针对他的商品做了某种操作，那这样无疑会产生数据热点。如何解决这类问题，也是分布式场景中面临的一个重要的问题。 既然简单取模有这么多的问题，那有没有办法解决这些问题呢？ 首先，我们来介绍第一种解决这个问题的尝试。 一致性Hash. 先来个图，这套图估计几乎所有对Nosql稍有了解的人都应该看过，在这里我会用另外的方式让大家更容易理解


                       

上面这个图，用代码来表示，可以认为是这样一套伪码 Def idmod = id % 1000 ; If(id >= 0 and id < 250) returndb1; Else if (id >= 250 and id < 500) returndb2; Else if (id >= 500 and id < 750) returndb3; Else returndb4; 这个return db1 db2 db3 db4 就对应上面图中的四个浅蓝色的点儿。 而如果要加一个node5 ，那么伪码会转变为 Def idmod = id % 1000 ; If(id >= 0 and id < 250) returndb1; Else if (id >= 250 and id < 500) returndb2; Else if (id >= 500 and id < 625) returndb5; else if(id >= 625 and id <750) returndb3 Else returndb4; 从这种结构的变化中，其实就可以解决我们在普通hash时候的面临的两个问题了。 1. 可以解决热点问题，只需要对热点的数据，单独的给他更多的计算和存储资源，就能部分的解决问题（但不是全部，因为迁移数据不是无成本的，相反，成本往往比较高昂） 2. 部分的能够解决扩容的问题，如果某个点需要加机器，他只会影响一个节点内的数据，只需要将那个节点的数据移动到新节点就可以了。 但一致性hash也会带来问题，如果数据原本分布就非常均匀，那么加一台机器，只能解决临近的一个节点上的热点问题，不会影响其他节点，这样，热点扩容在数据分布均匀的情况下基本等于n->2n方案。因为要在每个环上都加一台机器，才能保证所有节点的数据的一部分迁移到新加入的机器上。 这无疑对也会浪费机器。 于是，我们又引入了第三套机制:
虚拟节点hash Def hashid = Id % 65536  

可以很容易的看出，上面这套虚拟节点的方案，其实与id % 4的结果等价。 可以认为一致性hash和普通节点hash，都是虚拟节点hash的特例而已。 使用虚拟节点hash,我们就可以很容易的解决几乎所有在扩容上的问题了。 碰到热点？只需要调整虚拟节点map中的映射关系就行了 碰到扩容？只需要移动一部分节点的映射关系，让其进入新的机器即可 可以说是一套非常灵活的方案，但带来的问题是方案有点复杂了。 所以，我们一般在使用的方式是，首先使用简单的取模方案，如id % 4。在扩容的时候也是用N->2N的方案进行扩容。但如果碰到需求复杂的场景，我们会“无缝”的将业务方原来的简单取模方案，直接变为使用虚拟节点hash的方案，这样就可以支持更复杂的扩容和切分规则，又不会对业务造成任何影响了。 好，到这，我基本上就给大家介绍了如何使用Hash来完成分布式k-value系统的规则引擎构建了。 下一期我们来看一下使用树的方案，当然，主要也就是hbase这个东西了，可能会再介绍一下mongodb的自动扩容方案。**