Adam'sAboutArchivesRSSJun 30, 2018Jump consistent hash算法分析Jump Consistent Hash是一个来自Google的快速, 几乎没有内存消耗的一致性哈希算法. 这篇文章是我的翻译和理解思路.哈希算法的设计目标平衡性, 把对象均匀地分布在所有桶(bucket)中.单调性, 当桶的数量变化时, 只需要把一些对象从旧桶移动到新桶, 不需要做其它(例如旧桶之间的)移动.比如一个分布式存储的系统, 按哈希分布带来优化的便利, 平衡性可以避免数据倾斜, 单调性则使得扩容和减容更快速.算法的设计思路我们用循序渐进的思路来设计, ch(key, num_buckets)为桶数为num_buckets时的hash函数, 为了满足设计目标, 需要:num_buckets为1时, 任意key, ch(key, 1)==0, 全落在第0个桶里.num_buckets由1变为2后, ch(key, 2)应该有1/2的结果保持为0, 有1/2变为1.…num_buckets由n变为n+1后, ch(key, n+1)应该有n/(n+1)的结果保持不变, 有1/(n+1)跳变为n+1.因此, 只要我们用一个分布均匀的函数, 例如伪随机数生成器, 并且让这个伪随机数生成器的状态只依赖于key, 从0个桶开始推导, 变到第num_buckets个桶, 结果就是我们想要的hash值:int ch(int key, int num_buckets) {random.seed(key);int b = 0;for (int j = 1; j < num_buckets; j++) {if (random.next() < 1.0 / (j + 1))b = j;}return b;}很显然, 这个算法是O(n)的, 而且随着j越来越大, b=j需要执行的概率也越来越低. Google最终的算法叫Jump Consistent Hash, Jump指的是j是跳跃的, 那他们是怎么让j跳跃, 并保持结果正确呢?我们用概率的思路来想这个问题, 假设变化过程中的上一次结果是b, 下一次结果j大于等于一个大于b的数i的概率, 也就是可以跳到i的概率, 也就是从b+1到i的过程中, 桶序号都没有变的概率为:P(j>=i) = P(ch(key, b+1)==ch(key, i))这个概率也就是连续多次不变事件概率的乘积:P(j>=i) = P(ch(key, b+1)==ch(k, b+2)) * P(ch(key, b+2)==ch(key, b+3)) * ... * P(ch(key, i-1)==ch(key, i))由于单次不变的概率为:P(ch(key, i)==ch(key, i+1)) = i/(i+1)所以连续多次不变的概率为:P(j>=i) = (b+1)/(b+2) * (b+2)/(b+3) * ... * (i-1)/i = (b+1)/i基于之前的代码, 当随机结果r小于(b+1)/i时跳到i就可以保持概率不变, 也就是任意的r都可以跳到floor((b+1)/r):int ch(int key, int num_buckets) {random.seed(key);int b = -1;int j = 0;while (j < num_buckets) {b = j;double r = random.next();j = floor((b + 1) / r);}return b;}最终的完整代码最终代码里没有用random函数, 而是写了一个基于”线性同余方法”的伪随机数产生器, 意思是一样的.int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {int64_t b = -1, j = 0;while (j < num_buckets) {b = j;key = key * 2862933555777941757ULL + 1;j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));}return b;}May 31, 2018How Greenplum plans a JOINWhat is a “JOIN”INNER JOIN is an AND, OUTER JOIN is an OR.id name       id  name-- ----       --  ----1  Pirate     1   Rutabaga2  Monkey     2   Pirate3  Ninja      3   Darth Vader4  Spaghetti  4   NinjaINNER JOIN’s results are those tuples in table A AND B.# SELECT * FROM TableAINNER JOIN TableBON TableA.name = TableB.name;id |  name  | id |  name----+--------+----+--------3 | Ninja  |  4 | Ninja1 | Pirate |  2 | Pirate(2 rows)FULL [OUTER] JOIN’s results are those tuples in table A OR B.# SELECT * FROM TableAFULL OUTER JOIN TableBON TableA.name = TableB.name;id |   name    | id |    name----+-----------+----+-------------3 | Ninja     |  4 | Ninja|           |  3 | Darth Vader2 | Monkey    |    |1 | Pirate    |  2 | Pirate|           |  1 | Rutabaga4 | Spaghetti |    |(6 rows)LEFT [OUTER] JOIN’s results are those tuples in table A OR (A AND B).# SELECT * FROM TableALEFT OUTER JOIN TableBON TableA.name = TableB.name;id |   name    | id |  name----+-----------+----+--------1 | Pirate    |  2 | Pirate3 | Ninja     |  4 | Ninja2 | Monkey    |    |4 | Spaghetti |    |(4 rows)JOIN is not simple in GreenplumGreenplum is (was ?) a shared-nothin