buddystore

package module
v0.0.0-...-a689244 Latest Latest
Warning

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

 Go to latest Published: Dec 28, 2014 License: MIT Imports: 26 Imported by: 2

README

Go Chord

Build Status Coverage Status

This package provides a Golang implementation of the Chord protocol. Chord is used to organize nodes along a ring in a consistent way. It can be used to distribute work, build a key/value store, or serve as the underlying organization for a ring overlay topology.

The protocol is seperated from the implementation of an underlying network transport or RPC mechanism. Instead Chord relies on a transport implementation. A TCPTransport is provided that can be used as a reliable Chord RPC mechanism.

Documentation

GoDoc

To view the online documentation, go here.

Documentation

Overview

This package is used to provide an implementation of the Chord network protocol.

Index

Constants

View Source 
const (
	MaxIncSyncParallelism = 8
	MaxReplParallelism    = 12
)
View Source 
const BUDDYSTORE_INFOHASH_BASE = "BuddyStore"
View Source 
const ENOTINITIALIZED = -1
View Source 
const JOIN_STABILIZE_WAIT = 5
View Source 
const LISTEN_TIMEOUT = 30 * time.Second
View Source 
const NUM_TRACKER_REPLICAS = 2
View Source 
const OK = 0
View Source 
const PEERLEN = 6
View Source 
const RETRY_WAIT = 1 * time.Millisecond
View Source 
const TRACKER_TIMEOUT_SECS = 600 * time.Second
View Source 
const TRACKER_URL = "udp://tracker.openbittorrent.com:80/announce"

Variables

View Source 
var NUM_LM_REPLICA = 2

Functions

func CreateNewTCPTransport 

func CreateNewTCPTransport(localOnly bool) (int, Transport, *Config)

func CreateNewTCPTransportWithConfig 

func CreateNewTCPTransportWithConfig(localOnly bool, configGen func(string) *Config) (int, Transport, *Config)

func GetLocalExternalAddresses 

func GetLocalExternalAddresses() (localAddr string, externalAddr string)

Types

type BlackholeTransport 

type BlackholeTransport struct {
	// Implements:
	Transport
}

BlackholeTransport is used to provide an implemenation of the Transport that does not actually do anything. Any operation will result in an error.

func (*BlackholeTransport) AbortWLock 

func (*BlackholeTransport) AbortWLock(v *Vnode, key string, version uint, nodeID string, opsLogEntry *OpsLogEntry) (uint64, error)

func (*BlackholeTransport) BulkSet 

func (*BlackholeTransport) BulkSet(v *Vnode, key string, valLst []KVStoreValue) error

func (*BlackholeTransport) ClearPredecessor 

func (*BlackholeTransport) ClearPredecessor(target, self *Vnode) error

func (*BlackholeTransport) CommitWLock 

func (*BlackholeTransport) CommitWLock(v *Vnode, key string, version uint, nodeID string, opsLogEntry *OpsLogEntry) (uint64, error)

func (*BlackholeTransport) FindSuccessors 

func (*BlackholeTransport) FindSuccessors(vn *Vnode, n int, key []byte) ([]*Vnode, error)

func (*BlackholeTransport) Get 

func (*BlackholeTransport) Get(v *Vnode, key string, version uint) ([]byte, error)

func (*BlackholeTransport) GetPredecessor 

func (*BlackholeTransport) GetPredecessor(vn *Vnode) (*Vnode, error)

func (*BlackholeTransport) GetPredecessorList 

func (*BlackholeTransport) GetPredecessorList(vn *Vnode) ([]*Vnode, error)

func (*BlackholeTransport) List 

func (*BlackholeTransport) List(v *Vnode) ([]string, error)

func (*BlackholeTransport) ListVnodes 

func (*BlackholeTransport) ListVnodes(host string) ([]*Vnode, error)

func (*BlackholeTransport) MissingKeys 

func (*BlackholeTransport) MissingKeys(v *Vnode, replVn *Vnode, key string, ver []uint) error

func (*BlackholeTransport) Notify 

func (*BlackholeTransport) Notify(vn, self *Vnode) ([]*Vnode, error)

func (*BlackholeTransport) Ping 

func (*BlackholeTransport) Ping(vn *Vnode) (bool, error)

func (*BlackholeTransport) PurgeVersions 

func (*BlackholeTransport) PurgeVersions(v *Vnode, key string, maxVersion uint) error

func (*BlackholeTransport) RLock 

