Chris Kim's Digital Garden

04-P2P Systems & Distributed Hash Table

Properties3
description—
tagsarea/distributed-systems, topic/distributed-hash-table, topic/p2p, topic/chord-lookup, topic/consistent-hashing, topic/key-value-store
aliases—

8 min read

Peer-to-peer (P2P) system

A distributed system architecture:

  • No centralized control
  • Nodes are roughly symmetric in function
  • A node is both a client and a server
  • Large number of unreliable nodes

P2P adoption

  1. Client-to-client file sharing (ex. BitTorrent)
  2. Digital Currency (ex. Bitcoin)
  3. Voice/video telephony: user to user (Skype in old days)
    • Issues: Privacy and control

Why might P2P be a win?

  • High capacity for services through parallelism and scalability
    • More disks, network connections, CPUs, etc. as peers join
    • Data are divided and duplicated, accessible from multiple peers concurrently
  • Absence of a centralized server may mean:
    • Less chance of service overload as load increases
    • Easier deployment
    • A single failure won’t wreck the whole system
    • System as a whole is harder to attack

The lookup problem

Centralized lookup (Napster)

  • Simple, but O(n) and a single point of failure

Flooded queries (original Gnutella)

  • Robust, but O(n = number of peers) messages per lookup

What is Distributed Hash Tables (DHT)?

Distributed Hash Table: an abstraction of hash table in a distributed setting.

Assume:

Physical servers: 100
Virtual nodes: 1,000
Virtual nodes per server: 1,000 / 100 = 10
Hash function: SHA-1
Identifier space = M: 160 bits <- SHA-1 produces 160 bits identifier space
Identifier range: 0 through 2^160 - 1

A SHA-1 identifier is commonly written as 40 hex digits:

0000000000000000000000000000000000000000
through
ffffffffffffffffffffffffffffffffffffffff

Suppose the physical servers have these network addresses:

Server 1:    10.0.0.1
Server 2:    10.0.0.2
...
Server 100:  10.0.0.100

Each physical server receives 10 virtual nodes.
For this example, we generate each virtual-node identifier as:

vnode_id = SHA1(server_address + "#" + vnode_number)

For example:

SHA1("10.0.0.74#7") =
ae85fe88d1c78d5f40aca2aac0033a8e8d0c530c

Therefore, server 10.0.0.74 has 10 virtual node positions as follows:

10.0.0.74#0 → 5f82af43b3087b126c4c14462bbf017a6c6e8a66
10.0.0.74#1 → 1052909258d784f2881bf1e9367d89ae54f9ac2e
...
10.0.0.74#9 → e3ab664454c0e7ebee0af9691e6426dc976b5a9e

With virtual nodes, it is often clearer to say:

Physical server:
    network machine with an IP address

Virtual node:
    logical position with a 160-bit identifier

The 1,000 virtual nodes divide the ring into 1,000 ownership intervals.

Suppose a client wants to store these entries:

"user:42"             → user profile
"photo:beach.jpg"     → image metadata
"video:abc123"        → video metadata

We hash the application key:

key_id = SHA1(application_key)

Resulting mappings using our 1,000 virtual nodes:

Application keySHA-1 key identifierResponsible virtual nodePhysical server
user:42adf14d23...003ef4bc10.0.0.74#710.0.0.74
photo:beach.jpg462a322c...eab8f6f410.0.0.29#810.0.0.29
video:abc1236ef2d402...21c4e70a10.0.0.100#210.0.0.100

A complete put() example

Suppose a client performs:

put(
    key   = "user:42",
    value = {
        "name": "Chris",
        "email": "chris@example.com"
    }
)

Step 1: Hash the key

SHA1("user:42")
    = adf14d23d3caa1297fd8df9a6f360b9d003ef4bc

Step 2: Find the first virtual node clockwise, possibly using Chord Lookup

Previous vnode:
ad9a5f57195c65a0ad0c1ef28242dfa864b4283f

Data key:
adf14d23d3caa1297fd8df9a6f360b9d003ef4bc

Next vnode:
ae85fe88d1c78d5f40aca2aac0033a8e8d0c530c -> 10.0.0.74#7

Step 3: Contact the physical server

RPC to 10.0.0.74:

PUT
key_identifier = adf14d23d3caa1297fd8df9a6f360b9d003ef4bc
original_key    = "user:42"
value           = {
    "name": "Chris",
    "email": "chris@example.com"
}

The local stroage on server 10.0.0.74 might then contains:

Local database on 10.0.0.74

Key identifier:
	adf14d23d3caa1297fd8df9a6f360b9d003ef4bc

Original key:
	"user:42"

Value:
	{
	    "name": "Chris",
	    "email": "chris@example.com"
	}

Owned through virtual node:
	10.0.0.74#7

A complete get() example

Later, another client requests:

get("user:42")

It calculates the same SHA-1 value:

SHA1("user:42")
    = adf14d23d3caa1297fd8df9a6f360b9d003ef4bc

Because every participant uses the same hash function and ring membership information, it reaches the same result, possibly using Chord Lookup

Key identifier
    ↓ -- Chord Lookup
Responsible virtual node: 10.0.0.74#7
    ↓
Physical address: 10.0.0.74

It then sends:

RPC to 10.0.0.74:

GET
key_identifier = adf14d23d3caa1297fd8df9a6f360b9d003ef4bc
original_key    = "user:42"

Server 10.0.0.74 returns the value.
The original application key may be included so the server can distinguish between different keys in the extremely unlikely event of a SHA-1 identifier collision.

