buckets

README

buckets

A Go library providing generic, in-memory bucketed storage for resources.

Resources are distributed across a fixed number of buckets, each guarded by its own mutex. This reduces lock contention compared to a single global lock while keeping all state in-process.

This library originated from the internal bucketing used by maxcap.

Installation

go get codeberg.org/jrh3k5/buckets/pkg

Usage

The bucket.Buckets interface defines the contract for storing and retrieving resources by key. The interface is generic over both the bucket key type and the bucketed resource type.

Keys

Keys implement the bucket.ListKey interface, which maps a resource to one of the fixed buckets via a 0-based BucketIndex() and identifies the resource within that bucket via ResourceID().

The provided StringListKey hashes a string resource ID (using MD5, where collisions are tolerated for bucketing purposes) into a consistent bucket index for a given bucket count:

key, err := bucket.NewStringListKey("tenant-acme/user-abc", 256)
if err != nil {
    log.Fatal(err)
}

Custom key types are supported by implementing ListKey; this is useful if you already have a natural way to partition your resources.

Single-Value Buckets

BucketsList stores at most one resource per resource ID:

package main

import (
	"context"
	"log"

	bucket "codeberg.org/jrh3k5/buckets/pkg"
)

type Connection struct {
	// ...
}

func (c *Connection) Close() error {
	// ...
	return nil
}

func main() {
	ctx := context.Background()

	bucketsList, err := bucket.NewBucketsList[*bucket.StringListKey, string, *Connection](256)
	if err != nil {
		log.Fatal(err)
	}

	key, err := bucket.NewStringListKey("conn-abc123", 256)
	if err != nil {
		log.Fatal(err)
	}

	// Store a resource; any existing resource for this ID is overwritten.
	err = bucketsList.Add(ctx, key, &Connection{})
	if err != nil {
		log.Fatal(err)
	}

	// Mutate a stored resource in place. The returned boolean reports whether
	// a resource exists for the given key.
	found, err := bucketsList.Apply(ctx, key, func(_ context.Context, conn *Connection) error {
		return conn.Close()
	})
	if err != nil {
		log.Fatal(err)
	}
	_ = found

	// Remove and retrieve a resource.
	conn, found, err := bucketsList.Pop(ctx, key)
	if err != nil {
		log.Fatal(err)
	}
	_ = conn
	_ = found
}

AddIfNotExists provides get-or-create semantics. The creator function is only invoked when no resource exists for the given key, and the pre-existing resource is returned otherwise:

resource, err := bucketsList.AddIfNotExists(ctx, key, func(_ context.Context, _ *bucket.StringListKey) (*Connection, error) {
	return dialConnection(ctx)
})

EvictOlderThan evicts every resource that was added before the given time and returns them, which is useful for reaping abandoned resources:

evicted, err := bucketsList.EvictOlderThan(ctx, time.Now().Add(-5*time.Minute))
if err != nil {
    log.Fatal(err)
}

for _, conn := range evicted {
    _ = conn.Close()
}

Multi-Value Buckets

MultiValueBucketsList extends BucketsList for buckets that hold multiple values, such as all of a client's open sessions. Each bucket must implement the MultiValueBucketResource interface; MultiValueResource is a ready-made implementation that tracks values by ID and preserves insertion order (satisfying OrderedMultiValueBucketResource).

A common pattern is to get-or-create the bucket for a client, add values to it, and then cap the number of retained values:

package main

import (
	"context"
	"log"

	"codeberg.org/jrh3k5/buckets/pkg"
)

func main() {
	ctx := context.Background()

	const maximumSessionsPerClient = 10

	sessions, err := bucket.NewMultiValueBucketsList[
		*bucket.StringListKey,
		string,
		bucket.OrderedMultiValueBucketResource[string, string],
		string,
		string,
	](256)
	if err != nil {
		log.Fatal(err)
	}

	key, err := bucket.NewStringListKey("tenant-acme/user-abc", 256)
	if err != nil {
		log.Fatal(err)
	}

	// Get or create the client's bucket.
	clientSessions, err := sessions.AddIfNotExists(ctx, key, func(_ context.Context, _ *bucket.StringListKey) (bucket.OrderedMultiValueBucketResource[string, string], error) {
		return bucket.NewMultiValueResource[string, string](), nil
	})
	if err != nil {
		log.Fatal(err)
	}

	err = clientSessions.Add(ctx, "session-1", "session-one-value")
	if err != nil {
		log.Fatal(err)
	}

	// Enforce a cap of N most-recent values; older values are returned for cleanup.
	evicted, err := clientSessions.RetainLast(ctx, maximumSessionsPerClient)
	if err != nil {
		log.Fatal(err)
	}
	_ = evicted

	// Pop the first N values in insertion order.
	first, err := clientSessions.PopFirst(ctx, 2)
	if err != nil {
		log.Fatal(err)
	}
	_ = first
}

At the collection level, PopValues pops specific values out of a client's bucket without removing the bucket itself, and EvictValuesOlderThan sweeps all buckets, evicting sufficiently-old values and cleaning up any buckets left empty:

popped, err := sessions.PopValues(ctx, key, []string{"session-1", "session-2"})
if err != nil {
    log.Fatal(err)
}
_ = popped

evicted, err := sessions.EvictValuesOlderThan(ctx, time.Now().Add(-30*time.Minute))
if err != nil {
    log.Fatal(err)
}
_ = evicted

Thread Safety

All implementations are safe for concurrent use. Each bucket is guarded by its own mutex, so operations against different buckets do not contend with each other. Note that eviction times are captured with time.Now() when a resource or value is added.

Logging

This library uses the standard library's log/slog package for structured logging. Configure the default slog logger to control log output and verbosity.