sharedforeststore

package module
v0.0.0-...-651ff77 Latest Latest
Warning

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

Go to latest
Published: Aug 3, 2020 License: Apache-2.0 Imports: 16 Imported by: 0

README

Shared Forest Store

A high level content store for IPFS.

Problem Statement

The block datastore garbage collection problem

The default IPFS implementation uses pinning to keep track of what data to keep. It works similarity to how garbage collection works for heap allocation in memory managed programing languages. Superficially, this is a solved problem. But, just like how memory GC cycle slows down as heap grows, datastore GC also becomes unbearably slow for large IPFS deployments. (TODO: citation needed)

Initial Solution: pinning by reference counting

postables implemented a much faster alternative to pinning by counting the number of puts and deletes over a Blockstore interface.s

Although that solution largely alleviated the slowdown, it exposed a few problems with the approach:

  • A counter needs granted once delivery, which can not be dependent up on in RPC calls.
  • Blockstore is too low level to manage recursive references internally, this blocks some efficiency improvements and API simplification.

Solution

Shared Forest Store offers a collection of high level, idempotent, content store that combines the features of Pinner and Blockstore to create a "pinned" block store. It is design to be convent to use in an network facing, multiuser service.

Technical Design
Transactional Data Store

Both pinning metadata and block store operations are grouped into a single transaction. This offers true concurrency without locking and the database will never be in an inconsistent state. Any failed transition commits are retried automatically until either success or context cancellation.

Tagging is for Sharing

Tagging can be considered a keyed counter store, where each add is associated with a unique key. This not only offers idempotent operations, but by protecting the keys, users can share a single duplicating data store. For example, users could prefix their tags with a hash of the user's private key. By keeping this hash private, users can not delete each other's contents without any additional server side content protection logic.

Counting is for Speed

Where the additional features offered by tagging is unnecessary, counting is both faster and easier to use.

The CounterStore interface is primarily designed to aid in the transition from our internal counter store to this code base.

Counting is also an optional implementation for the internal references of a TagStore. Counting uses less metadata to keep track of internal references, while tagging offers more debugging keepabilities and quick reverse look up of why each block is needed.

Choose Between Single Transaction or Progressive

This content store library offers two transactional options when adding contents.

  • Single Transaction: where blocks of an IPLD graph are either all saved or none at all.
  • Progressive: where partial uploads are saved.

Single transaction is better for locally available content and cases where partial adds can't be managed.

Progressive upload allows splitting the commit of an add operation into committing of individual blocks and associated metadata. The progress of an add can also be reported.

Documentation

Index

Constants

This section is empty.

Variables

View Source
var ErrProgressReverted = errors.New("progress was reverted by an other action")
View Source
var ErrRunOnce = errors.New("progress can only run once")
View Source
var ErrSizeNotSupported = errors.New("size not supported")

Functions

func LinkDecoder

func LinkDecoder(id cid.Cid, data []byte) ([]cid.Cid, uint64, error)

LinkDecoder is the default function for DatabaseOptions.LinkDecoder. It decodes the required links for some common codecs. Total size returned is zero if not decodable.

Types

type BlockGetter

type BlockGetter interface {
	//GetBlock is equivalent to Blockstore.Get
	GetBlock(context.Context, cid.Cid) ([]byte, error)
}

BlockGetter returns the raw data referred to by cid. There are two use cases for BlockGetter: as a shared interface of all stores, and as a callback handler to provide the raw data only when needed.

type CidIterator

type CidIterator interface {
	//NextCid returns the next cid or io.EOF if the end is reached
	NextCid() (cid.Cid, error)
	//Close releases the resources used by this iterator for early exist
	Close() error
}

CidIterator is an iterator of cids.

type CodecNotSupportedError

type CodecNotSupportedError struct {
	Cid cid.Cid
}

func (*CodecNotSupportedError) Error

func (e *CodecNotSupportedError) Error() string

type Counted

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

func NewCountedStore

func NewCountedStore(ds datastore.TxnDatastore, opt *DatabaseOptions) *Counted

NewCountedStore creates a new Counted (implements CounterStore) from a transactional datastore.

func (*Counted) Decrement

func (c *Counted) Decrement(ctx context.Context, id cid.Cid) (count int64, err error)

func (*Counted) GetBlock

func (c *Counted) GetBlock(ctx context.Context, id cid.Cid) ([]byte, error)

func (*Counted) GetBlockSize

func (c *Counted) GetBlockSize(ctx context.Context, id cid.Cid) (int, error)

func (*Counted) GetCount

func (c *Counted) GetCount(ctx context.Context, id cid.Cid) (count int64, err error)

func (*Counted) Increment

func (c *Counted) Increment(ctx context.Context, id cid.Cid, bg BlockGetter) (count int64, err error)

func (*Counted) KeysIterator

func (c *Counted) KeysIterator(prefix string) CidIterator

