internal

package
v0.6.0 Latest Latest
Warning

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

 Go to latest Published: Oct 29, 2024 License: MIT Imports: 20 Imported by: 0

Documentation

Overview

Package singleflight provides a duplicate function call suppression mechanism.

Index

Constants

View Source 
const (
	NEW int8 = iota
	REMOVE
	UPDATE
	EVICTE
	WAIT
)
View Source 
const (
	LIST_PROBATION uint8 = 1
	LIST_PROTECTED uint8 = 2
	WHEEL_LIST     uint8 = 3
	LIST_WINDOW    uint8 = 4
)
View Source 
const (
	ADMIT_HASHDOS_THRESHOLD      = 6
	HILL_CLIMBER_STEP_DECAY_RATE = 0.98
	HILL_CLIMBER_STEP_PERCENT    = 0.0625
)
View Source 
const BlockBufferSize = 4 * 1024 * 1024

Variables

View Source 
var (
	VersionMismatch    = errors.New("version mismatch")
	RoundedParallelism int
	ShardCount         int
	StripedBufferSize  int
	WriteChanSize      int
	WriteBufferSize    int
)

Functions

func RoundUpPowerOf2 added in v0.4.0 

func RoundUpPowerOf2(v uint32) uint32

RoundUpPowerOf2 is based on https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2.

Types

type Buffer added in v0.4.0 

