Chapster — Chord-Powered Napster

A production-grade implementation of the Chord Distributed Hash Table (DHT) protocol for peer-to-peer file sharing and distributed key-value storage. This project implements the complete Chord protocol as described in the seminal paper by Stoica et al. (2001), including finger tables, stabilization, replication, and failure recovery.

Overview

Chapster is a distributed peer-to-peer system that enables:

Decentralized file storage and retrieval across multiple nodes
Efficient O(log N) lookups using Chord's finger table routing
Automatic load balancing through consistent hashing
Fault tolerance with R-way replication (default R=3)
Self-healing ring maintenance via stabilization protocol
Graceful node joins and exits with proper key redistribution
Dynamic file monitoring that detects changes to shared files

Why Chord?

Chord solves the problem of locating data in a large-scale distributed system without centralized coordination:

Each node maintains only O(log N) state
Lookups complete in O(log N) hops
Nodes can join/leave dynamically
Robust to network partitions and failures

Architecture

System Components

┌─────────────────────────────────────────────────────────────┐
│                        Chapster Node                        │
├─────────────────────────────────────────────────────────────┤
│  ┌──────────────┐  ┌──────────────┐  ┌─────────────────┐    │
│  │   CLI        │  │  FastAPI     │  │  TCP Server     │    │
│  │  Interface   │  │  REST API    │  │  (Port P)       │    │
│  │              │  │ (Port P+1K)  │  │                 │    │
│  └──────────────┘  └──────────────┘  └─────────────────┘    │
│         │                  │                   │            │
│         └──────────────────┼───────────────────┘            │
│                            ▼                                │
│              ┌─────────────────────────────┐                │
│              │       RingNode (State)      │                │
│              ├─────────────────────────────┤                │
│              │ • Identity & Hashing        │                │
│              │ • Finger Table (M=160)      │                │
│              │ • Successor List (R=3)      │                │
│              │ • File Metadata Storage     │                │
│              │ • Ring Pointers             │                │
│              └─────────────────────────────┘                │
│                            │                                │
│         ┌──────────────────┼──────────────────┐             │
│         ▼                  ▼                  ▼             │
│  ┌──────────────┐  ┌────────────────┐  ┌──────────────┐     │
│  │ Chord Ops    │  │ Stabilization  │  │ Replication  │     │
│  │ (finger.py)  │  │ (stabilize.py) │  │ (replica.py) │     │
│  └──────────────┘  └────────────────┘  └──────────────┘     │
└─────────────────────────────────────────────────────────────┘

Ring Topology

                 Node A (hash: 0.125)
                          ○
                         ╱ ╲
                Finger  ╱   ╲  Successor
                       ╱     ╲
                      ╱       ╲
         Node D      ○         ○      Node B
       (hash: 0.875)  ╲       ╱   (hash: 0.375)
                       ╲     ╱
                Pred.   ╲   ╱  Finger
                         ╲ ╱
                          ○
                  Node C (hash: 0.625)

         Ring Structure with Finger Shortcuts

Chord Protocol Implementation

Hash Space

Hash Function: SHA-1 (160-bit output)
Identifier Space: [0, 2^160) mapped to [0, 1)
Node ID: h = SHA-1(machine_hash_key + "ip:port") / 2^160
Key ID: h = SHA-1(file_hash_key + filename) / 2^160

Consistent Hashing

Each node n is responsible for keys in the range (predecessor(n), n] on the circular identifier ring.

Example with 4 nodes:
  Node A (0.125) owns keys in (0.875, 0.125]
  Node B (0.375) owns keys in (0.125, 0.375]
  Node C (0.625) owns keys in (0.375, 0.625]
  Node D (0.875) owns keys in (0.625, 0.875]

Finger Table

Each node maintains M = 160 finger table entries for efficient routing:

finger[i] = successor( (n + 2^i) mod 2^M )

finger[0]: Immediate successor
finger[1]: Node at distance 2^1
finger[k]: Node at distance 2^k
finger[159]: Node at distance 2^159

Routing Algorithm: To find key k, node n forwards the request to the closest preceding finger in its table. This achieves O(log N) hops.

Core Algorithms

1. Find Successor (O(log N) Lookup)

def find_successor(n, id):
    """
    Find the node responsible for identifier 'id'.
    Returns the first node whose ID is >= id on the ring.
    """
    if id ∈ (n, successor(n)]:
        return successor(n)
    else:
        n' = closest_preceding_finger(n, id)
        return n'.find_successor(id)

def closest_preceding_finger(n, id):
    """
    Search finger table backwards for the closest node
    preceding 'id' in the identifier space.
    """
    for i = M-1 down to 0:
        if finger[i] ∈ (n, id):
            return finger[i]
    return successor(n)

2. Stabilization Protocol

Runs periodically (every 15 seconds) to maintain ring consistency:

def stabilize(n):
    """
    Verify and correct immediate successor.
    Ask successor for its predecessor, which might be between us.
    """
    x = successor(n).predecessor
    if x ∈ (n, successor(n)):
        successor(n) = x
    successor(n).notify(n)

def notify(n, candidate):
    """
    Candidate thinks it might be our predecessor.
    Update if candidate is closer than current predecessor.
    """
    if predecessor(n) is None or candidate ∈ (predecessor(n), n):
        predecessor(n) = candidate

3. Fix Fingers Protocol

Periodically refreshes one finger table entry (every 15 seconds):

def fix_fingers(n):
    """
    Incrementally update finger table entries.
    Cycles through all M entries over time.
    """
    next = (next + 1) mod M
    if next == 0: next = 1  # Skip finger[0], managed by stabilize
    finger[next] = find_successor(n + 2^next)

4. Join Protocol

