v2 contracts

[maypok86]

Just random thoughts about new contracts...

[maypok86]

The approximate api of the builder.

type Builder[K comparable, V any] interface {
	// It seems better to separate cost and size after all.
	// In the experience of ristretto and communication with otter users,
	// people do not perceive specifying this with one parameter well.
	//
	// Also, with this api, we will be able to prohibit the simultaneous use of the MaximumSize and Cost functions.
	MaximumSize(maximumSize int) Builder[K, V]
	MaximumCost(maximumCost int) Builder[K, V]
	CollectStats() Builder[K, V]
	InitialCapacity(initialCapacity int) Builder[K, V]
	Cost(costFunc func(key K, value V) uint32) Builder[K, V]
	DeletionListener(deletionListener func(key K, value V, cause DeletionCause)) Builder[K, V]
	// We are slightly reducing the cognitive load on the user.
	TTL(ttl time.Duration) Builder[K, V]
	// It seems that the use of a variable ttl is almost never required and
	// the user should have at least some rule by which he wants to calculate the ttl.
	//
	// In principle, Set(key, value, ttl) can be transferred to Extension.
	//
	// It also becomes more difficult to use it when it is not needed. :)
	VarTTL(ttlFunc func(key K, value V) uint32) Builder[K, V]
	Build() (Cache[K, V], error)
}

func NewBuilder[K comparable, V any]() Builder[K, V] {
	...
}

[maypok86]

type Cache[K comparable, V any] interface {
	Has(key K) bool
	Get(key K) (V, bool)
	Set(key K, value V) bool
	// the existing value?
	// I also want to return the previous value, but then how to take into account the rejection due to the size?
	SetIfAbsent(key K, value V) bool
	Delete(key K)
	DeleteByFunc(f func(key K, value V) bool)
	Range(f func(key K, value V) bool)
	Clear()
	Close()
	Size() int
	Stats() Stats
	Extension() Extension[K, V]
}

[ben-manes]

I'd vote for changing terms from cost to weight for clarity, so it becomes MaximumWeight and Weigher(func) in the builder snippet above. (I just think cost is a more confusing term as be confused with the latency / miss penalty to fetch the item)

TTL is pretty well known term, but what "live" means depends on the implementation. Some use "time since creation" whereas others use "time since last write". Or sometime people will say TTL as the time for the client receiving it, like an http expiry duration header. So I think the acronym could be misinterpreted vs a more generic term like expiration.

Close() is there state requiring a lifecycle termination? That can be fair, just more error prone in my experience when users think of an on-heap cache and discard by GC like any other Map.

[maypok86]

It may be worth stopping returning bool in case of rejections. Then the API will become a little simpler. Still, otter guarantees that it can reject an item only because of the eviction policy, and not as a ristretto because of contention.

type Cache[K comparable, V any] interface {
	Set(key K, value V)
	SetIfAbsent(key K, value V) (V, bool)
}

[maypok86]

I'd vote for changing terms from cost to weight for clarity

It doesn't really matter to me here. It can be replaced with weight.

TTL is pretty well known term, but what "live" means depends on the implementation.

Oh, that's the truth. I have not yet seen any implementation on Go that uses "expire after last access". Except, goburrow, but it explicitly separates this from "expire after create/last write".

But if we separate the different versions by

1. ExpireAfterCreate
2. ExpireAfterWrite
3. ExpireAfterAccess

I need to answer one question. Can these functions be used for a single cache instance? It seems to me that this is absolutely useless, but if there is some kind of use case, then there will be a very unpleasant problem with the expiration policy with a variable ttl. And in fact, a similar problem is very likely to be in LoadingCache, but with Loader.

type Builder[K comparable, V any] interface {
	ExpireAfterCreate(duration time.Duration) Builder[K, V]
	ExpireAfterWrite(duration time.Duration) Builder[K, V]
	ExpireAfterAccess(duration time.Duration) Builder[K, V]
	ExpireAfter(/* what??? */) Builder[K, V]
}

It seems that there is a need to use an interface with several methods. But

1. What if one function is needed? Okay, we can use a structure that implements this interface and make a constructor for it.
2. And if there are two or three? Making implementations for all variants does not look like a good solution, also it is impossible to create an anonymous structure with methods in Go and in the end it will look terrible.

Ideally, we would avoid using the same interface for all three functions.

Could it be something like that?

type Builder[K comparable, V any] interface {
	ExpireAfter(opts ...ExpiryOption[K, V]) Builder[K, V]
}

type ExpiryOption[K comparable, V any] func(*expiry[K, V])

But this again looks doubtful.

Close() is there state requiring a lifecycle termination?

Yes, goroutine is used for the worker.

In general, the use of Close can be avoided using runtime.SetFinalizer. I was thinking about it once and decided that Close is a little better. But it has one big drawback. The user can just forget about it. So perhaps it would be more friendly to just automatically clean up resources. Moreover, it seems that a manual Close call is really required only when you need to understand whether an object is closed or not. Cache doesn't seem to need it.

[ben-manes]

Can these functions be used for a single cache instance?

They shouldn't be. Guava/Caffeine allow it prior to variable support and naivety as it seemed to have little cost, but I'd stop allowing multiple expiration policies if possible. Usually users seem to set both expireAfterAccess and expireAfterWrite to the same fixed value for zero benefit.

It seems that there is a need to use an interface with several methods.

Right, I have an expiry interface with create, update, read methods.

Ideally it would be on the builder for easiest discovery where all of the options funnel into variable expiration. You can see the discussion in https://github.com/ben-manes/caffeine/issues/1499, as users often made mistakes with the interface and of course it was pretty verbose.

If I could start anew then I'd make it convenient and fail at runtime if multiple where selected

