README
¶
go-amt-ipld
Array Mapped Trie (Persistent Vector) implementation using go-ipld
This package is a reference implementation of the IPLD AMT used in the Filecoin blockchain.
AMT is an array mapped trie, suitable for storing large arrays, including sparse arrays.
**See https://godoc.org/github.com/filecoin-project/go-amt-ipld for more information and API details
License
Dual MIT and Apache 2
Documentation
¶
Overview ¶
Package amt provides a reference implementation of the IPLD AMT (Array Mapped Trie) used in the Filecoin blockchain.
The AMT algorithm is similar to a HAMT https://en.wikipedia.org/wiki/Hash_array_mapped_trie but instead presents an array-like interface where the indexes themselves form the mapping to nodes in the trie structure. An AMT is suitable for storing sparse array data as a minimum amount of intermediate nodes are required to address a small number of entries even when their indexes span a large distance. AMT is also a suitable means of storing non-sparse array data as required, with a small amount of storage and algorithmic overhead required to handle mapping that assumes that some elements within any range of data may not be present.
Algorithm Overview ¶
The AMT algorithm produces a tree-like graph, with a single root node addressing a collection of child nodes which connect downward toward leaf nodes which store the actual entries. No terminal entries are stored in intermediate elements of the tree, unlike in a HAMT. We can divide up the AMT tree structure into "levels" or "heights", where a height of zero contains the terminal elements, and the maximum height of the tree contains the single root node. Intermediate nodes are used to span across the range of indexes.
Any AMT instance uses a fixed "width" that is consistent across the tree's nodes. An AMT's "bitWidth" dictates the width, or maximum-brancing factor (arity) of the AMT's nodes by determining how many bits of the original index are used to determine the index at any given level. A bitWidth of 3 (the default for this implementation) can generate indexes in the range of 0 to (2^3)-1=7, i.e. a "width" of 8. In practice, this means that an AMT with a bitWidth of 3 has a branching factor of _between 1 and 8_ for any node in the structure.
Considering the minimal case: a minimal AMT contains a single node which serves as both the root and the leaf node and can hold zero or more elements (an empty AMT is possible, although a special-case, and consists of a zero-length root). This minimal AMT can store array indexes from 0 to width-1 (8 for the default bitWidth of 3) without requiring the addition of additional nodes. Attempts to add additional indexes beyond width-1 will result in additional nodes being added and a tree structure in order to address the new elements. The minimal AMT node is said to have a height of 0. Every node in an AMT has a height that indicates its distance from the leaf nodes. All leaf nodes have a height of 0. The height of the root node dictates the overall height of the entire AMT. In the case of the minimal AMT, this is 0.
Elements are stored in a compacted form within nodes, they are "position-mapped" by a bitmap field that is stored with the node. The bitmap is a simple byte array, where each bit represents an element of the data that can be stored in the node. With a width of 8, the bitmap is a single byte and up to 8 elements can be stored in the node. The data array of a node _only stores elements that are present in that node_, so the array is commonly shorter than the maximum width. An empty AMT is a special-case where the single node can have zero elements, therefore a zero-length data array and a bitmap of `0x00`. In all other cases, the data array must have between 1 and width elements.
Determining the position of an index within the data array requires counting the number of set bits within the bitmap up to the element we are concerned with. If the bitmap has bits 2, 4 and 6 set, we can see that only 3 of the bits are set so our data array should hold 3 elements. To address index 4, we know that the first element will be index 2 and therefore the second will hold index 4. This format allows us to store only the elements that are set in the node.
Overflow beyond the single node AMT by adding an index beyond width-1 requires an increase in height in order to address all elements. If an element in the range of width to (width*2)-1 is added, a single additional height is required which will result in a new root node which is used to address two consecutive leaf nodes. Because we have an arity of up to width at any node, the addition of indexes in the range of 0 to (width^2)-1 will still require only the addition of a single additional height above the leaf nodes, i.e. height 1.
From the width of an AMT we can derive the maximum range of indexes that can be contained by an AMT at any given `height` with the formula width^(height+1)-1. e.g. an AMT with a width of 8 and a height of 2 can address indexes 0 to 8^(2+1)-1=511. Incrementing the height doubles the range of indexes that can be contained within that structure.
Nodes above height 0 (non-leaf nodes) do not contain terminal elements, but instead, their data array contains links to child nodes. The index compaction using the bitmap is the same as for leaf nodes, so each non-leaf node only stores as many links as it has child nodes.
Because additional height is required to address larger indexes, even a single-element AMT will require more than one node where the index is greater than the width of the AMT. For a width of 8, indexes 8 to 63 require a height of 1, indexes 64 to 511 require a height of 2, indexes 512 to 4095 require a height of 3, etc.
Retrieving elements from the AMT requires extracting only the portion of the requested index that is required at each height to determine the position in the data array to navigate into. When traversing through the tree, we only need to select from indexes 0 to width-1. To do this, we take log2(width) bits from the index to form a number that is between 0 and width-1. e.g. for a width of 8, we only need 3 bits to form a number between 0 and 7, so we only consume 3 bits per level of the AMT as we traverse. A simple method to calculate this at any height in the AMT (assuming bitWidth of 3, i.e. a width of 8) is:
1. Calculate the maximum number of nodes (not entries) that may be present in an sub-tree rooted at the current height. width^height provides this number. e.g. at height 0, only 1 node can be present, but at height 3, we may have a tree of up to 512 nodes (storing up to 8^(3+1)=4096 entries).
2. Divide the index by this number to find the index for this height. e.g. an index of 3 at height 0 will be 3/1=3, or an index of 20 at height 1 will be 20/8=2.
3. If we are at height 0, the element we want is at the data index, position-mapped via the bitmap.
4. If we are above height 0, we need to navigate to the child element at the index we calculated, position-mapped via the bitmap. When traversing to the child, we discard the upper portion of the index that we no longer need. This can be achieved by a mod operation against the number-of-nodes value. e.g. an index of 20 at height 1 requires navigation to the element at position 2, when moving to that element (which is height 0), we truncate the index with 20%8=4, at height 0 this index will be the index in our data array (position-mapped via the bitmap).
In this way, each sub-tree root consumes a small slice, log2(width) bits long, of the original index.
Adding new elements to an AMT may require up to 3 steps:
1. Increasing the height to accommodate a new index if the current height is not sufficient to address the new index. Increasing the height requires turning the current root node into an intermediate and adding a new root which links to the old (repeated until the required height is reached).
2. Adding any missing intermediate and leaf nodes that are required to address the new index. Depending on the density of existing indexes, this may require the addition of up to height-1 new nodes to connect the root to the required leaf. Sparse indexes will mean large gaps in the tree that will need filling to address new, equally sparse, indexes.
3. Setting the element at the leaf node in the appropriate position in the data array and setting the appropriate bit in the bitmap.
Removing elements requires a reversal of this process. Any empty node (other than the case of a completely empty AMT) must be removed and its parent should have its child link removed. This removal may recurse up the tree to remove many unnecessary intermediate nodes. The root node may also be removed if the current height is no longer necessary to contain the range of indexes still in the AMT. This can be easily determined if _only_ the first bit of the root's bitmap is set, meaning only the left-most is present, which will become the new root node (repeated until the new root has more than the first bit set or height of 0, the single-node case).
Further Reading ¶
See https://github.com/ipld/specs/blob/master/data-structures/hashmap.md for a description of a HAMT algorithm. And https://github.com/ipld/specs/blob/master/data-structures/vector.md for a description of a similar algorithm to an AMT that doesn't support internal node compression and therefore doesn't support sparse arrays.
Usage Considerations ¶
Unlike a HAMT, the AMT algorithm doesn't benefit from randomness introduced by a hash algorithm. Therefore an AMT used in cases where user-input can influence indexes, larger-than-necessary tree structures may present risks as well as the challenge imposed by having a strict upper-limit on the indexes addressable by the AMT. A width of 8, using 64-bit integers for indexing, allows for a tree height of up to 64/log2(8)=21 (i.e. a width of 8 has a bitWidth of 3, dividing the 64 bits of the uint into 21 separate per-height indexes). Careful placement of indexes could create extremely sub-optimal forms with large heights connecting leaf nodes that are sparsely packed. The overhead of the large number of intermediate nodes required to connect leaf nodes in AMTs that contain high indexes can be abused to create perverse forms that contain large numbers of nodes to store a minimal number of elements.
Minimal nodes will be created where indexes are all in the lower-range. The optimal case for an AMT is contiguous index values starting from zero. As larger indexes are introduced that span beyond the current maximum, more nodes are required to address the new nodes _and_ the existing lower index nodes. Consider a case where a width=8 AMT is only addressing indexes less than 8 and requiring a single height. The introduction of a single index within 8 of the maximum 64-bit unsigned integer range will require the new root to have a height of 21 and have enough connecting nodes between it and both the existing elements and the new upper index. This pattern of behavior may be acceptable if there is significant density of entries under a particular maximum index.
There is a direct relationship between the sparseness of index values and the number of nodes required to address the entries. This should be the key consideration when determining whether an AMT is a suitable data-structure for a given application.
Index ¶
- Constants
- func FromArray(ctx context.Context, bs cbor.IpldStore, vals []cbg.CBORMarshaler, ...) (cid.Cid, error)
- type Change
- type ChangeType
- type Option
- type Root
- func (r *Root) BatchDelete(ctx context.Context, indices []uint64, strict bool) (modified bool, err error)
- func (r *Root) BatchSet(ctx context.Context, vals []cbg.CBORMarshaler) error
- func (r *Root) Clone() *Root
- func (r *Root) Delete(ctx context.Context, i uint64) (bool, error)
- func (r *Root) FirstSetIndex(ctx context.Context) (uint64, error)
- func (r *Root) Flush(ctx context.Context) (cid.Cid, error)
- func (r *Root) ForEach(ctx context.Context, cb func(uint64, *cbg.Deferred) error) error
- func (r *Root) ForEachAt(ctx context.Context, start uint64, cb func(uint64, *cbg.Deferred) error) error
- func (r *Root) Get(ctx context.Context, i uint64, out cbg.CBORUnmarshaler) (bool, error)
- func (r *Root) Len() uint64
- func (r *Root) Set(ctx context.Context, i uint64, val cbg.CBORMarshaler) error
Constants ¶
const MaxIndex = math.MaxUint64 - 1
MaxIndex is the maximum index for elements in the AMT. This MaxUint64-1 so we don't overflow MaxUint64 when computing the length.
Variables ¶
This section is empty.
Functions ¶
func FromArray ¶
func FromArray(ctx context.Context, bs cbor.IpldStore, vals []cbg.CBORMarshaler, opts ...Option) (cid.Cid, error)
FromArray creates a new AMT and performs a BatchSet on it using the vals and options provided. Indexes from the array are used as the indexes for the same values in the AMT.
Types ¶
type Change ¶
Change represents a change to a DAG and contains a reference to the old and new CIDs.
func Diff ¶
func Diff(ctx context.Context, prevBs, curBs cbor.IpldStore, prev, cur cid.Cid, opts ...Option) ([]*Change, error)
Diff returns a set of changes that transform node 'a' into node 'b'. opts are applied to both prev and cur.
func ParallelDiff ¶ added in v4.1.0
type ChangeType ¶
type ChangeType int
ChangeType denotes type of change in Change
const ( Add ChangeType = iota Remove Modify )
These constants define the changes that can be applied to a DAG.
type Root ¶
type Root struct {
// contains filtered or unexported fields
}
Root is described in more detail in its internal serialized form, internal.Root
func LoadAMT ¶
LoadAMT loads an existing AMT from the given IpldStore using the given root CID. An error will be returned where the AMT identified by the CID does not exist within the IpldStore. If the given options, or their defaults, do not match the AMT found at the given CID, an error will be returned.
func (*Root) BatchDelete ¶
func (r *Root) BatchDelete(ctx context.Context, indices []uint64, strict bool) (modified bool, err error)
BatchDelete performs a bulk Delete operation on an array of indices. Each index in the given indices array will be removed from the AMT, if it is present. If `strict` is true, all indices are expected to be present, and this will return an error if one is not found.
Returns true if the AMT was modified as a result of this operation.
There is no special optimization applied to this method, it is simply a convenience wrapper around Delete for an array of indices.
func (*Root) BatchSet ¶
BatchSet takes an array of vals and performs a Set on each of them on an existing AMT. Indexes from the array are used as indexes for the same values in the AMT.
This is currently a convenience method and does not perform optimizations above iterative Set calls for each entry.
func (*Root) Delete ¶
Delete removes an index from the AMT. Returns true if the index was present and removed, or false if the index was not set.
If this delete operation leaves nodes with no remaining elements, the height will be reduced to fit the maximum remaining index, leaving the AMT in canonical form for the given set of data that it contains.
func (*Root) FirstSetIndex ¶
FirstSetIndex finds the lowest index in this AMT that has a value set for it. If this operation is called on an empty AMT, an ErrNoValues will be returned.
func (*Root) Flush ¶
Flush saves any unsaved node data and recompacts the in-memory forms of each node where they have been expanded for operational use.
func (*Root) ForEach ¶
ForEach iterates over the entire AMT and calls the cb function for each entry found in the leaf nodes. The callback will receive the index and the value of each element.
func (*Root) ForEachAt ¶
func (r *Root) ForEachAt(ctx context.Context, start uint64, cb func(uint64, *cbg.Deferred) error) error
ForEachAt iterates over the AMT beginning from the given start index. See ForEach for more details.
func (*Root) Get ¶
Get retrieves a value from index i. If the index is set, returns true and, if the `out` parameter is not nil, deserializes the value into that interface. Returns false if the index is not set.
func (*Root) Len ¶
Len returns the "Count" property that is stored in the root of this AMT. It's correctness is only guaranteed by the consistency of the build of the AMT (i.e. this code). A "secure" count would require iterating the entire tree, but if all nodes are part of a trusted structure (e.g. one where we control the entire build, or verify all incoming blocks from untrusted sources) then we ought to be able to say "count" is correct.
func (*Root) Set ¶
Set will add or update entry at index i with value val. The index must be within lower than MaxIndex.
Where val has a compatible CBORMarshaler() it will be used to serialize the object into CBOR. Otherwise the generic go-ipld-cbor DumbObject() will be used.
Setting a new index that is greater than the current capacity of the existing AMT structure will result in the creation of additional nodes to form a structure of enough height to contain the new index.
The height required to store any given index can be calculated by finding the lowest (width^(height+1) - 1) that is higher than the index. For example, a height of 1 on an AMT with a width of 8 (bitWidth of 3) can fit up to indexes of 8^2 - 1, or 63. At height 2, indexes up to 511 can be stored. So a Set operation for an index between 64 and 511 will require that the AMT have a height of at least 3. Where an AMT has a height less than 3, additional nodes will be added until the height is 3.
Source Files
Directories