func (*BlackholeTransport) RLock(v *Vnode, key string, nodeID string, opsLogEntry *OpsLogEntry) (string, uint, uint64, error)

func (*BlackholeTransport) Register 

func (*BlackholeTransport) Register(v *Vnode, o VnodeRPC)

func (*BlackholeTransport) Set 

func (*BlackholeTransport) Set(v *Vnode, key string, version uint, value []byte) error

func (*BlackholeTransport) SkipSuccessor 

func (*BlackholeTransport) SkipSuccessor(target, self *Vnode) error

func (*BlackholeTransport) SyncKeys 

func (*BlackholeTransport) SyncKeys(v *Vnode, ownerVn *Vnode, key string, ver []uint) error

func (*BlackholeTransport) WLock 

func (*BlackholeTransport) WLock(v *Vnode, key string, version uint, timeout uint, nodeID string, opsLogEntry *OpsLogEntry) (string, uint, uint, uint64, error)

type BuddyStore 

type BuddyStore struct {
	Config     *BuddyStoreConfig
	GlobalRing RingIntf
	SubRings   map[string]RingIntf
	Tracker    TrackerClient
	// contains filtered or unexported fields
}

func NewBuddyStore 

func NewBuddyStore(bsConfig *BuddyStoreConfig) *BuddyStore

func (BuddyStore) GetKVClient 

func (bs BuddyStore) GetKVClient(ringId string) (KVStoreClient, int)

func (BuddyStore) GetMyKVClient 

func (bs BuddyStore) GetMyKVClient() (KVStoreClient, int)

type BuddyStoreConfig 

type BuddyStoreConfig struct {
	MyID      string
	Friends   []string
	LocalOnly bool
}

type BuddyStoreError 

type BuddyStoreError struct {
	Err       string
	Transient bool
}

func PermanentError 

func PermanentError(str string, args ...interface{}) BuddyStoreError

func TransientError 

func TransientError(str string, args ...interface{}) BuddyStoreError

func (BuddyStoreError) Error 

func (bse BuddyStoreError) Error() string

func (BuddyStoreError) Temporary 

func (bse BuddyStoreError) Temporary() bool

func (BuddyStoreError) Timeout 

func (bse BuddyStoreError) Timeout() bool

type ClockIface 

type ClockIface interface {
	Now() time.Time
	AfterFunc(time.Duration, func()) *time.Timer
}

type Config 

type Config struct {
	Hostname      string           // Local host name
	NumVnodes     int              // Number of vnodes per physical node
	HashFunc      func() hash.Hash // Hash function to use
	StabilizeMin  time.Duration    // Minimum stabilization time
	StabilizeMax  time.Duration    // Maximum stabilization time
	NumSuccessors int              // Number of successors to maintain
	Delegate      Delegate         // Invoked to handle ring events

	RingId string
	// contains filtered or unexported fields
}

Configuration for Chord nodes

func DefaultConfig 

func DefaultConfig(hostname string) *Config

Returns the default Ring configuration

type Delegate 

type Delegate interface {
	NewPredecessor(local, remoteNew, remotePrev *Vnode)
	Leaving(local, pred, succ *Vnode)
	PredecessorLeaving(local, remote *Vnode)
	SuccessorLeaving(local, remote *Vnode)
	Shutdown()
}

Delegate to notify on ring events

type KVStore 

type KVStore struct {

	// Implements:
	KVStoreIntf
	// contains filtered or unexported fields
}

type KVStoreClient 

type KVStoreClient interface {
	Get(key string, retry bool) ([]byte, error)
	Set(key string, val []byte) error
	GetForSet(key string, retry bool) ([]byte, uint, error)
	SetVersion(key string, version uint, val []byte) error
}

type KVStoreClientImpl 

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

func NewKVStoreClient 

func NewKVStoreClient(ring *Ring) *KVStoreClientImpl

func NewKVStoreClientWithLM 

func NewKVStoreClientWithLM(ringIntf RingIntf, lm LMClientIntf) *KVStoreClientImpl

func (KVStoreClientImpl) Get 

func (kv KVStoreClientImpl) Get(key string, retry bool) ([]byte, error)

Inform the lock manager we're interested in reading the value for key. Expected return value: 

Current version number associated with key

Expected error conditions: 

Network failure     => Retryable failure
Key does not exist  => Fail immediately

Once current version number has been successfully read, contact nodes KV Store to read value at expected version. Expected error conditions: 

Key/version does not exist  => Retry with another node
All nodes returned error    => Fail