Caffeine.newBuilder() // user can chose one 
    .expireAfterCreate(Duration.ofMinutes(5))
    .expireAfterCreate((K key, V value) -> duration)
    .expireAfterWrite(Duration.ofMinutes(5))
    .expireAfterWrite((K key, V value) -> duration)
    .expireAfterAccess(Duration.ofMinutes(5))
    .expireAfterAccess((K key, V value) -> duration)
    .expireAfter(new Expiry...)

For backwards compatibility I went with static factories on the interface so they can do one of,

.expireAfter(Expiry.creating((Key key, Graph graph) -> duration))
.expireAfter(Expiry.writing((Key key, Graph graph) -> duration))
.expireAfter(Expiry.accessing((Key key, Graph graph) -> duration))

They can define their own Expiry as needed, but the create / write / access functions should cover most cases and be less error prone. The existing fixed policies, expireAfterWrite and expireAfterAccess, remain as is using the non-timerwheel logic where both can unfortunately be selected.

Yes, goroutine is used for the worker.

Does that need to be long-lived? I use a state machine to schedule the maintenance worker so only one should be in-flight. This submits a task to an Executor, so users can chose between OS threads, virtual threads, or run it on the calling thread. Is there a good reason to not create a new goroutine each time the maintenance is scheduled instead of reusing it?

I'd avoid finalizers, as at least in Java they are considered a misfeature and are being deprecated for removal. However java offers other options like weak and phantom references that cover the clean up needs better, without penalizing the GC or quirks like object resurrection. Maybe they're cleaner in Go.

[maypok86]

They shouldn't be.

Great, then this simplifies the situation a bit.

.expireAfterCreate(Duration.ofMinutes(5))
.expireAfterCreate((K key, V value) -> duration)

There is a small problem. There is no method overloading in Go and it even makes sense. If we can do without ExpireAfter, then ideally we would come up with a good name for ExpireAfter* with a lambda.

What about this?

1. VarExpireAfter*
2. ExpireAfter*Func

Does that need to be long-lived?

Actually, no, that's largely why I asked about removing goroutines, but most likely I didn't formulate it very clearly.

It would be cool to abandon this, but so far I don't understand the benefits for users from this, unlike adding LoadingCache and increasing the hit ratio. Also, at the moment, a ticker in the background is being used to get the time faster. It also needs to be stopped.

In fact, finalizers are incredibly often used when working with cgo. Moreover, there are simply no other good ways to clean up resources other than finalizers and Close in Go.

[maypok86]

Yeah, LoadingCache is really complicated.

type LoadingCache[K comparable, V any] interface {
	...
	Get(ctx context.Context, key K) (V, error)
	BulkGet(ctx context.Context, keys []K) (map[K]V, error)
	// extension?
	Extension() LoadingExtension[K, V]
}

type LoadingExtension[K comparable, V any] interface {
	GetQuietly(ctx context.Context, key K) (V, error)
	GetEntry(ctx context.Context, key K) (Entry[K, V], error)
	GetEntryQuietly(ctx context.Context, key K) (Entry[K, V], error)
}

// :(

type SingleLoader[K comparable, V any] interface {
	Load(ctx context.Context, key K) (V, error)
}

type BulkLoader[K comparable, V any] interface {
	BulkLoad(ctx context.Context, keys []K) (map[K]V, error)
}

type SingleBulkLoader[K comparable, V any] interface {
	SingleLoader[K, V]
	BulkLoader[K, V]
}

type Builder[K comparable, V any] interface {
	// and we are trying to cast to the BulkLoader inside,
	// otherwise we use the standard implementation of BulkLoad.
	BuildLoading(loader SingleLoader[K, V]) (LoadingCache[K, V], error)
}

[ben-manes]

ExpireAfter*Func

This seems more obvious, not sure about Go idioms if that is a common naming style.

LoadingCache is really complicated.

Unfortunately Go api design is outside my expertise. I was able to use Java features to layer it in a way to reduce user complexity, e.g. using default methods. The context wasn't needed since Java typically is paired with dependency injection with request-scoped providers, e.g. to get the logged in user bound to that thread. If not, then the user likely will use a loading get(key, func) instead of a LoadingCache where they'll only miss out on the refreshAfterWrite feature. I don't know if that context param makes automatic refreshing incompatible with Go idioms. If so, then you might prefer instead adding a loading get and getAll to the Cache interface?

[maypok86]

The main problem is that context.Context is often used for the following things:

1. Timeout
2. Storage of various meta-information. Fields for logging and tracing, etc.

Since it changes from request to request, it should also be used in loader.

And the idea of casting the interface is actually often used in the standard library. For example, here.

I need to think about it, but at least the loss of timeouts, spans and information in the logs look very critical.

[ben-manes]

It sounds like LoadingCache might not be a good fit for now, but putting loading methods on the Cache interface would work nicely. If later the LoadingCache is helpful then you can offer that as an API improvement without much new functionality. From gpt it might look like,

func GetIfPresent(key K) (V, bool)
func Get(ctx context.Context, key K, mappingFunction func(K) V) (V, error)
func GetAll(ctx context.Context, keys []K, mappingFunction func([]K) map[K]V) (map[K]V, error)

[proost]

if Extension method and LoadingCache methods are coexist on the Cache interface, bit confused to me. Because why GetQuietly, GetEntry, GetEntryQuitely methods can't be on the Cache interface. I think, Loader as a parameter in Builder method is not bad idea. Some library alread did.

[maypok86]

To be honest, I didn't really understand :(.

Why do I need to specify the loader every time I use the method?

type (
	LoaderFunc[K comparable, V any]     func(ctx context.Context, key K) (V, error)
	BulkLoaderFunc[K comparable, V any] func(ctx context.Context, keys []K) (map[K]V, error)
)

