go-dht/kademlia/kademlia.go
kademlia/kademlia.goRaw
1package kademlia
2
3import (
4 "errors"
5 "fmt"
6 "math/bits"
7 "net/rpc"
8 "strconv"
9
10 log "github.com/sirupsen/logrus"
11)
12
13const (
14 alpha = 3 // 'alpha', max parallalel calls
15 B = 20 // 'B', 160 bits, ID length
16 KBucketSize = 20 // 'K', bucket size
17)
18
19type ListedNode struct {
20 ID ID
21 Addr string
22 Port string
23}
24
25type Kademlia struct {
26 // N is this node data
27 N ListedNode
28 KBuckets [B][]ListedNode
29}
30
31func NewKademliaTable(id ID, addr, port string) *Kademlia {
32 return &Kademlia{
33 N: ListedNode{
34 ID: id,
35 Addr: addr,
36 Port: port,
37 },
38 }
39}
40
41func (kad Kademlia) String() string {
42 r := "Node ID: " + kad.N.ID.String() + ", KBuckets:\n"
43 for i, kb := range kad.KBuckets {
44 if len(kb) > 0 {
45 r += " KBucket " + strconv.Itoa(i) + "\n"
46 for _, e := range kb {
47 r += " " + e.ID.String() + "\n"
48 }
49 }
50 }
51 return r
52}
53
54func (kad Kademlia) GetClosestKBucket(id ID) (int, error) {
55 kb := kad.KBucket(id)
56 if kb == 0 {
57 // is this node
58 return kb, nil
59 }
60 if len(kad.KBuckets[kb]) != 0 {
61 return kb, nil
62 }
63 for i := 0; kb-i > 0 || kb+i < 8; i++ {
64 if len(kad.KBuckets[kb+i]) != 0 {
65 return kb + i, nil
66 }
67 if len(kad.KBuckets[kb-i]) != 0 {
68 return kb - i, nil
69 }
70 }
71 return 0, errors.New("not found")
72}
73
74func (kad Kademlia) KBucket(o ID) int {
75 d := kad.N.ID.Distance(o)
76 return kBucketByDistance(d[:])
77
78}
79
80func kBucketByDistance(b []byte) int {
81 z := countZeroes(b)
82 if z == 0 {
83 return 0
84 }
85 for i := 0; i < 8; i++ {
86 if z>>uint8(i) == 1 { // check until 1 instead of 0 to avoid one operation
87 return i
88 }
89 }
90 return 7
91}
92
93func countZeroes(b []byte) int {
94 for i := 0; i < B; i++ {
95 for a := b[i] ^ 0; a != 0; a &= a - 1 {
96 return (B * 8) - (i * 8) - (8 - bits.TrailingZeros8(bits.Reverse8(uint8(a))))
97 }
98 }
99 return (B*8 - 1) - (B*8 - 1)
100}
101
102func (kad *Kademlia) Update(o ListedNode) {
103 k := kad.KBucket(o.ID)
104 kb := kad.KBuckets[k]
105 if len(kb) >= KBucketSize {
106 // if n.KBuckets[k] is alrady full, perform ping of the first element
107 log.Debug("node.KBuckets[k] already full, performing ping to node.KBuckets[0]")
108 kad.PingOldNode(k, o)
109 return
110 }
111 // check that is not already in the list
112 exist, pos := existsInListedNodes(kad.KBuckets[k], o)
113 if exist {
114 // update position of o to the bottom
115 kad.KBuckets[k] = moveToBottom(kad.KBuckets[k], pos)
116 log.Debug("ListedNode (" + o.ID.String() + ") already exists, moved to bottom")
117 return
118 }
119 // not exists, add it to the kBucket
120 kad.KBuckets[k] = append(kad.KBuckets[k], o)
121 log.Debug("ListedNode (" + o.ID.String() + ") not exists, added to the bottom")
122 return
123}
124
125func (kad *Kademlia) PingOldNode(k int, o ListedNode) {
126 // TODO
127 // ping the n.KBuckets[k][0] (using goroutine)
128 // if no response (timeout), delete it and add 'o'
129 // n.KBuckets[k][0] = o
130}
131
132func (kad *Kademlia) CallPing(o ListedNode) error {
133 client, err := rpc.DialHTTP("tcp", o.Addr+":"+o.Port)
134 if err != nil {
135 return err
136 }
137 ln := ListedNode{
138 ID: kad.N.ID,
139 Addr: kad.N.Addr,
140 Port: kad.N.Port,
141 }
142 var reply ListedNode
143 err = client.Call("Node.Ping", ln, &reply)
144 if err != nil {
145 return err
146 }
147 // TODO use reply as PONG
148 return nil
149}
150
151func (kad *Kademlia) CallPong(o ListedNode) error {
152 client, err := rpc.DialHTTP("tcp", o.Addr+":"+o.Port)
153 if err != nil {
154 return err
155 }
156 ln := ListedNode{
157 ID: kad.N.ID,
158 Addr: kad.N.Addr,
159 Port: kad.N.Port,
160 }
161 var reply bool
162 err = client.Call("Node.Pong", ln, &reply)
163 if err != nil {
164 return err
165 }
166
167 return nil
168}
169
170func existsInListedNodes(lns []ListedNode, ln ListedNode) (bool, int) {
171 for i, v := range lns {
172 if v.ID.Equal(ln.ID) {
173 return true, i
174 }
175 }
176 return false, 0
177}
178
179func moveToBottom(kb []ListedNode, k int) []ListedNode {
180 e := kb[k]
181 kb = append(kb[:k], kb[k+1:]...)
182 kb = append(kb[:], e)
183 return kb
184}
185func removeFromListedNodes(lns []ListedNode, k int) []ListedNode {
186 lns = append(lns[:k], lns[k+1:]...)
187 return lns
188}
189
190func (kad Kademlia) CallFindNode(id ID, o ListedNode) ([]ListedNode, error) {
191 client, err := rpc.DialHTTP("tcp", o.Addr+":"+o.Port)
192 if err != nil {
193 return nil, err
194 }
195 var lns []ListedNode
196 err = client.Call("Node.FindNode", id, &lns)
197 if err != nil {
198 return nil, err
199 }
200
201 return lns, nil
202}
203
204func (kad Kademlia) NodeLookup(id ID) ([]ListedNode, error) {
205 log.Debug("[NodeLookup] get closest KBucket for ", id)
206 // find closest kbucket for this current node
207 k, err := kad.GetClosestKBucket(id)
208 if err != nil {
209 return []ListedNode{}, fmt.Errorf("No KBuckets")
210 }
211 log.Debug("[NodeLookup] closest KBucket", k)
212
213 var closest ListedNode
214 var newClosest ListedNode
215 closest = kad.N
216 var lns []ListedNode
217 lns = kad.KBuckets[k]
218 for !closest.ID.Equal(newClosest.ID) { // TODO
219 // call each ListedNode from the kbucket, asking for their list of closest kbucket
220 var newLns []ListedNode
221 closest = newClosest
222 for k, ln := range lns {
223 // TODO TMP for the moment is synchronous
224 fmt.Println("calling node", ln)
225 flns, err := kad.CallFindNode(id, ln)
226 if err != nil {
227 log.Debug(err)
228 }
229 removeFromListedNodes(lns, k)
230 // newLns = append(newLns, flns...)
231 for _, fln := range flns {
232 exist, _ := existsInListedNodes(newLns, fln)
233 if !exist {
234 fmt.Println("ln", fln.ID, " not exists")
235 newLns = append(newLns, fln)
236 }
237 }
238 }
239 lns = newLns
240 newClosest = updateClosest(id, lns, closest)
241 }
242 return lns, nil
243}
244
245func updateClosest(id ID, lns []ListedNode, closest ListedNode) ListedNode {
246 d := id.Distance(closest.ID)
247 closestZ := countZeroes(d[:])
248 for _, ln := range lns {
249 d := id.Distance(ln.ID)
250 z := countZeroes(d[:])
251 if z < closestZ {
252 closest = ln
253 closestZ = z
254 }
255 }
256 return closest
257}