chord

package module
v0.0.0-...-1fed3d5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 24, 2020 License: MIT Imports: 19 Imported by: 0

README

Chord DHT

A distributed hash table using the Chord lookup protocol, implemented in Go.

A demo can be found here

Goals

  • Implement a functioning DHT
  • Implement the Chord protocol for efficient node lookup
  • Extend Chord with data replication to provide increased availability
  • Learn gRPC and protocol buffers

Prerequisites

Must have go version 1.12 or greater installed on the host in order to build.

Build

To build the chord server and client, simply run:

make server
make client

The executable named chord will be created in both the server and client folders.

Configuration

Below are instructions for configuring your chord servers and clients.

Server

In ./server/config.yaml specify information about your server, like its ip and port. Here is an example:

addr: 172.0.0.1
port: 8001
logging: false
Client

In ./client/config.yaml specify the address of the chord server to send client requests to. Here is an example:

addr: 172.0.0.1:8001

Run

Below are instructions for running a chord server or client.

Server

To create a new chord ring:

./server/chord create

To join an existing chord ring:

./server/chord join <ip> <port>
Client

To put a new key-value pair into the DHT:

./client/chord put <key> <val>

To get the value for a key in the DHT:

./client/chord get <key>

To locate the node responsible for a key in the DHT (for debugging purposes):

./client/chord locate <key>

Local Development and Testing

To run multiple chord servers locally, run the test files in ./test.

To start node1 listening on 0.0.0.0:8001, run

go run test/node1.go

To start node2 listening on 0.0.0.0:8002, run

go run test/node2.go

There are 5 test files, so this allows you to run 5 separate servers locally.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Between 

func Between(key, a, b []byte) bool

Function: Between * * Description: * Check if a key is strictly between a and b.

func BetweenRightIncl 

func BetweenRightIncl(key, a, b []byte) bool

Function: BetweenRightIncl * * Description: * Check if a key is between a and b, right inclusive.

func BytesToUint64 

func BytesToUint64(b []byte) uint64

func CompareSuccessorLists 

func CompareSuccessorLists(a, b []*chordpb.Node) bool

returns true if same, false if different

func Contains 

func Contains(list []*chordpb.Node, node *chordpb.Node) bool

Function: Contains * * Description: * Returns true if node is in list.

func Distance 

func Distance(a, b uint64, n int) uint64

func GetHash 

func GetHash(key string) []byte

Function: GetHash * * Description: * Given an input string return the SHA-1 hash.

func GetLocationOnRing 

func GetLocationOnRing(id []byte) float64

Function: GetLocationOnRing * * Description: * Given an input id, return the location on the * Chord ring as a percent. Useful for debugging or * testing purposes. Assumes id is a multiple of 8 bits.

func GetPeerID 

func GetPeerID(key string, m int) []byte

Function: GetPeerID * * Description: * Given an input string (usually ip:port), return * the peer ID. The peer ID is a SHA-1 hash truncated * to m bits. There are 2^m -1 possible peer IDs. * m must be a multiple of 8.

func NewFingerTable 

func NewFingerTable(n *Node, m int) fingerTable

Function: NewFingerTable * * Description: * Create a new finger table for a node. Initially all entries * will contain n.

func PrintNode 

func PrintNode(n *chordpb.Node, hex bool, label string)

Function: PrintNode * * Description: * Print basic info about a chordpb.Node to stdout. Can either print out * the node's id in hex or decimal.

func PrintReplicaGroupMembership 

func PrintReplicaGroupMembership(n *Node)

func PrintSuccessorList 

func PrintSuccessorList(n *Node)

Function: PrintSuccessorList * * Description: * Print out a node's successor list *

func Uint64ToBytes 

func Uint64ToBytes(i uint64) []byte

Types

type Config 

type Config struct {
	KeySize int
	Addr    string
	Port    uint32

	Timeout    int // in ms
	ServerOpts []grpc.ServerOption
	DialOpts   []grpc.DialOption

	StabilizeInterval        int // in ms
	FixFingerInterval        int // in ms
	CheckPredecessorInterval int // in ms

	SuccessorListSize int

	Logging bool
}

func DefaultConfig 

func DefaultConfig(addr string, port int) *Config

func SetDefaultGrpcOpts 

func SetDefaultGrpcOpts(cfg *Config) *Config

type Node 

type Node struct {
	*chordpb.Node
	// contains filtered or unexported fields
}

Node implements the Chord GRPC Server interface

func CreateChord 

func CreateChord(config *Config) *Node

Function: CreateChord * * Description: * Create a new Chord ring and return the first node * in the ring.

func JoinChord 

func JoinChord(config *Config, addr string, port int) (*Node, error)

Function: JoinChord * * Description: * Join an existing Chord ring. addr and port specify * an existing node in the Chord ring. Returns a newly * created node with its successor set.

func (*Node) CheckPredecessor 

func (n *Node) CheckPredecessor(context context.Context, empty *chordpb.Empty) (*chordpb.Empty, error)

Function: CheckPredecessor * * Description: * Implementation of CheckPredecessor RPC. Simply return an empty response, confirming * the liveliness of a node.

func (*Node) CheckPredecessorRPC 

func (n *Node) CheckPredecessorRPC(other *chordpb.Node) (*chordpb.Empty, error)

Function: CheckPredecessorRPC * * Description: * Invoke a CheckPredecessor RPC on node "other," asking if that node is still alive

func (*Node) FindSuccessor 

func (n *Node) FindSuccessor(context context.Context, peerID *chordpb.PeerID) (*chordpb.Node, error)

