raccoon

package module
v0.2.0 Latest Latest
Warning

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

 Go to latest Published: Jan 10, 2024 License: Apache-2.0 Imports: 11 Imported by: 4

README

Raccoon

Raccoon package is a general purpose graph store. It wraps a KV store with a useful abstraction to work with graph structured data.

Edges and Nodes

The main abstraction behind Raccoon is that of an Edge. An Edge contains a Source Node and a Target Node. The Edge interface specifies methods to return the target and source Nodes.

An Edge is a user defined type which gets serialized and persisted in the backend store. Serialization is done by a Marsheler, an interface that marshals and unmarshals an Edge implementation. Raccoon provides two default Marshalers, one for protobuff serialization and another for Json.

Users are free to add custom additional fields in their edge types. Note that each Edge fully serializes its node data as well.

Secondary Indexes

A notable fetaure of Raccoon is a lightweight secondary indexing feature.

Users may define secondary indexes in their schemas, which can be used for faster lookup.

Secondary indexes are built from Edge's through a Mapper. A Mapper is a function that maps an Edge into a byte slice, which is used as the indexing key.

Keying System

Edge nodes must map to unique keys which are used internally by Raccoon. Edges are unique identified by the keys of their source and target nodes.

Key generation is specified through the NodeKeyer interface. Users must implement a NodeKeyer for their custom Node types.

Example usage

// TODO

Documentation

Overview

package object_kvstore define a generic wrapper store for a protobuff serializable entity

package raccoon is a lightweight and minimal graph store library

Index

Constants

View Source 
const Separator = '/'

Separator used to build keys

Variables

View Source 
var File_data_proto protoreflect.FileDescriptor

Functions

func ProduceTrue 

func ProduceTrue[T any](t T) bool

Types

type Data 

type Data struct {
	Data string `protobuf:"bytes,1,opt,name=data,proto3" json:"data,omitempty"`
	// contains filtered or unexported fields
}

func (*Data) Descriptor deprecated 

func (*Data) Descriptor() ([]byte, []int)

Deprecated: Use Data.ProtoReflect.Descriptor instead.

func (*Data) GetData 

func (x *Data) GetData() string

func (*Data) ProtoMessage 

func (*Data) ProtoMessage()

func (*Data) ProtoReflect 

func (x *Data) ProtoReflect() protoreflect.Message

func (*Data) Reset 

func (x *Data) Reset()

func (*Data) String 

func (x *Data) String() string

type DirectedEdge 

type DirectedEdge[Node any] interface {
	Edge[Node]
}

DirectedEdge specialization of an Edge.

type Edge 

type Edge[Node any] interface {
	GetSource() Node
	GetDest() Node
}

Edge represents a protobuff serializable type which is persisted. Edge contains a source and a target Node. Users implementing the Edge interface are free to add extra data to the edge type. Edges are uniquely identified through their nodes

type EdgeKeyer 

type EdgeKeyer[Node any] struct {
	// contains filtered or unexported fields
}

func NewEdgeKeyer 

func NewEdgeKeyer[Node any](keyer NodeKeyer[Node], base Key, inPrefix []byte, outPrefix []byte) EdgeKeyer[Node]

func (*EdgeKeyer[Node]) AllEdges 

func (k *EdgeKeyer[Node]) AllEdges() (Key, Key)

AllEdges return a pair of keys which span through all possible set of edges

func (*EdgeKeyer[Node]) AncestorsIterKey 

func (k *EdgeKeyer[Node]) AncestorsIterKey(src Node) (Key, Key)

func (*EdgeKeyer[Node]) IncomingKey 

func (k *EdgeKeyer[Node]) IncomingKey(src, dst Node) Key

OutgoingKey represents a key from target to source

func (*EdgeKeyer[Node]) OutgoingKey 

func (k *EdgeKeyer[Node]) OutgoingKey(src, dst Node) Key

OutgoingKey represents a key from source to target

func (*EdgeKeyer[Node]) SucessorsIterKeys 

func (k *EdgeKeyer[Node]) SucessorsIterKeys(src Node) (Key, Key)

Build a pair of keys for iteration. IterKeys are used to return all edges starting from Node

type EdgeStore 

type EdgeStore[Edg Edge[N], N any] struct {
	// contains filtered or unexported fields
}

Store for Graph Edges

Provides the usual Get, Set, Delete operations for records. Also exposes a higher level operation to return all records which contain a Node's sucessor and ancestor.

EdgeStore maintains an internal index for a node's ancestors and sucessors, allowing for fast lookup. Setting and Deleting records updates internal indexes to guarantee consistency. TODO make it atomic

