tiedb

package
v0.5.0 Latest Latest
Warning

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

 Go to latest Published: Sep 1, 2026 License: BSD-3-Clause Imports: 16 Imported by: 0

README

tiedb

Golang package to associate and relate bytes/strings using a trie and red-black-trees.

See ../docs/internals.md for the data structures, on-disk file format, and memory model (including the opt-in reverse-association index).

Documentation

Index

Constants

View Source 
const (
	ENTRY_SIZE = SIZE_DATATYPE +
		SIZE_LEVEL +
		SIZE_ID +
		SIZE_PARENTID +
		SIZE_VALUE

	SIZE_DATATYPE = 2
	SIZE_LEVEL    = 8
	SIZE_ID       = 8
	SIZE_PARENTID = SIZE_ID
	SIZE_VALUE    = 24 // 6 * 8 - 3 * 8

	FILE_ADD    = 0
	FILE_DELETE = 1

	// These values get written to the db files
	TYPE_DELETE      = 10
	TYPE_ENTRY       = 11
	TYPE_ASSOCIATION = 12
	TYPE_HASH        = 13

	// HASH_LEVEL is a sentinel level marking an entry ID that lives in the
	// whole-value hash store rather than in any trie level. A value routed
	// through BlobPolicy is stored as one 32-byte record and its Triple level
	// fields carry HASH_LEVEL, so getValue resolves it from hashEntries instead
	// of walking ParentId links.
	HASH_LEVEL = -1
)

Variables

This section is empty.

Functions

func Debug 

func Debug(value string)

Debug and Info are thin wrappers kept for existing call sites; they forward to the process slog logger (which tie-triplestore/tie-filehost point at a log file plus pretty stderr). Diagnostics stay off stdout — stdout is data.

func EntryToBytes 

func EntryToBytes(level int, entryID uint64, uv *UniqueValue) []byte

func HashToBytes 

func HashToBytes(entryID uint64, raw [32]byte) []byte

HashToBytes serializes a whole-value hash entry into the same 50-byte frame as the other record types: datatype(2) | level(8) | entryID(8) | raw hash(32). The 32-byte hash occupies the contiguous parentId+value region of the frame, so ENTRY_SIZE is unchanged. The level field is always HASH_LEVEL.

func Info 

func Info(value string)

Types

type AssociationSet 

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

AssociationSet is the inner association store: a mapping from UniqueAssociation to an int64 position (a disk offset in disk mode, or an arena index in memory mode). It replaces the former red-black tree: the query paths never use key ordering (Sort re-sorts by resolved strings, intersect/exclude use point lookups), so there is no need to keep entries ordered.

Three representations, chosen by size:

  • a single inline entry (no allocation) — the common forward-index case where a content-address key holds exactly one association
  • a flat slice — the small case (2..shardThreshold distinct keys), the most memory-compact form for the bimodal middle population
  • a sharded map — only once a set exceeds shardThreshold, for the reverse index's shared-value hot sets that many load workers hammer concurrently

It is internal to tiedb: association set algebra reaches callers only through Collection.QueryTags, so no map-of-generic type ever crosses into api/.

func (*AssociationSet) Delete 

func (s *AssociationSet) Delete(key UniqueAssociation)

func (*AssociationSet) ForEach 

func (s *AssociationSet) ForEach(fn func(key UniqueAssociation, pos int64))

ForEach visits every (key, position). Order is unspecified (the query paths re-sort by resolved strings, so tree ordering was never used).

func (*AssociationSet) Get 

func (s *AssociationSet) Get(key UniqueAssociation) (int64, bool)

func (*AssociationSet) HasRelation 

func (s *AssociationSet) HasRelation(rel uint64) bool

HasRelation reports whether any entry is stored under relation id rel. The set is keyed on the full {AssociateTo, Relation} pair with no per-relation index, so this scans — but it early-exits on the first match, and the sets it is meant for (one subject's forward associations = its handful of metadata triples) are tiny, so a hit or miss is effectively O(1) in practice.

func (*AssociationSet) Put 

func (s *AssociationSet) Put(key UniqueAssociation, value int64)

func (*AssociationSet) Size 

func (s *AssociationSet) Size() int

type BlobPolicy 

type BlobPolicy struct {
	Encode func(value string) (raw []byte, ok bool)
	Decode func(raw []byte) string
}

BlobPolicy, when non-nil on a Collection, routes matching values to a whole-value hash entry instead of the 24-byte-chunk trie. Encode maps a value string to its raw bytes, returning ok=false for values that should use the trie; Decode is the inverse, reconstructing the string from stored bytes. Both must be deterministic on the value alone so a value's identity is stable across Adds (the same hash is the Key of many triples).

type Collection 

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

func (*Collection) Add 

func (ic *Collection) Add(key string, value1 string, value2 string)

func (*Collection) CoTags 

func (ic *Collection) CoTags(q TagQuery, tagRelation string) ([]string, bool)

CoTags runs the same set algebra as QueryTags (same Include/Exclude/Scope/Reverse) and returns every unique tagRelation value2 carried by the matching entries. This is a "faceted refinement" query: given the current tag filter, what further tags exist on the matching set? Use tagRelation = "tag" for the standard case.

Returns (nil, false) when the seed term (Include[0]) has no reverse associations. Returns (nil, true) when the AND of include terms yields an empty set (unmet AND). The returned slice is unsorted and deduplicated; sort it in the caller if needed.

func (*Collection) Delete 

func (ic *Collection) Delete(key string, value1 string, value2 string) (string, bool)

func (*Collection) ExpandKeys 

func (ic *Collection) ExpandKeys(keys []string, filter string) []Row

ExpandKeys returns one Row per key holding that key's forward attributes (relation -> values), reusing the same GetAssociations + Sort path a query uses. Keys with no associations are skipped. Order follows the input keys. This is the multi-key batch fetch that lets a client attach metadata to many matches (or list many entries) in one round trip instead of one Get per key.

func (*Collection) ForEachTriple 

func (ic *Collection) ForEachTriple(do func(StringTriple))

ForEachTriple calls do for every forward triple in the collection. It walks each level's associations tree (keyed by entry ID) and runs each key's association subtree through the same Sort path used by Get, so the emitted triples match query results exactly. Intended for full-collection export.

func (*Collection) Get 

func (ic *Collection) Get(key string, value1 string) (TripleSet, bool)

func (*Collection) GetAssociations 

func (ic *Collection) GetAssociations(value string) (*AssociationSet, bool)

func (*Collection) GetPage 

func (ic *Collection) GetPage(s *AssociationSet, value1Filter string, o SortOptions) (result TripleSet, sorted []StringTriple, totalCount int)

GetPage runs one Sort and returns both views of the page: the unordered TripleSet map (for the existing OneKey/OneValue2 helpers and back-compat) and the ordered, paginated slice (for clients that need a stable sequence), together with the pre-pagination total. Building both from a single Sort avoids sorting twice.

func (*Collection) GetReverseAssociations 

func (ic *Collection) GetReverseAssociations(value string) (*AssociationSet, bool)

func (*Collection) GetTotalEntries 

func (ic *Collection) GetTotalEntries() uint64

func (*Collection) GetTripleSet 

func (ic *Collection) GetTripleSet(s *AssociationSet, value1Filter string, o SortOptions) (result TripleSet, totalCount int)

func (*Collection) QueryTags 

func (ic *Collection) QueryTags(q TagQuery) (result TripleSet, sorted []StringTriple, total int, found bool)

QueryTags resolves the include/exclude set algebra internally and returns a paginated result: the unordered TripleSet, the ordered+paged slice, and the pre-pagination total, plus whether the seed existed. The intermediate association trees never leave tiedb.

func (*Collection) SetBlobPolicy 

func (ic *Collection) SetBlobPolicy(p *BlobPolicy)

SetBlobPolicy installs a whole-value blob policy on this collection and allocates the backing hash store. Pass nil to keep the trie-only behavior. See [BlobPolicy]. Call before values are inserted.

func (*Collection) SetReverseRelations 

func (ic *Collection) SetReverseRelations(relations []string)

SetReverseRelations restricts which relations (value1) this collection indexes in reverse. Pass nil to index every relation (the default). Call before adding triples; it does not rebuild reverse indexes for triples already inserted.

func (*Collection) SetValues 

func (ic *Collection) SetValues(key string, value1 string, values []string)

SetValues makes (key, value1) hold exactly the given values: it removes every existing value2 for the relation and adds each of values. This is the multi-valued generalization of SimpleUpdate — the server-side "replace this relation" primitive, so clients no longer Get-then-Delete-each-then-Add. Passing an empty values slice clears the relation.

func (*Collection) SimpleUpdate 

func (ic *Collection) SimpleUpdate(key string, value1 string, newValue2 string, addOnFail bool) (string, bool)

SimpleUpdate makes a scalar (single-valued) field equal to newValue2: it removes every existing value2 for (key, value1) and adds newValue2. When the field does not yet exist it adds newValue2 only if addOnFail is set. Use this for fields that are meant to hold exactly one value.

func (*Collection) Sort 

func (ic *Collection) Sort(tree *AssociationSet, value1Filter string, o SortOptions) (sorted []StringTriple, totalCount int)

func (*Collection) Sync 

func (ic *Collection) Sync()

func (*Collection) Update 

func (ic *Collection) Update(key string, value1 string, value2 string, newValue2 string) (string, bool)

func (*Collection) UpdateAdd 

func (ic *Collection) UpdateAdd(key string, value1 string, value2 string, newValue2 string) (string, bool)

UpdateAdd replaces value2 with newValue2, adding newValue2 even when the original (key, value1, value2) did not exist. It always succeeds; the message notes when a fallback add was used instead of an update.

type CollectionKey 

type CollectionKey struct {
	Database   string
	Collection string
}

type FileIndexer 

type FileIndexer interface {
	// contains filtered or unexported methods
}

type FileMod 

type FileMod struct {
	Mode        int
	Level       int
	EntryType   int
	Position    int64
	Triple      *Triple
	EntryID     uint64
	UniqueValue *UniqueValue
	HashValue   [32]byte
}

type RawDataEntry 

type RawDataEntry struct {
	Position int64
	Data     [ENTRY_SIZE]byte
}

type ReadRequest 

type ReadRequest struct {
	Position  int64
	ReplyChan chan Triple
}

type Row 

type Row struct {
	Key        string              `json:"key"`
	Attributes map[string][]string `json:"attributes"`
}

Row is the flat, language-neutral result unit that crosses the wire. It groups one key's triples by relation: Attributes maps a relation (value1) to all its values (value2). A client reads row.Attributes["tag"] directly — no nested-map navigation or callbacks. TripleSet stays internal to the engine.

func RowsFromSorted 

func RowsFromSorted(sorted []StringTriple) []Row

RowsFromSorted folds an ordered []StringTriple into []Row, preserving the first-seen key order (the slice is already sorted/paginated by Sort). Triples for the same key coalesce into one Row; values under a relation keep their order of appearance.

type SortOptions 

type SortOptions struct {
	Offset int
	Limit  int
	SortBy string // Value1 to sort by
	// SortByValue orders matched keys by the VALUE each key holds under this
	// relation (a forward lookup per key), rather than by the matched triple.
	// Empty means no value-based ordering. Example: "gendb-imported-at" to sort
	// tables chronologically. Multi-valued relations sort by their smallest value.
	SortByValue string
	// Descending reverses the final ordering (applies to any sort mode).
	Descending bool
}

type StringTriple 

type StringTriple struct {
	Key    string
	Value1 string
	Value2 string
}

type TagQuery 

type TagQuery struct {
	Include         []string    // AND across all; Include[0] is the seed set
	Exclude         []string    // NOT any of these
	Scope           string      // restrict to associates of this value, ignoring relation
	MissingRelation string      // keep only matches with NO triple under this relation
	Reverse         bool        // seed via reverse associations (tag query) vs forward
	Filter          string      // filter-in on value1 (relation)
	Sort            SortOptions // pagination (Offset/Limit/SortBy)
}

TagQuery selects entries by association membership: a match must be associated with the seed (Include[0]) and with every other Include value, and with none of the Exclude values. It expresses "things tagged with all of these but none of those" directly, so callers no longer compose raw set operations. Include and Exclude terms are matched by reverse association; Reverse also selects the seed via reverse associations (the tag-query case) rather than forward.

Scope, when set, restricts matches to the associates of that value under a different relation than the Include/Exclude terms — e.g. scope a "tag" query to a "tie-type" so only audio files are returned. Because Scope's relation differs from the query terms' relation, it cannot be an Include term (intersect keys on the full {associate, relation} pair); it is applied by matching on associate identity alone. An empty Scope means no scoping.

type TieTree 

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

TieTree is the top-level database handle: a typed, concurrency-safe map from CollectionKey to *Collection, plus the settings applied to collections it creates. The per-level entry and association indexes are separate lockedTree instances held on each Collection.

func NewDB 

func NewDB(writeToDisk bool) *TieTree

func (*TieTree) Close 

func (db *TieTree) Close()

Close flushes and closes every live collection's disk writer, blocking until each has drained its pending writes, synced, and closed its file handle. It is the clean-shutdown counterpart to the periodic sync in dBWriter: call it from a signal handler so a terminating server durably persists its tail of writes instead of relying on the kernel to flush the page cache. A no-op in memory-only mode (collections have no writer goroutine then).

func (*TieTree) DropCollection 

func (db *TieTree) DropCollection(key CollectionKey) error

DropCollection deletes a collection's entire on-disk state and forgets its in-memory index. The live writer (if any) is closed first so its fd is released before the .tie file is removed, then the collection is dropped from the map; a later GetCollection reloads it lazily from the now-absent file, yielding an empty collection. This is the destructive counterpart to the additive Add/Restore path — the whole collection is overwritten, not merged. A no-op in memory-only mode returns nil after dropping the in-memory entry.

func (*TieTree) GetCollection 

func (db *TieTree) GetCollection(key CollectionKey) *Collection

func (*TieTree) SetBlobPolicy 

func (tree *TieTree) SetBlobPolicy(p *BlobPolicy)

SetBlobPolicy sets a whole-value blob policy applied to newly created collections: matching values (e.g. content-address hashes) are stored as a single hash entry instead of being chunked into the trie. Pass nil for the default trie-only behavior. Call before collections are created; existing collections are unaffected.

func (*TieTree) SetDefaultReverseRelations 

func (tree *TieTree) SetDefaultReverseRelations(relations []string)

SetDefaultReverseRelations restricts which relations (value1) newly created collections index in reverse. Pass nil to index every relation (the default). Call before collections are created; existing collections are unaffected.

func (*TieTree) SetReverseRelationsOverrides 

func (tree *TieTree) SetReverseRelationsOverrides(overrides map[CollectionKey][]string)

SetReverseRelationsOverrides pins the reverse-relation set for specific collections, overriding the default set by SetDefaultReverseRelations. Each keyed collection indexes exactly its listed relations in reverse; collections with no entry use the default. Call before collections are created; existing collections are unaffected. The reverse index is rebuilt from forward triples at load time, so a changed override takes effect after one restart.

type Triple 

type Triple struct {
	Level       int
	Key         uint64
	Value1Level int
	Value1      uint64
	Value2Level int
	Value2      uint64
}

type TripleSet 

type TripleSet map[string]Value1

func (TripleSet) ForEachKey 

func (s TripleSet) ForEachKey(do func(key string))

func (TripleSet) ForEachValue1 

func (s TripleSet) ForEachValue1(do func(key, value1 string))

func (TripleSet) ForEachValue2 

func (s TripleSet) ForEachValue2(do func(key, value1, value2 string))

func (TripleSet) Has 

func (s TripleSet) Has(key string) bool

type UniqueAssociation 

type UniqueAssociation struct {
	AssociateTo uint64
	Relation    uint64
}

type UniqueValue 

type UniqueValue struct {
	ParentId uint64
	Value    [SIZE_VALUE]byte
}

type Unit 

type Unit struct{}

type Value1 

type Value1 map[string]Value2

func (Value1) ForEach 

func (s Value1) ForEach(do func(value1 string))

func (Value1) ForEachValue2 

func (s Value1) ForEachValue2(do func(value1, value2 string))

func (Value1) Has 

func (s Value1) Has(value1 string) bool

type Value2 

type Value2 map[string]Unit

func (Value2) ForEach 

func (s Value2) ForEach(do func(value2 string))

func (Value2) Has 

func (s Value2) Has(value2 string) bool

func (Value2) One 

func (s Value2) One() (string, bool)

There must exist exactly 1 value2 for the provided value1! Otherwise it will return (empty string, false)")

func (Value2) ToSlice 

func (s Value2) ToSlice() []string

func (Value2) ToString 

func (s Value2) ToString() string

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.