type Buffer[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Buffer is a circular ring buffer stores the elements being transferred by the producers to the consumer. The monotonically increasing count of reads and writes allow indexing sequentially to the next element location based upon a power-of-two sizing.

The producers race to read the counts, check if there is available capacity, and if so then try once to CAS to the next write count. If the increment is successful then the producer lazily publishes the element. The producer does not retry or block when unsuccessful due to a failed CAS or the buffer being full.

The consumer reads the counts and takes the available elements. The clearing of the elements and the next read count are lazily set.

This implementation is striped to further increase concurrency.

func NewBuffer added in v0.4.0 

func NewBuffer[K comparable, V any]() *Buffer[K, V]

New creates a new lossy Buffer.

func (*Buffer[K, V]) Add added in v0.4.0 

func (b *Buffer[K, V]) Add(n ReadBufItem[K, V]) *PolicyBuffers[K, V]

Add lazily publishes the item to the consumer.

item may be lost due to contention.

func (*Buffer[K, V]) Clear added in v0.4.0 

func (b *Buffer[K, V]) Clear()

Clear clears the lossy Buffer and returns it to the default state.

func (*Buffer[K, V]) Free added in v0.4.0 

func (b *Buffer[K, V]) Free()

Free returns the processed buffer back and also clears it.

type CountMinSketch 

type CountMinSketch struct {
	Table      []uint64
	Additions  uint
	SampleSize uint
	BlockMask  uint
}

func NewCountMinSketch 

func NewCountMinSketch() *CountMinSketch

func (*CountMinSketch) Add 

func (s *CountMinSketch) Add(h uint64) bool

func (*CountMinSketch) Addn added in v0.5.0 

func (s *CountMinSketch) Addn(h uint64, n int)

used in test

func (*CountMinSketch) EnsureCapacity added in v0.3.0 

func (s *CountMinSketch) EnsureCapacity(size uint)

func (*CountMinSketch) Estimate 

func (s *CountMinSketch) Estimate(h uint64) uint

type DataBlock added in v0.2.6 

type DataBlock[V any] struct {
	Type          uint8 // 1: meta&timerwheel, 2: window, 3: probation, 4: protected
	SecondaryType uint8
	CheckSum      uint64
	Index         uint64 // helper filed, usage depends on Type/SecondaryType
	Data          []byte
	// contains filtered or unexported fields
}

func NewBlock added in v0.2.6 

func NewBlock[V any](tp uint8, buffer *bytes.Buffer, blockEncoder *gob.Encoder) *DataBlock[V]

func (*DataBlock[V]) MarkDirty added in v0.3.0 

func (b *DataBlock[V]) MarkDirty()

func (*DataBlock[V]) Save added in v0.3.0 

func (b *DataBlock[V]) Save() error

func (*DataBlock[V]) Write added in v0.3.0 

func (b *DataBlock[V]) Write(item V) (full bool, err error)

type Entry 

type Entry[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewEntry 

func NewEntry[K comparable, V any](key K, value V, cost int64, expire int64) *Entry[K, V]

used in test only

func (*Entry[K, V]) Next 

func (e *Entry[K, V]) Next(listType uint8) *Entry[K, V]

func (*Entry[K, V]) NextExpire added in v0.6.0 

func (e *Entry[K, V]) NextExpire() *Entry[K, V]

func (*Entry[K, V]) NextPolicy added in v0.6.0 

func (e *Entry[K, V]) NextPolicy() *Entry[K, V]

func (*Entry[K, V]) PolicyWeight added in v0.5.0 

func (e *Entry[K, V]) PolicyWeight() int64

func (*Entry[K, V]) Position added in v0.5.0 

func (e *Entry[K, V]) Position() string

func (*Entry[K, V]) Prev 

func (e *Entry[K, V]) Prev(listType uint8) *Entry[K, V]

func (*Entry[K, V]) PrevExpire added in v0.6.0 

func (e *Entry[K, V]) PrevExpire() *Entry[K, V]

func (*Entry[K, V]) PrevPolicy added in v0.6.0 

func (e *Entry[K, V]) PrevPolicy() *Entry[K, V]

func (*Entry[K, V]) Weight added in v0.5.0 

func (e *Entry[K, V]) Weight() int64

type Flag added in v0.5.0 

type Flag struct {
	Flags int8
}

Flag struct uses 8 bits, with each bit representing a boolean value. Currently, 5 bits are used. All bits are read/write in policy only(with policy mutex), so safe to put them together. Bit 1: Indicates if this entry is a root of linked list. Bit 2: Indicates if this entry is on probation. Bit 3: Indicates if this entry is protected. Bit 4: Indicates if this entry is removed from main(SLRU). Bit 5: Indicates if this entry is from NVM. Bit 6: Indicates if this entry is deleted by API. Bit 7: Indicates if this entry is window.

func (*Flag) IsDeleted added in v0.5.0 

func (f *Flag) IsDeleted() bool

func (*Flag) IsFromNVM added in v0.5.0 

func (f *Flag) IsFromNVM() bool

func (*Flag) IsProbation added in v0.5.0 

func (f *Flag) IsProbation() bool

func (*Flag) IsProtected added in v0.5.0 

func (f *Flag) IsProtected() bool

func (*Flag) IsRemoved added in v0.5.0 

func (f *Flag) IsRemoved() bool

func (*Flag) IsRoot added in v0.5.0 

func (f *Flag) IsRoot() bool

func (*Flag) IsWindow added in v0.6.0 

func (f *Flag) IsWindow() bool

func (*Flag) SetDeleted added in v0.5.0 

func (f *Flag) SetDeleted(isDeleted bool)

func (*Flag) SetFromNVM added in v0.5.0 

func (f *Flag) SetFromNVM(isFromNVM bool)

func (*Flag) SetProbation added in v0.5.0 

func (f *Flag) SetProbation(isProbation bool)

func (*Flag) SetProtected added in v0.5.0 

func (f *Flag) SetProtected(isProtected bool)

func (*Flag) SetRemoved added in v0.5.0 

func (f *Flag) SetRemoved(isRemoved bool)

func (*Flag) SetRoot added in v0.5.0 

func (f *Flag) SetRoot(isRoot bool)

func (*Flag) SetWindow added in v0.6.0 

func (f *Flag) SetWindow(isWindow bool)

type Group added in v0.2.0 

type Group[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Group represents a class of work and forms a namespace in which units of work can be executed with duplicate suppression.

func NewGroup added in v0.2.6 

func NewGroup[K comparable, V any]() *Group[K, V]

func (*Group[K, V]) Do added in v0.2.0 

func (g *Group[K, V]) Do(key K, fn func() (V, error)) (v V, err error, shared bool)

Do executes and returns the results of the given function, making sure that only one execution is in-flight for a given key at a time. If a duplicate comes in, the duplicate caller waits for the original to complete and receives the same results. The return value shared indicates whether v was given to multiple callers.

type Hasher 

type Hasher[K comparable] struct {
	// contains filtered or unexported fields
}

func NewHasher 

func NewHasher[K comparable](stringKeyFunc func(K) string) *Hasher[K]

type List 

type List[K comparable, V any] struct {
	// contains filtered or unexported fields
}

List represents a doubly linked list. The zero value for List is an empty list ready to use.

func NewList 

func NewList[K comparable, V any](size uint, listType uint8) *List[K, V]

New returns an initialized list.

func (*List[K, V]) Back 

func (l *List[K, V]) Back() *Entry[K, V]

Back returns the last element of list l or nil if the list is empty.

func (*List[K, V]) Contains 

func (l *List[K, V]) Contains(entry *Entry[K, V]) bool

func (*List[K, V]) Front 

func (l *List[K, V]) Front() *Entry[K, V]

Front returns the first element of list l or nil if the list is empty.

func (*List[K, V]) Len 

func (l *List[K, V]) Len() int

Len returns the number of elements of list l. The complexity is O(1).

func (*List[K, V]) MoveAfter 

func (l *List[K, V]) MoveAfter(e, mark *Entry[K, V])

MoveAfter moves element e to its new position after mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.

func (*List[K, V]) MoveBefore 

func (l *List[K, V]) MoveBefore(e, mark *Entry[K, V])

MoveBefore moves element e to its new position before mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.

func (*List[K, V]) MoveToBack 

func (l *List[K, V]) MoveToBack(e *Entry[K, V])

MoveToBack moves element e to the back of list l. If e is not an element of l, the list is not modified. The element must not be nil.

func (*List[K, V]) MoveToFront 

func (l *List[K, V]) MoveToFront(e *Entry[K, V])

MoveToFront moves element e to the front of list l. If e is not an element of l, the list is not modified. The element must not be nil.

func (*List[K, V]) Persist added in v0.2.6 

func (l *List[K, V]) Persist(writer io.Writer, blockEncoder *gob.Encoder, tp uint8) error

func (*List[K, V]) PopTail 

func (l *List[K, V]) PopTail() *Entry[K, V]

func (*List[K, V]) PushBack added in v0.2.6 

func (l *List[K, V]) PushBack(e *Entry[K, V])

Push push entry to the back of list

func (*List[K, V]) PushFront 

func (l *List[K, V]) PushFront(e *Entry[K, V])

PushFront push entry to list head

func (*List[K, V]) Remove 

func (l *List[K, V]) Remove(e *Entry[K, V])

Remove removes e from l if e is an element of list l. It returns the element value e.Value. The element must not be nil.

func (*List[K, V]) Reset 

func (l *List[K, V]) Reset()

type Loaded added in v0.2.0 

type Loaded[V any] struct {
	Value V
	Cost  int64
	TTL   time.Duration
}

type LoadingStore added in v0.2.0 

type LoadingStore[K comparable, V any] struct {
	*Store[K, V]
	// contains filtered or unexported fields
}

func NewLoadingStore added in v0.2.0 

func NewLoadingStore[K comparable, V any](store *Store[K, V]) *LoadingStore[K, V]

func (*LoadingStore[K, V]) Get added in v0.2.0 

func (s *LoadingStore[K, V]) Get(ctx context.Context, key K) (V, error)

func (*LoadingStore[K, V]) Loader added in v0.2.0 

func (s *LoadingStore[K, V]) Loader(loader func(ctx context.Context, key K) (Loaded[V], error))

type MetaData 

type MetaData[K comparable, V any] struct {
	// contains filtered or unexported fields
}

type NotFound added in v0.3.0 

type NotFound struct{}

func (*NotFound) Error added in v0.3.0 

func (e *NotFound) Error() string

type Pentry added in v0.2.6 

type Pentry[K comparable, V any] struct {
	Key          K
	Value        V
	Weight       int64
	PolicyWeight int64
	Expire       int64
	Frequency    int32
	Flag         Flag
}

entry for persistence

type PolicyBuffers added in v0.4.0 

type PolicyBuffers[K comparable, V any] struct {
	Returned []ReadBufItem[K, V]
}

PolicyBuffers is the set of buffers returned by the lossy buffer.

type RBMutex added in v0.4.0 

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

A RBMutex is a reader biased reader/writer mutual exclusion lock. The lock can be held by an many readers or a single writer. The zero value for a RBMutex is an unlocked mutex.

A RBMutex must not be copied after first use.

RBMutex is based on a modified version of BRAVO (Biased Locking for Reader-Writer Locks) algorithm: https://arxiv.org/pdf/1810.01553.pdf

RBMutex is a specialized mutex for scenarios, such as caches, where the vast majority of locks are acquired by readers and write lock acquire attempts are infrequent. In such scenarios, RBMutex performs better than sync.RWMutex on large multicore machines.

RBMutex extends sync.RWMutex internally and uses it as the "reader bias disabled" fallback, so the same semantics apply. The only noticeable difference is in reader tokens returned from the RLock/RUnlock methods.

func NewRBMutex added in v0.4.0 

func NewRBMutex() *RBMutex

NewRBMutex creates a new RBMutex instance.

func (*RBMutex) Lock added in v0.4.0 

func (mu *RBMutex) Lock()

Lock locks m for writing. If the lock is already locked for reading or writing, Lock blocks until the lock is available.

func (*RBMutex) RLock added in v0.4.0 

func (mu *RBMutex) RLock() *RToken

RLock locks m for reading and returns a reader token. The token must be used in the later RUnlock call.

Should not be used for recursive read locking; a blocked Lock call excludes new readers from acquiring the lock.

func (*RBMutex) RUnlock added in v0.4.0 

func (mu *RBMutex) RUnlock(t *RToken)

RUnlock undoes a single RLock call. A reader token obtained from the RLock call must be provided. RUnlock does not affect other simultaneous readers. A panic is raised if m is not locked for reading on entry to RUnlock.

func (*RBMutex) TryLock added in v0.4.0 

func (mu *RBMutex) TryLock() bool

TryLock tries to lock m for writing without blocking.

func (*RBMutex) TryRLock added in v0.4.0 

func (mu *RBMutex) TryRLock() (bool, *RToken)

TryRLock tries to lock m for reading without blocking. When TryRLock succeeds, it returns true and a reader token. In case of a failure, a false is returned.

func (*RBMutex) Unlock added in v0.4.0 

func (mu *RBMutex) Unlock()

Unlock unlocks m for writing. A panic is raised if m is not locked for writing on entry to Unlock.

As with RWMutex, a locked RBMutex is not associated with a particular goroutine. One goroutine may RLock (Lock) a RBMutex and then arrange for another goroutine to RUnlock (Unlock) it.

type RToken added in v0.4.0 

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

RToken is a reader lock token.

type ReadBufItem 

type ReadBufItem[K comparable, V any] struct {
	// contains filtered or unexported fields
}

type RemoveReason added in v0.1.2 

type RemoveReason uint8
const (
	REMOVED RemoveReason = iota
	EVICTED
	EXPIRED
)

type Result added in v0.2.0 

type Result struct {
	Val    interface{}
	Err    error
	Shared bool
}

Result holds the results of Do, so they can be passed on a channel.

type SecondaryCache added in v0.3.0 

type SecondaryCache[K comparable, V any] interface {
	Get(key K) (value V, cost int64, expire int64, ok bool, err error)
	Set(key K, value V, cost int64, expire int64) error
	Delete(key K) error
	HandleAsyncError(err error)
}

type SecondaryCacheItem added in v0.3.0 

type SecondaryCacheItem[K comparable, V any] struct {
	// contains filtered or unexported fields
}

type Serializer added in v0.3.0 

type Serializer[T any] interface {
	Marshal(v T) ([]byte, error)
	Unmarshal(raw []byte, v *T) error
}

type Shard 

type Shard[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewShard 

func NewShard[K comparable, V any](doorkeeper bool) *Shard[K, V]

type SimpleMapSecondary added in v0.5.0 

type SimpleMapSecondary[K comparable, V any] struct {
	ErrCounter atomic.Uint64

	ErrMode bool
	// contains filtered or unexported fields
}

used in test only

func NewSimpleMapSecondary added in v0.5.0 

func NewSimpleMapSecondary[K comparable, V any]() *SimpleMapSecondary[K, V]

func (*SimpleMapSecondary[K, V]) Delete added in v0.5.0 

func (s *SimpleMapSecondary[K, V]) Delete(key K) error

func (*SimpleMapSecondary[K, V]) Get added in v0.5.0 

func (s *SimpleMapSecondary[K, V]) Get(key K) (value V, cost int64, expire int64, ok bool, err error)

func (*SimpleMapSecondary[K, V]) HandleAsyncError added in v0.5.0 

func (s *SimpleMapSecondary[K, V]) HandleAsyncError(err error)

func (*SimpleMapSecondary[K, V]) Set added in v0.5.0 

func (s *SimpleMapSecondary[K, V]) Set(key K, value V, cost int64, expire int64) error

func (*SimpleMapSecondary[K, V]) SetClock added in v0.5.0 

func (s *SimpleMapSecondary[K, V]) SetClock(clock *clock.Clock)

type Slru 

type Slru[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewSlru 

func NewSlru[K comparable, V any](size uint) *Slru[K, V]

type Stats added in v0.4.1 

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

func (Stats) HitRatio added in v0.4.1 

func (s Stats) HitRatio() float64

func (Stats) Hits added in v0.4.1 

func (s Stats) Hits() uint64

func (Stats) Misses added in v0.4.1 

func (s Stats) Misses() uint64

type Store 

type Store[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewStore 

func NewStore[K comparable, V any](
	maxsize int64, doorkeeper bool, entryPool bool, listener func(key K, value V, reason RemoveReason),
	cost func(v V) int64, secondaryCache SecondaryCache[K, V], workers int, probability float32, stringKeyFunc func(k K) string,
) *Store[K, V]

New returns a new data struct with the specified capacity

func (*Store[K, V]) Close 

func (s *Store[K, V]) Close()

func (*Store[K, V]) DebugInfo added in v0.5.0 

func (s *Store[K, V]) DebugInfo() debugInfo

used for test, only

func (*Store[K, V]) Delete 

func (s *Store[K, V]) Delete(key K)

func (*Store[K, V]) DeleteWithSecondary added in v0.3.0 

func (s *Store[K, V]) DeleteWithSecondary(key K) error

func (*Store[K, V]) EstimatedSize added in v0.4.1 

func (s *Store[K, V]) EstimatedSize() int

func (*Store[K, V]) Get 

func (s *Store[K, V]) Get(key K) (V, bool)

func (*Store[K, V]) GetWithSecodary added in v0.3.0 

func (s *Store[K, V]) GetWithSecodary(key K) (value V, ok bool, err error)

func (*Store[K, V]) Len 

func (s *Store[K, V]) Len() int

func (*Store[K, V]) Persist added in v0.2.6 

func (s *Store[K, V]) Persist(version uint64, writer io.Writer) error

func (*Store[K, V]) Range added in v0.2.4 

func (s *Store[K, V]) Range(f func(key K, value V) bool)

func (*Store[K, V]) RangeEntry added in v0.5.0 

func (s *Store[K, V]) RangeEntry(f func(entry *Entry[K, V]))

used in test

func (*Store[K, V]) Recover added in v0.2.6 

func (s *Store[K, V]) Recover(version uint64, reader io.Reader) error

func (*Store[K, V]) Set 

func (s *Store[K, V]) Set(key K, value V, cost int64, ttl time.Duration) bool

func (*Store[K, V]) Stats added in v0.4.1 

func (s *Store[K, V]) Stats() Stats

func (*Store[K, V]) Wait added in v0.5.0 

func (s *Store[K, V]) Wait()

wait write chan, used in test

type StoreMeta added in v0.2.6 

type StoreMeta struct {
	Version   uint64
	StartNano int64
	Sketch    *CountMinSketch
}

func (*StoreMeta) Persist added in v0.2.6 

func (m *StoreMeta) Persist(writer io.Writer, blockEncoder *gob.Encoder) error

type StringKey added in v0.3.2 

type StringKey interface {
	StringKey() string
}

type TimerWheel 

type TimerWheel[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewTimerWheel 

func NewTimerWheel[K comparable, V any](size uint) *TimerWheel[K, V]

type TinyLfu 

type TinyLfu[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewTinyLfu 

func NewTinyLfu[K comparable, V any](size uint, hasher *Hasher[K]) *TinyLfu[K, V]

func (*TinyLfu[K, V]) Access 

func (t *TinyLfu[K, V]) Access(item ReadBufItem[K, V])

func (*TinyLfu[K, V]) EvictEntries 

func (t *TinyLfu[K, V]) EvictEntries()

func (*TinyLfu[K, V]) Remove 

func (t *TinyLfu[K, V]) Remove(entry *Entry[K, V], callback bool)

func (*TinyLfu[K, V]) Set 

func (t *TinyLfu[K, V]) Set(entry *Entry[K, V])

func (*TinyLfu[K, V]) UpdateCost 

func (t *TinyLfu[K, V]) UpdateCost(entry *Entry[K, V], weightChange int64)

type UnsignedCounter added in v0.4.1 

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

A UnsignedCounter is a unsigned striped int64 counter.

Should be preferred over a single atomically updated int64 counter in high contention scenarios.

A Counter must not be copied after first use.

func NewUnsignedCounter added in v0.4.1 

func NewUnsignedCounter() *UnsignedCounter

UnsignedCounter creates a new UnsignedCounter instance.

func (*UnsignedCounter) Add added in v0.4.1 

func (c *UnsignedCounter) Add(delta uint64)

Add adds the delta to the counter.

func (*UnsignedCounter) Inc added in v0.4.1 

func (c *UnsignedCounter) Inc()

Inc increments the counter by 1.

func (*UnsignedCounter) Reset added in v0.4.1 

func (c *UnsignedCounter) Reset()

Reset resets the counter to zero. This method should only be used when it is known that there are no concurrent modifications of the counter.

func (*UnsignedCounter) Value added in v0.4.1 

func (c *UnsignedCounter) Value() uint64

Value returns the current counter value. The returned value may not include all of the latest operations in presence of concurrent modifications of the counter.

type WriteBufItem 

type WriteBufItem[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Source Files

View all Source files

Directories

Path Synopsis

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.