论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2013-03-01 14:52 |只看该作者 |倒序浏览

下面是TS CLUSTER的工作流程图现在有个疑问：

cache server1怎么知道去cache server2请求数据，它是向整个集群发送广播？还是每个集群成员都相互通告自己的缓存内容（集群中维护着一个完整的内容--位置的数据表格）？

疑问, server1, 流程图

10249062_1339658797eOiy.png (31.28 KB, 下载次数: 30)

文库|博客

LnBSD

丰衣足食

论坛徽章:: 0

2楼 [报告]

发表于 2013-03-01 15:20 |只看该作者

本帖最后由 LnBSD 于 2013-03-01 15:22 编辑

回复 1# llzqq
老兄，一致性hash啊
你可以把它想象为url hash
和memcache的集群差不多的方式
等老赵进行权威解释吧

附：

TrafficServer的一致性hash实现与基于RBTree的一致性hash实现存在着比较大的差异。下面以Cluster模式的一致性哈希实现为例进行说明：
1 数据结构
在trafficser中实现一致性hash的结构为struct ClusterConfiguration，其定义如下：
struct ClusterConfiguration
{
int n_machines; //cluster包含的机器数目
ClusterMachine *machines[CLUSTER_MAX_MACHINES]; // 机器结构，256
ClusterMachine *machine_hash(unsigned int hash_value) // 计算hash在那台机器
{
return machines[hash_table[hash_value % CLUSTER_HASH_TABLE_SIZE]];
}
unsigned char hash_table[CLUSTER_HASH_TABLE_SIZE]; // hash空间 32707
…...
};
2. hash空间建立过程
假设有三台server，ip地址分别为1.1.1.1，2.2.2.2，3.3.3.3。则通过这三个ip地址能够分别计算出来三个hash值，再在该hash值的基础上加入随机因子计算出来另外的hash值（hash = 1103515145 * hash + 12345），依次递归可以得到三台server的一连串hash值。如下所示：
server：hash1->hash2->hash3.......hash n
hash(n) = 1103515145 * hash(n - 1) + 12345
再利用hash%/ CLUSTER_HASH_TABLE_SIZE分别得到hash table的slot，如果发生冲突则再用本hash链的下一个hash值，直至分配到一个hash table的slot。通过这样的方式依次利用server1、server2、server3 hash链中的hash值交替的填充hash table。
备注：实现文件trafficserver/iocore/cluster/ClusterHash.cc，实现函数为：build_hash_table_machine()
3 机器变动处理
在增加一台server（假设为Server4）时，由于原有server的hash链不会发生改变。因此，通过原有的hash链中hash值得到的slot不会发生变化。只是由于交替插入的时候引入了Server4的hash链，因此重新生成hash table时，server1-server3 hash链中插入hash table的hash值个数变少了。而这些少的slot正好由Server4 hash链中的hash值代替了。从而实现一致性hash。
在删除一台server（Server3）时，由于原有server的hash链不会发生改变。因此，通过原有的hash链中hash值得到的slot不会发生变化。只是由于交替插入的时候由于删除了Server3的hash链，因此重新生成hash table时，server1-server2 hash链中插入hash table的hash值个数变多了。而这些多的slot正好代替Server3 hash链中的hash值。从而实现一致性hash。
4 不足
基于hash链的一致性hash实现在有节点变动的时候需要重建hash table，其时间复杂度为O（hash table size * hash冲突）。而基于RBTree实现的时间复杂度为O（log（hash table size）*虚拟node数）。因此，在一些情况下，时间复杂度会高于RBTree的实现。