Documentation
¶
Overview ¶
Package timed implements modification-time-indexed storage that can be accessed in modification-time order as well as key order.
Timed storage builds on top of a basic key-value storage by maintaining two actual database entries for each logical entry. The two actual entries for the logical entry (kind, key) → val are:
- (kind, key) → (modtime, val)
- (kindByTime, modtime, key) → ()
The “kind” is a key namespace that allows maintaining multiple independent sets of modification-time-indexed storage in a single storage.DB.
The “modtime” (of type DBTime) is an opaque timestamp representing the time when the logical entry was last set. Other than being a monotonically increasing integer, no specific semantics are guaranteed about the meaning of the dbtime.
An Entry represents a single logical entry:
type Entry struct {
ModTime DBTime // time entry was written
Kind string // key namespace
Key []byte // key
Val []byte // value
}
The basic Get, Set, Scan, Delete, and DeleteRange functions are analogous to those in storage.DB but modified to accomodate the new entries:
Get(db, kind, key) returns an *Entry. The db is the underlying storage being used.
Set(db, batch, kind, key, val) adds or replaces an entry. The db is the underlying storage, which is consulted, but the actual modifications are written to batch, so that the two different actual entries can be applied as a single unit.
Scan(db, kind, start, end) returns an iterator yielding *Entry.
Delete(db, batch, kind, key) deletes an entry.
DeleteRange(db, batch, kind, start, end) deletes a range of entries.
In addition to these operations, the time index enables one new operation:
- After(db, kind, dbtime) returns an iterator yielding entries updated after dbtime, ordered by time of update.
In typical usage, a client stores the latest e.DBTime it has observed and then uses that value in a future call to After to find only recent entries. The Watcher encapsulates that pattern and adds mutual exclusion so that multiple processes or goroutines using the same Watcher will not run concurrently.
Index ¶
- func Delete(db storage.DB, b storage.Batch, kind string, key []byte)
- func DeleteRange(db storage.DB, b storage.Batch, kind string, start, end []byte)
- func Scan(db storage.DB, kind string, start, end []byte) iter.Seq[*Entry]
- func ScanAfter(db storage.DB, kind string, t DBTime, filter func(key []byte) bool) iter.Seq[*Entry]
- func Set(db storage.DB, b storage.Batch, kind string, key, val []byte)
- type DBTime
- type Entry
- type Watcher
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Delete ¶
Delete adds to b the database updates to delete the value corresponding to (kind, key), if any.
func DeleteRange ¶
DeleteRange adds to b the database updates to delete all entries (kind, key) → val with start ≤ key ≤ end. To allow deleting an arbitrarily large range, DeleteRange calls b.MaybeApply after adding the updates for each (kind, key). The effect is that a large range deletion may not be applied atomically to db. The caller still needs to use b.Apply to apply the final updates (or, for small ranges, all of them).
Types ¶
type DBTime ¶
type DBTime int64
A DBTime is an opaque timestamp representing the time when a database entry was last set. Timestamps increase monotonically: comparing two times from entries of the same kind indicates which entry was written first. Otherwise, timestamps are opaque and have no specific meaning.
type Entry ¶
type Entry struct {
ModTime DBTime // time entry was written
Kind string // key namespace
Key []byte // key
Val []byte // value
}
An Entry is a single entry written to the time-indexed storage.
type Watcher ¶
type Watcher[T any] struct { // contains filtered or unexported fields }
A Watcher is a named cursor over recently modified time-stamped key-value pairs (written using Set). The state of the cursor is stored in the underlying database so that it persists across program restarts and is shared by all clients of the database.
Across all Watchers with the same db, kind, and name, database locks are used to ensure that only one at a time can iterate over Watcher.Recent. This provides coordination when multiple instances of a program that notice there is work to be done and more importantly avoids those instances conflicting with each other.
The Watcher's state (most recent dbtime marked old) is stored in the underlying database using the key ordered.Encode(kind+"Watcher", name), and while a Watcher is iterating, it locks a database lock with the same name as that key.
func NewWatcher ¶
NewWatcher returns a new named Watcher reading keys of the given kind from db. Use Watcher.Recent to iterate over recent entries.
The name distinguishes this Watcher from other Watchers watching the same kind of keys for different purposes.
The Watcher applies decode(e) to each time-stamped Entry to obtain the T returned in the iteration.
func (*Watcher[T]) Flush ¶
func (w *Watcher[T]) Flush()
Flush flushes the definition of recent (changed by MarkOld) to the database. Flush is called automatically at the end of an iteration, but it can be called explicitly during a long iteration as well.
func (*Watcher[T]) MarkOld ¶
MarkOld marks entries at or before t as “old”, meaning they will no longer be iterated over by Watcher.Recent. A future call to Recent, perhaps even on a different Watcher with the same configuration, will start its iteration starting immediately after time t.
If a newer time t has already been marked “old” in this watcher, then MarkOld(t) is a no-op.
MarkOld must be called during an iteration over Recent, so that the database lock corresponding to this Watcher is held. In the case of a process crash before the iteration completes, the effect of MarkOld may be lost. Calling Watcher.Flush forces the state change to the underlying database.
func (*Watcher[T]) Recent ¶
Recent returns an iterator over recent entries, meaning those entries set after the last time recorded using Watcher.MarkOld. The events are ordered by the time they were last Set (that is, by ModTime).
When the iterator is invoked or ranged over, it acquires a database lock corresponding to (db, name, kind), to prevent other racing instances of the same Watcher from visiting the same entries. It releases the lock automatically when the iteration ends or is stopped.
The iterator must be used from only a single goroutine at a time, or else it will panic reporting “Watcher already locked”. This means that while an iterator can be used multiple times in sequence, it cannto be used from multiple goroutines, nor can a new iteration be started inside an existing one. (If a different process holds the lock, the iterator will wait for that process. The in-process lock check aims to diagnose simple deadlocks.)
Source Files