3 ms·
So you're basically building up a segment tree as more writes come in? Something like this: ---AC--- | | | | --AB-- --BC--
by ZephyrBlu 6y ago
So you're basically building up a segment tree as more writes come in? Something like this:
---AC---
| |
| |
--AB-- --BC--
| | | |
| | | |
A B C
This improves your read speeds, but also increases the amount of data you have to store right? Not saying this tradeoff is bad, just trying to understand the system :).
Also, I see you're using a NoSQL database. How do you store the tries that represent profiles? I'm not familiar with tries, but I assume they have to be serialized in some way to be stored in the database.
- petethepig 6y agoYes, this is pretty close. In our case each new layer has 10 elements and there's no overlaps, so something like this: ABCDEFGHIJ KLMNOPQRST + + | | +-+-+-+-+++-+-+-+-+ +-+-+-+-+++-+-+-+-+ | | | | | | | | | | | | | | | | | | | | + + + + + + + + + + + + + + + + + + + + A B C D E F G H I J K L M N O P Q R S T And yes, it comes at a cost of increased storage requirements. This is still pretty efficient though as we found out. Behind the scenes we're using BadgerDB which is a key-value db that handles all the disk operations. All of the data structures we use (segment tries, tries and call trees) are at some point serialized and flushed to disk. For example, here is the trie serialization code https://github.com/pyroscope-io/pyroscope/blob/main/pkg/storage/dict/serialize.go#L14 https://github.com/pyroscope-io/pyroscope/blob/main/pkg/stor...
- ZephyrBlu 6y agoCool! Thanks for explaining :).