讨论班 邵松松 一致性哈希算法.pptx

文档介绍：一致性哈希map/reduce过程一致性哈希在map/reduce中的应用Question Hadoop是如何保证任务平均分配的? 任务存储存储的平均分配一致性哈希在map/reduce中的应用Answer一致性哈希(ConsistenceHashing)广泛应用于分布式存储、Memcached哈希算法HashMap当使用HashMap时,key被均匀地映射到数组之上,映射方法就是利用key的hash与数组长度取模,即:hash(object)%Nn个服务器1,2,3….n考虑不利因素不利因素服务器掉线hash(object)%(N-1);访问加重添加服务器hash(object)%(N+1);意味着什么呢?一致性哈希(consistenthashing)Hash算法的一个衡量指标是单调性(Monotonicity): 单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证新的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。consistenthashing是一种hash算法,简单的说,在移除/添加一个服务器时,它能够尽可能小的改变已存在key映射关系,尽可能的满足单调性的要求。一致性哈希(consistenthashing) 通常的hash算法都是将value映射到一个32为的key值,也即是0~2^32-1次方的数值空间;我们可以将这个空间想象成一个首(0)尾(2^32-1)(consistenthashing) 接下来考虑4个对象object1~object4,通过hash函数计算出hash值key在环上的分布 hash(object1)=key1; …… hash(object4)=key4;一致性哈希(consistenthashing) Consistenthashing的基本思想就是将对象和cache都映射到同一个hash数值空间中,并且使用相同的hash算法。 假设当前有A,B和C共3台cache,那么其映射结果将如图3所示,他们在hash空间中,以对应的hash值排列。 hash(cacheA)=keyA; …… hash(cacheC)=keyC;