Well now that you use your custom storage implementation, it’s not necessary to have special encoding for keys, right? As far as I can see in the Olivine code, it uses :gb_trees for index structure with custom find_page_for_key implementation which looks for key with the default erlang term ordering.
I am also experimenting with storage stuff and I am currently writing a very simple and minimal LSM implementation to try out as a Bedrock backend.
Please do share when ready, I’ve been strongly considering writing an Elixir LSM as well
Another nice thing about using binaries is that, as I understand it, the BEAM will just keep slicing up the refcounted binary from the page load without any coping.
Imagine you have an LSM. If you have to decode the keys to binary search the index/data blocks all of a sudden you’re copying a bunch of memory and creating a bunch of terms that could have just been binary slices. This is not free.
The same would be true when binary searching a Btree page.
So even if you want term order I still think it would be better to use an encoding which sorts lexicographically in binary form.
I think I will be taking this approach in my own work so if you have a dissenting argument here I would of course very much like to hear it!
Slices are great for temporary work, but the memory bloat can be more permanent. The slice retains a reference to the underlying binary and there can be significant amounts of memory that are accidentally / quietly retained. For example, you read in a 10mb chunk from somewhere, and slice out one 10 byte value to keep. As long as there’s a reference to the 10 byte value, the whole 10mb sticks around, even if you’ve discarded all references to the 10mb chunk. You can sever this linkage with an explicit :binary.copy, though. :binary.referenced_byte_size can tell you more about this, too. There are a bunch of fun toys in:
In the case of a storage engine you would only retain the page during a given query (only during the binary search, even) so I think what I said remains correct. I guess you would definitely want to copy out any binaries that you intend to return, though.
Is there any mechanism for the VM to recognize that it’s holding on to a huge binary for a small slice? I just assumed it would figure that out on its own tbh.
Also, tangential, but does anyone know how refcounted binaries interact with ets? Specifically, if you store a binary in an ets table is it copied?
Just so. Things destined for the network or disk might not matter, but things handed back to other processes (with their own arbitrary lifetimes) will definitely cause you issues with unexpected retains. My understanding is that :binary.copy only actually does anything if the parameter is a slice – it won’t duplicate things unnecessarily, and so it’s okay to use it defensively “at the exits.”
Not that i’m aware of. We’re just expected to manage this stuff.
Binaries (>= 64 bytes) are never copied. Everything else will be if the :ets table is accessed from another process.
In general, anything other than a “large” binary is copied when crossing a process boundary, whether it’s an :ets read, or a message send, etc. For :ets reads, the reader “pays the toll” and will recursively copy whatever is read into it’s own space and for message sends, the sender “pays the toll” of copying the message into the receiver’s space.
This is why it can be faster to pass large binaries around between processes instead of large structures (and why Bedrock now binary-encodes transactions early and passes those around).
Thank you! On deck next is a full slate of atomic operations, control over the read/write conflicts sets and other refinements necessary to support a fdb-style high-contention-allocator and directory layer. Stay tuned.
Mm, I have thought about doing this. Especially since it may be possible to encode things in such a way that the batch fragment destined for a particular storage server can essentially travel through the TLog (and WAL on disk) without ever being decoded.
In practice I think the FDB tagging design (randomly assigning tags when the storage servers’ tlogs overlap) makes this messy. Frankly this design is bad and I don’t know what they were thinking. I guess it just pre-dates the idea of copysets.
It would be much better to create TLog teams as copysets and assign storage tags at the team level. When I was reading through your code I think that might even be what you did, in which case congrats for dodging that mess!
It’s a one-way door, though. Once you go full copyset you can only move data at the team level, so you can never go back. Meaning small deployments have to use copysets too even when it’s less than ideal. I think I’m just going to commit to that design, though. Spilling the TLogs without team-level tags is just so messy and it’s keeping me up at night.
I considered this, but if you want the DB to work embedded then you have no control over whether it’s headed for the network or not because you don’t know if the read is local to the node. So copying it is!
In practice copying the returned keys/values out of the page is exactly what you would do in a “normal” (non-Erlang) implementation anyway so it’s no big deal.
This is a premature optimization. Let’s do the terms-as-keys and compare the performance. First make it working, then beautiful, then fast and so on.
This is a false dilemma. We can have 0-copy for binaries and simple tuples while having arbitrary terms-as-keys at the same time, because if we have string keys or tuple of strings keys, we can instantiate them with binary_to_term (or implement own version of binary_to_term for strings with fallback to :erlang.binary_to_term) without copying as well.
This is a more broader point than just this discussion about keys. If I wanted the most efficient, well tested and production ready FoundationDB in Elixir, I’d just use vanilla Foundation DB with NIFs interface. So, if someone is ever going to use Bedrock, it will be not because of it’s performance, but it will be more of it’s interoperability with Elixir, ability to work with it the Elixir way, introspect it in Elixir and so on. This is just my personal point, and I will understand if you think the other way about this project
P.S. I keep saying “we” when proposing solutions, but I am not in your team and it looks awkward (for me at least), and that’s just my poor English, please don’t mind it.
The threshold for “premature” is IMO much higher for a storage engine. I have been debating (with myself) whether it’s even possible to write a useful storage engine in Elixir, and one of the biggest problems is a lack of control over memory allocation.
I’ve been leaning towards LSM in part because the design necessitates copying where a Btree would benefit greatly from in-place mutation of pages (in memory not on disk) which seems more natural in a functional language. Still, there are challenges.
Being able to binary search the blocks without decoding (and therefore copying) the keys seems to me like it would be a meaningful advantage. But of course some microbenchmarks could show it matters less than I think!
I don’t see how this would work because they have to be comparable (bin_a < bin_b) in encoded form to avoid decoding. But maybe I am misunderstanding you?
This is entirely reasonable. I personally have a specific set of goals which preclude the use of FDB, but Bedrock (while similar in some ways) is not my project and likely has different goals. That’s not up to me to comment on.
What other functionality do you think would benefit from using terms down to the storage layer? Introspection/debugging is a good example.
This is normal in English; native speakers do this all the time. It doesn’t look awkward to me.
For example, I read from binary some encoded with :erlang.term_to_binary string. It will look like <<131, 109, size :: 32, string :: binary-size(size)>>. I can’t compare encoded (because it will compare by size first), but I can use this pattern to extract the string and then compare it without any copying since it will be just a reference sub binary.
This way we leave the decision to optimize the key for fast comparison (or not) to the user. If user wants to have really fast comparison, they can implement their own encoding and just write strings into the storage
I understand now, thanks for clarifying. I don’t know the term_to_binary encodings but if it’s easy to pull the raw binary out with a quick pattern match as you suggest then I agree this could be a reasonable approach.
