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.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 ¶
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) FindSuccessor ¶
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 ¶
Given a hashed website name, return the records associated with it if it exists, else return nil.
func (*Node) GetShiftRecords ¶
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) PrintCache ¶
func (node *Node) PrintCache()
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 ¶
Upon receiving a PUT message, or signal, it will simply
- Put the entry into local storage
- Call node.replicate(payload)
func (*Node) QueryDNS ¶
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
Source Files