Distributed hash table: Difference between revisions

Revision as of 11:47, 3 July 2023

Revision as of 15:34, 6 July 2023

Line 49:

{{further|Consistent hashing}}

Consistent hashing employs a function <math>\delta(k_1, k_2)</math> that defines an abstract notion of the distance between the keys <math>k_1</math> and <math>k_2</math>, which is unrelated to geographical distance or network [[Latencynetwork (engineering)|latency]]. Each node is assigned a single key called its ''identifier'' (ID). A node with ID <math>i_x</math> owns all the keys <math>k_m</math> for which <math>i_x</math> is the closest ID, measured according to <math>\delta(k_m, i_x)</math>.

For example, the [[Chord (peer-to-peer)|Chord DHT]] uses consistent hashing, which treats nodes as points on a circle, and <math>\delta(k_1, k_2)</math> is the distance traveling clockwise around the circle from <math>k_1</math> to <math>k_2</math>. Thus, the circular keyspace is split into contiguous segments whose endpoints are the node identifiers. If <math>i_1</math> and <math>i_2</math> are two adjacent IDs, with a shorter clockwise distance from <math>i_1</math> to <math>i_2</math>, then the node with ID <math>i_2</math> owns all the keys that fall between <math>i_1</math> and <math>i_2</math>.