README
¶
Dory
A cache utilising spare/unused memory.
Background
Dory was inspired by looking at resource utilisation within clusters. Generally, when tasks are launched in a cluster (i.e. on Kubernetes), they are provisioned with more memory than will be used on a regular basis. A HTTP server might be provisioned for 128MiB of memory, but only uses 32MiB 99% of the time, increasing and decreasing as load varies. The provisioned memory amount is usually the peak that the server is expected to use.
In a desktop or traditional server, that unused memory will be used by the page cache to keep pages from disk in memory. This improves performance by avoiding slow disk accesses (even for SSDs). However, in a distributed system, the page cache is significantly less effective due to the use of remote/distributed storage systems instead of local disk.
So the idea is to try and use that unused memory for a cache, but with the ability to rapidly return that memory to the OS when needed.
Design
Before discussing design, it's important to talk about non-goals for Dory. Specifically:
- NOT designed for ultra high performance
- NOT designed for consistency
- NOT designed to be memory efficient
Although these are non-goals, it's important to be reasonable. Memory overhead is on the order of ~100 bytes/key-value pair. Currently, ~50% of CPU usage is in the protocol stack, which is a very minimal implementation of the redis protocol.
That said, the single primary design goal is to be able to rapidly return memory to the OS. This is mainly achieved by avoid the heap as much as possible. Although Go has an excellent garbage collector, factors such as heap fragmentation, a problem which exists in every language and runtime, prevent memory from being returned to the OS in a deterministic manner.
Instead, anonymous mmap'd areas are created, and managed using a structure called PackedTable (naming is hard). PackedTable implements a key-value table while keeping the key/value data in a single []byte buffer, backed by the mmap. The structure is similar to an SSTable, where the key/values are stored contiguously, with an index stored in a Go map. When memory needs to be returned to the OS, the mmap'd area is simply unmapped.
At a higher level, the Memcache holds a list of PackedTables and a map of keys to PackedTables. The indirection in Memcache allows for any number of PackedTables to disappear at any point in time. The Memcache also monitors the level of free memory by polling /proc/meminfo and adjusting the number of PackedTables as necessary.
Usage
The dory directory contains the server. By default, dory listens on port
6379, since it implements a small subset of the redis protocol.
Dory only implements the following redis commands:
- SET
- GET
- DEL
- EXISTS
The protocol has been tested with redis-benchmark, redis-cli and
the go-redis client library.
The ideal way to deploy dory would be as a DaemonSet on kubernetes. A single instance on every node will use up any available unused memory on the node. However, work needs to be done on a client library to make this feasible.
Licence
Dory is released under the Apache 2.0 license
Documentation
¶
Index ¶
- Constants
- Variables
- type DiscardableTable
- func (t *DiscardableTable) Delete(key []byte) bool
- func (t *DiscardableTable) DeletedSpace() int
- func (t *DiscardableTable) Discard()
- func (t *DiscardableTable) Element() *list.Element
- func (t *DiscardableTable) FreeSpace() int
- func (t *DiscardableTable) Get(key []byte) []byte
- func (t *DiscardableTable) Has(key []byte) bool
- func (t *DiscardableTable) KeyHashes() []uint64
- func (t *DiscardableTable) LiveSpace() int
- func (t *DiscardableTable) Meta() interface{}
- func (t *DiscardableTable) NumDeleted() int
- func (t *DiscardableTable) NumEntries() int
- func (t *DiscardableTable) Put(key, val []byte, hash uint64) error
- func (t *DiscardableTable) Recycle(meta interface{}) *DiscardableTable
- func (t *DiscardableTable) Reset()
- func (t *DiscardableTable) SetElement(e *list.Element)
- type HashFunc
- type MemFunc
- type Memcache
- func (c *Memcache) Delete(key []byte)
- func (c *Memcache) Get(key, buf []byte) []byte
- func (c *Memcache) Has(key []byte) bool
- func (c *Memcache) MaxKeySize() int
- func (c *Memcache) MaxValSize() int
- func (c *Memcache) MinKeySize() int
- func (c *Memcache) MinValSize() int
- func (c *Memcache) Put(key, val []byte)
- type MemcacheOptions
- type PackedTable
- func (t *PackedTable) Delete(key []byte) bool
- func (t *PackedTable) DeletedSpace() int
- func (t *PackedTable) EntrySize(key, val []byte) int
- func (t *PackedTable) FreeSpace() int
- func (t *PackedTable) GC()
- func (t *PackedTable) Get(key []byte) []byte
- func (t *PackedTable) Has(key []byte) bool
- func (t *PackedTable) Keys() [][]byte
- func (t *PackedTable) LiveSpace() int
- func (t *PackedTable) NumDeleted() int
- func (t *PackedTable) NumEntries() int
- func (t *PackedTable) Put(key, val []byte) error
- func (t *PackedTable) Reset()
Constants ¶
const ( DefaultTableSize = 4 * megabyte DefaultCacheSize = 64 * megabyte DefaultMaxKeySize = 1024 DefaultMaxValSize = 1024 * 1024 )
Variables ¶
var (
ErrNoSpace = errors.New("insufficent space left")
)
Functions ¶
This section is empty.
Types ¶
type DiscardableTable ¶
type DiscardableTable struct {
// contains filtered or unexported fields
}
TODO: Rename to MmappedTable?
func NewDiscardableTable ¶
func NewDiscardableTable(size int, meta interface{}) *DiscardableTable
func (*DiscardableTable) Delete ¶
func (t *DiscardableTable) Delete(key []byte) bool
func (*DiscardableTable) DeletedSpace ¶
func (t *DiscardableTable) DeletedSpace() int
func (*DiscardableTable) Discard ¶
func (t *DiscardableTable) Discard()
func (*DiscardableTable) Element ¶
func (t *DiscardableTable) Element() *list.Element
func (*DiscardableTable) FreeSpace ¶
func (t *DiscardableTable) FreeSpace() int
func (*DiscardableTable) Get ¶
func (t *DiscardableTable) Get(key []byte) []byte
func (*DiscardableTable) Has ¶
func (t *DiscardableTable) Has(key []byte) bool
func (*DiscardableTable) KeyHashes ¶
func (t *DiscardableTable) KeyHashes() []uint64
func (*DiscardableTable) LiveSpace ¶
func (t *DiscardableTable) LiveSpace() int
func (*DiscardableTable) Meta ¶
func (t *DiscardableTable) Meta() interface{}
func (*DiscardableTable) NumDeleted ¶
func (t *DiscardableTable) NumDeleted() int
func (*DiscardableTable) NumEntries ¶
func (t *DiscardableTable) NumEntries() int
func (*DiscardableTable) Recycle ¶
func (t *DiscardableTable) Recycle(meta interface{}) *DiscardableTable
func (*DiscardableTable) Reset ¶
func (t *DiscardableTable) Reset()
func (*DiscardableTable) SetElement ¶
func (t *DiscardableTable) SetElement(e *list.Element)
type HashFunc ¶
HashFunc is a function which hashes a byte array into a 64-bit hash. The hash should have uniform distribution, suitable for use in a hash table.
type MemFunc ¶
MemFunc is a function that returns the amount of memory (in bytes) that should be used by tables in a Memcache. The usage argument is the bytes of memory currently being used by tables.
func AvailableMemory ¶
AvailableMemory returns a MemFunc that cause Memcache to use all available memory on the system. The minFree argument is the minimum amount of memory that should be kept free. The maxUtilisation is the maximum fraction of available memory that should be used.
func ConstantMemory ¶
ConstantMemory returns a MemFunc that causes Memcache to use a fixed amount of memory.
type Memcache ¶
type Memcache struct {
// contains filtered or unexported fields
}
func NewMemcache ¶
func NewMemcache(opts MemcacheOptions) *Memcache
func (*Memcache) MaxKeySize ¶
func (*Memcache) MaxValSize ¶
func (*Memcache) MinKeySize ¶
func (*Memcache) MinValSize ¶
type MemcacheOptions ¶
type PackedTable ¶
type PackedTable struct {
// contains filtered or unexported fields
}
PackedTable is a simple key/value table that stores key and value data contiguously within a single []byte slice. The only data stored outside the slice is an index used to locate entries in the slice.
The primary goals are to minimise heap fragmentation, and allow the user to instantly free memory used by this table (i.e. using munmap()). A good side effect is to also reduce Go GC pressure, although this is not a primary goal.
Note: PackedTable is not thread-safe.
func NewPackedTable ¶
func NewPackedTable(buf []byte, autoGcThreshold int) *PackedTable
Construct a new PackedTable using the given slice to store key/value data. autoGcThreshold is the number of bytes of data deleted before the table automatically performs a garbage collection (technically a compaction). If autoGcThreshold is 0, automatic GC is disabled. Note: The slice MUST be smaller than 1GiB in length.
func (*PackedTable) Delete ¶
func (t *PackedTable) Delete(key []byte) bool
Delete removes the key, and returns true if the key existed. Deleting a key may not automatically free space used by that key/value. Space is only reclaimed if the amount of deleted space exceeds the auto-GC threshold, or a GC is explicitly performed.
func (*PackedTable) DeletedSpace ¶
func (t *PackedTable) DeletedSpace() int
DeletedSpace returns the number of bytes used by deleted entries in the table. This space may be reclaimed by running a garbage collection. Note: LiveSpace + FreeSpace + DeletedSpace == len(buf)
func (*PackedTable) EntrySize ¶
func (t *PackedTable) EntrySize(key, val []byte) int
EntrySize returns the amount of space used in the table's slice by the given key/value. May be used to determine if there is sufficient space to store the key/value.
func (*PackedTable) FreeSpace ¶
func (t *PackedTable) FreeSpace() int
FreeSpace returns the number of bytes of usable free space in the table.
func (*PackedTable) GC ¶
func (t *PackedTable) GC()
GC performs a garbage collection to reclaim free space.
func (*PackedTable) Get ¶
func (t *PackedTable) Get(key []byte) []byte
Get returns a slice of the value for the key, if it exists in the table, or nil if the key does not exist. The returned slice will be a slice into the table's memory and MUST NOT be modified, and is only valid until the next call into PackedTable.
func (*PackedTable) Has ¶
func (t *PackedTable) Has(key []byte) bool
Has returns whether or not the table contains the requested key.
func (*PackedTable) Keys ¶
func (t *PackedTable) Keys() [][]byte
Keys returns a list of keys. Returned keys are slices into this table's memory, MUST NOT be modified, and are only valid until the next call into PackedTable.
func (*PackedTable) LiveSpace ¶
func (t *PackedTable) LiveSpace() int
LiveSpace return the number of bytes used by entries in the table.
func (*PackedTable) NumDeleted ¶
func (t *PackedTable) NumDeleted() int
NumDeleted returns the number of deleted entries in the table. This space may be reclaimed by running a garbage collection.
func (*PackedTable) NumEntries ¶
func (t *PackedTable) NumEntries() int
NumEntries returns the number of entries in the table. Should probably be renamed to Len().
func (*PackedTable) Put ¶
func (t *PackedTable) Put(key, val []byte) error
Put adds the key/value into the table, if there is sufficient free space. Returns nil on success, or ErrNoSpace if there is insufficient free space. If the table already contains the key, the existing key/value will be deleted (as if Delete() was called), and the new entry inserted.
Source Files
Directories