cluster

README

cluster

Package cluster provides an Insert/Select/Delete API on top of a single Pool object. Cluster accepts KeyScoreMember tuples from clients, which map to Redis sorted set semantics. Briefly, key identifies the set, member the element in the set, and score is a sort of version associated with the element. Write (Insert or Delete) operations are no-ops if the passed score is less than or equal to any previously written score for that member.

All elements of the KeyScoreMember tuple are expected to be provided by the client. As scores are typically timestamps, an important consideration is that cluster is totally reliant on an external clock.

Associative, commutative, idempotent

To ensure a given Member is only represented by the highest Score in the logical set identified by Key, and to ensure the correct semantics for Deletes (i.e. that a newer Delete takes precedence over an older Insert) cluster uses a Redis script to manage membership in two physical sets: an "Inserts" set key+; and a "Deletes" set key-. The design is facially similar to the 2P-set CRDT.

In pseudocode, that script is:

bool valid(key, score, member):
	if contains(key+, member) and score < score_of(key+, member):
		return false
	if contains(key-, member) and score <= score_of(key-, member):
		return false
	return true

insert(key, score, member):
	if valid(key, score, member):
		add(key+, member, score)
		del(key-, member)

delete(key, score, member):
	if valid(key, score, member):
		add(key-, member, score)
		del(key+, member)

Script execution is atomic, and a single logical key is deterministically stored on a single node. These properties ensure that every possible finite set of (WriteOp + KeyScoreMember) operations resolves to the same final state, regardless of the execution order. (I think another way of stating that is that any valid linearization of write operations is equal to any of that linearization's permutations. Feedback on this point would be appreciated.) Interleaved reads will always return correct data from the perspective of that specific history.

It's also interesting to note that Select returns a complete KeyScoreMember tuple. If we have some mechanism of detecting inconsistent data via reads—for example, by intelligently comparing results from multiple clusters—we immediately have enough information to issue repairing write operations against the inconsistent clusters.

Documentation

Overview

Package cluster provides a sorted-set API (via Redis ZSETs) on top of a group of Redis instances.

Index

• type Cluster
  • func New(pool *pool.Pool, maxSize int, instr instrumentation.Instrumentation) Cluster
• type Deleter
• type Element
• type Inserter
• type Presence
• type Scanner
• type Scorer
• type Selecter

Types

type Cluster

type Cluster interface {
	Inserter
	Selecter
	Deleter
	Scorer
	Scanner
}

Cluster defines methods that efficiently provide ZSET semantics on a cluster.

func New

func New(pool *pool.Pool, maxSize int, instr instrumentation.Instrumentation) Cluster

New creates and returns a new Cluster backed by a concrete Redis cluster. maxSize for each key will be enforced at write time. Instrumentation may be nil.

type Deleter

type Deleter interface {
	Delete(tuples []common.KeyScoreMember) error
}

Deleter defines the method to delete elements from a sorted set. A key- member's score must be larger than the currently stored score for the delete to be accepted. A non-nil error indicates only physical problems, not logical.

type Element

type Element struct {
	Key             string
	KeyScoreMembers []common.KeyScoreMember
	Error           error
}

Element combines a submitted key with its selected score-members. If there was an error while selecting a key, the error field will be populated, and common.KeyScoreMembers may be empty. TODO rename.

type Inserter

type Inserter interface {
	Insert(tuples []common.KeyScoreMember) error
}

Inserter defines the method to add elements to a sorted set. A key-member's score must be larger than the currently stored score for the insert to be accepted. A non-nil error indicates only physical problems, not logical.

type Presence

type Presence struct {
	Present  bool
	Inserted bool // false = deleted
	Score    float64
}

Presence represents the state of a given key-member in a cluster.

type Scanner

type Scanner interface {
	Keys(batchSize int) <-chan []string
}

Scanner emits all keys in the keyspace over a returned channel. When the keys are exhaused, the channel is closed. The order in which keys are emitted is unpredictable. Scanning is performed one Redis instance at a time in random order of the instances. If an instance is down at the time it is tried to be scanned, it is skipped (no retries). See also implications of the Redis SCAN command. Note that keys for which only deletes have happened (and no inserts) will not be emitted.

type Scorer

type Scorer interface {
	Score([]common.KeyMember) (map[common.KeyMember]Presence, error)
}

Scorer defines the method to retrieve the presence information of a set of key-members.

type Selecter

type Selecter interface {
	Select(keys []string, offset, limit int) <-chan Element
}

Selecter defines the method to retrieve elements from a sorted set.