Organize storage/access around a page

[joe-elliott]

The current backend design hits a number of limitations as the size of the index and bloom filters continue to grow due to compaction. Reorganize around the idea of page access to allow for bloom/index/objects to grow larger as time goes on. Research and determine a good page size that is cache friendly and easy to work with.

One of the big concerns is partial updates. Partial reads are possible by using GET with the Content-Range header, but uncertain if partial updates are possible with the PATCH method. This will not matter to ingestion as it will cut relatively small blocks, but compaction will struggle as blocks become larger and larger.

• Bloom

  • Not straightforward at all. Unsure how to request/work with a partial bloom filters. Here are some ideas on partition bloom filters that are not directly applicable, but may be revealing:
    https://news.ycombinator.com/item?id=22010586
    https://github.com/nehbit/aether/blob/master/aether-core/aether/services/rollingbloom/rollingbloom.go

• Index

  • Currently the write/read paths are designed to pull/push an entire index at once. Split the index into n same sized "pages". We can then use the roughly linear distribution of trace ids to make guesses about which pages to pull first. This will greatly increase the max size of a block.

• Objects

  • This one is straightforward. We already index sets of objects per index record. It is currently based on a configurable value. We could change this to be max MB per index record instead of max traces.

https://en.wikipedia.org/wiki/External_memory_algorithm
https://en.wikipedia.org/wiki/Cache-oblivious_algorithm

[joe-elliott]

Also think about blocklist polling. As the blocklist grows this will become worse. There is almost certainly a maximum value of blocks before things no longer work.

[joe-elliott]

Compaction already does this through an iterator interface. Could be added to the query path relatively easily by adding an additional Finder that access the index in a paged fashion.

That may be all that's necessary, but using tempo at very large scales would be necessary to confirm.

[annanay25]

This now only applies to the index. Bloom filter sizes were addressed in another PR.