Optimization: 

Prioritize reading from local vnode if one of them may contain this data.

func (KVStoreClientImpl) GetForSet 

func (kv KVStoreClientImpl) GetForSet(key string, retry bool) ([]byte, uint, error)

Similar to KVStore.Get, but useful for transactional read-update-write operations along with KVStore.SetVersion.

First, get a write lease from the lock manager. This prevents any further write operations on the same key. Proceed to read the latest version of the key and get its data, which is returned.

func (*KVStoreClientImpl) Set 

func (kv *KVStoreClientImpl) Set(key string, value []byte) error

Inform the lock manager we're interested in setting the value for key. Expected return value: 

Next available version number to write value to

Expected error conditions: 

Network failure     => Retryable failure
Key does not exist  => Fail immediately
Access permissions? => Fail immediately

Once next version number has been successfully read, contact master KV Store to write value at new version. Expected error conditions: 

Key/version too old  => TODO: Inform lock manager
Transient error      => TODO: Retry

If write operation succeeded without errors, send a commit message to the lock manager to finalize the operation. Until the commit returns successfully, the new version of this value will not be advertised. Expected error conditions: 

Lock not found       => TODO: Return
Transient error      => TODO: Retry

If write operation failed, send an abort message to the lock manager to cancel the operation. This is simply to speed up the lock release operation instead of waiting for a timeout to happen. Expected error conditions: 

Lock not found       => TODO: Return
Transient error      => TODO: Retry

func (*KVStoreClientImpl) SetVersion 

func (kv *KVStoreClientImpl) SetVersion(key string, version uint, value []byte) error

Similar to KVStore.Set, but useful for transactional read-update-write operations along with KVStore.GetForSet.

Use the version number from the write lease acquired in KVStore.GetForSet. Perform regular Set operation with commit/abort.

type KVStoreIntf 

type KVStoreIntf interface {
	// contains filtered or unexported methods
}

type KVStoreValue 

type KVStoreValue struct {
	Ver uint   // version
	Val []byte // value
}

type LMClientIntf 

type LMClientIntf interface {
	RLock(key string, forceNoCache bool) (uint, error)
	WLock(key string, version uint, timeout uint) (uint, error)
	CommitWLock(key string, version uint) error
	AbortWLock(key string, version uint) error
	InvalidateRLock(lockID string) error
}

type LManager 

type LManager struct {
	//  Local state managed by the LockManager
	Ring      *Ring  //  This is to get the Ring's transport when the server has to send invalidations to lm_client cache
	Vn        *Vnode //  The Vnode this LockManager is associated with
	CurrentLM bool   // Boolean flag which says if the node is the current Lock Manager.

	VersionMap map[string]uint        //  key-version mappings. A map of key to the corresponding version
	RLocks     map[string]*RLockEntry // Will have the CopySets for whom the RLocks have been provided for a key
	WLocks     map[string]*WLockEntry // Will have mapping from key to the metadata to be maintained

	TimeoutTicker *time.Ticker // Ticker that will periodically check WLocks for invalidation
	LMCheckTicker *time.Ticker // Ticker that will periodically checks if LM has changed

	OpsLog []*OpsLogEntry //  Actual log used for write-ahead logging each operation

	// HARP Replication
	CommitPoint uint64 //  Current Commit point of LManager.
	CommitIndex int
	// contains filtered or unexported fields
}

In-memory implementation of LockManager that implements LManagerIntf

func (*LManager) CheckStatus 

func (lm *LManager) CheckStatus()
This method is called after JOIN_STABILIZE_WAIT time.

1. Check if this lm is the CurrentLM, if yes, you should have received the current set of Locks from the original LockManager. In that case, we are ready to go. Set CurrentLM to true. Set block to false. 2. If not the current LM, then just set block to false so that you can start acting as the secondary

func (*LManager) ReplayLog 

func (lm *LManager) ReplayLog()

func (*LManager) ScheduleLMCheckTicker 

func (lm *LManager) ScheduleLMCheckTicker()

Logic is moved to stabilize operation in vnode.go

func (*LManager) SyncWithSuccessor 

func (lm *LManager) SyncWithSuccessor() bool
TODO : What if I have no log? Two possibilities

1. I just joined. Go and ask the successor for the opsLog and replay it. 2. Its genesis, there was no LM before this. Go and ask the successor to confirm it. Well, just ask the successor and execute whatever you have to.. Return true, if the successor has state, else return false (birth)

func (*LManager) UpdateVersionMap 

