alnoki
commented
1 year ago Flat/compact implementation
Structs
/// A storage-efficient sorted map based on a B+ tree.
///
/// Inner Node IDs unset at bit 63, leaf node IDs set at bit 63.
struct BPlusMap<V> has store {
/// Maximum number of children, $m$, to an inner node.
inner_node_order: u8,
/// Maximum number of key-value pairs, $l$, in a leaf node.
leaf_node_order: u8,
/// `NIL` if empty, otherwise node ID of root node, which may be
/// an inner node or a leaf node.
root: u64,
/// Minimum key in map, ignored if empty.
min_key: u128,
/// Maximum key in map, ignored if empty.
max_key: u128,
/// Minimum key's leaf node ID, `NIL` if empty. The head of the
/// doubly linked list of leaf nodes.
head_node_id: u64,
/// Maximum key's leaf node ID, `NIL` if empty. The tail of the
/// doubly linked list of leaf nodes.
tail_node_id: u64,
/// Map from inner node ID to inner node.
inner_nodes: TableWithLength<u64, InnerNode>,
/// Map from leaf node ID to leaf node.
leaf_nodes: TableWithLength<u64, LeafNode<V>,
/// Inner node ID at top of inactive stack. `NIL` if no inactive
/// nodes.
inner_stack_top: u64,
/// Leaf node ID at top of inactive stack. `NIL` if no inactive
/// nodes.
leaf_stack_top: u64
}
/// Inactive if no children, else active. Inactive inner nodes are
/// stored in a stack.
struct InnerNode has store {
/// | Node status | Meaning if `NIL` | Meaning if not `NIL` |
/// |-------------|--------------------|----------------------|
/// | Active | Node is root | Parent inner node ID |
/// | Inactive | Is bottom of stack | Next node in stack |
parent: u64,
/// Inactive if empty, else an active node.
children: vector<Child>
}
/// Indicates a child to an inner node, either another inner node or
/// a leaf node.
struct Child has store {
/// The minimum key allowed in the subtree with the given node
/// ID. Ignored if the leftmost child of an inner node.
min_key: u128,
/// Node ID of corresponding child.
node_id: u64
}
/// Inactive if no pairs, else active. Active leaf nodes are stored
/// in a sorted doubly linked list (DLL), and inactive leaf nodes
/// are stored in a stack.
struct LeafNode<V> has store {
/// | Node status | Meaning if `NIL` | Meaning if not `NIL` |
/// |-------------|------------------|----------------------|
/// | Active | Node is root | Parent inner node ID |
/// | Inactive | Ignored | Ignored |
parent: u64,
/// | Node status | Meaning if `NIL` | Meaning if not `NIL` |
/// |-------------|------------------|----------------------|
/// | Active | Is DLL list head | Previous DLL node |
/// | Inactive | Ignored | Ignored |
previous: u64,
/// | Node status | Meaning if `NIL` | Meaning if not `NIL` |
/// |-------------|--------------------|----------------------|
/// | Active | Is DLL list tail | Next DLL node |
/// | Inactive | Is bottom of stack | Next node in stack |
next: u64,
/// Key-value pairs sorted by key.
pairs: vector<Pair<V>>
}
/// A key-value pair.
struct Pair<V> has store {
/// Inserted key.
key: u128,
/// Inserted and optionally mutated value.
value: V
}
Implementation details
Unlike Aptos' SimpleMap, which relies on the computationally-intensive aptos_framework::comparator module, the above implementation relies only on the primitive integer comparators <, >, <=, >=, !=, ==, etc.
This approach minimizes external function calls, but disallows for generality of the key type:
ideally the data structure would support any kind of integer key, but there is presently no Move support for a generic integer type.
Hence the most general u128 is chosen, with the expectation of upcasting for u8 or u64 keys.
It is proposed that public APIs mimic those of Rust's BTreeMap.
Ideally simple helper functions of the form is_leaf_node_id() and to_leaf_node_id() would support function inlining to reduce function call gas costs.
If inlining is not supported, however, functions can still be written as if they were to be inlined by the compiler, then manually inlined later.
Ideally the Aptos Framework would provide getters for the number of free bytes per global storage operation.
Here, public functions for the BPlusMap could accept an immutable reference to a V type, and calculate the corresponding optimal $l$ value accordingly.
As for $m$, this may hinge on gas optimizations, but could potentially be derived from the free bytes amount if testing reveals that the gas cost bottleneck is how compact inner nodes are.
See Beingessner 2022 for more optimality discussions and a comparisons with Rust's BTreeMap.
Sibling pointers may additionally be helpful for inner nodes, due to sibling adoption operations.
AVL queue background
During the time of implementation of Econia's AVL queue, Aptos' gas schedule was subject to regular changes and documentation was practically nonexistent. At the time, provided guidance indicated that gas optimality rested upon minimizing the number of bytes in a per-item operation, such that AVL queue data structures are bitpacked for a minimimized byte footprint.
However, the gas schedule has converged on a byte-wise cost schema that only applies after a critical number of bytes have been operated on, in effect rendering the first 1k bytes "free". This development essentially renders all AVL queue bitpacking operations unnecessary, to the extent that AVL queue gas computation costs are higher than required by the finalized schedule.
Moreover, with the AVL queue offering only 5-bit height tracking and 14-bit access keys, AVL queue height is limited to 18, with a maximum node count of 16383. One implication of this schema is an eviction paradigm whereby the tail of the AVL queue is evicted whenever no more nodes can be inserted.
From an order book persepctive, ideally this paradigm would minimize denial-of-service (DoS) attacks that attempt to increase gas costs by inserting excessive bogus orders: only 18 borrows max are required to search in a full tree. However, this paradigm enables a form of adversarial eviction whereby an attacker can clear out the order book by placing excessive transactions.
M-ary trees
Motivation
With the first 1k bytes of a global storage operation effectively free, and with computational costs dwarfed by storage costs, a proposed remedy is to replace the AVL queue with an m-ary tree-based structure, having at most $m$ children per node. Notably, an AVL tree is an m-ary tree with $m=2$, but in the proposed implementation, $m$ would be set to include as much data as possible in each node without exceeding 1k bytes.
Compared with a binary search tree with $n$ nodes having height on the order of $\log_2 n$, an m-ary tree has height on the order of $\log_m n$. Here, for example, with $m=5$ (up to 5 children per node) and 16383 nodes (the maximum number contained in an AVL queue), height is on the order of $\log_5 16383$ for an m-ary tree versus $\log_2 16383$ for an AVL queue:
Notably, for up to $m=10$ children per node, height is on the order of only 6 for as many as 1 million orders:
Hence an m-ary tree essentially invalidates the need to implement eviction logic, as a malicious actor would have to place upwards of millions of orders to render order book operations prohibitively costly.
B+ trees
In particular, a B+ tree is proposed as the core m-ary tree data structure since it only contains data at leaf nodes, rendering inner nodes as compact as possible. Moreover, leaf node data in a B+ tree is sorted in a linked list, providing for much simpler indexing. With a B+ tree for both bids and asks, it may be appropriate to implement leaf nodes as a doubly linked list, to enable traversal in both ascending and descending order.
Additionally, several design methodologies are considered:
econia::market::Orderis a value. Leaf nodes contain a vector of structs each having a key and the table ID of a corresponding order. Orders are partitioned into separate table entries, and can be accessed in $O(1)$ lookup time via a "value access key" (value table ID). Indexing requires traversing the linked list and then borrowing the corresponding order in the separate data structure.Ordercan shift in memory due to node splitting.Implementation considerations
Vector operations
Regardless of the approach, vectors will be required for storing multiple keys and "child pointers" (table indices) for each node. For example, consider an inner node storing $[1, 3, 7, 12, 15, 18]$ in a standard
vector: Here, inserting $19$ requires a simple (and inexpensive) push back operation, but inserting $2$ requires an $O(n)$ operation, either by re-orering essentially the entire vector after a push back via swaps,$$[1, 3, 7, 12, 15, 18, 2]$$
$$[1, 2, 7, 12, 15, 18, 3]$$
$$[1, 2, 3, 12, 15, 18, 7]$$
$$[1, 2, 3, 7, 15, 18, 12]$$
$$[1, 2, 3, 7, 12, 18, 15]$$
$$[1, 2, 3, 7, 12, 15, 18]$$
or by using a
tmpvariable approach:$$[1, 3, 7, 12, 15, 18], tmp = 2$$
$$[1, 2, 7, 12, 15, 18], tmp = 3$$
$$[1, 2, 3, 12, 15, 18], tmp = 7$$
$$[1, 2, 3, 7, 15, 18], tmp = 12$$
$$[1, 2, 3, 7, 12, 15], tmp = 15$$
$$[1, 2, 3, 7, 12, 15, 18]$$
One solution is to use a singly linked list, but this approach eliminates the kind of binary lookup made possible during search operations.
Notably, with market fills operating on the head or tail of the leaf node doubly linked list, one potential approach is to use a static vector for inner nodes, and a doubly linked list of data items within each leaf node: in a flat/compact approach, for example, leaf node lookup makes use of a binary search within inner node vectors, and linear search at leaf nodes. Here, popping the head of the entire data structure does not require updating every element within the corresponding leaf node's internal doubly linked list.
Notably, actual gas operations may render a static vector the least expensive, due to average number of expected operations, previous/next pointer borrows and upates, etc.
In a static vector implementation, insertion operations that require breaking up a tree could implement the sorted insert during the split operation, to reduce vector lookup.
Operations may be based on Aptos'
SimpleMapimplementation.Iteration
Should internal node indices be required for iteration, it is proposed that an
IteratororIndexstruct be used rather than passing table entry IDs, which essentially function as memory pointers.Nested list style
In a nested approach, where price levels are generally static over time and order sequence numbers are constantly churning over, it may be practial to use a doubly linked list inside nodes for the sequence number dimension, and a static vector inside nodes for the price number dimension. With operations inside each price level typically either popping from the front or appending to the tail of the resultant price-time priority queue, operations tend toward $O(1)$ within the sequence number dimension, and $O(\log n)$ within the price level dimension (due to binary search within a price level node).
Sample implementation
See below for an analysis of a flat/partitioned sample implementation.
Structs
Height
Node(assuming no more than 127 vector elements), the fixed size $f$ of the node is:Itemhas size $i$:Nodesize (in bytes) $s$, the max number of children $m$ is:$$f + im = s$$ $$im = s - f$$ $$m = \lfloor (s - f) / i \rfloor$$
Gas
Storage gas costs are defined thusly:
Conclusions
econia::b_plus_deque, stylized asbpdq). For clarity, and since B+ operations are sorted by default, however, “B+ map” may be more appropriate, to indicate a key-value collection (sorted operations are simply a bonus).@Arinerron @chad-mcdonald @chen-robert @fcremo