type CounterStore

type CounterStore interface {
	ReadStore
	//Decrement is equivalent to Blockstore.DeleteBlock.
	//Decrement is recursive if count hits 0.
	//If count >= 0, the reference counter got decreased by one.
	//If count == 0, the block referred to by cid is deleted.
	//If count == -1, the block referred to by cid does not exits
	// or was already deleted.
	//If err != nil, the operation failed and count should be ignored.
	Decrement(context.Context, cid.Cid) (int64, error)
	//GetCount is equivalent to Blockstore.Has.
	//The count could have changed by the time the function returned.
	//So it should not be used for decision making in a concurrent use case.
	GetCount(context.Context, cid.Cid) (int64, error)
	//Increment is equivalent to Blockstore.Put with recursive increment
	// for linked contents. The recursion only happens when count is
	// increased from 0 to 1.
	//The BlockGetter is responsible for providing any missing blocks during recursion.
	//If the BlockGetter returned any errors, an error is returned and no
	// count is modified.
	Increment(context.Context, cid.Cid, BlockGetter) (int64, error)
}

CounterStore is a recursively counted BlockStore. When incrementing a counter, if it increased from 0 to 1, then the raw data is saved from BlockGetter and increment is called recursively to all the linked blocks.

Given the following linked graph:
    A -> C -> D
    B -> C -> D
And the following increment operations:
    A, B, C, A
The result count will be:
    A:2, B:1, C:3, D:1
This can be interpreted as:
    A is added twice.
    B is added once.
    C is added once, and required by two other blocks, A and B, for a total count of 3
    D is only required by C.
As you can see, the order of increments does not matter.

Decrement removes the result of one increment.

type DatabaseOptions

type DatabaseOptions struct {
	LinkDecoder LinkDecoderFunc
}

type LinkDecoderFunc

type LinkDecoderFunc func(cid.Cid, []byte) ([]cid.Cid, uint64, error)

LinkDecoderFunc is a function that decodes a raw data according to cid to return linked cids. It also returns the total size of all contents in bytes if availed.

type ProgressManager

type ProgressManager interface {
	//Run is blocking until the progress finishes.
	Run(context.Context) error
	//CopyReport fill the given report with current status without allocating heap.
	CopyReport(*ProgressReport) error
}

ProgressManager handles running and reporting on a progress.

var ProgressCompleted ProgressManager = (*StoreProgressManager)(nil)

ProgressCompleted is a typed nil of *StoreProgressManager to indicate there is no progress to track

type ProgressReport

type ProgressReport struct {

	//HaveBytes is the amount of bytes we know we have
	HaveBytes uint64
	//KnownBytes is the amount of bytes we need
	KnownBytes uint64
	// contains filtered or unexported fields
}

ProgressReport reports progress for one cid's dependents. If KnownBytes is not 0, then ( HaveBytes ÷ KnownBytes ) is an estimated progress. The HaveBytes values are pessimistic as more existing dependents could already exist. KnownBytes is only available if the data operated on contains this metadata.

type ProgressiveCounted

type ProgressiveCounted struct {
	Counted
}

func NewProgressiveCountedStore

func NewProgressiveCountedStore(ds datastore.TxnDatastore, opt *DatabaseOptions) *ProgressiveCounted

NewProgressiveCountedStore creates a new ProgressiveCounted (implements ProgressiveCounterStore) from a transactional datastore.

func (*ProgressiveCounted) GetProgressReport

func (c *ProgressiveCounted) GetProgressReport(ctx context.Context, id cid.Cid, r *ProgressReport) error

func (*ProgressiveCounted) ProgressiveContinue

func (c *ProgressiveCounted) ProgressiveContinue(ctx context.Context, id cid.Cid, bg BlockGetter) ProgressManager

func (*ProgressiveCounted) ProgressiveIncrement

func (c *ProgressiveCounted) ProgressiveIncrement(ctx context.Context, id cid.Cid, bg BlockGetter) (ProgressManager, int64, error)

type ProgressiveCounterStore

type ProgressiveCounterStore interface {
	CounterStore
	//ProgressiveIncrement first increases the counter, and only returns a ProgressManager with count and nil error
	//if increased count is committed. To continue with the rest of the progress, ProgressManager.Run() must be called
	ProgressiveIncrement(context.Context, cid.Cid, BlockGetter) (ProgressManager, int64, error)
	//ProgressiveContinue is ProgressiveIncrement without the increment to continue a previous partial ProgressiveIncrement.
	ProgressiveContinue(context.Context, cid.Cid, BlockGetter) ProgressManager
	//GetProgressReport reports the progress for a cid
	GetProgressReport(context.Context, cid.Cid, *ProgressReport) error
}

ProgressiveCounterStore is a CounterStore that allows partial uploads

type ProgressiveTagCounted

type ProgressiveTagCounted struct {
	TagCounted
}

