Skip to content
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

Download entries in parallel #34

Open
AGWA opened this issue Jan 16, 2019 · 1 comment
Open

Download entries in parallel #34

AGWA opened this issue Jan 16, 2019 · 1 comment
Labels
refinement An improvement, but not a new feature

Comments

@AGWA
Copy link
Member

AGWA commented Jan 16, 2019

It's possible to obtain significantly higher throughput by downloading entries in parallel. There are several challenges with this approach, however:

  1. We don't know how many entries a log will return, so it's hard to know what the optimal job size is.
  2. We'll need to gracefully handle rate limiting.
  3. It's much easier to update the Collapsed Merkle Tree serially. I see a few ways to handle this:
    1. We could force the entries to be processed in serial by using a buffered channel of buffered channels. However, I think it will be difficult to reason about buffers.
    2. We could split up jobs on subtree boundaries, making it easy to merge the Collapsed Merkle Trees of all the jobs at the end.
    3. We could devise a sparse Collapsed Merkle Tree data structure which allows nodes to be appended in any order.
@AGWA AGWA added the refinement An improvement, but not a new feature label Sep 22, 2023
@AGWA
Copy link
Member Author

AGWA commented Feb 9, 2024

A data structure like this might be useful:

type DiscontiguousCollapsedTree []CollapsedTreeSegment
type CollapsedTreeSegment struct {
    Index uint64
    Tree  CollapsedTree
}
func (t *DiscontiguousCollapsedTree) Add(index uint64, tree CollapsedTree) {
    maxSize := uint64(1) << bits.TrailingZeros64(index)
    if tree.size > maxSize {
        // error: tree too large to be placed at this index
    }
    // find segment prior to index in *t. append tree to this segment if tree is contiguous (and also see if we can merge in the following segment), otherwise insert a new segment in *t at this location
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
refinement An improvement, but not a new feature
Projects
None yet
Development

No branches or pull requests

1 participant