type Cache[K comparable, V any] interface {
	Has(key K) bool
	Get(key K) (V, bool)
	BulkGet(keys []K) (map[K]V, bool)
	// We are trying to use the loader passed when creating the cache instance,
	// if nothing was passed to Load.
	// But what if the loader has not been passed anywhere?
	Load(ctx context.Context, key K, loader ...LoaderFunc[K, V]) (V, error)
	BulkLoad(ctx context.Context, keys []K, bulkLoader ...BulkLoaderFunc[K, V]) (map[K]V, error)
}

Or we can even use a more canonical `Option'. Unfortunately, this is one allocation per request.

Load(ctx context.Context, key K, opts ...LoadOption[K, V]) (V, error)
BulkLoad(ctx context.Context, keys []K, opts ...LoadOption[K, V]) (map[K]V, error)

But what to do with the methods in the Extension is not very clear. It seems they don't need to have a Load version. And we can leave everything as it is.

It is also interesting what needs to be done to allow the use of explicit ttl. We can hide this in the Extension, the problem is that when creating a cache, we need to know that a individual ttl will be used for each entry. Of course, we can ask to specify ExpireAfter*Func, but this is not intuitive at all.

@proost for me, the methods in Extension allow bypassing the standard cache API (getting a full entry, getting data without updating statistics and eviction policy, explicitly passing ttl).

For the user, Load only automatically downloads data from an external source if nothing is found.

Although with the integration of the API, the line is really blurred.

[maypok86]

Also, if we use Get and Load in the same type, it may be better to use a more common Option when creating a cache instead of a builder. The only thing I don't like about options is the requirement to specify useless generic types.

WithMaximumSize[K, V](1000)

I used the builder to create a more typed cache and add LoadingCache more easily, but it turned out to be difficult to add new features :( (you need to add the same function in a lot of places).

[rueian]

It may be worth stopping returning bool in case of rejections. Then the API will become a little simpler. Still, otter guarantees that it can reject an item only because of the eviction policy.

When I was trying to make SetIfAbsent(key K, value V) return (V, bool), the rejection of exceeding the MaxAvailableCost blocked me. There is also a potential issue related to the rejection if users want to implement their own loading cache like me.

In terms of the API SetIfAbsent(key K, value V) (V, bool), I think users would only expect the following two return cases:

1. (newly setted V, true)
2. (existing V, false)

That is, if the second returned value is false, users will expect the first returned value to be the V already in the cache. However, in case of rejection, there can be no such V in the cache and users have no way to tell.

If we want to keep the rejection behavior, I think a slightly complicated API is needed, such as SetIfAbsent(key K, value V) (V, int) where some specific int can be used to indicate rejection.

[rueian]

To be honest, I didn't really understand :(.

Why do I need to specify the loader every time I use the method?

I guess, it has something to do with developer experience. Many times, it is hard to prepare the loader function at initialization. Or the loader function may need some conditional dependencies that can't be determined at initialization.

[ben-manes]

That is, if the second returned value is false, users will expect the first returned value to be the V already in the cache. However, in case of rejection, there can be no such V in the cache and users have no way to tell.

Since the entry hangs around until GC'd anyway, it didn't seem too awful to me to handle the rejection within the eviction policy logic instead of at the map insertion. The add / update tasks shuffle an entry that is too large for immediate eviction to avoid flushing the cache. Then it is handled however the entry was added (load, put, replace), its linearizable, and simple to understand. I think the only immediate rejection that I do is for AsyncCache when inserting a completed and failed future value, but that's quite minor since it has the callback handler otherwise if it fails after insert.

[maypok86]

In terms of the API SetIfAbsent(key K, value V) (V, bool), I think users would only expect the following two return cases:

@rueian Yes, it seems like a good solution.

I guess, it has something to do with developer experience. Many times, it is hard to prepare the loader function at initialization. Or the loader function may need some conditional dependencies that can't be determined at initialization.

This is true, but I was referring specifically to the requirement of specifying a loader.

That is, instead of

Load(ctx context.Context, key K, loader LoaderFunc[K, V]) (V, error)

it seems better to optionally handle loader

Load(ctx context.Context, key K, loader ...LoaderFunc[K, V]) (V, error)

But it's very likely a special effect from ChatGPT. But something bothers me much more. What should we do if loader was not passed either in the builder and explicitly in the function? It seems easiest to just return some kind of predefined error.

[maypok86]

About LoadingCache

I've been thinking about LoadingCache for a long time and here's a little observation.

type LoadingCache[K comparable, V any] interface {
	...
	Get(ctx context.Context, key K) (V, error)
	BulkGet(ctx context.Context, keys []K) (map[K]V, error)
	// extension?
	Extension() LoadingExtension[K, V]
}

type LoadingExtension[K comparable, V any] interface {
	GetQuietly(ctx context.Context, key K) (V, error)
	GetEntry(ctx context.Context, key K) (Entry[K, V], error)
	GetEntryQuietly(ctx context.Context, key K) (Entry[K, V], error)
}

For me, the main problem with the API that originally came to my mind is LoadingExtension, but it looks like it's just not needed. GetQuietly/GetEntryQuietly are just getting from the hash table, they don't need a loader. Loader is needed exclusively for GetEntry, but in principle it can be removed. I added it only as a small syntactic sugar. Other methods in Extension are very unlikely to require using loader internally.

Separate LoadingCache vs Cache with Load methods

Perhaps the main dilemma.

It seems that both options have their pros and cons.

LoadingCache

Pros:

• A more general architecture
• It's easier to add AsyncCache (Promise/Future style)

Cons:

• It is unclear how to create it if the user has not passed the loader in the builder (Do we really need an explicit loader in the Load methods?). Of course, we can create it, but then the user will be required to pass the loader in each request.
• It can become difficult to maintain and use when adding features.

In fact, I've never seen anything like Promise/Future used in Go (except for the very rare return of channels), but it would be cool to be able to do something like that. Only I also haven't seen any issue about it in other caches, but okay.

Cache with Load methods

Pros:

• Easy to implement and maintain

Cons:

• It is unclear how to add AsyncCache

Options

Could it really be possible to add options to various methods instead of explicitly passing loader (it will also be possible to add additional features with ease)? This is a canonical method that is used in many projects and is well known in Go. Also, additional allocation for options can be avoided using sync.Pool.

type Option[K comparable, V any] func(*options[K, V])

type Cache[K comparable, V any] interface {
    Get(key K, opts ...Option[K, V]) (V, ok)
    Load(ctx context.Context, key K, opts ...Option[K, V]) (V, error)
}

Explicit TTL

It is unclear what to do with this...

What is the best way to allow explicit ttl setting for each entry? The main problem is that otter needs to know when creating that the ttl for each entry may be different, but the user still does not have a function for calculating it. We can add this to the Extension or just take it from the options, but how should the user create a cache in this case?

Builder vs Options

In Go, people use options more often than builders, although I don't like how generic options look. How do you like these two alternatives?

cache, err := otter.NewCache[int, int](
	WithMaximumSize[int, int](1000),
	WithExpireAfterWrite[int, int](time.Hour),
	WithCollectStats[int, int](),
)

vs

cache, err := otter.NewBuilder[int, int]().
	MaximumSize(1000).
	ExpireAfterWrite(time.Hour).
	CollectStats().
	Build()

I still think the builder is a little more beautiful.

[maypok86]

In the case of LoadingCache, I'm still leaning towards something like this.

cache, err := otter.NewBuilder[int, int]().
	MaximumSize(1000).
        ExpireAfterWrite(time.Hour).
	CollectStats().
	Loader(func(ctx context.Context, key K) (V, error) {
		...
        }).
	BulkLoader(func(ctx context.Context, keys []K) (map[K]V, error) {
		...
        }).
	BuildLoading()

[ben-manes]

JCache is an alternative standardized Java api which I don't like, but might be a helpful reference. They have a more powerful loader called EntryProcessor which computes around the entry for CRUD and metadata changes. Here's a tutorial from one of the implementers. They allow for the cache to be built with a loader and writer, so the api is just get and put methods. It makes the caller not know if the data was fetched (null means absent locally or in system of record?). They also view a cache as very distinct from a map, whereas I think devs know their core collection interfaces very well so its intuitive to extend that concept. Anyway, API design is all opinion and maybe you'll prefer theirs.

[maypok86]

JCache is an alternative standardized Java api

To be honest, it looks overloaded.

Actually, I quite like the alternative with options, but I'm still not completely sure about this decision and I want to hear someone else's opinion.

Of course, this approach has drawbacks, but in my opinion it looks quite good. The only thing that bothers me a little is the use of sync.Pool for Get operations, but

1. The use of options is very rarely required.
2. There is often a fastpath.
3. sync.Pool is a thread-local storage after all. There should not be a significant decrease in throughput (there should definitely be more than 75+ million qps, but this should be checked).

Option

type GetOption[K comparable, V any] func(*getOptions[K, V])

func WithRecordStats[K comparable, V any](recordStats bool) GetOption[K, V] {
	return func(o *getOptions[K, V]) {
		o.recordStats = recordStats
	}
}

func WithQuietly[K comparable, V any]() GetOption[K, V] {
	return func(o *getOptions[K, V]) {
		o.isQuietly = true
	}
}

func WithLoader[K comparable, V any](loader func(ctx context.Context, key K) (V, error)) GetOption[K, V] {
	return func(o *getOptions) {
		o.loader = loader
	}
}

type SetOption[K comparable, V any] func(*setOptions[K, V])

func WithTTL[K comparable, V any](duration time.Duration) SetOption[K, V] {
	return func(so *setOptions[K, V]) {
		so.ttl = duration
	}
}

Cache

type basicCache[K comparable, V any] interface {
	Set(key K, value V, opts ...SetOption[K, V])
	SetIfAbsent(key K, value V, opts ...SetOption[K, V]) (V, bool)
	Delete(key K)
	DeleteByFunc(f func(key K, value V) bool)
	Range(f func(key K, value V) bool)
	Clear()
	Size() int
	Stats() Stats
}

type Cache[K comparable, V any] interface {
	basicCache[K, V]
	Has(key K, opts ...GetOption[K, V]) bool
	Get(key K, opts ...GetOption[K, V]) (V, bool)
	GetEntry(key K, opts ...GetOption[K, V]) (Entry[K, V], bool)
	BulkGet(keys []K, opts ...GetOption[K, V]) (map[K]V, bool)
}

type LoadingCache[K comparable, V any] interface {
	basicCache[K, V]
	Get(ctx context.Context, key K, opts ...GetOption[K, V]) (V, error)
	GetEntry(ctx context.Context, key K, opts ...GetOption[K, V]) (Entry[K, V], error)
	BulkGet(ctx context.Context, key K, opts ...GetOption[K, V]) (map[K]V, error)
}

Builder

type Builder[K comparable, V any] interface {
	MaximumSize(maximumSize int) Builder[K, V]
	MaximumWeight(maximumWeight int) Builder[K, V]
	CollectStats() Builder[K, V]
	InitialCapacity(initialCapacity int) Builder[K, V]
	Weigher(weigher func(key K, value V) uint32) Builder[K, V]
	DeletionListener(deletionListener func(key K, value V, cause DeletionCause)) Builder[K, V]
	ExpireAfterCreate(duration time.Duration) Builder[K, V]
	ExplicitExpireAfterCreate() Builder[K, V]
	ExpireAfterWrite(duration time.Duration) Builder[K, V]
	ExplicitExpireAfterWrite() Builder[K, V]
	ExpireAfterAccess(duration time.Duration) Builder[K, V]
	ExplicitExpireAfterAccess() Builder[K, V]
	Loader(loader func(ctx context.Context, key K) (V, error)) Builder[K, V]
	BulkLoader(bulkLoader func(ctx context.Context, keys []K) (map[K]V, error)) Builder[K, V]
	Build() (Cache[K, V], error)
	BuildLoading() (LoadingCache[K, V], error)
}

Examples

// get quietly
value, ok := cache.Get(key, otter.WithQuietly[K, V]())

// explicit ttl
cache, err := otter.NewBuilder[int, int]().
	MaximumSize(1000).
	ExplicitExpireAfterWrite().
	CollectStats().
	Build()
...
cache.Set(key, value, otter.WithTTL[int, int](time.Hour))

// loader
loader := ...

cache.Get(ctx, key, otter.WithLoader(loader))

[rueian]

The main problem is that otter needs to know when creating that the ttl for each entry may be different, but the user still does not have a function for calculating it. We can add this to the Extension or just take it from the options

How about letting the loader return TTL as well? I think, in many cases, TTL can only be known when loading the entry.

Loader(loader func(ctx context.Context, key K) (V, time.Duration, error)) Builder[K, V]
BulkLoader(bulkLoader func(ctx context.Context, keys []K) (map[K]WithTTL[V], error)) Builder[K, V]

[maypok86]

Oh, I can hardly imagine cases in which the ttl is not known in advance. It seems that in such cases, network requests are not needed and such a function in the builder is enough.

type Builder[K comparable, V any] interface {
    ExpireAfterCreateFunc(f func(key K, value V) time.Duration) Builder[K, V]
}

And when the ttl is returned in the loader, it is unlikely that the user will understand what needs to be returned as ttl there if it is not used.

[maypok86]

Okay, it seems that such an api should be good enough. So I can start developing.)

[element-of-surprise]

Was just reading this thread and saw that you want to go with "Go options" style, but don't want to pay the cost in allocations.

You can allocate the options on the stack in basically the same manner and save the allocation. Might fit your use case, might not, but threw up an example for you: https://go.dev/play/p/_CuzLs19qR-

Happy coding.

[maypok86]

Haha, it really works. I tried to allocate on the stack and pass a pointer, but it leaked onto the heap and I didn't try to fix the escape analysis decision somehow.

Thank you very much! I have almost no free time for otter right now, but I hope there will be more of it later and I will release v2 anyway. :(

[element-of-surprise]

Trick I came up a while ago. Was working on something where I spent so much time getting rid of allocations, allocating the options seemed a bad idea. And I get the time thing, have a lot of that problem. Cheers!

[ben-manes]

sturdyc might be a helpful reference. It has loading, request coalescing (“buffering”), fallback caching (“passthrough”), and negative caching ("non-existent") but lacks good eviction/expiration. Their internal inFlight is a future and the missing record is an optional, which is how caffeine lets callers do these. Since that’s not idiomatic in go, their api does seem nice (as a non-go developer).

[maypok86]

Thoughts about Otter v2

Disclaimer: I'm sorry for such a long message. I have noted questionable (relatively) points with ⚠️. Comments will be very helpful.

Basic concepts and features

I would like to achieve the following goals in v2:

• Make the API as intuitive as possible.
• Try to remove areas that generate an increased cognitive load on the user, or at least reduce this load.
• Make simple things as simple as possible and allow complex things to be done.
• Hide advanced functionality to keep the main API minimalistic.
• Add tools for custom collection of cache statistics.
• Add tools to protect against cache stampedes (loading, refreshing).

Builder vs Functional options

Functional options are much more common in Go than builder and are considered more canonical by many people, but I absolutely don't like how they look with generics.

Functional options

cache, err := otter.New[string, string](100,
    WithCollectStats[string, string](),
    WithTTL[string, string](time.Hour),
    WithInitialCapacity[string, string](100),
)

vs

Builder

cache, err := otter.MustBuilder[string, string](100).
    CollectStats().
    TTL(time.Hour).
    InitialCapacity(100).
    Build()

So for now, I'm still decided to use the builder to construct the cache. ⚠️

Capacity

The user is obliged to immediately specify the cache capacity in the builder now. After that, he can also specify the function of calculating the cost of the item. The sum of all costs <= capacity specified in the builder. By default, the cost of any item is 1.

Now the API looks like this.

cache, err := otter.MustBuilder[string, string](int(10_000_000)).
    Cost(func(key string, value string) uint32 {
        return uint32(len(key) + len(value))
    }).
    InitialCapacity(int(1000)).
    Build()

It should become something like that.

A cache that specifies the capacity in the number of items.

cache, err := otter.NewBuilder[string, string]().
    MaximumSize(uint64(10_000)).
    Build()

A cache that specifies the capacity in the maximum sum of entry weights.

cache, err := otter.NewBuilder[string, string]().
    MaximumWeight(uint64(10_000_000)).
    Weigher(func(key string, value string) uint32 {
        return uint32(len(key) + len(value))
    }).
    InitialCapacity(int(1000)).
    Build()

• Rename cost to weight, since cost is often used in the context of latency / miss penalty.
• Separate eviction based on the number of items from eviction based on weight, since users often specify a function that always returns 1 in the builder. Because of this, otter cannot fully optimize the node size. It will also allow otter to create a cache without an eviction policy.
• Changing the type of maximumSize and maximumWeight from int to uint64 for greater safety. Unfortunately, I'm not completely sure that it's worth doing this. ⚠️
• Keep the initialCapacity type equal to int (preallocating the hash table, etc.). ⚠️
• I don't like that maximumSize and initialCapacity look different, although they are very similar, but maybe there is nothing wrong with that. ⚠️

DeletionListener

The user may want to do something when deleting an entry. Now it's implemented like this:

// DeletionCause the cause why a cached entry was deleted.
type DeletionCause uint8

const (
    // Explicit the entry was manually deleted by the user.
    Explicit DeletionCause = iota
    // Replaced the entry itself was not actually deleted, but its value was replaced by the user.
    Replaced
    // Size the entry was evicted due to size constraints.
    Size
    // Expired the entry's expiration timestamp has passed.
    Expired
)

type Builder[K comparable, V any] interface {
    DeletionListener(deletionListener func(key K, value V, cause DeletionCause)) Builder[K, V]
}

I like that such an API allows the user not to use a huge number of callbacks, but the user has to carefully choose the causes he needs. From what I've seen, in most cases the user is only interested in "was the entry automatically deleted or not?". So it might be worth adding such a method:

func (dc DeletionCause) WasEvicted() bool {
    switch dc {
    case Size, Expired:
        return true
    default:
        return false
    }
}

Stats

Currently, the user cannot specify a custom implementation of the statistics collector in the builder. He can only get a snapshot of the statistics from the cache.

type Stats interface {
    Hits() int64
    Misses() int64
    Ratio() float64
    RejectedSets() int64
    EvictedCount() int64
    EvictedWeight() int64
}

...

cache, err := otter.MustBuilder[string, string](10_000).
    CollectStats().
    Build()

stats := cache.Stats()

I think this API option is good.

type Stats interface {
    Hits() uint64
    Misses() uint64
    HitRatio() float64
    MissRatio() float64
    RejectedSets() uint64
    Evictions() uint64
    EvictionWeight() uint64
}

// general contract
type StatsCollector interface {
    CollectHits(count int)
    CollectMisses(count int)
    CollectEviction(weight uint32, cause DeletionCause)
    Snapshot() Stats
}

// optional
type LoadingStatsCollector interface {
    CollectLoadSuccess(loadDuration time.Duration)
    CollectLoadFailure(loadDuration time.Duration)
}

type Builder[K comparable, V any] interface {
    // if the collectors are not specified, then we use the default one.
    // if one collector is specified, then we use it.
    // if more than one collector is specified, then we return an error.
    CollectStats(statsCollector ...StatsCollector) Builder[K, V]
}

...

// basic usage example
cache, err := otter.NewBuilder[string, string]().
    MaximumSize(10_000).
    // enable the stats collector with concurrent counters
    CollectStats().
    Build()

// with custom collector
prometheusAdapter := ...
cache, err := otter.NewBuilder[string, string]().
    MaximumSize(10_000).
    CollectStats(prometheusAdapter).
    Build()

It may be worth allowing multiple collectors to be specified or not requiring the implementation of a Snapshot... ⚠️

I really like the API more obvious to the user.

type Builder[K comparable, V any] interface {
    CollectStats(statsCollector StatsCollector) Builder[K, V]
}

// usage example
cache, err := otter.NewBuilder[string, string]().
    MaximumSize(10_000).
    CollectStats(otter.NewStatsCounter()).
    Build()

Close

Ideally, I would like the experience of using the in-memory on-heap cache to coincide as much as possible with the use of hashmaps, but since otter uses background goroutines, otter has to have the Close method in its API.

It would be great to get rid of this method, but the options for achieving this are very unpleasant.

• Otter won't be able to use runtime.SetFinalizer will fail, as it simply won't start due to references from goroutines.
• We can try to get rid of background goroutines and switch to finite state machine-based scheduling, but I don't want to suffer so much because of Close :).

So I guess I'll leave Close in place for now and then maybe delete its implementation and mark it as a deprecated method. ⚠️

Expiration

Almost all cache libraries in Go allow you to specify TTL for entries, but all have problems:

• Many don't have an expiration policy at all and delete expired entries only after accessing them. (Not an otter case)
• It's unclear exactly how TTL is reset. For example, some libraries don't update TTL during updates, which may not be obvious to the user. Or when tokens expire, you usually need to update the TTL even after reading the token from the cache. (otter is able to update the TTL only after writing)

It is proposed to switch from the term TTL to ExpiresAfter and add methods like:

type Builder[K comparable, V any] interface {
    ExpireAfterCreate(duration time.Duration) Builder[K, V]
    // it is useful if the ttl is specified in the http header
    // or to simulate a probabilistic early expiration.
    ExpireAfterCreateFunc(f func(key K, value V) time.Duration) Builder[K, V]
    // write = create + update
    ExpireAfterWrite(duration time.Duration) Builder[K, V]
    ExpireAfterWriteFunc(f func(key K, value V) time.Duration) Builder[K, V]
    // access = read + write
    ExpireAfterAccess(duration time.Duration) Builder[K, V]
    ExpireAfterAccessFunc(f func(key K, value V) time.Duration) Builder[K, V]
}

The user can select only one of the expiration methods.

In the first iteration, it's planned to add expiration only for create, write and access, but I'm very confused that then users may need separate features for read and `update'. As a result, the expiration API in the builder will turn into an absolute mess.

