Documentation
¶
Overview ¶
Package cache provides subtree caching functionality.
Index ¶
- func PopulateLogSubtreeNodes(treeHasher merkle.TreeHasher) storage.PopulateSubtreeFunc
- func PopulateMapSubtreeNodes(treeHasher merkle.TreeHasher) storage.PopulateSubtreeFunc
- func PrepareLogSubtreeWrite() storage.PrepareSubtreeWriteFunc
- func PrepareMapSubtreeWrite() storage.PrepareSubtreeWriteFunc
- type GetSubtreeFunc
- type GetSubtreesFunc
- type MockNodeStorage
- type NodeStorage
- type SetSubtreesFunc
- type SubtreeCache
- func (s *SubtreeCache) Flush(setSubtrees SetSubtreesFunc) error
- func (s *SubtreeCache) GetNodeHash(id storage.NodeID, getSubtree GetSubtreeFunc) ([]byte, error)
- func (s *SubtreeCache) GetNodes(ids []storage.NodeID, getSubtrees GetSubtreesFunc) ([]storage.Node, error)
- func (s *SubtreeCache) SetNodeHash(id storage.NodeID, h []byte, getSubtree GetSubtreeFunc) error
- type Suffix
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func PopulateLogSubtreeNodes ¶
func PopulateLogSubtreeNodes(treeHasher merkle.TreeHasher) storage.PopulateSubtreeFunc
PopulateLogSubtreeNodes re-creates a Log subtree's InternalNodes from the subtree Leaves map.
This uses the CompactMerkleTree to repopulate internal nodes, and so will handle imperfect (but left-hand dense) subtrees. Note that we only rebuild internal nodes when the subtree is fully populated. For an explanation of why see the comments below for PrepareLogSubtreeWrite.
func PopulateMapSubtreeNodes ¶
func PopulateMapSubtreeNodes(treeHasher merkle.TreeHasher) storage.PopulateSubtreeFunc
PopulateMapSubtreeNodes re-creates Map subtree's InternalNodes from the subtree Leaves map.
This uses HStar2 to repopulate internal nodes.
func PrepareLogSubtreeWrite ¶
func PrepareLogSubtreeWrite() storage.PrepareSubtreeWriteFunc
PrepareLogSubtreeWrite prepares a log subtree for writing. If the subtree is fully populated the internal nodes are cleared. Otherwise they are written.
To see why this is necessary consider the case where a tree has a single full subtree and then an additional leaf is added.
This causes an extra level to be added to the tree with an internal node that is a hash of the root of the left full subtree and the new leaf. Note that the leaves remain at level zero in the overall tree coordinate space but they are now in a lower subtree stratum than they were before the last node was added as the tree has grown above them.
Thus in the case just discussed the internal nodes cannot be correctly reconstructed in isolation when the tree is reloaded because of the dependency on another subtree.
Fully populated subtrees don't have this problem because by definition they can only contain internal nodes built from their own contents.
func PrepareMapSubtreeWrite ¶
func PrepareMapSubtreeWrite() storage.PrepareSubtreeWriteFunc
PrepareMapSubtreeWrite prepares a map subtree for writing. For maps the internal nodes are never written to storage and are thus always cleared.
Types ¶
type GetSubtreeFunc ¶
type GetSubtreeFunc func(id storage.NodeID) (*storagepb.SubtreeProto, error)
GetSubtreeFunc describes a function which can return a Subtree from storage.
type GetSubtreesFunc ¶
type GetSubtreesFunc func(ids []storage.NodeID) ([]*storagepb.SubtreeProto, error)
GetSubtreesFunc describes a function which can return a number of Subtrees from storage.
type MockNodeStorage ¶
type MockNodeStorage struct {
// contains filtered or unexported fields
}
Mock of NodeStorage interface
func NewMockNodeStorage ¶
func NewMockNodeStorage(ctrl *gomock.Controller) *MockNodeStorage
func (*MockNodeStorage) EXPECT ¶
func (_m *MockNodeStorage) EXPECT() *_MockNodeStorageRecorder
func (*MockNodeStorage) GetSubtree ¶
func (_m *MockNodeStorage) GetSubtree(_param0 storage.NodeID) (*storagepb.SubtreeProto, error)
func (*MockNodeStorage) SetSubtrees ¶
func (_m *MockNodeStorage) SetSubtrees(_param0 []*storagepb.SubtreeProto) error
type NodeStorage ¶
type NodeStorage interface {
GetSubtree(n storage.NodeID) (*storagepb.SubtreeProto, error)
SetSubtrees(s []*storagepb.SubtreeProto) error
}
NodeStorage provides an interface for storing and retrieving subtrees.
type SetSubtreesFunc ¶
type SetSubtreesFunc func(s []*storagepb.SubtreeProto) error
SetSubtreesFunc describes a function which can store a collection of Subtrees into storage.
type SubtreeCache ¶
type SubtreeCache struct {
// contains filtered or unexported fields
}
SubtreeCache provides a caching access to Subtree storage. Currently there are assumptions in the code that all subtrees are multiple of 8 in depth and that log subtrees are always of depth 8. It is not possible to just change the constants above and have things still work. This is because of issues like byte packing of node IDs.
func NewSubtreeCache ¶
func NewSubtreeCache(strataDepths []int, populateSubtree storage.PopulateSubtreeFunc, prepareSubtreeWrite storage.PrepareSubtreeWriteFunc) SubtreeCache
NewSubtreeCache returns a newly intialised cache ready for use. populateSubtree is a function which knows how to populate a subtree's internal nodes given its leaves, and will be called for each subtree loaded from storage. TODO(al): consider supporting different sized subtrees - for now everything's subtrees of 8 levels.
func (*SubtreeCache) Flush ¶
func (s *SubtreeCache) Flush(setSubtrees SetSubtreesFunc) error
Flush causes the cache to write all dirty Subtrees back to storage.
func (*SubtreeCache) GetNodeHash ¶
func (s *SubtreeCache) GetNodeHash(id storage.NodeID, getSubtree GetSubtreeFunc) ([]byte, error)
GetNodeHash returns a single node hash from the cache.
func (*SubtreeCache) GetNodes ¶
func (s *SubtreeCache) GetNodes(ids []storage.NodeID, getSubtrees GetSubtreesFunc) ([]storage.Node, error)
GetNodes returns the requested nodes, calling the getSubtrees function if they are not already cached.
func (*SubtreeCache) SetNodeHash ¶
func (s *SubtreeCache) SetNodeHash(id storage.NodeID, h []byte, getSubtree GetSubtreeFunc) error
SetNodeHash sets a node hash in the cache.
Source Files