README
¶
LRU 
LRU is a persistent read-through local cache backed by BoltDB and a remote store of your choosing.
Currently A Work In Progress
Documentation
¶
Index ¶
- Variables
- type Algorithm
- type BasicLRU
- func (bl *BasicLRU) Cap() int64
- func (bl *BasicLRU) Empty()
- func (bl *BasicLRU) Get(key []byte) int64
- func (bl *BasicLRU) Len() int64
- func (bl *BasicLRU) PutAndEvict(key []byte, size int64) ([][]byte, int64)
- func (bl *BasicLRU) PutOnStartup(key []byte, size int64) bool
- func (bl *BasicLRU) Size() int64
- type Buffer
- type LRU
- type Stats
- type Store
- type TwoQ
Constants ¶
This section is empty.
Variables ¶
var ( // ErrNoKey represents the error encountered when no key is provided. ErrNoKey = errors.New("no key provided") // ErrNoValue represents the error encountered when no error or value is // returned from the remote store. ErrNoValue = errors.New("no value returned from the store") )
Functions ¶
This section is empty.
Types ¶
type Algorithm ¶
type Algorithm interface {
// Cap returns the total capacity of the LRU in bytes.
Cap() int64
// Empty completely empties the LRU.
Empty()
// Get returns the size of the item identified by the provided key, or
// -1 if the key does not exist in the LRU.
Get([]byte) int64
// Len returns the total number of items in the LRU.
Len() int64
// PutAndEvict inserts the provided key and size into the LRU and
// returns a slice of keys that have been evicted as well as the total
// size in bytes that were evicted.
PutAndEvict([]byte, int64) ([][]byte, int64)
// PutOnStartup adds the provided key and size to LRU and returns true
// if the key was successfully added.
PutOnStartup([]byte, int64) bool
// Size returns the total size in bytes of all items in the LRU.
Size() int64
}
Algorithm represents the underlying algorithm managing an LRU.
type BasicLRU ¶
type BasicLRU struct {
// contains filtered or unexported fields
}
BasicLRU is an implementation of a basic least recently used (LRU) cache. For more information, see: https://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used
func DefaultBasicLRU ¶
DefaultBasicLRU returns a new BasicLRU instance with the provided capacity and an eviction ratio of 0.1%.
func NewBasicLRU ¶
NewBasicLRU returns a new BasicLRU with the provided capacity, and eviction ratio.
evictRatio represents the percentage of items (based on size) that should be evicted when the LRU's capacity is exceeded.
func (*BasicLRU) Get ¶
Get returns the size of the value corresponding to the provided key, or -1 if the key doesn't exist in the LRU.
func (*BasicLRU) PutAndEvict ¶
PutAndEvict inserts the provided key and value size into the LRU and returns a slice of keys that have been evicted and total bytes evicted.
func (*BasicLRU) PutOnStartup ¶
PutOnStartup adds the provided key and value size into the LRU as an initial item. All items are inserted into the LRU until full, where items are dropped and 'false' is returned.
type Buffer ¶
type Buffer struct {
// contains filtered or unexported fields
}
Buffer represents data obtained from the cache using an underlying pooled buffer. After using a Buffer, its Close method should be called to release the underlying buffer back into the global pool. At this time, the byte slice returned from the Bytes method is invalid, and should not be used any further.
func (*Buffer) Bytes ¶
Bytes returns the Buffer's underlying byte slice. The returned slice is only valid before calling the Buffer's Close method. After that time, its contents may change or become invalid.
type LRU ¶
type LRU struct {
// contains filtered or unexported fields
}
LRU is a persistent read-through local cache backed by BoltDB and a remote store of your choosing.
func NewLRU ¶
NewLRU returns a new LRU object with the provided database path, bucket name, LRU algorithm, and remote store. Before using the returned LRU, its Open method must be called first.
func (*LRU) Close ¶
Close closes the LRU's remote store and the connection to the local bolt database and returns any error encountered.
func (*LRU) Get ¶
Get attempts to retrieve the value for the provided key. An error is returned if either no value exists or an error occurs while retrieving the value from the remote store. Byte slices returned by this method should not be modified.
func (*LRU) GetBuffer ¶
GetBuffer attempts to retrieve the value for the provided key, returning a Buffer. An error is returned if either no value exists or an error occurs while retrieving the value from the remote store. After finishing with the returned Buffer, its Close method should be called.
The advantage to using this method over Get is that an internal buffer pool is utilized to minimize creating and allocating new byte slices. Upon using the Buffer's underlying data, the Buffer's Close method should be called. This will invalidate the Buffer for further use and return the underlying buffer back into the pool to be used by another call to GetBuffer. The Buffer's Bytes and WriteTo methods cannot be called concurrently with its Close method.
func (*LRU) Open ¶
Open opens the LRU's remote store and, if successful, the local bolt database. If the bolt database contains existing items, the LRU is filled up to its capacity and the overflow is deleted from the database.
func (*LRU) ResetStats ¶
ResetStats resets all stats to their initial state and returns the LRU's stats as they were immediately before being reset.
type Stats ¶
type Stats struct {
StartTime time.Time `json:"start_time"`
Uptime time.Duration `json:"uptime"`
Hits int64 `json:"hits"`
Misses int64 `json:"misses"`
GetBytes int64 `json:"get_bytes"`
Puts int64 `json:"puts"`
PutBytes int64 `json:"put_bytes"`
Evicted int64 `json:"evicted"`
EvictedBytes int64 `json:"evicted_bytes"`
Size int64 `json:"size"`
Capacity int64 `json:"capacity"`
NumItems int64 `json:"num_items"`
}
Stats contains a number of stats pertaining to an LRU.
type Store ¶
type Store interface {
Get([]byte) ([]byte, error) // retrieve the value with the provided key
Open() error // open the store
Close() error // close the store
}
Store is an interface representing a remote data store.
type TwoQ ¶
type TwoQ struct {
// contains filtered or unexported fields
}
TwoQ is an implementation of the 2Q LRU algorithm, as defined by Theodore Johnson and Dennis Shasha: http://www.vldb.org/conf/1994/P439.PDF
The TwoQ struct consists of a master item map, the total capacity in bytes, and three basic LRUs. The hot LRU is the "frequently accessed" LRU, which contains items that have been requested more than once. The warm LRU is the "recently accessed" LRU, which contains items that have been requested only once. Items in the hot or warm LRUs should have values that exist in the backing cache. When items are evicted from the hot or warm LRUs, they are pushed to the front of the cold LRU. Items in the cold LRU represent items that have been recently evicted. If an item is inserted into the 2Q LRU that exists in the cold LRU, it is immediately added to the front of the hot LRU, instead of the warm LRU (where items not yet in any LRU are placed).
When an item is inserted into the 2Q LRU, it checks if it currently exists in any of the internal basic LRUs. If in the hot LRU, it is moved to the front. If in the warm LRU, the item is removed and inserted into the hot LRU. If in in the cold LRU, the item is inserted directly into the hot LRU and the 2Q LRU is pruned. If the item does not yet exist in any of the internal LRUs, it is inserted into the front of the warm LRU and the 2Q LRU is pruned.
When a pruning occurs, the 2Q LRU's size is compared to its total capacity. If the size is less than or equal to the capacity, nothing happens. Otherwise, the warm LRU is pruned if its size exceeds its capacity. If the warm LRU is under its capacity, the hot LRU is pruned. During pruning, items are removed from the back of the LRU and their keys are returned.
func DefaultTwoQ ¶
DefaultTwoQ returns a new TwoQ LRU with the provided capacity.
func NewTwoQ ¶
NewTwoQ returns a new TwoQ instance given the provided capacity, eviction ratio, warm/hot ratio, and cold ratio.
evictRatio represents the percentage of items (based on size) that should be evicted when the LRUs capacity are exceeded. warmHotRatio represents the percentage of items (based on size) that should exist in the warm LRU compared to the hot LRU. This ratio matters when items are being evicted. coldRatio is a percentage representing the number of items (based on size) that should be kept in the cold LRU compared to the total capacity.
func (*TwoQ) Get ¶
Get returns the size of the value corresponding to the provided key, or -1 if the key doesn't exist in the LRU.
func (*TwoQ) PutAndEvict ¶
PutAndEvict inserts the provided key and value size into the LRU and returns a slice of keys that have been evicted and total bytes evicted.
func (*TwoQ) PutOnStartup ¶
PutOnStartup adds the provided key and value size into the LRU as an initial item. All items are inserted into the warm LRU until full, where items begin to be inserted into the cold LRU. It returns true if the item was inserted into the warm LRU successfully.
Source Files