ProgressiveTagCounted supports both ProgressiveTagStore and ProgressiveCounterStore interfaces. It is backed by CounterStore and shares its counters.

func NewProgressiveTagCountedStore

func NewProgressiveTagCountedStore(db datastore.TxnDatastore, opt *DatabaseOptions) *ProgressiveTagCounted

NewProgressiveTagCountedStore creates a new ProgressiveTagCounted from a transactional datastore.

func (*ProgressiveTagCounted) GetProgressReport

func (c *ProgressiveTagCounted) GetProgressReport(ctx context.Context, id cid.Cid, r *ProgressReport) error

func (*ProgressiveTagCounted) ProgressiveContinue

func (c *ProgressiveTagCounted) ProgressiveContinue(ctx context.Context, id cid.Cid, bg BlockGetter) ProgressManager

func (*ProgressiveTagCounted) ProgressiveIncrement

func (c *ProgressiveTagCounted) ProgressiveIncrement(ctx context.Context, id cid.Cid, bg BlockGetter) (ProgressManager, int64, error)

func (*ProgressiveTagCounted) ProgressivePutTag

func (c *ProgressiveTagCounted) ProgressivePutTag(ctx context.Context, id cid.Cid, tag datastore.Key, bg BlockGetter) ProgressManager

type ProgressiveTagCounterStore

type ProgressiveTagCounterStore interface {
	ProgressiveTagStore
	ProgressiveCounterStore
}

ProgressiveTagCounterStore combines the features of both ProgressiveTagStore and ProgressiveCounterStore.

type ProgressiveTagStore

type ProgressiveTagStore interface {
	TagStore
	//ProgressivePutTag return the ProgressManager for adding a tag, nothing is done until ProgressManager.Run() is called
	ProgressivePutTag(context.Context, cid.Cid, datastore.Key, BlockGetter) ProgressManager
	//GetProgressReport reports the progress for a cid
	GetProgressReport(context.Context, cid.Cid, *ProgressReport) error
}

ProgressiveTagStore is a TagStore that allows partial uploads

type ReadStore

type ReadStore interface {
	BlockGetter
	//GetBlockSize is equivalent to Blockstore.GetSize
	GetBlockSize(context.Context, cid.Cid) (int, error)
	//KeysIterator replaces Blockstore.AllKeysChan.
	KeysIterator(prefix string) CidIterator
}

ReadStore is the base interface for CounterStore and TagStore

type StoreProgressManager

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

StoreProgressManager implements ProgressManager

func (*StoreProgressManager) CopyReport

func (m *StoreProgressManager) CopyReport(r *ProgressReport) error

func (*StoreProgressManager) Run

type TagCounted

type TagCounted struct {
	Counted
}

TagCounted supports both TagStore and CounterStore interfaces. It is backed by a CounterStore and shares its counters.

func NewTagCountedStore

func NewTagCountedStore(db datastore.TxnDatastore, opt *DatabaseOptions) *TagCounted

NewTagCountedStore creates a new TagCounted from a transactional datastore.

func (*TagCounted) GetTags

func (c *TagCounted) GetTags(ctx context.Context, id cid.Cid) ([]datastore.Key, error)

func (*TagCounted) HasTag

func (c *TagCounted) HasTag(ctx context.Context, id cid.Cid, tag datastore.Key) (bool, error)

func (*TagCounted) PutTag

func (c *TagCounted) PutTag(ctx context.Context, id cid.Cid, tag datastore.Key, bg BlockGetter) error

func (*TagCounted) RemoveTag

func (c *TagCounted) RemoveTag(ctx context.Context, id cid.Cid, tag datastore.Key) error

type TagCounterStore

type TagCounterStore interface {
	TagStore
	CounterStore
}

TagCounterStore combines the features of both TagStore and CounterStore.

type TagStore

type TagStore interface {
	ReadStore
	//PutTag adds a tag to contents referenced by the given cid.
	PutTag(context.Context, cid.Cid, datastore.Key, BlockGetter) error
	//HasTag returns if the cid is tagged with a key.
	HasTag(context.Context, cid.Cid, datastore.Key) (bool, error)
	//GetTags list tags on the cid, for administrative and debugging.
	//This function should be hidden from public facing APIs to make tags secret.
	GetTags(context.Context, cid.Cid) ([]datastore.Key, error)
	//RemoveTag removes a tag set on the cid, the contents are also removed
	//if there are no tags left.
	RemoveTag(context.Context, cid.Cid, datastore.Key) error
}

TagStore is an extension of CounterStore where the count is replaced by a set of tags. At the cost of increased metadata size, this allows each operation to be idempotent, and therefor safe to user over an undependable network connection. The tag can also be used for debugging and easily finding out who pinned which file.

type Tx

type Tx struct {
	context.Context
	// contains filtered or unexported fields
}

Tx is a datastore transaction where all actions are group in to a single transaction.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL