node

Documentation

Overview

This repository implements a simplified Chord protocol: a decentralized peer-to-peer (P2P) distributed hash table (DHT) for distributed data storage and lookup. The system orchestrates nodes forming a ring-based network structure where each node maintains information about its successor, predecessor, and a portion of the network keyspace. It includes functionalities for node joining, stabilizing the network, and updating finger tables, enabling efficient decentralized lookup of key-value pairs across a distributed system where each node manages a segment of the overall keyspace. The implementation involves periodic checks, such as node stabilization, finger table fixing, predecessor checks, and message handling for essential network operations like finding successors and notifying or updating neighboring nodes.

Index

• Constants
• type LRUCache
• type Node
  • func (node *Node) CallRPC(msg message.RequestMessage, IP string) message.ResponseMessage
  • func (node *Node) CheckPredecessor()
  • func (node *Node) ClosestPrecedingNode(id uint64) Pointer
  • func (node *Node) CreateNetwork()
  • func (node *Node) FindSuccessor(id uint64, hopCount int) (Pointer, int)
  • func (node *Node) FixFingers()
  • func (node *Node) GetQuery(hashedId uint64) []string
  • func (node *Node) GetShiftRecords(prececId uint64) map[uint64][]string
  • func (node *Node) HandleIncomingMessage(msg *message.RequestMessage, reply *message.ResponseMessage) error
  • func (node *Node) JoinNetwork(helper string)
  • func (node *Node) Notify(x Pointer) bool
  • func (node *Node) PrintCache()
  • func (node *Node) PrintFingers()
  • func (node *Node) PrintPredecessor()
  • func (node *Node) PrintStorage()
  • func (node *Node) PrintSuccessor()
  • func (node *Node) PutQuery(succesorId uint64, payload map[uint64][]string) bool
  • func (node *Node) QueryDNS(website string)
• type Pointer

Constants

const (
	M                  = 32
	CACHE_SIZE         = 5
	REPLICATION_FACTOR = 2
)

Constants

const (
	PING                   = "ping"                   // Used to check predecessor.
	ACK                    = "ack"                    // Used for general acknowledgements.
	GET_SUCCESSOR          = "get_successor"          // Used in RPC call to get node.Successor
	FIND_SUCCESSOR         = "find_successor"         // Used to find successor.
	CLOSEST_PRECEDING_NODE = "closest_preceding_node" // Used to find the closest preceding node, given a successor id.
	GET_PREDECESSOR        = "get_predecessor"        // Used to get the predecessor of some node.
	NOTIFY                 = "notify"                 // Used to notify a node about a new predecessor.
	PUT                    = "put"                    // Used to insert a DNS query.
	GET                    = "get"                    // Used to retrieve a DNS record.
	SHIFT                  = "shift"                  // Used to shift entries.
	EMPTY                  = "empty"                  // Placeholder or undefined message type or errenous communications.
	REPLICATE              = "replicate"              // Used to replicate data.
)

Message types.

Types

type LRUCache

type LRUCache struct {
	// contains filtered or unexported fields
}

Used for in-memory-storage. Used to maintain the list of recent queries, and improve query speed.

type Node

type Node struct {
	Nodeid        uint64                         // ID of the node
	IP            string                         // localhost or IP address AND port number. Can be set through environment variables.
	FingerTable   []Pointer                      // id mapping to ip address
	Successor     Pointer                        // Nodeid of it's direct successor.
	Predecessor   Pointer                        // Nodeid of it's direct predecessor.
	CachedQuery   map[uint64]LRUCache            // caching queries on the node locally
	HashIPStorage map[uint64]map[uint64][]string // storage for hashed ips associated with the node
	CacheTime     uint64                         // To keep track of scalar timestamp to assign to LRUCache
	SuccList      []Pointer                      // Maintain a list of successors for fault tolerance
}

Represents everything that a node in the chord network needs to take care of.

func (*Node) CallRPC

func (node *Node) CallRPC(msg message.RequestMessage, IP string) message.ResponseMessage

Node utility function to call RPC given a request message, and a destination IP address.

func (*Node) CheckPredecessor

func (node *Node) CheckPredecessor()

Each node also runs check predecessor periodically, to clear the node’s predecessor pointer if n.predecessor has failed; this allows it to accept a new predecessor in notify.

func (*Node) ClosestPrecedingNode

func (node *Node) ClosestPrecedingNode(id uint64) Pointer

Works jointly with FindSuccessor(id). If id doesn't fall between my id, and my immediate successors id, then we find the closest preceding node, so we can call find successor on that node.

func (*Node) CreateNetwork

func (node *Node) CreateNetwork()

Create new network (genesis node)

func (*Node) FindSuccessor

func (node *Node) FindSuccessor(id uint64, hopCount int) (Pointer, int)

If id falls between its successor, find successor is finished and node n returns its successor. Otherwise, n searches its finger table for the node whose ID most immediately precedes id, and then invokes find successor at that ID

func (*Node) FixFingers

func (node *Node) FixFingers()

Each node periodically calls fix fingers to make sure its finger table entries are correct; this is how new nodes initialize their finger tables, and it is how existing nodes incorporate new nodes into their finger tables.

func (*Node) GetQuery

func (node *Node) GetQuery(hashedId uint64) []string

Given a hashed website name, return the records associated with it if it exists, else return nil.

func (*Node) GetShiftRecords

func (node *Node) GetShiftRecords(prececId uint64) map[uint64][]string

Called when a SHIFT message is received. This means that there are new nodes in the network. The node will ask you to handover all the entries that falls between you and it. This method helps process this logic.

func (*Node) HandleIncomingMessage

func (node *Node) HandleIncomingMessage(msg *message.RequestMessage, reply *message.ResponseMessage) error

The default method called by all RPCs. This method receives different types of requests, and calls the appropriate functions.

func (*Node) JoinNetwork

func (node *Node) JoinNetwork(helper string)

Join existing chord network

func (*Node) Notify

func (node *Node) Notify(x Pointer) bool

x thinks it might be nodes predecessor

func (*Node) PrintCache

func (node *Node) PrintCache()

func (*Node) PrintFingers

func (node *Node) PrintFingers()

Node utility function to print fingers

func (*Node) PrintPredecessor

func (node *Node) PrintPredecessor()

Node utility function to print predecessor

func (*Node) PrintStorage

func (node *Node) PrintStorage()

func (*Node) PrintSuccessor

func (node *Node) PrintSuccessor()

Node utility function to print the successor

func (*Node) PutQuery

func (node *Node) PutQuery(succesorId uint64, payload map[uint64][]string) bool

Upon receiving a PUT message, or signal, it will simply

1. Put the entry into local storage
2. Call node.replicate(payload)

func (*Node) QueryDNS

func (node *Node) QueryDNS(website string)

Mother code for all DNS query logic. It executes one of the following logic pathways:

1. Query node -> check local cache -> return entry

2. Query node -> check local cache -> query local storage -> put in local cache -> return entry

3. Query node -> check local cache -> query local storage -> find successor, and send get -> put in local cache -> return entry

4. Query node -> check local cache -> query local storage -> find successor, and send get -> query legacy DNS -> send to appropriate node, or self -> put in local cache -> return entry

type Pointer

type Pointer struct {
	Nodeid uint64 // ID of the pointed Node
	IP     string // IP of the pointed Node
}