After inserting all three entries, the physical arragement could be:

Server 10.0.0.29
└── vnode #8
    └── "photo:beach.jpg"

Server 10.0.0.74
└── vnode #7
    └── "user:42"

Server 10.0.0.100
└── vnode #2
    └── "video:abc123"

The other 95 physical servers happen not to own these three particular example entries, but they would own many other keys.
With millions of independently hashed keys, data would generally be distributed across all 100 servers.

Observations

Because DHT keys and nodes share one same identifier space, the DHT can define a consistent rule for which key maps to which node, like Consistent Hashing

Hash collection can happen:

  • Key identifier collision:
    • The storage layer can also preserve the original app key to distinguish values sharing an identifier.
  • Node identifier collision:
    • Generating a new identifier
    • Using additional identity information
    • Rejecting the joining node
    • etc

The Chord Lookup Service (Lookup with finger table)

What Chord solves

Chord is useful when there is no central directory and no requirement that every participant knows every node.
Each Chord node knows only a small amount of the entire system:

its successor
its predecessor
a finger table containing selected shortcuts

Suppose Node 15 receives a request for key ID 83.
Node 15 does not have a complete list such as:

all 1,000 vnode IDs and IP addresses

Instead, it asks:

Among the nodes I know, which one gets me closest to 83 without passing it?

It forwards the lookup:

Node 15 → Node 47 → Node 72 → Node 81 → Node 86

Node 86 is the first active node clockwise from key 83, so it is responsible.

Therefore, Chord lookup answers:

Given a key identifier, find the responsible node without requiring knowledge of global ring map.

Chord identifiers

  • Hashed values (integers) using the same hash function

    • Key identifier = SHA-1(key)
    • Node identifier = SHA-1(IP address)

  • How does Chord partition data?

    • i.e., map key IDs to node IDs

  • Why hash key and address?

    • Uniformly distributed in the ID space
    • Hashed key leads to load balancing; hashed address leads to independent failure

Consistent Hashing

Chord lookup assumes consistent hashing for keys and nodes distribution:

Key is stored as its successor: node with next-higher ID

Basic lookup - naive lookup

  • Each nodes only knows its successor
  • Node 0 knows Node 1 stores key 1

Chord lookup - finger tables


Each node keeps m = 3 states of successor nodes scoped by key ranges defiend by separators.

For example, N is node ID = 1
(1 + 21-1) mod 23 = 2
(1 + 22-1) mod 23 = 3
(1 + 23-1) mod 23 = 5

Two possible DHT designs

Design 1: Everyone knows the whole ring

Each client or server stores:

all vnode IDs
all vnode-to-server mappings

Lookup:

hash key
binary-search local ring table
contact responsible server directly

Advantages:

  • Simple and fast lookup (approximately O(log N) local computation )
  • Usually one network request to the destination
  • Easy to understand

Disadvantages:

  • Every node must receive membership updates
  • Join, leave, and failure information must be broadcast
  • Large clusters can create significant metadata traffic
  • Stale membership information may send requests to failed nodes

For a cluster with only 100 servers and 1,000 virtual nodes, this approach is very practical. The complete token map is not especially large.

Design 2: Chord-style decentralized routing

Each node stores only roughly O(log N) routing entries rather than all N nodes.

Lookup:

hash key
route through several Chord nodes
reach responsible node

Advantages:

  • No central directory required
  • Each node keeps only limited routing state
  • Membership management is decentralized
  • Can theoretically scale to very large peer-to-peer networks

Disadvantages:

  • A lookup may require several network hops
  • Routing tables can become stale
  • Stabilization logic is more complicated
  • Usually slower than direct lookup from a complete ring map

Why hashing alone is not enough

Hashing tells you the key’s coordinate:

"user:42" -- SHA-1 --> adf14d23...

But it doesn’t automatically tell you:

which active vnode comes next?
what IP address owns that vnode?
is that node still alive?
has a new node joined between two old nodes?

To determine the owner, you need membership information.
That information can come from:

A centralized directory
A complete ring map copied to every node
A metadata service
Gossip-based membership dissemination
Chord routing
Another DHT routing protocol

Wrapup

DHT
    distributed key-to-node mapping abstraction

Consistent hashing
    rule for deciding which node should own a key

Chord
    decentralized protocol for locating that node

Finger table
    routing shortcuts used by Chord

A DHT does not inherently require Chord. In a managed cluster of 100 servers, maintaining a complete ring map on every server may be simpler. Chord is particularly attractive for decentralized, dynamic, peer-to-peer environments where keeping a complete global membership list everywhere is undesirable.

Chord - node joining

  • Node 2 lookup itself to find out its successor, which in this case is Node 3.
  • Nodes moved key 2 to node 2
  • Period stablization message from each node to its successor maintains node positions

As a result:

Chord - failures and successor list

Node fails
    ↓
Other nodes initially retain stale pointers
    ↓
Communication attempts time out
    ↓
Predecessor selects first live node in successor list
    ↓
Lookups retry through alternative fingers/successors
    ↓
Stabilization removes stale routing entries
    ↓
Keys map to the next living successor
    ↓
Actual values remain available only if the storage layer replicated them

Why don’t all services use P2P?

  1. High latency and limited bandwidth between peers (vs. intra/inter-datacenter, client-server model)
  2. User computers are less reliable than managed servers
  3. Lack of trust in peers’ correct behavior
    • Securing DHT routing is hard, unsolved in practice

Backlinks