We can try to do something like this based on chaining.

type Builder[K comparable, V any] interface {
	ExpireAfter() ExpireAfterBuilder[K, V]
}

type ExpireAfterBuilder[K comparable, V any] interface {
	Create(duration time.Duration) Builder[K, V]
	CreateFunc(f func(key K, value V) time.Duration) Builder[K, V]
	Write(duration time.Duration) Builder[K, V]
	WriteFunc(f func(key K, value V) time.Duration) Builder[K, V]
	Access(duration time.Duration) Builder[K, V]
	AccessFunc(f func(key K, value V) time.Duration) Builder[K, V]
	Read(duration time.Duration) Builder[K, V]
	ReadFunc(f func(key K, value V) time.Duration) Builder[K, V]
	Update(duration time.Duration) Builder[K, V]
	UpdateFunc(f func(key K, value V) time.Duration) Builder[K, V]
}

But I have a strong desire to force users to pass the function always ⚠️

type Builder[K comparable, V any] interface {
	ExpireAfter() ExpireAfterBuilder[K, V]
}

type ExpireAfterBuilder[K comparable, V any] interface {
	Create(f func(key K, value V) time.Duration) Builder[K, V]
	Write(f func(key K, value V) time.Duration) Builder[K, V]
	Access(f func(key K, value V) time.Duration) Builder[K, V]
	Read(f func(key K, value V) time.Duration) Builder[K, V]
	Update(f func(key K, value V) time.Duration) Builder[K, V]
}

