mutable_forest.go

package storage

import (
	"fmt"

	dbm "github.com/tendermint/tendermint/libs/db"
)

const (
	commitsPrefix = "c"
	treePrefix    = "t"
)

type ForestReader interface {
	Reader(prefix []byte) (KVCallbackIterableReader, error)
}

// MutableForest is a collection of versioned lazily-loaded RWTrees organised by prefix. It maintains a global state hash
// by storing CommitIDs in a special commitsTree (you could think of it is a two-layer single tree rather than a forest).
//
// The trees (or sub-trees if you prefer) in the forest are RWTrees which wrap an IAVL MutableTree routing writes to the
// MutableTree and reads to the last saved ImmutableTree. In this way reads act only against committed state and can be
// lock free (this allows us to avoid blocking commits - particularly for long-running iterations).
//
// The trees in the forest are created lazily as required by new writes. There is a cache of most recently used trees
// and trees that may require a save are marked as such. New writes are only available to read after a Save().
//
// Here is an example forest (the output is generated by the Dump() function):
//  .
//  ├── balances
//  │   ├── Caitlin -> 2344
//  │   ├── Cora -> 654456
//  │   ├── Edward -> 34
//  │   └── Lindsay -> 654
//  └── names
//      ├── Caitlin -> female
//      ├── Cora -> female
//      ├── Edward -> male
//      └── Lindsay -> unisex
//
// Here there are two tree indexed by the prefixes 'balances' and 'names'.
//
// To perform reads of the forest we access it in the following way:
//
//   tree, err := forest.Reader("names")
//   gender := tree.Get("Cora")
//
// To perform writes:
//
//   tree, err := forest.Writer("names")
//   tree.Set("Cora", "unspecified")
//
// If there is no tree currently stored at the prefix passed then it will be created when the forest is saved:
//
//  hash, version, err := forest.Save()
//
// where the global version for the forest is returned.

type MutableForest struct {
	// A tree containing a reference for all contained trees in the form of prefix -> CommitID
	commitsTree *RWTree
	*ImmutableForest
	// Map of prefix -> tree for trees that may require a save (but only will be if they have actually been updated)
	dirty map[string]*RWTree
	// List of dirty prefixes in deterministic order so we may loop over them on Save() and obtain a consistent commitTree hash
	dirtyPrefixes []string
}

func NewMutableForest(db dbm.DB, cacheSize int) (*MutableForest, error) {
	tree := NewRWTree(NewPrefixDB(db, commitsPrefix), cacheSize)
	forest, err := NewImmutableForest(tree, NewPrefixDB(db, treePrefix), cacheSize, WithOverwriting)
	if err != nil {
		return nil, err
	}
	return &MutableForest{
		ImmutableForest: forest,
		commitsTree:     tree,
		dirty:           make(map[string]*RWTree),
	}, nil
}

// Load mutable forest from database, pass overwriting = true if you wish to make writes to version version + 1.
// this will
func (muf *MutableForest) Load(version int64) error {
	return muf.commitsTree.Load(version, true)
}

func (muf *MutableForest) Save() ([]byte, int64, error) {
	// Save each tree in forest that requires save
	for _, prefix := range muf.dirtyPrefixes {
		tree := muf.dirty[prefix]
		if tree.Updated() {
			err := muf.saveTree([]byte(prefix), tree)
			if err != nil {
				return nil, 0, err
			}
		}
	}
	// empty dirty cache
	muf.dirty = make(map[string]*RWTree, len(muf.dirty))
	muf.dirtyPrefixes = muf.dirtyPrefixes[:0]
	return muf.commitsTree.Save()
}

func (muf *MutableForest) GetImmutable(version int64) (*ImmutableForest, error) {
	commitsTree, err := muf.commitsTree.GetImmutable(version)
	if err != nil {
		return nil, fmt.Errorf("MutableForest.GetImmutable() could not get commits tree for version %d: %v",
			version, err)
	}
	return NewImmutableForest(commitsTree, muf.treeDB, muf.cacheSize)
}

// Calls to writer should be serialised as should writes to the tree
func (muf *MutableForest) Writer(prefix []byte) (*RWTree, error) {
	// Try dirty cache first (if tree is new it may only be in this location)
	prefixString := string(prefix)
	if tree, ok := muf.dirty[prefixString]; ok {
		return tree, nil
	}
	tree, err := muf.tree(prefix)
	if err != nil {
		return nil, err
	}
	// Mark tree as dirty
	muf.dirty[prefixString] = tree
	muf.dirtyPrefixes = append(muf.dirtyPrefixes, prefixString)
	return tree, nil
}

// Delete a tree - if the tree exists will return the CommitID of the latest saved version
func (muf *MutableForest) Delete(prefix []byte) (*CommitID, error) {
	bs, removed := muf.commitsTree.Delete(prefix)
	if !removed {
		return nil, nil
	}
	return UnmarshalCommitID(bs)
}

// Get the current global hash for all trees in this forest
func (muf *MutableForest) Hash() []byte {
	return muf.commitsTree.Hash()
}

// Get the current global version for all versions of all trees in this forest
func (muf *MutableForest) Version() int64 {
	return muf.commitsTree.Version()
}

func (muf *MutableForest) saveTree(prefix []byte, tree *RWTree) error {
	hash, version, err := tree.Save()
	if err != nil {
		return fmt.Errorf("MutableForest.saveTree() could not save tree: %v", err)
	}
	return muf.setCommit(prefix, hash, version)
}

func (muf *MutableForest) setCommit(prefix, hash []byte, version int64) error {
	bs, err := MarshalCommitID(hash, version)
	if err != nil {
		return fmt.Errorf("MutableForest.setCommit() could not marshal CommitID: %v", err)
	}
	muf.commitsTree.Set([]byte(prefix), bs)
	return nil
}