chordhash

README

Algroithms related to consistent hashing and the Chord DHT.

This package implements low-level fatures, such as:

• Node-ID Arithmetic as described in Chord
• A circular sorted associative Map called Circle.
• A holistic member ring that is capable to emulate the "finger table".

Documentation

Index

• func NodeNonNil(n *avl.Node) *avl.Node
• func Strnode(n *avl.Node) string
• type Circle
  • func (c *Circle) Init()
  • func (c *Circle) Next(key interface{}) (node *avl.Node)
  • func (c *Circle) NextOrEqual(key interface{}) (node *avl.Node)
  • func (c *Circle) Prev(key interface{}) (node *avl.Node)
  • func (c *Circle) PrevOrEqual(key interface{}) (node *avl.Node)
  • func (c *Circle) Step(node *avl.Node) (next *avl.Node)
  • func (c *Circle) StepReverse(node *avl.Node) (prev *avl.Node)
• type NodeID
  • func (n NodeID) Bits() int
  • func (n NodeID) Clone() NodeID
  • func (n NodeID) Decrement()
  • func (n NodeID) FingerBase(k uint)
  • func (n NodeID) Increment()
  • func (n *NodeID) Set(other NodeID)
• type NodeManager
  • func (n *NodeManager) Init()
  • func (n *NodeManager) Insert(id NodeID, attachment interface{})
  • func (n *NodeManager) LookupFinger(id NodeID) *avl.Node
  • func (n *NodeManager) LookupPrecise(id NodeID) *avl.Node
  • func (n *NodeManager) Predecessor() *avl.Node
  • func (n *NodeManager) Remove(id NodeID)
  • func (n *NodeManager) Replace(id NodeID, new_attachment interface{})
  • func (n *NodeManager) SetSelf(id NodeID)
  • func (n *NodeManager) Successor() *avl.Node

Functions

func NodeNonNil

func NodeNonNil(n *avl.Node) *avl.Node

func Strnode

func Strnode(n *avl.Node) string

Types

type Circle

type Circle struct {
	Tree *avl.Tree
}

func (*Circle) Init

func (c *Circle) Init()

func (*Circle) Next

func (c *Circle) Next(key interface{}) (node *avl.Node)

func (*Circle) NextOrEqual

func (c *Circle) NextOrEqual(key interface{}) (node *avl.Node)

func (*Circle) Prev

func (c *Circle) Prev(key interface{}) (node *avl.Node)

func (*Circle) PrevOrEqual

func (c *Circle) PrevOrEqual(key interface{}) (node *avl.Node)

func (*Circle) Step

func (c *Circle) Step(node *avl.Node) (next *avl.Node)

func (*Circle) StepReverse

func (c *Circle) StepReverse(node *avl.Node) (prev *avl.Node)

type NodeID

type NodeID []byte

func (NodeID) Bits

func (n NodeID) Bits() int

Returns:

len(n)*8

func (NodeID) Clone

func (n NodeID) Clone() NodeID

Generates a Copy.

func (NodeID) Decrement

func (n NodeID) Decrement()

Calculates:

n = (n - 1) mod 1<<n.Bits()

func (NodeID) FingerBase

func (n NodeID) FingerBase(k uint)

Calculates:

n = (n + (1<<k)) mod 1<<n.Bits()

func (NodeID) Increment

func (n NodeID) Increment()

Calculates:

n = (n + 1) mod 1<<n.Bits()

func (*NodeID) Set

func (n *NodeID) Set(other NodeID)

Assigns the Value of the NodeID 'other' to 'n', adjusting the buffer size, if necessary.

Internally, it does:

*n = append((*n)[:0],other...)

type NodeManager

type NodeManager struct {
	Finger, Nodes Circle
	Self          string
}

A Node manager, offering a holistic member-list and -ring implementation.

This implementation requires the whole list of cluster-members, whereas Chord only requires a Finger-Table.

func (*NodeManager) Init

func (n *NodeManager) Init()

func (*NodeManager) Insert

func (n *NodeManager) Insert(id NodeID, attachment interface{})

func (*NodeManager) LookupFinger

func (n *NodeManager) LookupFinger(id NodeID) *avl.Node

func (*NodeManager) LookupPrecise

func (n *NodeManager) LookupPrecise(id NodeID) *avl.Node

func (*NodeManager) Predecessor

func (n *NodeManager) Predecessor() *avl.Node

func (*NodeManager) Remove

func (n *NodeManager) Remove(id NodeID)

func (*NodeManager) Replace

func (n *NodeManager) Replace(id NodeID, new_attachment interface{})

func (*NodeManager) SetSelf

func (n *NodeManager) SetSelf(id NodeID)

func (*NodeManager) Successor

func (n *NodeManager) Successor() *avl.Node