collections

package
v4.20.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 20, 2024 License: Apache-2.0 Imports: 8 Imported by: 5

README

LRUCache

Implements a Least Recently Used Cache with optional TTL and stats collection

This is a LRU cache based off github.com/golang/groupcache/lru expanded with the following

  • Peek() - Get the value without updating the expiration or last used or stats
  • Keys() - Get a list of keys at this point in time
  • Stats() - Returns stats about the current state of the cache
  • AddWithTTL() - Adds a value to the cache with a expiration time
  • Each() - Concurrent non blocking access to each item in the cache
  • Map() - Efficient blocking modification to each item in the cache

TTL is evaluated during calls to .Get() if the entry is past the requested TTL .Get() removes the entry from the cache counts a miss and returns not ok

cache := collections.NewLRUCache(5000)
go func() {
    for {
        select {
        // Send cache stats every 5 seconds
        case <-time.Tick(time.Second * 5):
            stats := cache.GetStats()
            metrics.Gauge(metrics.Metric("demo", "cache", "size"), int64(stats.Size), 1)
            metrics.Gauge(metrics.Metric("demo", "cache", "hit"), stats.Hit, 1)
            metrics.Gauge(metrics.Metric("demo", "cache", "miss"), stats.Miss, 1)
        }
    }
}()

cache.Add("key", "value")
value, ok := cache.Get("key")

for _, key := range cache.Keys() {
    value, ok := cache.Get(key)
    if ok {
        fmt.Printf("Key: %+v Value %+v\n", key, value)
    }
}

ExpireCache

ExpireCache is a cache which expires entries only after 2 conditions are met

  1. The Specified TTL has expired
  2. The item has been processed with ExpireCache.Each()

This is an unbounded cache which guaranties each item in the cache has been processed before removal. This cache is useful if you need an unbounded queue, that can also act like an LRU cache.

Every time an item is touched by .Get() or .Set() the duration is updated which ensures items in frequent use stay in the cache. Processing the cache with .Each() can modify the item in the cache without updating the expiration time by using the .Update() method.

The cache can also return statistics which can be used to graph cache usage and size.

NOTE: Because this is an unbounded cache, the user MUST process the cache with .Each() regularly! Else the cache items will never expire and the cache will eventually eat all the memory on the system

// How often the cache is processed
syncInterval := time.Second * 10

// In this example the cache TTL is slightly less than the sync interval
// such that before the first sync; items that where only accessed once
// between sync intervals should expire. This technique is useful if you
// have a long syncInterval and are only interested in keeping items
// that where accessed during the sync cycle
cache := collections.NewExpireCache((syncInterval / 5) * 4)

go func() {
    for {
        select {
        // Sync the cache with the database every 10 seconds
        // Items in the cache will not be expired until this completes without error
        case <-time.Tick(syncInterval):
            // Each() uses FanOut() to run several of these concurrently, in this
            // example we are capped at running 10 concurrently, Use 0 or 1 if you
            // don't need concurrent FanOut
            cache.Each(10, func(key inteface{}, value interface{}) error {
                item := value.(Item)
                return db.ExecuteQuery("insert into tbl (id, field) values (?, ?)",
                    item.Id, item.Field)
            })
        // Periodically send stats about the cache
        case <-time.Tick(time.Second * 5):
            stats := cache.GetStats()
            metrics.Gauge(metrics.Metric("demo", "cache", "size"), int64(stats.Size), 1)
            metrics.Gauge(metrics.Metric("demo", "cache", "hit"), stats.Hit, 1)
            metrics.Gauge(metrics.Metric("demo", "cache", "miss"), stats.Miss, 1)
        }
    }
}()