func (lm *LManager) UpdateVersionMap(versionMap *map[string]uint)

Called by the old LM on the new LM to update it with the Locks

type LManagerClient 

type LManagerClient struct {
	Vnode  *Vnode               //  Vnode associated with this LMClient
	Ring   RingIntf             // Ring with whom the client is associated with
	RLocks map[string]*RLockVal //  Map of <keys, ReadLock Values>
	WLocks map[string]*WLockVal //  Map of <keys, WriteLock Values>

	// Implements:
	LMClientIntf
	// contains filtered or unexported fields
}

func (*LManagerClient) AbortWLock 

func (lm *LManagerClient) AbortWLock(key string, version uint) error

func (*LManagerClient) CommitWLock 

func (lm *LManagerClient) CommitWLock(key string, version uint) error

func (*LManagerClient) InvalidateRLock 

func (lm *LManagerClient) InvalidateRLock(lockID string) error

func (*LManagerClient) RLock 

func (lm *LManagerClient) RLock(key string, forceNoCache bool) (version uint, err error)

Called by the client before making a read on the key Param key : The key to be looked up Param forceNoCache : Invalidate existing ReadLocks and get a new lock from LM

func (*LManagerClient) WLock 

func (lm *LManagerClient) WLock(key string, version uint, timeout uint) (uint, error)

type LManagerIntf 

type LManagerIntf interface {
	// contains filtered or unexported methods
}

Should be extensible to be used by any underlying storage implementation

type LocalTransport 

type LocalTransport struct {

	// Implements:
	Transport
	// contains filtered or unexported fields
}

LocalTransport is used to provides fast routing to Vnodes running locally using direct method calls. For any non-local vnodes, the request is passed on to another transport.

func (*LocalTransport) AbortWLock 

func (lt *LocalTransport) AbortWLock(targetLm *Vnode, key string, version uint, nodeID string, opsLogEntry *OpsLogEntry) (uint64, error)

func (*LocalTransport) BulkSet 

func (lt *LocalTransport) BulkSet(target *Vnode, key string, valLst []KVStoreValue) error

func (*LocalTransport) ClearPredecessor 

func (lt *LocalTransport) ClearPredecessor(target, self *Vnode) error

func (*LocalTransport) CommitWLock 

func (lt *LocalTransport) CommitWLock(targetLm *Vnode, key string, version uint, nodeID string, opsLogEntry *OpsLogEntry) (uint64, error)

func (*LocalTransport) Deregister 

func (lt *LocalTransport) Deregister(v *Vnode)

func (*LocalTransport) FindSuccessors 

func (lt *LocalTransport) FindSuccessors(vn *Vnode, n int, key []byte) ([]*Vnode, error)

func (*LocalTransport) Get 

func (lt *LocalTransport) Get(target *Vnode, key string, version uint) ([]byte, error)

func (*LocalTransport) GetPredecessor 

func (lt *LocalTransport) GetPredecessor(vn *Vnode) (*Vnode, error)

func (*LocalTransport) GetPredecessorList 

func (lt *LocalTransport) GetPredecessorList(vn *Vnode) ([]*Vnode, error)

func (*LocalTransport) InvalidateRLock 

func (lt *LocalTransport) InvalidateRLock(targetClient *Vnode, lockID string) error

func (*LocalTransport) IsLocalVnode 

func (lt *LocalTransport) IsLocalVnode(target *Vnode) bool

func (*LocalTransport) JoinRing 

func (lt *LocalTransport) JoinRing(target *Vnode, ringId string, self *Vnode) ([]*Vnode, error)

func (*LocalTransport) List 

func (lt *LocalTransport) List(target *Vnode) ([]string, error)

func (*LocalTransport) ListVnodes 

func (lt *LocalTransport) ListVnodes(host string) ([]*Vnode, error)

func (*LocalTransport) MissingKeys 

func (lt *LocalTransport) MissingKeys(target *Vnode, ownerVn *Vnode, key string, ver []uint) error

func (*LocalTransport) Notify 

func (lt *LocalTransport) Notify(vn, self *Vnode) ([]*Vnode, error)

func (*LocalTransport) Ping 

func (lt *LocalTransport) Ping(vn *Vnode) (bool, error)

func (*LocalTransport) PurgeVersions 

func (lt *LocalTransport) PurgeVersions(target *Vnode, key string, maxVersion uint) error

func (*LocalTransport) RLock 

