How many bytes is a node, in practice? If you stuff hundreds or thousands of pointers in a node, plus a bunch of log, isn't that a lot of data to clone when you do a path-copy? It seems like there's a major trade-off there, unless you always write in large batches. I suppose you could have fast "cons-ing" of events onto the root log without any copying. It would be interesting to know what choices lead to good performance in a sample use case.
Hitchhiker trees: functional, persistent, off-heap sorted maps
21–30 of 33 posts
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#22> the best-performing data structure for looking up sorted keys cannot do those queries faster than O(log(n)) Feels like a digression off the actual tree structure, but isn't this incorrect, since a hash map can do key lookups in O(1)? With caveats, of course. It's a great idea over all, but I'd also be curious how well overlaying an event log on a cuckoo hash would work in comparison.
It's a common misconception that hashmaps have constant time lookups. In order for the lookup to be constant time, the hash function must output enough bits to avoid causing too many collisions. For example, 16 bits is too little for a hash map with a million keys. In fact, the hash function output size should be O(log(n)) where n is the number of entries. Processing log(n) bits takes at least O(log(n)) time. QED
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#23How many bytes is a node, in practice? If you stuff hundreds or thousands of pointers in a node, plus a bunch of log, isn't that a lot of data to clone when you do a path-copy? It seems like there's a major trade-off there, unless you always write in large batches. I suppose you could have fast "cons-ing" of events onto the root log without any copying. It would be interesting to know what choices lead to good perfor…
The code actually includes a benchmarking tool that's meant to help in figuring out this decision. Once you've selected your key size (or distribution), value size (or distribution), and backend, you can play with these factors. Intuitively, targeting "block" size should improve perf. So, 4k-1MB if you're in memory or local, 1.5k-9k if you're over the network (and depending on configuration).
I did some work to split nodes based on size rather than number of children, but that requires accurate & fast size estimation of the decompressed objects, which isn't possible in general.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#24> the best-performing data structure for looking up sorted keys cannot do those queries faster than O(log(n)) Feels like a digression off the actual tree structure, but isn't this incorrect, since a hash map can do key lookups in O(1)? With caveats, of course. It's a great idea over all, but I'd also be curious how well overlaying an event log on a cuckoo hash would work in comparison.
Creator here. As other commenters noted, this data structure only requires keys to be sortable, not hashable, and the best sorted performance we can achieve is O(log(n)).
That said, when a Cuckoo hash gets very full and bounces entries around a lot, there might be an advantage to buffering operations and choosing insertion patterns that reduce the batch's insertion time. Then again, Cuckoo hashes already perform so well for situations they're designed for, so it's hard to improve them with an event log overlay.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#25> the best-performing data structure for looking up sorted keys cannot do those queries faster than O(log(n)) Feels like a digression off the actual tree structure, but isn't this incorrect, since a hash map can do key lookups in O(1)? With caveats, of course. It's a great idea over all, but I'd also be curious how well overlaying an event log on a cuckoo hash would work in comparison.
It's a common misconception that hashmaps have constant time lookups. In order for the lookup to be constant time, the hash function must output enough bits to avoid causing too many collisions. For example, 16 bits is too little for a hash map with a million keys. In fact, the hash function output size should be O(log(n)) where n is the number of entries. Processing log(n) bits takes at least O(log(n)) time. QED
> Processing log(n) bits takes at least O(log(n)) time.
No, because log(n) might be smaller than the word size of the machine, which is the common case for hash table implementations.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#26Earlier quoted context omitted.
It's a common misconception that hashmaps have constant time lookups. In order for the lookup to be constant time, the hash function must output enough bits to avoid causing too many collisions. For example, 16 bits is too little for a hash map with a million keys. In fact, the hash function output size should be O(log(n)) where n is the number of entries. Processing log(n) bits takes at least O(log(n)) time. QED
> Processing log(n) bits takes at least O(log(n)) time. No, because log(n) might be smaller than the word size of the machine, which is the common case for hash table implementations.
If you limit log(n) and thus n to a constant, like the word size of the machine, then every algorithm is constant time.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#27Earlier quoted context omitted.
> Processing log(n) bits takes at least O(log(n)) time. No, because log(n) might be smaller than the word size of the machine, which is the common case for hash table implementations.
If you limit log(n) and thus n to a constant, like the word size of the machine, then every algorithm is constant time .
When log(n) is within the word size the hashmap lookup for the most part is actually constant i.e., few specific machine operation. A generic log(n) algorithm still requires log(n) distinct operation for the most part however small that number is.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#28very cool!
any idea how this would compare to clojure-wrapping
https://github.com/OpenHFT/Chronicle-Map ?
Seems like there are some similar design goals between the two.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#29Those are very cool, and functional too! > As it turns out, after I implemented the fractal tree, I spoke with a former employee of Tokutek, a company that commercialized fractal tree indices. That person told me that we’d actually implemented fractal reads identically! That's not necessarily a good thing. Last I heard Tokutek patented that. Not a laywer, from what I understand patents specifically pertain to "implem…
Creator here. I would absolutely agree with this, but let me shed a bit more light to clarify: the underlying idea of B+ trees with inline caches is not patented (or maybe it was, but a long time ago?). Tokutek's patents are all focused on the methods they use to achieve concurrent operations on a single tree--they have a very interesting & novel locking protocol. The Hitchhiker tree completely avoids their patents,…
Thanks for explaining. That makes sense.
Great work by the way! Really like the description of the code structure on the README page.
If patent is indeed not an issue, I might play with translating that to Erlang. You already did the hard work and also made it functional. I'd have to learn to read Clojure.
Speaking of functional, I was surprised to find the other day, Erlang's queue module implements an Okasaki API, complete with funny function names like deah, liat, and snoc.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#30I'm not sure I understand this. The claim is that "we dramatically improve the performance of insertions without hurting the IO cost of queries" by writing to the root's event log. However, it seems to me that this is only delaying the eventual write to the leaf node, not avoiding it. As more items are written, eventually the log will overflow and write to its children, and so on, until it is written to the leaf. This is what would happen in a regular B+ tree anyway, so what has been gained?
What am I missing?