func NewEdgeStore 

func NewEdgeStore[Edg Edge[N], N any](store KVStore, prefix []byte, keyer NodeKeyer[N], marshaler Marshaler[Edg]) EdgeStore[Edg, N]

func (*EdgeStore[Edg, N]) Delete 

func (s *EdgeStore[Edg, N]) Delete(edg Edg) error

Delete record associated to edge entry from store

func (*EdgeStore[Edg, N]) GetAncestors 

func (s *EdgeStore[Edg, N]) GetAncestors(node N) ([]Edg, error)

Return all Records in which `node` is the edge's target

func (*EdgeStore[Edg, N]) GetEdg 

func (s *EdgeStore[Edg, N]) GetEdg(source, dest N) (Option[Edg], error)

Fetch stored Record for the given edge. Return record, an ok flag and a potential error If the OK flag is false, no record was found or an error ocurred

func (*EdgeStore[Edg, N]) GetSucessors 

func (s *EdgeStore[Edg, N]) GetSucessors(node N) ([]Edg, error)

Return all Records in which `node` is the edge's source

func (*EdgeStore[Edg, N]) List 

func (s *EdgeStore[Edg, N]) List() ([]Edg, error)

List dumps all Edges in the EdgeStore. Performs pre-loading as opposed to streaming

func (*EdgeStore[Edg, N]) Set 

func (s *EdgeStore[Edg, N]) Set(edg Edg) error

Set a record in the backend storage engine.

type Ider 

type Ider[T any] interface {
	Id(T) []byte
}

Return a unique key (id) for the given object

func IderFromNodeKeyer 

func IderFromNodeKeyer[Edg Edge[N], N any](nodeKeyer NodeKeyer[N]) Ider[Edg]

type Iterator 

type Iterator interface {
	// Valid returns whether the current iterator is valid. Once invalid, the Iterator remains
	// invalid forever.
	Valid() bool

	// Next moves the iterator to the next key in the database, as defined by order of iteration.
	// If Valid returns false, this method will panic.
	Next()

	// Key returns the key at the current position. Panics if the iterator is invalid.
	// CONTRACT: key readonly []byte
	Key() (key []byte)

	// Value returns the value at the current position. Panics if the iterator is invalid.
	// CONTRACT: value readonly []byte
	Value() (value []byte)

	// Error returns the last error encountered by the iterator, if any.
	Error() error

	// Close closes the iterator, relasing any allocated resources.
	Close() error
}

type Json 

type Json[T any] struct{}

Marshaler to represent objects as Json

func (*Json[T]) Marshal 

func (m *Json[T]) Marshal(obj *T) ([]byte, error)

func (*Json[T]) Unmarshal 

func (m *Json[T]) Unmarshal(bytes []byte) (T, error)

type KVStore 

type KVStore interface {
	Get(key []byte) ([]byte, error)
	Has(key []byte) (bool, error)
	Set(key, value []byte) error
	Delete(key []byte) error
	Iterator(start, end []byte) Iterator
}

Type alias for KVStore

func KvFromCosmosKv 

func KvFromCosmosKv(store types.KVStore) KVStore

func NewLevelDB 

func NewLevelDB(path, file string) (KVStore, error)

func NewMemKV 

func NewMemKV() KVStore

func NewWrapperKV 

func NewWrapperKV(store KVStore, prefix []byte) KVStore

type Key 

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

Key represents a hiearachical key built from fragments. Key fragments are ordered and the final key is built joining fragments with a a constant separator.

func (Key) Append 

func (k Key) Append(fragments ...[]byte) Key

func (Key) Fragments 

func (k Key) Fragments() [][]byte

func (Key) Join 

func (k Key) Join(other Key) Key

func (Key) ToBytes 

func (k Key) ToBytes() []byte

type Mapper 

type Mapper[T any] func(T) []byte

Mapper type is used to map a Record to a value used by secundary indexes

type Marshaler 

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

Marshaler marshalls and unmarshalls objects into a byte array, which gets persisted in the underlying store

func ProtoMarshaler 

func ProtoMarshaler[T proto.Message](factory func() T) Marshaler[T]

type NodeKeyer 

type NodeKeyer[T any] interface {
	// Maps a Node into a key.
	Key(T) []byte

	// Return the lowest possible key
	MinKey() []byte

	// Return the highest possible key
	MaxKey() []byte
}

NodeKeyer interface specify methods to map a node into an identifier key. Keys are an user defined byte array. Key values are opaque to the library however they must be deterministic and unique. Furthermore, keys should have known bounds, which are used for iteration.

NodeKeyer decouples node identification from data, which allows for different key generation strategies based on usage patterns.

type ObjKV 

type ObjKV[T any] interface {
	// Fetch object from store using the given key
	Get(key []byte) (Option[T], error)

	// Check whether key exists in KVStore
	Has(key []byte) (bool, error)

	// Set key with obj
	Set(key []byte, obj T) error

	// Remove key from store
	Delete(key []byte) error
}

Type ObjKV wraps KVStore by abstracting object marshaling

func NewObjKV 

func NewObjKV[O any](kv KVStore, keyPrefix []byte, marshaler Marshaler[O]) ObjKV[O]

Return an ObjKV from a KVStore using marshaler to (un)marshal objects. Prefixes all keys with keyPrefix.

type ObjectPredicate 

type ObjectPredicate[Obj any] func(Obj) bool

type ObjectStore 

type ObjectStore[Obj any] struct {
	// contains filtered or unexported fields
}

func NewObjStore 

func NewObjStore[O any](kv KVStore, marshaler Marshaler[O], ider Ider[O]) ObjectStore[O]

func (*ObjectStore[Obj]) Delete 

func (s *ObjectStore[Obj]) Delete(obj Obj) error

func (*ObjectStore[Obj]) DeleteById 

func (s *ObjectStore[Obj]) DeleteById(id []byte) error

func (*ObjectStore[Obj]) Filter 

func (s *ObjectStore[Obj]) Filter(predicate ObjectPredicate[Obj]) ([]Obj, error)

func (*ObjectStore[Obj]) GetObject 

func (s *ObjectStore[Obj]) GetObject(id []byte) (Option[Obj], error)

func (*ObjectStore[Obj]) Has 

func (s *ObjectStore[Obj]) Has(obj Obj) (bool, error)

func (*ObjectStore[Obj]) HasById 

func (s *ObjectStore[Obj]) HasById(id []byte) (bool, error)

func (*ObjectStore[Obj]) List 

func (s *ObjectStore[Obj]) List() ([]Obj, error)

func (*ObjectStore[Obj]) ListIds 

func (s *ObjectStore[Obj]) ListIds() ([][]byte, error)

func (*ObjectStore[Obj]) SetObject 

func (s *ObjectStore[Obj]) SetObject(obj Obj) error

type Option 

type Option[T any] struct {
	// contains filtered or unexported fields
}

Option type is a container for a value Option may or may not contain value

func None 

func None[T any]() Option[T]

Build an empty Option

func Some 

func Some[T any](val T) Option[T]

Build an Option with val as its inner value

func (*Option[T]) IsEmpty 

func (o *Option[T]) IsEmpty() bool

Return true if Option does not contain a value

func (*Option[T]) Value 

func (o *Option[T]) Value() T

Return a copy of the options type Calling Value on an empty option will panic

type Predicate 

type Predicate[T any] func(T) bool

Predicate type defines a filter over a Record set

type ProtoConstraint 

type ProtoConstraint[T any] interface {
	proto.Message
	*T
}

type RaccoonSchema 

type RaccoonSchema[Edg Edge[N], N any] struct {
	Indexes    []SecondaryIndex[Edg, N]
	Store      KVStore
	KeysPrefix []byte
	Keyer      NodeKeyer[N]
	Marshaler  Marshaler[Edg]
}

Raccoon Store schema

type RaccoonStore 

type RaccoonStore[Edg Edge[N], N any] struct {
	// contains filtered or unexported fields
}

RaccoonStore is a general purpose Graph store. It's built on top of a kv-store backend and provides common operations required while working with graphs.

RaccoonStore has a lightweight secondary indexing framework, which can be used to optimize recurring access patterns.

The main RaccoonStore type is a lightweight orchestrator on top of the primary index store and additional secondary index stores.

TODO Make these atomic

func NewRaccoonStore 

func NewRaccoonStore[Edg Edge[N], N any](schema RaccoonSchema[Edg, N]) RaccoonStore[Edg, N]

Build a Raccoon instance from a schema definition

func (*RaccoonStore[Edg, N]) Delete 

func (s *RaccoonStore[Edg, N]) Delete(edg Edg) error

Delete edg from the persistent storage

func (*RaccoonStore[Edg, N]) FilterByIdx 

func (s *RaccoonStore[Edg, N]) FilterByIdx(idxName string, value []byte, predicate Predicate[Edg]) ([]Edg, error)

Filter and return all Edges from index idxName, indexed by value that match the given predicate

func (*RaccoonStore[Edg, N]) Get 

func (s *RaccoonStore[Edg, N]) Get(source, dest N) (Option[Edg], error)

Fetch and Edge from the source and destiniation nodes

func (*RaccoonStore[Edg, N]) GetAncestors 

func (s *RaccoonStore[Edg, N]) GetAncestors(node N) ([]Edg, error)

Return the direct ancestors of a Node, that is, returns all edges that have node as dest. Note: Does not recursively fetch Ancestors

func (*RaccoonStore[Edg, N]) GetByIdx 

func (s *RaccoonStore[Edg, N]) GetByIdx(idxName string, value []byte) ([]Edg, error)

Fetch all Edges from index idxName indexed by value

func (*RaccoonStore[Edg, N]) GetSucessors 

func (s *RaccoonStore[Edg, N]) GetSucessors(node N) ([]Edg, error)

Return all direct sucessors of a Node, that is, returns all edges that have node as source. Note: Does not recursively fetch Ancestors

func (*RaccoonStore[Edg, N]) List 

func (s *RaccoonStore[Edg, N]) List() ([]Edg, error)

List returns all Edges in RaccoonStore

func (*RaccoonStore[Edg, N]) Set 

func (s *RaccoonStore[Edg, N]) Set(edg Edg) error

Set an Edge

type SecondaryIdxKeyer 

type SecondaryIdxKeyer[Edg Edge[N], N any] struct {
	// contains filtered or unexported fields
}

func NewSecIdxKeyer 

func NewSecIdxKeyer[Edg Edge[N], N any](keyer NodeKeyer[N], mapper Mapper[Edg], idxName string, prefix []byte) SecondaryIdxKeyer[Edg, N]

func (*SecondaryIdxKeyer[Edg, N]) IterKeys 

func (k *SecondaryIdxKeyer[Edg, N]) IterKeys(idx []byte) (Key, Key)

func (*SecondaryIdxKeyer[Edg, N]) Key 

func (k *SecondaryIdxKeyer[Edg, N]) Key(edg Edg) Key

Return key for a record Format: /{prefix}/{idxName}/{val}/{recordKey}

type SecondaryIndex 

type SecondaryIndex[Edg Edge[N], N any] struct {
	Name   string
	Mapper Mapper[Edg]
}

Secondary Index schema definition Specifies the index name and a mapper function.

type SecondaryIndexStore 

type SecondaryIndexStore[Edg Edge[N], N any] struct {
	// contains filtered or unexported fields
}

Store Wrapper for records indexed by a certain field Keys in store have the pattern: {prefix}/{indexName}/{mappedValue}/{edgeKey}

func NewSecondaryIdxStore 

func NewSecondaryIdxStore[Edg Edge[N], N any](store KVStore, prefix []byte, indexName string, keyer NodeKeyer[N], mapper Mapper[Edg], marshaler Marshaler[Edg]) SecondaryIndexStore[Edg, N]

func (*SecondaryIndexStore[Edg, N]) Delete 

func (s *SecondaryIndexStore[Edg, N]) Delete(edg Edg) error

func (*SecondaryIndexStore[Edg, N]) FilterByIdx 

func (s *SecondaryIndexStore[Edg, N]) FilterByIdx(idx []byte, predicate Predicate[Edg]) ([]Edg, error)

func (*SecondaryIndexStore[Edg, N]) GetByIdx 

func (s *SecondaryIndexStore[Edg, N]) GetByIdx(idx []byte) ([]Edg, error)

func (*SecondaryIndexStore[Edg, N]) Set 

func (s *SecondaryIndexStore[Edg, N]) Set(edg Edg) error

type TypePointer 

type TypePointer[T any] interface {
	*T
}

type UndirectedEdge 

type UndirectedEdge[Node any] interface {
	Edge[Node]
}

UndirectedEdge specialization of an Edge.

type WrapperKV 

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

WrapperKV implements raccoon's KVStore to a KVStore by wrapping its methods with a global prefix

func (*WrapperKV) Delete 

func (kv *WrapperKV) Delete(key []byte) error

func (*WrapperKV) Get 

func (kv *WrapperKV) Get(key []byte) ([]byte, error)

func (*WrapperKV) Has 

func (kv *WrapperKV) Has(key []byte) (bool, error)

func (*WrapperKV) Iterator 

func (kv *WrapperKV) Iterator(start, end []byte) Iterator

func (*WrapperKV) Set 

func (kv *WrapperKV) Set(key, value []byte) error

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.