cache.Add("domain-id", Item{Id: 1, Field: "value"},
item, ok := cache.Get("domain-id")
if ok {
    fmt.Printf("%+v\n", item.(Item))
}

Priority Queue

Provides a Priority Queue implementation as described here

queue := collections.NewPriorityQueue()

queue.Push(&collections.PQItem{
    Value: "thing3",
    Priority: 3,
})

queue.Push(&collections.PQItem{
    Value: "thing1",
    Priority: 1,
})

queue.Push(&collections.PQItem{
    Value: "thing2",
    Priority: 2,
})

// Pops item off the queue according to the priority instead of the Push() order
item := queue.Pop()

fmt.Printf("Item: %s", item.Value.(string))

// Output: Item: thing1

Documentation

Overview

Copyright 2017 Mailgun Technologies Inc

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at 

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at 

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

This work is derived from github.com/golang/groupcache/lru

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at 

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at 

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type CacheItem 

type CacheItem struct {
	Key      Key
	Value    interface{}
	ExpireAt *clock.Time
}

type ExpireCache 

type ExpireCache struct {
	// contains filtered or unexported fields
}

ExpireCache is a cache which expires entries only after 2 conditions are met 1. The Specified TTL has expired 2. The item has been processed with ExpireCache.Each()

This is an unbounded cache which guaranties each item in the cache has been processed before removal. This is different from a LRU cache, as the cache might decide an item needs to be removed (because we hit the cache limit) before the item has been processed.

Every time an item is touched by `Get()` or `Add()` the duration is updated which ensures items in frequent use stay in the cache

Processing can modify the item in the cache without updating the expiration time by using the `Update()` method

The cache can also return statistics which can be used to graph track the size of the cache

NOTE: Because this is an unbounded cache, the user MUST process the cache with `Each()` regularly! Else the cache items will never expire and the cache will eventually eat all the memory on the system

func NewExpireCache 

func NewExpireCache(ttl clock.Duration) *ExpireCache

New creates a new ExpireCache.

func (*ExpireCache) Add 

func (c *ExpireCache) Add(key, value interface{})

Put the key, value and TTL in the cache

func (*ExpireCache) Each 

func (c *ExpireCache) Each(concurrent int, callBack func(key interface{}, value interface{}) error) []error

Processes each item in the cache in a thread safe way, such that the cache can be in use while processing items in the cache

func (*ExpireCache) Get 

func (c *ExpireCache) Get(key interface{}) (interface{}, bool)

Retrieves a key's value from the cache

func (*ExpireCache) GetStats 

func (c *ExpireCache) GetStats() ExpireCacheStats

Retrieve stats about the cache

func (*ExpireCache) Keys 

func (c *ExpireCache) Keys() (keys []interface{})

Get a list of keys at this point in time

func (*ExpireCache) Peek 

func (c *ExpireCache) Peek(key interface{}) (value interface{}, ok bool)

Get the value without updating the expiration

func (*ExpireCache) Size 

func (c *ExpireCache) Size() int64

Returns the number of items in the cache.

func (*ExpireCache) Update 

func (c *ExpireCache) Update(key, value interface{}) error

Update the value in the cache without updating the TTL

type ExpireCacheStats 

type ExpireCacheStats struct {
	Size int64
	Miss int64
	Hit  int64
}

type Key 

type Key interface{}

A Key may be any value that is comparable. See http://golang.org/ref/spec#Comparison_operators

type LRUCache 

type LRUCache struct {
	// MaxEntries is the maximum number of cache entries before
	// an item is evicted. Zero means no limit.
	MaxEntries int

	// OnEvicted optionally specifies a callback function to be
	// executed when an entry is purged from the cache.
	OnEvicted func(key Key, value interface{})
	// contains filtered or unexported fields
}

Cache is an thread safe LRU cache that also supports optional TTL expiration You can use an non thread safe version of this

func NewLRUCache 

func NewLRUCache(maxEntries int) *LRUCache

New creates a new Cache. If maxEntries is zero, the cache has no limit and it's assumed that eviction is done by the caller.

func (*LRUCache) Add 

func (c *LRUCache) Add(key Key, value interface{}) bool

Add or Update a value in the cache, return true if the key already existed

func (*LRUCache) AddWithTTL 

func (c *LRUCache) AddWithTTL(key Key, value interface{}, ttl clock.Duration) bool

Adds a value to the cache with a TTL

func (*LRUCache) Each 

func (c *LRUCache) Each(concurrent int, callBack func(key interface{}, value interface{}) error) []error

Processes each item in the cache in a thread safe way, such that the cache can be in use while processing items in the cache. Processing the cache with `Each()` does not update the expiration or last used.

func (*LRUCache) Get 

func (c *LRUCache) Get(key Key) (value interface{}, ok bool)

Get looks up a key's value from the cache.

func (*LRUCache) Keys 

func (c *LRUCache) Keys() (keys []interface{})

Get a list of keys at this point in time

func (*LRUCache) Map 

func (c *LRUCache) Map(mapping func(item *CacheItem) bool)

Map modifies the cache according to the mapping function, If mapping returns false the item is removed from the cache and `OnEvicted` is called if defined. Map claims exclusive access to the cache; as such concurrent access will block until Map returns.

func (*LRUCache) Peek 

func (c *LRUCache) Peek(key interface{}) (value interface{}, ok bool)

Get the value without updating the expiration or last used or stats

func (*LRUCache) Remove 

func (c *LRUCache) Remove(key Key)

Remove removes the provided key from the cache.

func (*LRUCache) Size 

func (c *LRUCache) Size() int

Len returns the number of items in the cache.

func (*LRUCache) Stats 

func (c *LRUCache) Stats() LRUCacheStats

Returns stats about the current state of the cache

type LRUCacheStats 

type LRUCacheStats struct {
	Size int64
	Miss int64
	Hit  int64
}

Holds stats collected about the cache

type PQItem 

type PQItem struct {
	Value    interface{}
	Priority int // The priority of the item in the queue.
	// contains filtered or unexported fields
}

An PQItem is something we manage in a priority queue.

type PriorityQueue 

type PriorityQueue struct {
	// contains filtered or unexported fields
}

Implements a PriorityQueue

func NewPriorityQueue 

func NewPriorityQueue() *PriorityQueue
Example 
package main

import (
	"fmt"

	"github.com/mailgun/holster/v4/collections"
)

func main() {
	queue := collections.NewPriorityQueue()

	queue.Push(&collections.PQItem{
		Value:    "thing3",
		Priority: 3,
	})

	queue.Push(&collections.PQItem{
		Value:    "thing1",
		Priority: 1,
	})

	queue.Push(&collections.PQItem{
		Value:    "thing2",
		Priority: 2,
	})

	// Pops item off the queue according to the priority instead of the Push() order
	item := queue.Pop()

	fmt.Printf("Item: %s", item.Value.(string))

}

Output:

Item: thing1

func (PriorityQueue) Len 

func (p PriorityQueue) Len() int

func (*PriorityQueue) Peek 

func (p *PriorityQueue) Peek() *PQItem

func (*PriorityQueue) Pop 

func (p *PriorityQueue) Pop() *PQItem

func (*PriorityQueue) Push 

func (p *PriorityQueue) Push(el *PQItem)

func (*PriorityQueue) Remove 

func (p *PriorityQueue) Remove(el *PQItem)

func (*PriorityQueue) Update 

func (p *PriorityQueue) Update(el *PQItem, priority int)

Modifies the priority and value of an Item in the queue.

type TTLMap 

type TTLMap struct {
	// Optionally specifies a callback function to be
	// executed when an entry has expired
	OnExpire func(key string, i interface{})
	// contains filtered or unexported fields
}

func NewTTLMap 

func NewTTLMap(capacity int) *TTLMap

func (*TTLMap) Get 

func (m *TTLMap) Get(key string) (interface{}, bool)

func (*TTLMap) GetInt 

func (m *TTLMap) GetInt(key string) (retval int, found bool, reterr error)

func (*TTLMap) Increment 

func (m *TTLMap) Increment(key string, value, ttlSeconds int) (retval int, reterr error)

func (*TTLMap) Len 

func (m *TTLMap) Len() int

func (*TTLMap) RemoveExpired 

func (m *TTLMap) RemoveExpired(iterations int) int

func (*TTLMap) RemoveLastUsed 

func (m *TTLMap) RemoveLastUsed(iterations int)

func (*TTLMap) Set 

func (m *TTLMap) Set(key string, value interface{}, ttlSeconds int) error

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.