...

// usage example
cache, err := otter.NewBuilder[string, string]().
    MaximumWeight(10_000_000).
    Weigher(func(key string, value string) uint32 {
        return uint32(len(key) + len(value))
    }).
    CollectStats(prometheusAdapter).
    ExpireAfter().Write(func(key string, value string) time.Duration {
        return time.Hour
    }).
    Build()

P.S. We can still do something like this. Maybe it's even better than the rest. Anyway, I like it better :).

type ExpiryStrategy uint32

const (
    ExpireAfterCreate ExpiryStrategy = iota
    ExpireAfterWrite
    ExpireAfterAccess
    ExpireAfterRead
    ExpireAfterUpdate
)

type Builder[K comparable, V any] interface {
    Expire(strategy ExpiryStrategy, duration time.Duration) Builder[K, V]
    ExpireFunc(strategy ExpiryStrategy, f func(key K, value V) time.Duration) Builder[K, V]
}
...

// usage example
cache, err := otter.NewBuilder[string, string]().
    MaximumSize(10_000).
    Expire(otter.ExpireAfterWrite, time.Hour).
    Build()

Loader

The main innovation of v2 should be the ability to specify a loader, which will allow the user to receive an entry from a slow resource only once, and not send several identical requests. This usually greatly improves the tail latency.

