slides/src/kademlia/kademlia.md
src/kademlia/kademlia.mdRaw
1---
2marp: true
3---
4
5
6# Kademlia
7
8
9<br><br><br>
10[@arnaucube](https://twitter.com/arnaucube)
11
122019-04-26
13
14---
15
16### Overview
17- nodes self sets a random unique ID (UUID)
18- nodes are grouped in `neighbourhoods` determined by the `node ID` distance
19- Kademlia uses `distance` calculation between two nodes
20 - distance is computed as XOR (exclusive or) of the two `node ID`s
21
22---
23
24- XOR acts as the distance function between all `node ID`s. Why:
25 - distance between a node and itself is zero
26 - is symmetric: distance between A to B is the same to B to A
27 - follows `triangle inequality`
28 - given A, B, C vertices (points) of a triangle
29 - AB <= (AC + CB)
30 - the distance from A to B is shorter or equal to the sum of the distance from A to C plus the distance from C to B
31 - so, we get the shortest path
32---
33- with that last 3 properties we ensure that XOR
34 - captures all of the essential & important features of a "real" distance function
35 - is simple and cheap to calculate
36- each search iteration comes one bit closer to the target
37 - a basic Kademlia network with `2^n` nodes will only take `n` steps (in worst case) to find that node
38
39---
40
41### Routing tables
42- each node has a routing table, that consists of a `list` for each bit of the `node ID`
43 - each entry holds the necessary data to locate another node
44 - IP address, port, `node ID`, etc
45 - each entry corresponds to a specific distance from the node
46 - for example, node in the Nth position in the `list`, must have a differing Nth bit from the `node ID`
47 - so, the list holds a classification of 128 distances of other nodes in the network
48---
49- as nodes are encountered on the network, they are added to the `lists`
50 - store and retrieval operations
51 - helping other nodes to find a key
52 - every node encountered will be considered for inclusion in the lists
53 - keps network constantly updated
54 - adding resilience to failures and attacks
55---
56- `k-buckets`
57 - `k` is a system wide number
58 - every `k-bucket` is a `list` having up to `k` entries inside
59 - example:
60 - network with `k=20`
61 - each node will have `lists` containing up to 20 nodes for a particular bit
62- possible nodes for each `k-bucket` decreases quickly
63 - as there will be very few nodes that are that close
64- since quantity of possible IDs is much larger than any node population, some of the `k-buckets` corresponding to very short distances will remain empty
65---
66- example:
67
68 - network size: 2^3
69 - max nodes: 8, current nodes: 7
70 - let's take 6th node (110) (black leaf)
71 - 3 `k-buckets` for each node in the network (gray circles)
72 - nodes 0, 1, 2 (000, 001, 010) are in the farthest `k-bucket`
73 - node 3 (011) is not participating in the network
74 - middle `k-bucket` contains the nodes 4 and 5 (100, 101)
75 - last `k-bucket` can only contain node 7 (111)
76
77---
78
79- Each node knows its neighbourhood well and has contact with a few nodes far away which can help locate other nodes far away.
80- Kademlia priorizes long connected nodes to remain stored in the `k-buckets`
81 - as the nodes that have been connected for a long time in a network will probably remain connected for a long time in the future
82---
83- when a `k-bucket` is full and a new node is discovered for that `k-bucket`
84 - node sends a ping to the last recently seen node in the `k-bucket`
85 - if the node is still alive, the new node is stored in a secondary list (a replacement cache)
86 - replacement cache is used if a node in the `k-bucket` stops responding
87 - basically, new nodes are used only when older nodes disappear
88
89---
90
91### Protocol messages
92- PING
93- STORE
94- FIND_NODE
95- FIND_VALUE
96Each `rpc` msg includes a random value from the initiator, to ensure that the response corresponds to the request
97
98---
99
100### Locating nodes
101- node lookups can proceed asynchronously
102 - `α` denotes the quantity of simultaneous lookups
103 - `α` tipically is 3
104- node initiates a FIND_NODE request to the `α` nodes in its own `k-bucket` that are closest ones to the desired key
105---
106- when the recipient nodes receive the request, they will look in their `k-buckets` and return the `k` closest nodes to the desired key that they know
107- the requester will update a results list with the results (`node ID`s) that receives
108 - keeping the `k` best ones (the `k` nodes that are closer to the searched key)
109- the requester node will select these `k` best results and issue the request to them
110- the proces is repeated again and again until get the searched key
111---
112- iterations continue until no nodes are returned that are closer than the best previous results
113 - when iterations stop, the best `k` nodes in the results list are the ones in the whole network that are the closest to the desired key
114- node information can be augmented with RTT (round trip times)
115 - when the RTT is spended, another query can be initiated
116 - always the query's number are <= `α` (quantity of simultaneous lookups)
117
118---
119
120### Locating resources
121- data (values) located by mapping it to a key
122 - typically a hash is used for the map
123- locating data follows the same procedure as locating the closest nodes to a key
124 - except the search terminates when a node has the requested value in his store and returns this value
125
126---
127
128#### Data replicating & caching
129- values are stored at several nodes (k of them)
130- the node that stores a value
131 - periodically explores the network to find the k nodes close to the key value
132 - to replicate the value onto them
133 - this compensates the disappeared nodes
134---
135- avoiding "hot spots"
136 - for popular values (might have many requests)
137 - near nodes outside the k closest ones, store the value
138 - this new storing is called `cache`
139 - caching nodes will drop the value after a certain time
140 - depending on their distance from the key
141 - in this way the value is stored farther away from the key
142 - depending on the quantity of requests
143 - allows popular searches to find a storer more quickly
144 - alleviates possible "hot spots"
145- not all implementations of Kademlia have these functionallities (replicating & caching)
146 - in order to remove old information quickly from the system
147
148---
149
150### Joining the network
151- to join the net, a node must first go through a `bootstrap` process
152- `bootstrap` process
153 - needs to know the IP address & port of another node (bootstrap node)
154 - compute random unique `node ID` number
155 - inserts the bootstrap node into one of its k-buckets
156---
157- `bootstrap` process [...]
158 - perform a node lookup of its own `node ID` against the bootstrap node
159 - this populate other nodes `k-buckets` with the new `node ID`
160 - populate the joining node `k-buckets` with the nodes in the path between that node and the bootstrap node
161 - refresh all `k-buckets` further away than the `k-bucket` the bootstrap node falls in
162 - this refresh is a lookup of a random key that is within that `k-bucket` range
163 - initially nodes have one `k-bucket`
164 - when is full, it can be split