Yes, after storing many items in a distributed hash table spread over a hundred computers, if hypothetically we used the sort of hash function popular for in-RAM hash table, adding another computer would cause every item to be re-hashed and nearly every item to move from one computer to another, which could take days.
So instead we use special hash functions specifically designed for DHT applications, which allow us to add computers and more-or-less immediately start using them and only re-arrange a few items. (Ideally, with around 100 computers, about 1 percent of the items in each and every computer already in the DHT would move to the new computer).
Confusingly, some people use "consistent hashing" to refer to any such system where relatively few items are re-shuffled when a new computer is added or removed from the system, although most use "consistent hashing" to refer to the one particular such system described below.
I now know of 4 different hash algorithms solve the distributed hash table problem, all of them (coincidentally?) published in 2001.
(Are there others?)
- rendezvous hashing, also called highest random weight hashing (HRW):
A client with a list of computers Cj looks up some key K by giving each computer a score Sj = hash( K | Cj ).
The key, value pair K,V is stored on the computer with the highest score.
(For two-failure-tolerant systems, the key,value pair K,V is stored on the three computers with the highest scores).
- consistent hashing:
A client with a list of computers Cj maps each computer to a location on the the edge of a circle. The client looks up some key K by starting at the point where K maps onto the circle, and walking clockwise until it hits a computer. (Each computer is actually mapped to many "replica" points on the edge of the circle). (For two-failure-tolerant systems, the key,value pair K,V should be stored on the first three different computers it walks across).
The "distance" walked is d = (unsigned int)(hash(K) - hash(Cj)).
In some implementations, such as Chord and Pastry, none of the computers nor the client really knows all of the computers in the DHT. The client sends a request to a few of the closest computers ''that it knows'', asking about the key. Each such computer either responds with the (key, value) data item if it has it, or with a list of other, closer computers.
- content addressable network (CAN) has some similarities to consistent hashing, except instead of a one-dimensional circle-edge, it uses a multi-dimensional torus.
- Kademlia algorithm:
A client that only knows about a few of the computers in the DHT looks up some key K by finding the computers that are "close" to the key, where the "distance" is calculated as d = hash(Cj) XOR hash(K). (This abstract "distance" function is completely uncorrelated with the real, physical distance in miles between servers). The client sends a request to a few of the closest computers ''that it knows'', asking about the key. Each such computer consults its tables and reply with a list of the closest computers to the desired key ''that it knows''. The client sends a request to a few of those ever-closer computers, asking about that key, and repeats that process until no new nodes are returned that are closer than the best previous results. (For two-failure-tolerant systems, the key,value pair K,V should be stored on the three "closest" computers to that key K).
There is one additional technique often used to make adding a new computer to a DHT appear "instantaneous": indirection.
Immediately after adding a new computer to a DHT system, most items should remain in the same place, but there are typically lots of items that need to move from each old computer to the new computer -- it may take a day before all those items are moved, typically as a low-priority "background task".
Long before all those items are moved, each old computer sends a brief summary of those items to the new computer, and when some client asks the new computer for some particular item, the new computer either (a) admits to the client it doesn't have that file yet, and tells the client which one of the old computers still has that item, or (b) bumps up the priority of moving that item to a "foreground task", possibly streaming each block of that item to the client as soon as it is received from the old computer.
