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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cluster ¶
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 Scanner ¶ added in v0.0.2
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.
Source Files