Notes on Distributed System -- Distributed Hash Table Based On Chord

task: 基于Chord实现一个Hash Table

 

我负责写Node，队友写SuperNode和Client。总体参考paper[Stoica et al., 2001]上的伪代码

FindSuccessor(key)：对chord环上的任意一个key，返回他的successor

FindPredecessor(key)：对chord环上的任意一个key，返回他的Predecessor

n.Closet_Preceding_Finger(key)：对chord环上的任意一个key，在node n的Finger table中查找它的最近的Predecessor

注意几个坑点：

1. 在UpdateDHT时，因为这个函数是被递归调用的，所以有可能会出现若干个node形成infinite loop的情况。解决方法就是在updateDHT函数入口设置一个List来记录visited过的节点，如果下次遇到重复的就退出。

2. 在FindSuccesor / FindPredecessor里，假设这个书名就该在自己node上 那findsuccessor里就不需要rpc，直接访问自己的的successor就行了。这个需要特别判断一下，不然自己rpc自己是会崩的

3. 在UpdateDHT的伪代码中，if(s属于[n, finger[i].node)) 这里在测试中发现有问题。我们改成了if(finger[i].start属于[finger[i].node, s])解决了问题。它表示对于finger[i]这一项，新节点s比该项的当前值finger[i].node靠后，且是该节点能触到的位置finger[i].start的successor，所以要更新。    （所以顶会论文也会出错么？

 

FingerTable的实现：

public class FingerItem{    //For FingerTable[i],
    Address Node;           //  Node = Successor(FingerTable[i].start)
    long ivx; long ivy;     //  [ivx, ivy) = [FingerTable[i].start, FingerTable[i+1].start)
    long start;             //  start = (NodeInfo.ID+(long)(Math.pow(2,i-1))) % (long)(Math.pow(2,ChordLen)))
    public FingerItem(Address _Node, long _ivx, long _ivy, long _start) {
        Node=_Node;
        ivx=_ivx;
        ivy=_ivy;
        start=_start;
    }
    public static long FingerCalc(long _n, int _k, int _m) {
        if (_k == _m + 1)
            return (_n);
        else
            return ((_n + (long) (Math.pow(2, _k - 1))) % (long) (Math.pow(2, _m)));
    }
    public void PrintItem(int i){
        System.out.println("FingerItem"+i+" "+Node+" "+ivx+"_"+ivy+" : "+start);
    }
}

FingerItem[ChordLen] FingerTable;