New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[experimental] LayeredMap which views a sequence of MapLayers #12722
Conversation
⏱️ 4h 15m total CI duration on this PR
🚨 3 jobs on the last run were significantly faster/slower than expected
|
This stack of pull requests is managed by Graphite. Learn more about stacking. |
e43b2d5
to
b941c9e
Compare
use std::sync::{Arc, Weak}; | ||
|
||
#[derive(Debug)] | ||
pub enum Ref<T> { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
similar to the Ref here https://github.com/aptos-labs/aptos-core/blob/main/storage/scratchpad/src/sparse_merkle/node.rs#L139. reuse?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
maybe, when it's out of '/experimental'
#[derive(Debug)] | ||
struct LayerInner<K: Key, V: Value> { | ||
root: NodeRef<K, V>, | ||
children: Mutex<Vec<Arc<LayerInner<K, V>>>>, |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
what is children used for?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
same with SMT, there can be branches in the block tree.
|
||
#[derive(Clone, Debug)] | ||
pub struct LayeredMap<K: Key, V: Value> { | ||
bottom_layer: MapLayer<K, V>, |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
why do we need the bottom_layer? could we assume the LRU cache contains all the base key, value pairs?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Think "FrozenSparseMerkleTree" -- you need to make sure nodes created between bottom layer and top layer don't go away while you read, by holding a strong ref to the bottom layer root.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
b941c9e
to
4a3f159
Compare
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
✅ Forge suite
|
✅ Forge suite
|
Description
A multi-versional mapping data structure much like the in memory sparse merkle tree but doesn't do the hashing on nodes.
This is useful for implementing the per-block speculative LRU cache / Active State coming up.
Type of Change
Which Components or Systems Does This Change Impact?
How Has This Been Tested?
proptest
Key Areas to Review
Checklist