func (lt *LocalTransport) RLock(targetLm *Vnode, key string, nodeID string, opsLogEntry *OpsLogEntry) (string, uint, uint64, error)

func (*LocalTransport) Register 

func (lt *LocalTransport) Register(v *Vnode, o VnodeRPC)

func (*LocalTransport) Set 

func (lt *LocalTransport) Set(target *Vnode, key string, version uint, value []byte) error

func (*LocalTransport) SkipSuccessor 

func (lt *LocalTransport) SkipSuccessor(target, self *Vnode) error

func (*LocalTransport) SyncKeys 

func (lt *LocalTransport) SyncKeys(target *Vnode, ownerVn *Vnode, key string, ver []uint) error

func (*LocalTransport) WLock 

func (lt *LocalTransport) WLock(targetLm *Vnode, key string, version uint, timeout uint, nodeID string, opsLogEntry *OpsLogEntry) (string, uint, uint, uint64, error)

type MockClock 

type MockClock struct {
	mock.Mock
	// contains filtered or unexported fields
}

func NewClock 

func NewClock() *MockClock

func NewFrozenClock 

func NewFrozenClock() *MockClock

func (*MockClock) Advance 

func (m *MockClock) Advance(d time.Duration) *MockClock

func (*MockClock) AfterFunc 

func (m *MockClock) AfterFunc(d time.Duration, f func()) *time.Timer

func (*MockClock) Freeze 

func (m *MockClock) Freeze() *MockClock

func (*MockClock) Now 

func (m *MockClock) Now() time.Time

type OpsLogEntry 

type OpsLogEntry struct {
	OpNum   uint64     //  Operation Number
	Op      string     //  Operation that was performed
	Key     string     //  Key on which the operation was performed
	Version uint       //  Version number of the Key
	Timeout *time.Time // Timeout setting if any. For instance, WLocks have timeouts associated with them. When the primary fails, the second should know when to invalidate that entry

	// For handling replication. Nodes should be able to reconstruct the state using this log
	CopySet     *RLockEntry //  2D array. Maps nodeID and remote address. Used for RLock calls to maintain copysets
	LockId      string      //  For RLocks and WLocks, the LockID which the primary LM used should be replicated to the secondaries. Do not generate new LockIDs in the secondary
	CommitPoint uint64      // Operation number of the last committed operation
	Vn          *Vnode      //  Identity of the VNode, can be extended to be used for sending out of band signals to the primary.
}

Struct for the Log used for Lock state replication

type RLockEntry 

type RLockEntry struct {
	CopySet map[string][]string //  For each key, there will be a list of nodes and corresponding LockIDs given out. Used during invalidation
}

type RLockVal 

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

type RealClock 

type RealClock struct {
}

func (*RealClock) AfterFunc 

func (r *RealClock) AfterFunc(d time.Duration, f func()) *time.Timer

func (*RealClock) Now 

func (r *RealClock) Now() time.Time

type Ring 

type Ring struct {

	// Implements:
	RingIntf
	// contains filtered or unexported fields
}

Stores the state required for a Chord ring

func BlockingJoin 

func BlockingJoin(conf *Config, trans Transport, existing string) (*Ring, error)
BlockingJoin. Called by the buddynode that wants to block all operations until the network is healed.

Reason : All its operations should happen in its namespace. And its namespace i.e. the ring, specicifically the bootstrap members are present in the original ring

func Create 

func Create(conf *Config, trans Transport) (*Ring, error)

Creates a new Chord ring given the config and transport

func Join 

func Join(conf *Config, trans Transport, existing string) (*Ring, error)

Joins an existing Chord ring

func (*Ring) GetConfig 

func (r *Ring) GetConfig() *Config

func (*Ring) GetHashFunc 

func (r *Ring) GetHashFunc() func() hash.Hash

func (*Ring) GetLocalLocalVnode 

func (r *Ring) GetLocalLocalVnode() *localVnode

func (*Ring) GetLocalVnode 

func (r *Ring) GetLocalVnode() *Vnode

func (*Ring) GetNumSuccessors 

func (r *Ring) GetNumSuccessors() int

func (*Ring) GetRingId 

func (r *Ring) GetRingId() string

func (*Ring) Leave 

func (r *Ring) Leave() error

Leaves a given Chord ring and shuts down the local vnodes

func (*Ring) Len 

func (r *Ring) Len() int

Len is the number of vnodes

func (*Ring) Less 

func (r *Ring) Less(i, j int) bool

Less returns whether the vnode with index i should sort before the vnode with index j.

