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

Remove index table #96

Closed
aalda opened this issue Apr 1, 2019 · 1 comment · Fixed by #97
Closed

Remove index table #96

aalda opened this issue Apr 1, 2019 · 1 comment · Fixed by #97
Assignees
Labels
clean up propose a clean up or a redesign of ugly things

Comments

@aalda
Copy link
Contributor

aalda commented Apr 1, 2019

We are using the index table to map from event hashes to history tree versions, but that responsibility should be exclusive of the hyper tree, given that now, it stores the raw version in the shortcut leaves.

In this manner, we could eliminate the need for using another table to support fast mappings. With this change, every membership operation must query first the hyper tree before generating the audit path from the history tree, and thus, incurs in a latency penalty. However, given that the hyper tree is the only one that holds a lock for queries, in theory, it shouldn't reduce balloon's throughput.

This change helps to reduce space and write amplification in storage.

@aalda aalda added the clean up propose a clean up or a redesign of ugly things label Apr 1, 2019
@aalda aalda self-assigned this Apr 1, 2019
@aalda
Copy link
Contributor Author

aalda commented Apr 2, 2019

These are the results obtained in the microbenchmarks before and after removing the index table. The benchmarks execute 1,000,000 operations in every run. The results are shown in nanoseconds per operation.

Add
(ns/op)
Sequential Query
(ns/op)
Parallel Query - 10
(ns/op)
Parallel Query - 100
(ns/op)
Without index 97773 213293 139587 96872
With index 101912 110294 92270 106911

We can observe that sequential queries almost duplicate latencies when removing the index table. This result was the expected given that we are now quering both trees (hyper and history) sequentially. However, as we increase parallelism, it gets better results. It also slightly improves Add latencies.

aalda added a commit to aalda/qed that referenced this issue Apr 2, 2019
Add parallel benchmark for balloon queries

closes BBVA#96
@iknite iknite closed this as completed in #97 Apr 2, 2019
suizman pushed a commit to jllucas/qed that referenced this issue Jun 4, 2019
Add parallel benchmark for balloon queries

closes BBVA#96


Former-commit-id: 0593929
suizman pushed a commit that referenced this issue Sep 30, 2019
Add parallel benchmark for balloon queries

closes #96


Former-commit-id: c4e6a84 [formerly 0593929]
Former-commit-id: db4f056
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
clean up propose a clean up or a redesign of ugly things
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant