posting

package
v1.0.3 Latest Latest
Warning

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

 Go to latest Published: Feb 7, 2018 License: AGPL-3.0, Apache-2.0 Imports: 33 Imported by: 178

Documentation

Overview

Package btree implements in-memory B-Trees of arbitrary degree.

btree implements an in-memory B-Tree for use as an ordered data structure. It is not meant for persistent storage solutions.

It has a flatter structure than an equivalent red-black or other binary tree, which in some cases yields better memory usage and/or performance. See some discussion on the matter here: 

http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html

Note, though, that this project is in no way related to the C++ B-Tree implementation written about there.

Within this tree, each node contains a slice of items and a (possibly nil) slice of children. For basic numeric values or raw structs, this can cause efficiency differences when compared to equivalent C++ template code that stores values in arrays within the node:

  • Due to the overhead of storing values as interfaces (each value needs to be stored as the value itself, then 2 words for the interface pointing to that value and its type), resulting in higher memory use.
  • Since interfaces can point to values anywhere in memory, values are most likely not stored in contiguous blocks, resulting in a higher number of cache misses.

These issues don't tend to matter, though, when working with strings or other heap-allocated structures, since C++-equivalent structures also must store pointers and also distribute their values across the heap.

This implementation is designed to be a drop-in replacement to gollrb.LLRB trees, (http://github.com/petar/gollrb), an excellent and probably the most widely used ordered tree implementation in the Go ecosystem currently. Its functions, therefore, exactly mirror those of llrb.LLRB where possible. Unlike gollrb, though, we currently don't support storing multiple equivalent values.

  • Copyright (C) 2017 Dgraph Labs, Inc. and Contributors *
  • This program is free software: you can redistribute it and/or modify
  • it under the terms of the GNU Affero General Public License as published by
  • the Free Software Foundation, either version 3 of the License, or
  • (at your option) any later version. *
  • This program is distributed in the hope that it will be useful,
  • but WITHOUT ANY WARRANTY; without even the implied warranty of
  • MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  • GNU Affero General Public License for more details. *
  • You should have received a copy of the GNU Affero General Public License
  • along with this program. If not, see <http://www.gnu.org/licenses/>.

Package posting takes care of posting lists. It contains logic for mutation layers, merging them with BadgerDB, etc.

Package lru implements an LRU cache.

Index

Constants

View Source 
const (
	// Set means overwrite in mutation layer. It contributes 0 in Length.
	Set uint32 = 0x01
	// Del means delete in mutation layer. It contributes -1 in Length.
	Del uint32 = 0x02

	// Metadata Bit which is stored to find out whether the stored value is pl or byte slice.
	BitUidPosting byte = 0x01

	BitCompletePosting byte = 0x08
	BitEmptyPosting    byte = 0x10 | BitCompletePosting
)
View Source 
const (
	MB = 1 << 20
)

Variables

View Source 
var (
	// ErrRetry can be triggered if the posting list got deleted from memory due to a hard commit.
	// In such a case, retry.
	ErrRetry = fmt.Errorf("Temporary Error. Please retry.")
	// ErrNoValue would be returned if no value was found in the posting list.
	ErrNoValue    = fmt.Errorf("No value found")
	ErrInvalidTxn = fmt.Errorf("Invalid transaction")
)
View Source 
var (
	ErrTsTooOld = x.Errorf("Transaction is too old")
)

Functions

func Cleanup added in v1.0.1 

func Cleanup()

func CommitLists added in v0.7.0 

func CommitLists(commit func(key []byte) bool)

func DeleteAll added in v0.8.3 

func DeleteAll() error

func DeleteCountIndex added in v0.8.2 

func DeleteCountIndex(ctx context.Context, attr string) error

func DeleteIndex added in v0.8.2 

func DeleteIndex(ctx context.Context, attr string) error

func DeletePredicate added in v0.8.2 

func DeletePredicate(ctx context.Context, attr string) error

func DeleteReverseEdges added in v0.8.2 

func DeleteReverseEdges(ctx context.Context, attr string) error

func EvictLRU added in v0.8.3 

func EvictLRU()

This doesn't sync, so call this only when you don't care about dirty posting lists in // memory(for example before populating snapshot) or after calling syncAllMarks

func Init 

func Init(ps *badger.ManagedDB)

Init initializes the posting lists package, the in memory and dirty list hash.

func NewPosting added in v0.8.2 

func NewPosting(t *intern.DirectedEdge) *intern.Posting

func Oracle added in v0.9.0 

func Oracle() *oracle

func RebuildCountIndex added in v0.8.2 

func RebuildCountIndex(ctx context.Context, attr string, startTs uint64)

func RebuildIndex added in v0.7.2 

func RebuildIndex(ctx context.Context, attr string, startTs uint64)

RebuildIndex rebuilds index for a given attribute. We commit mutations with startTs and ignore the errors.

func RebuildListType added in v1.0.3 

func RebuildListType(ctx context.Context, attr string, startTs uint64) error

This function is called when the schema is changed from scalar to list type. We need to fingerprint the values to get the new ValueId.

func RebuildReverseEdges added in v0.8.2 

func RebuildReverseEdges(ctx context.Context, attr string, startTs uint64)

RebuildReverseEdges rebuilds the reverse edges for a given attribute.

func StopLRUEviction added in v0.9.0 

func StopLRUEviction()

func TxnMarks added in v0.9.0 

func TxnMarks() *x.WaterMark

func Txns added in v0.9.0 

func Txns() *transactions

func TypeID added in v0.7.3 

func TypeID(edge *intern.DirectedEdge) types.TypeID

TypeID returns the typeid of destination vertex

func UnmarshalOrCopy added in v0.8.2 

func UnmarshalOrCopy(val []byte, metadata byte, pl *intern.PostingList)

Copies the val if it's uid only posting, be careful

Types

type BTree added in v1.0.0 

type BTree struct {
	x.SafeMutex
	// contains filtered or unexported fields
}

BTree is an implementation of a B-Tree.

BTree stores []byte instances in an ordered structure, allowing easy insertion, removal, and iteration.

Write operations are not safe for concurrent mutation by multiple goroutines, but Read operations are.

func (*BTree) Ascend added in v1.0.0 

func (t *BTree) Ascend(iterator btreeIterator)

Ascend calls the iterator for every value in the tree within the range [first, last], until iterator returns false.

func (*BTree) AscendGreaterOrEqual added in v1.0.0 

func (t *BTree) AscendGreaterOrEqual(pivot []byte, iterator btreeIterator)

AscendGreaterOrEqual calls the iterator for every value in the tree within the range [pivot, last], until iterator returns false.

func (*BTree) Delete added in v1.0.0 

func (t *BTree) Delete(item []byte) []byte

Delete removes an item equal to the passed in item from the tree, returning it. If no such item exists, returns nil.

func (*BTree) DeleteAll added in v1.0.2 

func (t *BTree) DeleteAll()

DeleteAll Resets the btree

func (*BTree) Descend added in v1.0.0 

func (t *BTree) Descend(iterator btreeIterator)

Descend calls the iterator for every value in the tree within the range [last, first], until iterator returns false.

func (*BTree) DescendLessOrEqual added in v1.0.0 

func (t *BTree) DescendLessOrEqual(pivot []byte, iterator btreeIterator)

DescendLessOrEqual calls the iterator for every value in the tree within the range [pivot, first], until iterator returns false.

func (*BTree) Insert added in v1.0.0 

func (t *BTree) Insert(item []byte)

nil cannot be added to the tree (will panic).

type CacheStats added in v0.8.2 

type CacheStats struct {
	Length    int
	Size      uint64
	NumEvicts uint64
}

type List 

type List struct {
	x.SafeMutex
	// contains filtered or unexported fields
}

func Get added in v0.8.2 

func Get(key []byte) (rlist *List)

Get stores the List corresponding to key, if it's not there already. to lru cache and returns it.

plist := Get(key, group) ... // Use plist TODO: This should take a node id and index. And just append all indices to a list. When doing a commit, it should update all the sync index watermarks. worker pkg would push the indices to the watermarks held by lists. And watermark stuff would have to be located outside worker pkg, maybe in x. That way, we don't have a dependency conflict.

func GetLru added in v1.0.0 

func GetLru(key []byte) *List

GetLru checks the lru map and returns it if it exits

func GetNoStore added in v0.8.2 

func GetNoStore(key []byte) (rlist *List)

GetNoStore takes a key. It checks if the in-memory map has an updated value and returns it if it exists or it gets from the store and DOES NOT ADD to lru cache.

func ReadPostingList added in v0.9.0 

func ReadPostingList(key []byte, it *badger.Iterator) (*List, error)

constructs the posting list from the disk using the passed iterator. Use forward iterator with allversions enabled in iter options.

func (*List) AbortTransaction added in v0.9.0 

func (l *List) AbortTransaction(ctx context.Context, startTs uint64) error

func (*List) AddMutation 

func (l *List) AddMutation(ctx context.Context, txn *Txn, t *intern.DirectedEdge) (bool, error)

AddMutation adds mutation to mutation layers. Note that it does not write anything to disk. Some other background routine will be responsible for merging changes in mutation layers to BadgerDB. Returns whether any mutation happens.

func (*List) AddMutationWithIndex added in v0.7.0 

func (l *List) AddMutationWithIndex(ctx context.Context, t *intern.DirectedEdge,
	txn *Txn) error

AddMutationWithIndex is AddMutation with support for indexing. It also supports reverse edges.

func (*List) AllUntaggedValues added in v0.9.3 

func (l *List) AllUntaggedValues(readTs uint64) ([]types.Val, error)

func (*List) AllValues added in v0.8.2 

func (l *List) AllValues(readTs uint64) ([]types.Val, error)

func (*List) AlreadyCommitted added in v0.9.0 

func (l *List) AlreadyCommitted(startTs uint64) bool

func (*List) CommitMutation added in v0.9.0 

func (l *List) CommitMutation(ctx context.Context, startTs, commitTs uint64) error

func (*List) Conflicts added in v0.9.0 

func (l *List) Conflicts(readTs uint64) []uint64

func (*List) EstimatedSize added in v0.8.2 

func (l *List) EstimatedSize() int32

func (*List) Facets added in v0.7.3 

func (l *List) Facets(readTs uint64, param *intern.FacetParams, langs []string) (fs []*api.Facet,
	ferr error)

Facets gives facets for the posting representing value.

func (*List) GetLangTags added in v0.9.3 

func (l *List) GetLangTags(readTs uint64) ([]string, error)

GetLangTags finds the language tags of each posting in the list.

func (*List) IsEmpty added in v1.0.2 

func (l *List) IsEmpty() bool

func (*List) Iterate added in v0.7.0 

func (l *List) Iterate(readTs uint64, afterUid uint64, f func(obj *intern.Posting) bool) error

Iterate will allow you to iterate over this Posting List, while having acquired a read lock. So, please keep this iteration cheap, otherwise mutations would get stuck. The iteration will start after the provided UID. The results would not include this UID. The function will loop until either the Posting List is fully iterated, or you return a false in the provided function, which will indicate to the function to break out of the iteration. 

	pl.Iterate(func(p *intern.Posting) bool {
   // Use posting p
   return true  // to continue iteration.
   return false // to break iteration.
 })

func (*List) Length 

func (l *List) Length(readTs, afterUid uint64) int

Length iterates over the mutation layer and counts number of elements.

func (*List) MarshalToKv added in v0.9.0 

func (l *List) MarshalToKv() (*intern.KV, error)

func (*List) Postings added in v0.8.2 

func (l *List) Postings(opt ListOptions, postFn func(*intern.Posting) bool) error

Postings calls postFn with the postings that are common with uids in the opt ListOptions.

func (*List) SetForDeletion 

func (l *List) SetForDeletion() bool

SetForDeletion will mark this List to be deleted, so no more mutations can be applied to this.

func (*List) SyncIfDirty added in v0.7.2 

func (l *List) SyncIfDirty(delFromCache bool) (committed bool, err error)

func (*List) Uids added in v0.4.3 

func (l *List) Uids(opt ListOptions) (*intern.List, error)

Uids returns the UIDs given some query params. We have to apply the filtering before applying (offset, count). WARNING: Calling this function just to get Uids is expensive

func (*List) Value 

func (l *List) Value(readTs uint64) (rval types.Val, rerr error)

Returns Value from posting list. This function looks only for "default" value (one without language).

func (*List) ValueFor added in v0.8.2 

func (l *List) ValueFor(readTs uint64, langs []string) (rval types.Val, rerr error)

Returns Value from posting list, according to preferred language list (langs). If list is empty, value without language is returned; if such value is not available, value with smallest Uid is returned. If list consists of one or more languages, first available value is returned; if no language from list match the values, processing is the same as for empty list.

func (*List) ValueForTag added in v0.8.2 

func (l *List) ValueForTag(readTs uint64, tag string) (rval types.Val, rerr error)

type ListOptions added in v0.4.3 

type ListOptions struct {
	ReadTs    uint64
	AfterUID  uint64       // Any UID returned must be after this value.
	Intersect *intern.List // Intersect results with this list of UIDs.
}

ListOptions is used in List.Uids (in posting) to customize our output list of UIDs, for each posting list. It should be intern.to this package.

type Options added in v0.8.2 

type Options struct {
	Mu             sync.Mutex
	AllottedMemory float64

	CommitFraction float64
}
var Config Options

type PIterator added in v0.8.2 

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

func (*PIterator) Init added in v0.8.2 

func (it *PIterator) Init(pl *intern.PostingList, afterUid uint64)

func (*PIterator) Next added in v0.8.2 

func (it *PIterator) Next()

func (*PIterator) Posting added in v0.8.2 

func (it *PIterator) Posting() *intern.Posting

func (*PIterator) Valid added in v0.8.2 

func (it *PIterator) Valid() bool

type Txn added in v0.9.0 

type Txn struct {
	StartTs             uint64
	IgnoreIndexConflict bool

	// Fields which can changed after init
	sync.Mutex

	// Stores list of proposal indexes belonging to the transaction, the watermark would
	// be marked as done only when it's committed.
	Indices []uint64
	// contains filtered or unexported fields
}

func (*Txn) AbortMutations added in v0.9.0 

func (tx *Txn) AbortMutations(ctx context.Context) error

func (*Txn) AddDelta added in v0.9.0 

func (t *Txn) AddDelta(key []byte, p *intern.Posting, ignore bool)

func (*Txn) CommitMutations added in v0.9.0 

func (tx *Txn) CommitMutations(ctx context.Context, commitTs uint64) error

Don't call this for schema mutations. Directly commit them.

func (*Txn) CommitMutationsMemory added in v0.9.0 

func (tx *Txn) CommitMutationsMemory(ctx context.Context, commitTs uint64) error

func (*Txn) Fill added in v0.9.0 

func (t *Txn) Fill(ctx *api.TxnContext)

func (*Txn) LastIndex added in v0.9.2 

func (t *Txn) LastIndex() uint64

LastIndex returns the index of last prewrite proposal associated with the transaction.

func (*Txn) SetAbort added in v0.9.0 

func (t *Txn) SetAbort()

func (*Txn) ShouldAbort added in v0.9.0 

func (t *Txn) ShouldAbort() bool

type TxnPrefixIterator added in v1.0.0 

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

func NewTxnPrefixIterator added in v1.0.0 

func NewTxnPrefixIterator(txn *badger.Txn,
	iterOpts badger.IteratorOptions, prefix, key []byte) *TxnPrefixIterator

func (*TxnPrefixIterator) Close added in v1.0.0 

func (t *TxnPrefixIterator) Close()

func (*TxnPrefixIterator) Key added in v1.0.0 

func (t *TxnPrefixIterator) Key() []byte

func (*TxnPrefixIterator) Next added in v1.0.0 

func (t *TxnPrefixIterator) Next()

func (*TxnPrefixIterator) Valid added in v1.0.0 

func (t *TxnPrefixIterator) Valid() bool

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.