tldr: Chord

-
Part of the tldr series, which summarizes papers I'm currently reading. Inspired by the morning paper

Stoica et. al

Introduction

The motivation for this paper is distributed peer-to-peer applications, which can't efficiently locate the node that stores a particular data item. Specifically, Chord supports 1 operation: given a key, it maps the key to a node. 

It uses consistent hashing to balance load, and Chord nodes only needs routing information for a few other nodes. 

Motivation & Context

Chord is a library linked to client and server applications that:
  • Provides a function, lookup(key) --> IP address of node with key
  • Notifies application on node of changes in its set of keys 
The above figure shows an example of an application using Chord.

Chord addresses the following issues:
  • Load balance
    • Chord is basically a distributed hash function that evenly spreads out keys over the nodes.
  • Decentralization
    • Chord is fully distributed
  • Scalability
    • The cost of lookup in Chord is proportional to the log of the number of nodes.
  • Availability
    • Chord automatically recovers to node failures, and adapts to new nodes.
  • Flexible naming
    • There are no constraints on the keys that Chord can look up.

Protocol

The Chord protocol provides the following guarantees:
  • With high probability, when the Nth node joins or leaves the network, O(1/N) of the keys are moved to a different location 
  • Each node maintains information about O(log N) other nodes
  • Lookup takes O(log N) messages 
  • When a node joins or leaves the network, updating the routing information takes O(log^2 N) messages

Consistent Hashing

Chord uses consistent hashing. The hash function assigns an m-bit identifier to each node and key  using a base hash function. Specifically, a node's IP address is hashed to get the node's identifier, and a node's key is hashed to get the key's identifier. 

Here's how keys are assigned to nodes: 
  • Node and key identifiers are ordered in an identifier circle mod 2^m. 
  • A key is assigned to the first node whose identifier is greater or equal to that key's identifier. This node is called a successor node. 
For example, in the figure below, the green dots represent the three nodes: 0, 1, and 3. The keys are 1, 2, 6, and boxed. Key 2 is located at node 3 because that's the first node greater or equal to 2. 

Why are identifier circles used? They actually contain the "damage" that happens when nodes enter or leave the network. For example, when a node joins the network, some keys assigned to the new node's successor now become assigned to the new node. No other disruptions occur.

Routing Information

Each node only stores information about only a small number of other nodes, and mostly about nodes closer to it. Let m again be the number of bits in the key and node identifiers. Each node maintains a routing table with at most m entries, called the finger table. The ith entry in the table of node n contains the identity of the first node that succeeds n by at least 2^(i-1) on the identifier circle. That first node is called the ith finger of node n. The figure below shows examples of fingers.

There are two operations that will be important later on:
  • find_successor(id)
    • If a node doesn’t know the successor of a key, it can find another node whose ID is closer to the key.
    • To do this, the node can repeatedly search its finger table for the node whose ID immediately precedes the key, and ask that node for the node that it knows is closest to the key.
  • find_predecessor(id)

Node Joins

In order to preserve the ability to locate keys, Chord preserves 2 invariants:
  • Every node’s successor is correctly updated. 
  • For every key k, the node successor(k) is responsible for k. 
Each node maintains a predecessor pointer that contains the identifier and IP address of the immediate predecessor of that node. Then, when a node n joins the network, Chord: 
  • Initializes the predecessor and fingers of node n 
  • Update fingers and predecessors of existing nodes to take n into account 
  • Notify the higher layer software so it can transfer values associated with keys that node n is now responsible for 

Popular posts from this blog

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each i...
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized...
Read more

tldr: Raft + Implementation Tips

-
Image
Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . Raft (Extended Version) + Implementation Tips [2014] Ongaro et al. Note: For implementation tips, see the end of this blog post.  Introduction Consensus algorithms The r eplicated state machine approach  is useful for providing fault-tolerance in distributed systems. It lets a cluster of unreliable machines continue operating even when some of its members fail. In this approach, machines   usually use a replicated log to stay in sync. As shown in the figure below, each server's log stores the same commands in the same order. Every state machine executes commands from its own log in order. State machines are deterministic, so each produces the same order of outputs. Once the majority of machines have responded, the command is done executing. Consensus algorithms ensure that the replicated log stays consistent. In the figure above, clients s...
Read more