filecoin-project / filecoin-project/specs

Sector set storage

Open
#116 50 comments 0 reactions 2 assignees Claimed by @whyrusleeping View on GitHub
Dominant language
SCSS
Stars
363
Forks
164
PR merge metrics
No merged PRs in 30d

Description

We need a data structure to hold sectors on chain, inside the miner actor. Currently, we just have them all in a big map, which won’t scale well (every change to it creates a new object, meaning we would rewrite the entire thing with every change).

This issue is a place to brainstorm solutions.

#### Requirements
* Ordered Set
* no values, just keys (TODO: is this true? Is it just storing CommRs?)
* ~~‘Ordered’ requirement isn’t as strict as it sounds, we really just need to be able to reference elements within a given set by their index within the set. It is okay if indexes of items change with insertions and deletions.~~
* Efficient additions and random removals
* ~O(log(n)) changed objects per mutation
* Efficient lookup by key and index

#### Nice to haves
* Efficient batch remove by index range

### Does the HAMT work?
We could potentially use the HAMT code, but we would need to adapt it to have efficient index lookups. To do this, we could annotate links to children with a count of how many values exist in and under that child, allowing us to know at each node which child the thing we are looking up is in.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.