5 ms·

Nice work! I have maybe a dumb question: why not use a RDBMS to store the logs and use a b-tree index for the range queries? Is there a type of query that you m

Nice work! I have maybe a dumb question: why not use a RDBMS to store the logs and use a b-tree index for the range queries? Is there a type of query that you must build your own segment tree index for?

petethepig 6y ago
We write profiles to DB with 10 second resolution, so 1 profile with approximately 1000 samples per 10 seconds. When we later read this data, if we're talking about 1 minute of data, we need to merge 6 profiles (1 per 10 seconds). However, if we're talking about an hour of profiling data, that turns into 360 merges. Each merge is expensive, so this whole process becomes somewhat impractical. That's where segment trees come into play. On each write we "pre-aggregate" data for wider time ranges so that next time there's a wide read we can use a "wider" profile and thus reduce the total number of merges we need to make. Hope this helps visualize it: https://pyroscope-public.s3.amazonaws.com/slides-segment-trees.png https://pyroscope-public.s3.amazonaws.com/slides-segment-tre... Let me know if you have any other questions, happy to answer here or in our Slack.
- tracyhenry 6y ago
  Thanks, this perfectly answers my question!
- 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 ago
    Yes, 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 ago
      Cool! Thanks for explaining :).
m00dy 6y ago
great question.

petethepig 6y ago

We write profiles to DB with 10 second resolution, so 1 profile with approximately 1000 samples per 10 seconds. When we later read this data, if we're talking about 1 minute of data, we need to merge 6 profiles (1 per 10 seconds). However, if we're talking about an hour of profiling data, that turns into 360 merges. Each merge is expensive, so this whole process becomes somewhat impractical. That's where segment trees come into play. On each write we "pre-aggregate" data for wider time ranges so that next time there's a wide read we can use a "wider" profile and thus reduce the total number of merges we need to make. Hope this helps visualize it: https://pyroscope-public.s3.amazonaws.com/slides-segment-trees.png https://pyroscope-public.s3.amazonaws.com/slides-segment-tre... Let me know if you have any other questions, happy to answer here or in our Slack.

tracyhenry 6y ago
Thanks, this perfectly answers my question!
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 ago
  Yes, 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 ago
    Cool! Thanks for explaining :).

m00dy 6y ago

great question.