There are several libraries in Go that allow the user to specify loaders, but only to get one entry. But usually requests are made in batches and the user wants to be able to receive a batch immediately.

This is what a typical loader that libraries ask for looks like:

func(key K) (V, error) {

}

Some notes about the wishlist:

• The loader must use context to store various additional information about the original request.
• I would like to allow the user to implement only one of the loaders (one or bulk).
• Most likely, we will need to be able to optionally implement additional methods for the loader in the future. (reload to reload, refresh to asynchronously update the entry).
• I really want to try to get another one from one method (one = bulk([]K{key}), bulk = sequental (or with goroutine pool) one(keys[i])), but it seems better to require the user to implement the loader always. In this case, no one better than the user will be able to know how to get the data better (it can be especially painful when trying to guess the bulk).
• Sometimes the user will want to use a closure for the loader, since he won't know all the data when initializing the cache.
• Based on this, I decided that the loader should be asked to be specified in the cache method, and the loader should be made an interface. We can also add auxiliary types to simplify the user's life.

package otter

import "context"

type Loader[K comparable, V any] interface {
    Load(ctx context.Context, key K) (V, error)
}

type LoaderFunc[K comparable, V any] func(ctx context.Context, key K) (V, error)

func (lf LoaderFunc[K, V]) Load(ctx context.Context, key K) (V, error) {
    return lf(ctx, key)
}