func (*Ring) Lookup 

func (r *Ring) Lookup(n int, key []byte) ([]*Vnode, error)

Does a key lookup for up to N successors of a key

func (*Ring) Shutdown 

func (r *Ring) Shutdown()

Shutdown shuts down the local processes in a given Chord ring Blocks until all the vnodes terminate.

func (*Ring) Swap 

func (r *Ring) Swap(i, j int)

Swap swaps the vnodes with indexes i and j.

func (*Ring) Transport 

func (r *Ring) Transport() Transport

type RingIntf 

type RingIntf interface {
	Leave() error
	Shutdown()
	Lookup(n int, key []byte) ([]*Vnode, error)
	Transport() Transport
	GetNumSuccessors() int
	GetLocalVnode() *Vnode
	GetLocalLocalVnode() *localVnode
	GetRingId() string
	GetHashFunc() func() hash.Hash
}

type TCPResponse 

type TCPResponse interface {
	Error() error
	SetError(error)
}

type TCPResponseBody 

type TCPResponseBody interface {
}

type TCPResponseImpl 

type TCPResponseImpl struct {
	Err string `json:"err,string,omitempty"`

	// Implements:
	TCPResponse `json:"-"`
}

func (*TCPResponseImpl) Error 

func (t *TCPResponseImpl) Error() error

func (*TCPResponseImpl) SetError 

func (t *TCPResponseImpl) SetError(err error)

type TCPTransport 

type TCPTransport struct {

	// Implements:
	Transport
	// contains filtered or unexported fields
}

TCPTransport provides a TCP based Chord transport layer. This allows Chord to be implemented over a network, instead of only using the LocalTransport. It is meant to be a simple implementation, optimizing for simplicity instead of performance. Messages are sent with a header frame, followed by a body frame. All data is encoded using the GOB format for simplicity.

Internally, there is 1 Goroutine listening for inbound connections, 1 Goroutine PER inbound connection.

func InitTCPTransport 

func InitTCPTransport(listen string, timeout time.Duration) (*TCPTransport, error)

Creates a new TCP transport on the given listen address with the configured timeout duration.

func (*TCPTransport) AbortWLock 

func (t *TCPTransport) AbortWLock(target *Vnode, key string, version uint, nodeID string, opsLogEntry *OpsLogEntry) (uint64, error)

AbortWLock transport layer implementation Param Vnode : The destination Vnode i.e. the Lock Manager Param key : The key for which the read lock should be obtained

func (*TCPTransport) BulkSet 

func (t *TCPTransport) BulkSet(target *Vnode, key string, valLst []KVStoreValue) error

func (*TCPTransport) ClearPredecessor 

func (t *TCPTransport) ClearPredecessor(target, self *Vnode) error

Clears a predecessor if it matches a given vnode. Used to leave.

func (*TCPTransport) CommitWLock 

func (t *TCPTransport) CommitWLock(target *Vnode, key string, version uint, nodeID string, opsLogEntry *OpsLogEntry) (uint64, error)

CommitWLock transport layer implementation Param Vnode : The destination Vnode i.e. the Lock Manager Param key : The key for which the read lock should be obtained Param version : The version of the key to be committed

func (*TCPTransport) FindSuccessors 

func (t *TCPTransport) FindSuccessors(vn *Vnode, n int, k []byte) ([]*Vnode, error)

Find a successor

func (*TCPTransport) Get 

func (t *TCPTransport) Get(target *Vnode, key string, version uint) ([]byte, error)

func (*TCPTransport) GetPredecessor 

func (t *TCPTransport) GetPredecessor(vn *Vnode) (*Vnode, error)

Request a nodes predecessor

func (*TCPTransport) GetPredecessorList 

func (t *TCPTransport) GetPredecessorList(vn *Vnode) ([]*Vnode, error)

Request a nodes predecessor list

func (*TCPTransport) InvalidateRLock 

func (t *TCPTransport) InvalidateRLock(target *Vnode, lockID string) error

InvalidateRLock transport layer implementation Param Vnode : The destination Vnode i.e. the Client where the RLock should be invalidated Param lockID : The exact lock to be invalidated

func (*TCPTransport) JoinRing 

func (t *TCPTransport) JoinRing(target *Vnode, ringId string, joiner *Vnode) ([]*Vnode, error)

func (*TCPTransport) List 

func (t *TCPTransport) List(target *Vnode) ([]string, error)

func (*TCPTransport) ListVnodes 

