cluster

README

cluster

Package cluster provides an Insert/Select/Delete API on top of a single Shards 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, the 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_of(key+, member) >= score:
	    return false
	if contains(key-, member) and score_of(key-, member) >= score:
	    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(shards *shard.Shards, maxSize int, instr instrumentation.Instrumentation) Cluster
• type Deleter
• type Element
• type Inserter
• type Scorer
• type Selecter

Types

type Cluster

type Cluster interface {
	Inserter
	Selecter
	Deleter
	Scorer
}

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

func New

func New(shards *shard.Shards, 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 Scorer

type Scorer interface {
	Score(key, member string) (float64, bool, error)
}

Scorer defines the method to retrieve the score of a specific key-member, if it's known to the cluster. It also returns whether that key-member is inserted (present) or deleted (not present) via the bool return parameter (true = inserted).

type Selecter

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

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