type BulkLoader[K comparable, V any] interface {
    BulkLoad(ctx context.Context, keys []K) (map[K]V, error)
}

type BulkLoaderFunc[K comparable, V any] func(ctx context.Context, keys []K) (map[K]V, error)

func (blf BulkLoaderFunc[K, V]) BulkLoad(ctx context.Context, keys []K) (map[K]V, error) {
    return blf(ctx, keys)
}

type Cache[K comparable, V any] interface {
    Load(ctx context.Context, loader Loader[K, V], key K) (V, error)
    BulkLoad(ctx context.Context, bulkLoader BulkLoader[K, V], keys []K) (map[K]V, error)
}

It's expected that the loader will be implemented once during cache initialization, but the user still has the ability to change the behavior using closures.

P.S. I still decided to abandon the implementation of the loader via Compute. Yes, the cache becomes non-linearizable, but there will be many other delays for the in-memory cache that should hide this. I will only need to provide for the case of a race between load and deletion. It seems that this is the only case that can bother users. Interestingly, no one is doing this in Go now and I haven't heard any complaints.

// goroutine 1
loader := func(ctx context.Context, key string) (string, error) {
    return db.Get(ctx, key)
}
value, err := cache.Load(ctx, loader, key1)

...

// goroutine 2
db.Update(key1)
cache.Delete(key1)

It's expected that there will be no entry with key1 in the cache, but there is a high probability that the entry in the cache will remain with a naive implementation using singleflight.

Logger

When calling the loader and using other future features, sometimes the user will need to log various errors, so a contract for the logger is needed. It is supposed to use the slog API, but with context. The user can simply ignore the context when implementing the logger.

type Logger interface {
    Warn(ctx context.Context, msg string, args ...any)
    Error(ctx context.Context, msg string, args ...any)
}

type Builder[K comparable, V any] interface {
    Logger(logger Logger) Builder[K, V]
}