func (t *TCPTransport) ListVnodes(host string) ([]*Vnode, error)

Gets a list of the vnodes on the box

func (*TCPTransport) MissingKeys 

func (t *TCPTransport) MissingKeys(target *Vnode, replVn *Vnode, key string, ver []uint) error

func (*TCPTransport) Notify 

func (t *TCPTransport) Notify(target, self *Vnode) ([]*Vnode, error)

Notify our successor of ourselves

func (*TCPTransport) Ping 

func (t *TCPTransport) Ping(vn *Vnode) (bool, error)

Ping a Vnode, check for liveness

func (*TCPTransport) PurgeVersions 

func (t *TCPTransport) PurgeVersions(target *Vnode, key string, maxVersion uint) error

func (*TCPTransport) RLock 

func (t *TCPTransport) RLock(target *Vnode, key string, nodeID string, opsLogEntry *OpsLogEntry) (string, uint, uint64, error)

RLock tranasport layer implementation Param Vnode : The destination Vnode i.e. the Lock Manager Param key : The key for which the read lock should be obtained

func (*TCPTransport) Register 

func (t *TCPTransport) Register(v *Vnode, o VnodeRPC)

Register for an RPC callbacks

func (*TCPTransport) Set 

func (t *TCPTransport) Set(target *Vnode, key string, version uint, value []byte) error

func (*TCPTransport) Shutdown 

func (t *TCPTransport) Shutdown()

Shutdown the TCP transport

func (*TCPTransport) SkipSuccessor 

func (t *TCPTransport) SkipSuccessor(target, self *Vnode) error

Instructs a node to skip a given successor. Used to leave.

func (*TCPTransport) SyncKeys 

func (t *TCPTransport) SyncKeys(target *Vnode, ownerVn *Vnode, key string, ver []uint) error

func (*TCPTransport) WLock 

func (t *TCPTransport) WLock(target *Vnode, key string, version uint, timeout uint, nodeID string, opsLogEntry *OpsLogEntry) (string, uint, uint, uint64, error)

WLock transport layer implementation Param Vnode : The destination Vnode i.e. the Vnode with the Lock Manager Param key : The key for which the write lock should be obtained Param version : The version of the key Param timeout : Requested Timeout value. Param NodeID : NodeID of the requesting node

type TimeoutItem 

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

TimeoutQueue based on PriorityQueue from http://golang.org/pkg/container/heap/

type TimeoutQueue 

type TimeoutQueue []*TimeoutItem

A TimeoutQueue implements heap.Interface and holds TimeoutItems.

func (*TimeoutQueue) Get 

func (pq *TimeoutQueue) Get(i int) *TimeoutItem

func (TimeoutQueue) Len 

func (pq TimeoutQueue) Len() int

func (TimeoutQueue) Less 

func (pq TimeoutQueue) Less(i, j int) bool

func (*TimeoutQueue) Peek 

func (pq *TimeoutQueue) Peek() *TimeoutItem

func (*TimeoutQueue) Pop 

func (pq *TimeoutQueue) Pop() interface{}

func (*TimeoutQueue) Push 

func (pq *TimeoutQueue) Push(x interface{})

func (TimeoutQueue) Swap 

func (pq TimeoutQueue) Swap(i, j int)

type Tracker 

type Tracker interface {
	// contains filtered or unexported methods
}

func NewTracker 

func NewTracker() Tracker

func NewTrackerWithClock 

func NewTrackerWithClock(clock ClockIface) Tracker

func NewTrackerWithClockAndStore 

func NewTrackerWithClockAndStore(clock ClockIface, kvClient KVStoreClient) Tracker

func NewTrackerWithStore 

func NewTrackerWithStore(store KVStoreClient) Tracker

type TrackerClient 

type TrackerClient interface {
	JoinRing(string, bool) (*Ring, error)
	LeaveRing(string) error
}

func NewTrackerClient 

func NewTrackerClient(ring RingIntf) TrackerClient

type TrackerClientImpl 

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

func (*TrackerClientImpl) JoinRing 

func (tr *TrackerClientImpl) JoinRing(ringId string, localOnly bool) (*Ring, error)

func (*TrackerClientImpl) LeaveRing 

func (tr *TrackerClientImpl) LeaveRing(ringId string) error

type TrackerImpl 

type TrackerImpl struct {

	// Implements:
	Tracker
	// contains filtered or unexported fields
}

type Transport 

