Skip to content

SeaweedFS is a distributed storage system for object storage (S3), file systems, Iceberg table buckets, and Lance vector buckets, designed to handle billions of files with O(1) disk access and effortless horizontal scaling.

8.0 KB
Raw Blame
package needle_map

/* CompactMap is an in-memory map of needle indices, optimized for memory usage.
 *
 * It's implemented as a map of sorted indices segments, which are in turn accessed through binary
 * search. This guarantees a best-case scenario (ordered inserts/updates) of O(1) and a worst case
 * scenario of O(log n) runtime, with memory usage unaffected by insert ordering.
 *
 * Note that even at O(log n), the clock time for both reads and writes is very low, so CompactMap
 * will seldom bottleneck index operations.
 */

import (
	"fmt"
	"math"
	"slices"
	"sort"
	"sync"

	"github.com/seaweedfs/seaweedfs/weed/storage/types"
)

const (
	MaxCompactKey    = math.MaxUint16
	SegmentChunkSize = 50000 // should be <= MaxCompactKey
)

type CompactKey uint16
type CompactOffset [types.OffsetSize]byte
type CompactNeedleValue struct {
	key    CompactKey
	offset CompactOffset
	size   types.Size
}

type Chunk uint64
type CompactMapSegment struct {
	list     []CompactNeedleValue
	chunk    Chunk
	firstKey CompactKey
	lastKey  CompactKey
}

type CompactMap struct {
	sync.RWMutex

	segments map[Chunk]*CompactMapSegment
}

func (ck CompactKey) Key(chunk Chunk) types.NeedleId {
	return (types.NeedleId(SegmentChunkSize) * types.NeedleId(chunk)) + types.NeedleId(ck)
}

func OffsetToCompact(offset types.Offset) CompactOffset {
	var co CompactOffset
	types.OffsetToBytes(co[:], offset)
	return co
}

func (co CompactOffset) Offset() types.Offset {
	return types.BytesToOffset(co[:])
}

func (cnv CompactNeedleValue) NeedleValue(chunk Chunk) NeedleValue {
	return NeedleValue{
		Key:    cnv.key.Key(chunk),
		Offset: cnv.offset.Offset(),
		Size:   cnv.size,
	}
}

func newCompactMapSegment(chunk Chunk) *CompactMapSegment {
	return &CompactMapSegment{
		list:     []CompactNeedleValue{},
		chunk:    chunk,
		firstKey: MaxCompactKey,
		lastKey:  0,
	}
}

func (cs *CompactMapSegment) len() int {
	return len(cs.list)
}

func (cs *CompactMapSegment) cap() int {
	return cap(cs.list)
}

func (cs *CompactMapSegment) compactKey(key types.NeedleId) CompactKey {
	return CompactKey(key - (types.NeedleId(SegmentChunkSize) * types.NeedleId(cs.chunk)))
}

// bsearchKey returns the CompactNeedleValue index for a given ID key.
// If the key is not found, it returns the index where it should be inserted instead.
func (cs *CompactMapSegment) bsearchKey(key types.NeedleId) (int, bool) {
	ck := cs.compactKey(key)

	switch {
	case len(cs.list) == 0:
		return 0, false
	case ck == cs.firstKey:
		return 0, true
	case ck <= cs.firstKey:
		return 0, false
	case ck == cs.lastKey:
		return len(cs.list) - 1, true
	case ck > cs.lastKey:
		return len(cs.list), false
	}

	i := sort.Search(len(cs.list), func(i int) bool {
		return cs.list[i].key >= ck
	})
	return i, cs.list[i].key == ck
}

// set inserts/updates a CompactNeedleValue.
// If the operation is an update, returns the overwritten value's previous offset and size.
func (cs *CompactMapSegment) set(key types.NeedleId, offset types.Offset, size types.Size) (oldOffset types.Offset, oldSize types.Size) {
	i, found := cs.bsearchKey(key)
	if found {
		// update
		o := cs.list[i].offset.Offset()
		oldOffset.OffsetLower = o.OffsetLower
		oldOffset.OffsetHigher = o.OffsetHigher
		oldSize = cs.list[i].size

		o.OffsetLower = offset.OffsetLower
		o.OffsetHigher = offset.OffsetHigher
		cs.list[i].offset = OffsetToCompact(o)
		cs.list[i].size = size
		return
	}

	// insert
	if len(cs.list) >= SegmentChunkSize {
		panic(fmt.Sprintf("attempted to write more than %d entries on CompactMapSegment %p!!!", SegmentChunkSize, cs))
	}
	if len(cs.list) == SegmentChunkSize-1 {
		// if we max out our segment storage, pin its capacity to minimize memory usage
		nl := make([]CompactNeedleValue, SegmentChunkSize, SegmentChunkSize)
		copy(nl, cs.list[:i])
		copy(nl[i+1:], cs.list[i:])
		cs.list = nl
	} else {
		cs.list = append(cs.list, CompactNeedleValue{})
		copy(cs.list[i+1:], cs.list[i:])
	}

	ck := cs.compactKey(key)
	cs.list[i] = CompactNeedleValue{
		key:    ck,
		offset: OffsetToCompact(offset),
		size:   size,
	}
	if ck < cs.firstKey {
		cs.firstKey = ck
	}
	if ck > cs.lastKey {
		cs.lastKey = ck
	}

	return
}

// get seeks a map entry by key. Returns an entry pointer, with a boolean specifying if the entry was found.
func (cs *CompactMapSegment) get(key types.NeedleId) (*CompactNeedleValue, bool) {
	if i, found := cs.bsearchKey(key); found {
		return &cs.list[i], true
	}

	return nil, false
}

// delete deletes a map entry by key. Returns the entries' previous Size, if available.
func (cs *CompactMapSegment) delete(key types.NeedleId) types.Size {
	if i, found := cs.bsearchKey(key); found {
		if !cs.list[i].size.IsDeleted() {
			ret := cs.list[i].size
			if cs.list[i].size == 0 {
				// size=0 needles can't be marked deleted by negating, use tombstone
				cs.list[i].size = types.TombstoneFileSize
			} else {
				cs.list[i].size = -cs.list[i].size
			}
			return ret
		}
	}

	return types.Size(0)
}

// remove erases a map entry entirely, returning whether it existed.
func (cs *CompactMapSegment) remove(key types.NeedleId) bool {
	i, found := cs.bsearchKey(key)
	if !found {
		return false
	}
	copy(cs.list[i:], cs.list[i+1:])
	cs.list = cs.list[:len(cs.list)-1]
	if len(cs.list) == 0 {
		cs.firstKey, cs.lastKey = MaxCompactKey, 0
	} else {
		cs.firstKey = cs.list[0].key
		cs.lastKey = cs.list[len(cs.list)-1].key
	}
	return true
}

func NewCompactMap() *CompactMap {
	return &CompactMap{
		segments: map[Chunk]*CompactMapSegment{},
	}
}

func (cm *CompactMap) Len() int {
	l := 0
	for _, s := range cm.segments {
		l += s.len()
	}
	return l
}

func (cm *CompactMap) Cap() int {
	c := 0
	for _, s := range cm.segments {
		c += s.cap()
	}
	return c
}

func (cm *CompactMap) String() string {
	if cm.Len() == 0 {
		return "empty"
	}
	return fmt.Sprintf(
		"%d/%d elements on %d segments, %.02f%% efficiency",
		cm.Len(), cm.Cap(), len(cm.segments),
		float64(100)*float64(cm.Len())/float64(cm.Cap()))
}

func (cm *CompactMap) segmentForKey(key types.NeedleId) *CompactMapSegment {
	chunk := Chunk(key / SegmentChunkSize)
	if cs, ok := cm.segments[chunk]; ok {
		return cs
	}

	cs := newCompactMapSegment(chunk)
	cm.segments[chunk] = cs
	return cs
}

// Set inserts/updates a NeedleValue.
// If the operation is an update, returns the overwritten value's previous offset and size.
func (cm *CompactMap) Set(key types.NeedleId, offset types.Offset, size types.Size) (oldOffset types.Offset, oldSize types.Size) {
	cm.Lock()
	defer cm.Unlock()

	cs := cm.segmentForKey(key)
	return cs.set(key, offset, size)
}

// Get seeks a map entry by key. Returns an entry pointer, with a boolean specifying if the entry was found.
func (cm *CompactMap) Get(key types.NeedleId) (*NeedleValue, bool) {
	cm.RLock()
	defer cm.RUnlock()

	chunk := Chunk(key / SegmentChunkSize)
	cs, ok := cm.segments[chunk]
	if !ok {
		return nil, false
	}
	if cnv, found := cs.get(key); found {
		nv := cnv.NeedleValue(cs.chunk)
		return &nv, true
	}
	return nil, false
}

// Delete deletes a map entry by key. Returns the entries' previous Size, if available.
func (cm *CompactMap) Delete(key types.NeedleId) types.Size {
	cm.Lock()
	defer cm.Unlock()

	chunk := Chunk(key / SegmentChunkSize)
	cs, ok := cm.segments[chunk]
	if !ok {
		return types.Size(0)
	}
	return cs.delete(key)
}

// Remove erases a map entry entirely, returning whether it existed. Unlike
// Delete it leaves no tombstoned entry behind.
func (cm *CompactMap) Remove(key types.NeedleId) bool {
	cm.Lock()
	defer cm.Unlock()

	chunk := Chunk(key / SegmentChunkSize)
	cs, ok := cm.segments[chunk]
	if !ok {
		return false
	}
	return cs.remove(key)
}

// AscendingVisit runs a function on all entries, in ascending key order. Returns any errors hit while visiting.
func (cm *CompactMap) AscendingVisit(visit func(NeedleValue) error) error {
	cm.RLock()
	defer cm.RUnlock()

	chunks := []Chunk{}
	for c := range cm.segments {
		chunks = append(chunks, c)
	}
	slices.Sort(chunks)

	for _, c := range chunks {
		cs := cm.segments[c]
		for _, cnv := range cs.list {
			nv := cnv.NeedleValue(cs.chunk)
			if err := visit(nv); err != nil {
				return err
			}
		}
	}
	return nil
}