5 ms·
The Chord algorithm sounds like a very good choice, however I'm more skeptical about the radix tree approach. I fear you might get a huge performance penalty.
by shin_lao 14y ago
The Chord algorithm sounds like a very good choice, however I'm more skeptical about the radix tree approach. I fear you might get a huge performance penalty.
- kibwen 14y agoI'm no data structures expert (far from it), but via hearsay I've only heard good things about radix trees. Care to elaborate?
- amalcon 14y agoRadix trees are great, with the right workload. The main competition (for strings) are the ternary search tree (for sparse keyspaces with rare insertions) and the B-Tree (which is nominally disk-optimized, but that optimization also tends to help with the L3 cache). None of those are best for all workloads. There are situations where using a radix-tree is actually faster than a hashtable with a good hash function, and situations where it is slower than a red-black tree.
- zond 14y agoI would have preferred other algorithms, but there was a strict need for 1) sorted data and 2) that 2 identical trees had the same structure (for the merkle element). Not many structures were left to choose from, and radix seemed to work well enough.
- shin_lao 14y agoMy concern is that you're mixing two different concepts. Do you really need data to be ordered? Why do you care about having "close" data on the same node?
- zond 14y agoThe synchronization uses Merkle trees, and they require ordered data since they hash contiguous data into a tree of hashes. And to avoid having a separate structure for the Merkle trees I just hash all nodes in the main tree, and compare the hashes to find differences. Thus the same content must have the same structure, or the comparisons won't work.
- shin_lao 14y agoI think I didn't make myself clear: - You say However, since it could be very useful for users of a database to store ordered data, or to wilfully concentrate certain data on certain parts of the cluster, god does not force the user to hash the keys. -> why do you care about how the data is actually stored? - To map keys to values, a mapping structure is needed. For infrastructural reasons (synchronization and cleaning) as well as for functionality of different kinds, we need a sorted mapping, and it has to be deterministically structured. -> why?
- zond 14y ago> why do you care about how the data is actually stored? I just said I don't. 'god does not force the user to hash the keys'. > > To map keys to values, a mapping structure is needed. For infrastructural reasons (synchronization and cleaning) as well as for functionality of different kinds, we need a sorted mapping, and it has to be deterministically structured. > why? Functionality: To be able to return the first or the n'th entry it has to be ordered. Synchronization/cleaning: To be able to hash element 0000-000f we need an efficient way to fetch a segment of elements, thus it again has to be ordered. To optimize the hashing so that I don't have to keep two separate data structures I keep the hashes in the nodes of the sorted data structure. Thus the structure has to be deterministically structured or the hashes won't be equal even if the trees contain the same data.
- shin_lao 14y agoThank you for your answers.
- shin_lao 14y agoOther comments, timestamps will not work as you expect if you have a network partition and you are using your own time synchronization mechanism. Use NTP instead.
- zond 14y agoI don't think I understand what you mean. Or you don't understand how my timestamps and time synchronization works?