type Transport interface {
	// Gets a list of the vnodes on the box
	ListVnodes(string) ([]*Vnode, error)

	// Ping a Vnode, check for liveness
	Ping(*Vnode) (bool, error)

	// Request a nodes predecessor
	GetPredecessor(*Vnode) (*Vnode, error)

	// Notify our successor of ourselves
	Notify(target, self *Vnode) ([]*Vnode, error)

	// Find a successor
	FindSuccessors(*Vnode, int, []byte) ([]*Vnode, error)

	// Clears a predecessor if it matches a given vnode. Used to leave.
	ClearPredecessor(target, self *Vnode) error

	// Instructs a node to skip a given successor. Used to leave.
	SkipSuccessor(target, self *Vnode) error

	// Get the list of predecessors
	GetPredecessorList(*Vnode) ([]*Vnode, error)

	// Register for an RPC callbacks
	Register(*Vnode, VnodeRPC)

	// Lock Manager operations
	RLock(*Vnode, string, string, *OpsLogEntry) (string, uint, uint64, error)
	WLock(*Vnode, string, uint, uint, string, *OpsLogEntry) (string, uint, uint, uint64, error)
	CommitWLock(*Vnode, string, uint, string, *OpsLogEntry) (uint64, error)
	AbortWLock(*Vnode, string, uint, string, *OpsLogEntry) (uint64, error)
	InvalidateRLock(*Vnode, string) error

	// KV Store operations
	Get(target *Vnode, key string, version uint) ([]byte, error)
	Set(target *Vnode, key string, version uint, value []byte) error
	List(target *Vnode) ([]string, error)
	BulkSet(target *Vnode, key string, valLst []KVStoreValue) error
	SyncKeys(target *Vnode, ownerVn *Vnode, key string, ver []uint) error
	MissingKeys(target *Vnode, replVn *Vnode, key string, ver []uint) error
	PurgeVersions(target *Vnode, key string, maxVersion uint) error

	// Tracker operations
	JoinRing(target *Vnode, ringId string, self *Vnode) ([]*Vnode, error)
	LeaveRing(target *Vnode, ringId string) error

	// TODO: Is this the right place?
	IsLocalVnode(vn *Vnode) bool
}

Implements the methods needed for a Chord ring

func InitLocalTransport 

func InitLocalTransport(remote Transport) Transport

Creates a local transport to wrap a remote transport

type Vnode 

type Vnode struct {
	Id   []byte // Virtual ID
	Host string // Host identifier
	// contains filtered or unexported fields
}

Represents an Vnode, local or remote

func (*Vnode) String 

func (vn *Vnode) String() string

Converts the ID to string

type VnodeRPC 

type VnodeRPC interface {
	GetPredecessor() (*Vnode, error)
	Notify(*Vnode) ([]*Vnode, error)
	FindSuccessors(int, []byte) ([]*Vnode, error)
	ClearPredecessor(*Vnode) error
	SkipSuccessor(*Vnode) error
	GetPredecessorList() ([]*Vnode, error)
	GetId() (string, error)

	// KV Store operations
	Get(key string, version uint) ([]byte, error)
	Set(key string, version uint, value []byte) error
	List() ([]string, error)
	BulkSet(key string, valLst []KVStoreValue) error
	SyncKeys(ownerVn *Vnode, key string, ver []uint) error
	MissingKeys(replVn *Vnode, key string, ver []uint) error
	PurgeVersions(key string, maxVersion uint) error

	// Lock Manager operations
	RLock(key string, nodeID string, remoteAddr string, opsLogEntry *OpsLogEntry) (string, uint, uint64, error)
	WLock(key string, version uint, timeout uint, nodeID string, opsLogEntry *OpsLogEntry) (string, uint, uint, uint64, error)
	CommitWLock(key string, version uint, nodeID string, opsLogEntry *OpsLogEntry) (uint64, error)
	AbortWLock(key string, version uint, nodeID string, opsLogEntry *OpsLogEntry) (uint64, error)
	InvalidateRLock(lockID string) error
	CheckWLock(key string) (bool, uint, error)
	UpdateVersionMap(versionMap *map[string]uint)

	// Tracker operations
	JoinRing(ringId string, self *Vnode) ([]*Vnode, error)
	LeaveRing(ringId string) error
}

These are the methods to invoke on the registered vnodes

type WLockEntry 

type WLockEntry struct {
	LockID string
	// contains filtered or unexported fields
}

TODO : Discuss : LockID is currently 160 bits long. Is that good enough?

type WLockVal 

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

Source Files

View all Source files

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.