def join(n, n'):
    """
    Join ring via existing node n'.
    """
    predecessor(n) = None
    init_finger_table(n, n')  # Initialize finger table
    update_others(n)           # Update others' finger tables
    transfer_keys(n)           # Move keys from successor

Key Features

1. Replication (R = 3)

Each key is replicated on R successive nodes
Primary node stores in other_files
Replica nodes store in replica_files
Successor list maintains R successors for replication
On failure, replicas are promoted to primary

Replication Strategy:

Node A owns key K → replicates to successors B, C, D
  A: other_files[K] = primary     (DHT routing responsibility)
  B: replica_files[K] = replica   (backup copy)
  C: replica_files[K] = replica   (backup copy)
  D: replica_files[K] = replica   (backup copy)

2. Failure Detection & Recovery

Heartbeat Mechanism

Every 15 seconds, each node pings its successor
On failure, promotes successor_list[1] to successor
Rebuilds successor list and pushes replicas

Predecessor Failure

check_predecessor pings predecessor every 15 seconds
On failure, clears predecessor (stabilization will fix)

Garbage Collection

Every 60 seconds, scans all file metadata
Pings each unique node referenced
Removes mappings to unreachable nodes

3. File Operations

File Lookup

Hash filename → file_hash
Use Chord find_successor(file_hash) → responsible node (O(log N) hops)
Query responsible node for file metadata
Metadata includes: [owner_ip, owner_port, filename, owner_hash]
File physically stays on original node's disk

File Download

Lookup file metadata via Chord routing
Get list of peers hosting the file (primary + replicas)
User selects peer to download from
Stream file with progress bar (tqdm)
Save to downloads/ directory

Dynamic File Monitoring

The system automatically monitors the shared/ directory for changes:

New files: Detected and registered with the network
Removed files: De-registered from the network and replicas
Missing registrations: Re-registered if network records are stale

4. Graceful Exit

When a node leaves:

Notify predecessor: update successor pointer
Notify successor: update predecessor pointer
Transfer owned keys (other_files) to successor
Transfer replicas to successor list members
Exit cleanly

Getting Started

Prerequisites

Python 3.10+
Docker (optional, for containerized deployment)
Make (optional, for build automation)

Installation

Option 1: Docker (Recommended)

# Build the Docker image
make build
# OR
cd code && docker build -t my-peer .

Option 2: Local Python Environment

# Create virtual environment
python3 -m venv venv
source venv/bin/activate

# Install dependencies
pip install -r code/requirements.txt

Usage

Running Nodes

Single Node (Docker)

# Start first node (creates ring)
make run PORT=6000

Multiple Nodes

# Terminal 1: First node
make run PORT=6000

# Terminal 2: Second node
make run PORT=6001

# Terminal 3: Third node
make run PORT=6002

Detached Mode

make run-detached PORT=6000
make run-detached PORT=6001
make run-detached PORT=6002

CLI Commands

Create a New Ring

peer> create-ring <machine_hash_key> <file_hash_key>

# Example
peer> create-ring my_ring_v1 file_key_v1

Join an Existing Ring

peer> join-ring <bootstrap_ip> <bootstrap_port>

# Example
peer> join-ring 192.168.1.100 6000

View Node Metadata

peer> meta

Outputs:

Node identity (IP, port, hash)
Ring keys (machine_hash_key, file_hash_key)
Successor and predecessor
Successor list (for replication)
Finger table (first 10 entries)
Local files
Owned files (primary DHT responsibility)
Replica files

Lookup a File

peer> lookup <filename>

# Example
peer> lookup document.pdf

Outputs:

File hash
Responsible node
List of peers hosting the file

Download a File

peer> download <filename>

# Example
peer> download document.pdf

Process:

Finds responsible node via Chord
Lists all peers with the file
Prompts user to select peer
Downloads with progress bar
Saves to downloads/ directory

Exit Gracefully

peer> exit-gracefully

Performs clean shutdown with key redistribution.

Technical Details

Threading Model

Each node runs 9 concurrent threads:

Main Thread: CLI (blocking input loop)
TCP Server: Handles incoming Chord protocol messages
FastAPI Server: REST API on port+1000 for visualization
Stabilize Loop: Runs every 15s, verifies successor and pushes replicas
Fix Fingers Loop: Runs every 15s, refreshes one finger entry
Check Predecessor Loop: Runs every 15s, pings predecessor
Heartbeat Loop: Runs every 15s, pings successor for failure detection
Garbage Collection Loop: Runs every 60s, removes dead node references
File Monitor Loop: Runs every 30s, detects local file changes

Message Protocol (TCP JSON)

All inter-node communication uses JSON-over-TCP:

// Request format
{"type": "FIND_SUCCESSOR", "hash": 0.42}

// Response format
{"successor": ["192.168.1.100", 6000, 0.45]}

22 Message Types:

Ring Management: REQUEST_KEYS, SET_NEW_PRED, SET_NEW_SUCC
Chord Protocol: FIND_SUCCESSOR, GET_PREDECESSOR, GET_SUCCESSOR, NOTIFY, UPDATE_FINGER_TABLE, CLOSEST_PRECEDING_FINGER
File Operations: LOOKUP_FILE, DOWNLOAD_FILE, REGISTER_FILE, REMOVE_FILE, REMOVE_REPLICA, TRANSFER_KEYS_TO_NEW_NODE
Replication: STORE_REPLICA, SEND_REPLICAS_G_EXIT, REQUEST_SUCCESSOR_OF_NODE
Health Checks: HEARTBEAT, PING, HEARTBEAT_FAILED_CHANGE_PREDECESSORS
Exit Handling: SEND_SUCCESSOR_G_EXIT, SEND_PREDECESSOR_G_EXIT, SEND_OTHER_F_G_EXIT

File Metadata Structure

# other_files: Primary DHT responsibility
other_files = {
    file_hash: [
        [owner_ip, owner_port, filename, owner_hash],
        ...
    ]
}

# replica_files: Backup copies for fault tolerance
replica_files = {
    file_hash: [
        [owner_ip, owner_port, filename, owner_hash],
        ...
    ]
}

# local_files: Physically present on this node's disk
local_files = [
    (filename, file_hash),
    ...
]

Key Insight: File metadata is distributed via DHT routing, but physical files remain on original node's disk. When downloading, the DHT lookup returns the physical location, and the file is streamed directly from that node.

Configuration Parameters

R = 3                            # Replication factor
M = 160                          # Bits in hash space (SHA-1)
STABILIZE_INTERVAL = 15          # seconds
FIX_FINGERS_INTERVAL = 15        # seconds
CHECK_PREDECESSOR_INTERVAL = 15  # seconds
HEARTBEAT_INTERVAL = 15          # seconds
GARBAGE_COLLECT_INTERVAL = 60    # seconds
FILE_MONITOR_INTERVAL = 30       # seconds
TIMEOUT = 5.0                    # seconds for network operations

Complexity Analysis

Operation	Time Complexity	Space Complexity
Lookup (find_successor)	O(log N) hops	O(1)
Insert/Delete key	O(log N) hops	O(1)
Node join	O(log² N) messages	O(log N) per node
Node failure recovery	O(log² N) messages	O(1)
Stabilization (per round)	O(N) total messages	O(log N) per node
Finger table maintenance	O(N log N) total	O(log N) per node

API Reference

REST API (FastAPI)

Each node exposes a REST API on port + 1000:

# Get node state
curl http://localhost:7000/state

Response:

{
  "ip": "192.168.1.100",
  "port": 6000,
  "key_m": "my_ring_v1",
  "key_f": "file_key_v1",
  "hash": 0.234567,
  "successor": ["192.168.1.101", 6001, 0.456789],
  "predecessor": ["192.168.1.102", 6002, 0.123456],
  "successor_list": [...],
  "finger_table": [[0, [...]], [1, [...]], ...],
  "files": [["doc.pdf", 0.789], ...],
  "other_files": {...},
  "replica_files": {...}
}

Visualization

Run make viz and open http://localhost:8080/ in a browser to visualize:

Ring topology
Node positions by hash
Successor/predecessor links
Finger table connections
File distribution

Project Structure

Chapster/
├── code/
│   ├── main.py              # Entry point: starts server + CLI
│   ├── node.py              # RingNode class: state management
│   ├── chord_finger.py      # Chord protocol algorithms
│   ├── server.py            # TCP server + message handlers
│   ├── client.py            # CLI commands (create, join, lookup, download)
│   ├── stabilize.py         # Background maintenance loops
│   ├── replication.py       # Replication helpers
│   ├── fast.py              # FastAPI REST API
│   ├── utils.py             # Networking, logging, hashing utilities
│   ├── config.py            # Configuration constants
│   ├── pretty_print.py      # Colored CLI output
│   ├── requirements.txt     # Python dependencies
│   └── Dockerfile           # Container image
├── instances/               # Node storage (mounted volumes)
│   ├── 6000/
│   │   ├── shared/          # Files hosted by this node
│   │   ├── downloads/       # Downloaded files
│   │   └── logs/            # Log files
│   ├── 6001/
│   └── 6002/
├── visualization/
│   └── index.html           # Web-based ring visualizer
│   └── server.py            # Visualization server
│   └── Dockerfile           # Container image for visualizer
├── Makefile                 # Build and run automation
└── README.md                # This file

References

Original Chord Paper: Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., & Balakrishnan, H. (2001). Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review, 31(4), 149-160.
Consistent Hashing: Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., & Lewin, D. (1997). Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. ACM STOC.

License

GPLv3 License - See LICENSE file for details.

Contributing

Contributions welcome! Please:

Fork the repository
Create a feature branch
Submit a pull request with clear description

Built with ❤️ for Distributed Systems

Name		Name	Last commit message	Last commit date
Analysis		Analysis
code		code
visualization		visualization
.gitignore		.gitignore
LICENSE		LICENSE
Makefile		Makefile
README.md		README.md
classes_Chapster.png		classes_Chapster.png
packages_Chapster.png		packages_Chapster.png

Latest commit

History

Folders and files

Repository files navigation