Function: FindSuccessor * * Description: * Implementation of FindSuccessor RPC. Returns the successor of peerID. * If peerID is between our id and our successor's id, then return our successor. * Otherwise, check our finger table and forward the request to the closest preceding node.

func (*Node) FindSuccessorRPC 

func (n *Node) FindSuccessorRPC(other *chordpb.Node, id []byte) (*chordpb.Node, error)

Function: FindSuccessorRPC * * Description: * Invoke a FindSuccessor RPC on node "other," asking for the successor of a given id.

func (*Node) Get 

func (n *Node) Get(context context.Context, key *chordpb.Key) (*chordpb.Value, error)

Function: Get * * Description: * Implementation of Get RPC.

func (*Node) GetKeys 

func (n *Node) GetKeys(context context.Context, id *chordpb.PeerID) (*chordpb.KVs, error)

Function: GetKeys * * Description: * Implementation of GetKeys RPC. The caller of this RPC is requesting keys for which it * it responsible for along the chord ring. We simply check our own datastore for keys * that the other node is responsible for and send it.

func (*Node) GetKeysRPC 

func (n *Node) GetKeysRPC(other *chordpb.Node, id []byte) (*chordpb.KVs, error)

func (*Node) GetPredecessor 

func (n *Node) GetPredecessor(context context.Context, empty *chordpb.Empty) (*chordpb.Node, error)

Function: GetPredecessor * * Description: * Implementation of GetPredecessor RPC. Returns the node's current predecessor

func (*Node) GetPredecessorRPC 

func (n *Node) GetPredecessorRPC(other *chordpb.Node) (*chordpb.Node, error)

Function: GetPredecessorRPC * * Description: * Invoke a GetPredecessor RPC on node "other," asking for it's current predecessor.

func (*Node) GetRPC 

func (n *Node) GetRPC(other *chordpb.Node, key string) (*chordpb.Value, error)

func (*Node) GetSuccessorList 

func (n *Node) GetSuccessorList(context context.Context, empty *chordpb.Empty) (*chordpb.SuccessorList, error)

Function: GetSuccessorList * * Description: * Return a node's successor list

func (*Node) GetSuccessorListRPC 

func (n *Node) GetSuccessorListRPC(other *chordpb.Node) (*chordpb.SuccessorList, error)

Function: GetSuccessorListRPC * * Description: * Get another node's successor list

func (*Node) Locate 

func (n *Node) Locate(context context.Context, key *chordpb.Key) (*chordpb.Node, error)

Function: Locate * * Description: * Implementation of Locate RPC.

func (*Node) LocateRPC 

func (n *Node) LocateRPC(other *chordpb.Node, key string) (*chordpb.Node, error)

func (*Node) Notify 

func (n *Node) Notify(context context.Context, node *chordpb.Node) (*chordpb.Empty, error)

Function: Notify * * Description: * Implementation of Notify RPC. A Node is notifying us that it believes it is our predecessor. * Check if this is true based on our predecessor/successor knowledge and update.

func (*Node) NotifyRPC 

func (n *Node) NotifyRPC(other *chordpb.Node) error

Function: NotifyRPC * * Description: * Invoke a Notify RPC on node "other," telling it that we believe we are its predecessor

func (*Node) PrintFingerTable 

func (n *Node) PrintFingerTable(hex bool)

Function: PrintFingerTable * * Description: * Print the entire finger table for a node. Can either print out the * node ids in hex or decimal.

func (*Node) Put 

func (n *Node) Put(context context.Context, kv *chordpb.KV) (*chordpb.Empty, error)

Function: Put * * Description: * Implementation of Put RPC.

func (*Node) PutRPC 

func (n *Node) PutRPC(other *chordpb.Node, key string, value []byte) (*chordpb.Empty, error)

func (*Node) RecvCoordinatorMsg 

func (n *Node) RecvCoordinatorMsg(context context.Context, msg *chordpb.CoordinatorMsg) (*chordpb.Empty, error)

Function: ReceiveCoordinatorMsg * * Description: * Implementation of RecvCoordinatorMsg RPC. Other nodes will send us coordinator messages. * This is a modified form of the Bully algorithm for leader election. When we receive a * coordinator msg from another node it means we are a member of their successor list. * We immediately recognize that we are apart of its replica group and take the necessary actions, * like creating a new replica group object internally, removing replica groups we are * no longer a member of etc.

func (*Node) RecvCoordinatorMsgRPC 

func (n *Node) RecvCoordinatorMsgRPC(other *chordpb.Node, newLeaderId []byte, oldLeaderId []byte) error

func (*Node) RemoveReplicas 

func (n *Node) RemoveReplicas(context context.Context, replicaMsg *chordpb.ReplicaMsg) (*chordpb.Empty, error)

Function: RemoveReplicas * * Description: * Implementation of RemoveReplicas RPC. A leader is informing us that certain keys do not belong * in this replica group anymore. Remove the specified keys from the leaders replica group internally

func (*Node) RemoveReplicasRPC 

func (n *Node) RemoveReplicasRPC(other *chordpb.Node, req *chordpb.ReplicaMsg) error

func (*Node) SendReplicas 

func (n *Node) SendReplicas(context context.Context, replicaMsg *chordpb.ReplicaMsg) (*chordpb.Empty, error)

Function: SendReplicas * * Description: * Implementation of SendReplicas RPC. A leader is sending us kv replicas. Add them to the leaders * replica group internally.

func (*Node) SendReplicasRPC 

func (n *Node) SendReplicasRPC(other *chordpb.Node, req *chordpb.ReplicaMsg) error

type ReplicaGroup 

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

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.