Which logger should I use by default? I suspect that it's better to make at least one based on slog. ⚠️

Extension && Map

Sometimes it may happen that the user cannot solve his problem using the available methods. In this case, Extension and Map should come to his aid.

• Extension is a set of hack functions that allow the user to get low-level access to cache functions (eviction policies, expiration, etc.).
• Map is a set of functions that allows the user to use the cache as a map.

Also, these structures will allow us to hide a huge set of functions from users, otherwise the cache API will become simply huge.

So far, it's supposed to do something like this.

type Cache[K comparable, V any] interface {
    AsMap() Map[K, V]
    Extension() Extension[K, V]
}

type Map[K comparable, V any] interface {
    SetIfAbsent(key K, value V) (V, bool)
    DeleteFunc(f func(key K, value V) bool)
    Range(f func(key K, value V) bool)
}

type Extension[K comparable, V any] interface {
    GetEntry(key K) (Entry[K, V], bool)
    GetQuietly(key K) (V, bool)
    GetEntryQuietly(key K) (Entry[K, V], bool)
    Expiry() ExpiryExtension[K, V]
    Eviction() EvictionExtension[K, V]
}

// immutable
type Entry[K comparable, V any] interface {
    Key() K
    Value() V
    Weight() uint32
    ExpiresAt() int64
    ExpiresAfter() time.Duration
    HasExpired() bool
}

type ExpiryExtension[K comparable, V any] interface {
    // It's useful if the user cannot use the function to dynamically calculate the TTL.
    Set(key K, value V, duration time.Duration) (V, bool)
    SetIfAbsent(key K, value V, duration time.Duration) (V, bool)
    // it should help those who aren't satisfied with the API provided by loader.
    SetExpiresAfter(key K, duration time.Duration) bool
}

type EvictionExtension[K comparable, V any] interface {
    GetCapacity() uint64
    SetCapacity(capacity uint64) bool
}

Packages

If I put some of the code in small (sometimes even too much) packages, it seems that the API can be simplified a bit, but I'm not sure that many people will like it.

Instead of otter.DeletionCause we get deletion.Cause. otter/deletion/case.go

package deletion

// Cause the cause why a cached entry was deleted.
type Cause uint8

const (
    // Explicit the entry was manually deleted by the user.
    Explicit Cause = iota + 1
    // Replaced the entry itself was not actually deleted, but its value was replaced by the user.
    Replaced
    // Size the entry was evicted due to size constraints.
    Size
    // Expired the entry's expiration timestamp has passed.
    Expired
)

func (c Cause) String() string {
    switch c {
    case Explicit:
        return "Explicit"
    case Replaced:
        return "Replaced"
    case Size:
        return "Size"
    case Expired:
        return "Expired"
    default:
        panic("unknown deletion cause")
    }
}

func (c Cause) WasEvicted() bool {
    switch c {
    case Size, Expired:
        return true
    default:
        return false
    }
}

Instead of otter.StatsCollector and otter.NewStatsCounter() we get stats.Collector and stats.NewCounter().

otter/stats/collector.go

package stats

import (
    "time"

    "github.com/maypok86/otter/v2/deletion"
)

type Collector interface {
    CollectHits(count int)
    CollectMisses(count int)
    CollectEviction(weight uint32, cause deletion.Cause)
    Snapshot() Stats
}

type LoadCollector interface {
    CollectLoadSuccess(loadDuration time.Duration)
    CollectLoadFailure(loadDuration time.Duration)
}

type Stats struct {
    ...
}

type counter struct {
    ...
}

func NewCounter() Collector {

}

Instead of otter.ExpireAfterWrite we get expiry.AfterWrite. otter/expiry/strategy.go

package expiry

type Strategy uint8

const (
    AfterCreate Strategy = iota + 1
    AfterWrite
    AfterAccess
    AfterRead
    AfterUpdate
)

Then we can get a pretty nice API.

package main

import (
    "context"
    "fmt"
    "time"
    "unsafe"

    "github.com/maypok86/otter/v2"
    "github.com/maypok86/otter/v2/deletion"
    "github.com/maypok86/otter/v2/expiry"
    "github.com/maypok86/otter/v2/stats"
)

func main() {
    ctx := context.Background()
    loader, err := ...
    logger, err := ...
    cache, err := otter.NewBuilder[int, int]().
        MaximumWeight(100 * 1024 * 1024).
        Weigher(func(key int, value int) uint32 {
            return uint32(unsafe.Sizeof(key) + unsafe.Sizeof(value))
        }).
        DeletionListener(func(key int, value int, cause deletion.Cause) {
            fmt.Println(key, value, cause)
        }).
        Expire(expiry.AfterAccess, time.Hour).
        CollectStats(stats.NewCounter()).
        Logger(logger).
        Build()

	key := 1
	value, err := cache.Load(ctx, loader, key)
	cache.Extension().Expiry().Set(key, value, time.Minute)
	cache.AsMap().SetIfAbsent(key, value)
	cache.AsMap().DeleteFunc(func(key int, value int) bool {
		return true
	})
}

Or a simpler example.

package main

import (
    "time"

    "github.com/maypok86/otter/v2"
    "github.com/maypok86/otter/v2/expiry"
    "github.com/maypok86/otter/v2/stats"
)

func main() {
    cache, err := otter.NewBuilder[int, int]().
        MaximumSize(10_000).
        Expire(expiry.AfterAccess, time.Hour).
        CollectStats(stats.NewCounter()).
        Build()

    key := 1
    value := 2
    cache.Set(key, value)
    value, ok := cache.Get(key)
    cache.AsMap().DeleteFunc(func(key int, value int) bool {
        return true
    })
}

It seems that the only question is the increased number of imports. ⚠️