hashing

Documentation

Index

• type NodeLoad
• type Ring
  • func NewRing(vnodeCount int, maxLoadFactor float64) *Ring
  • func (r *Ring) AddNode(nodeID string) bool
  • func (r *Ring) DecrementLoad(nodeID string)
  • func (r *Ring) GetLoad(nodeID string) int64
  • func (r *Ring) GetNode(key string) (string, bool)
  • func (r *Ring) GetNodes(key string, n int) []string
  • func (r *Ring) HasNode(nodeID string) bool
  • func (r *Ring) IncrementLoad(nodeID string)
  • func (r *Ring) IsEmpty() bool
  • func (r *Ring) Members() []string
  • func (r *Ring) RemoveNode(nodeID string) bool
  • func (r *Ring) SetOnNodeAdded(fn func(nodeID string))
  • func (r *Ring) SetOnNodeRemoved(fn func(nodeID string))
  • func (r *Ring) Size() int
• type VNode

Types

type NodeLoad

type NodeLoad struct {
	NodeID string
	Active atomic.Int64
}

NodeLoad tracks the current load on a physical node.

type Ring

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

Ring implements consistent hashing with bounded loads. It distributes keys across nodes using virtual nodes on a hash ring, and enforces a maximum load factor to prevent any single node from being overloaded (Google's "Consistent Hashing with Bounded Loads").

func NewRing

func NewRing(vnodeCount int, maxLoadFactor float64) *Ring

NewRing creates a new consistent hash ring. vnodeCount is the number of virtual nodes per physical node. maxLoadFactor is ε for bounded loads (e.g., 0.25 means max 125% of avg).

func (*Ring) AddNode

func (r *Ring) AddNode(nodeID string) bool

AddNode adds a physical node to the ring with its virtual nodes. Returns false if the node already exists.

func (*Ring) DecrementLoad

func (r *Ring) DecrementLoad(nodeID string)

DecrementLoad atomically decrements the load for a node. Call this when a request finishes being processed by the node.

func (*Ring) GetLoad

func (r *Ring) GetLoad(nodeID string) int64

GetLoad returns the current load for a node.

func (*Ring) GetNode

func (r *Ring) GetNode(key string) (string, bool)

GetNode returns the node responsible for the given key. It implements bounded loads: if the target node is overloaded, it moves clockwise to the next eligible node.

func (*Ring) GetNodes

func (r *Ring) GetNodes(key string, n int) []string

GetNodes returns up to n distinct nodes responsible for the given key, walking clockwise from the key's position on the ring. Used for replication: first node = primary, rest = secondaries.

func (*Ring) HasNode

func (r *Ring) HasNode(nodeID string) bool

HasNode checks if a node exists in the ring.

func (*Ring) IncrementLoad

func (r *Ring) IncrementLoad(nodeID string)

IncrementLoad atomically increments the load for a node. Call this when a request starts being processed by the node.

func (*Ring) IsEmpty

func (r *Ring) IsEmpty() bool

IsEmpty returns true if the ring has no nodes.

func (*Ring) Members

func (r *Ring) Members() []string

Members returns the list of all physical node IDs in the ring.

func (*Ring) RemoveNode

func (r *Ring) RemoveNode(nodeID string) bool

RemoveNode removes a physical node and all its virtual nodes from the ring. Returns false if the node doesn't exist.

func (*Ring) SetOnNodeAdded

func (r *Ring) SetOnNodeAdded(fn func(nodeID string))

SetOnNodeAdded sets a callback invoked when a node is added to the ring.

func (*Ring) SetOnNodeRemoved

func (r *Ring) SetOnNodeRemoved(fn func(nodeID string))

SetOnNodeRemoved sets a callback invoked when a node is removed from the ring.

func (*Ring) Size

func (r *Ring) Size() int

Size returns the number of physical nodes in the ring.

type VNode

type VNode struct {
	Hash   uint64
	NodeID string
	Index  int // Virtual node index for this physical node.
}

VNode represents a virtual node on the consistent hash ring.