2 ms·

Well, if you're willing to incur a slight latency penalty on each access, incremental rehashing is terrifically easy. Just keep both the old and new backing ar

Well, if you're willing to incur a slight latency penalty on each access, incremental rehashing is terrifically easy. Just keep both the old and new backing arrays around, and consult a pointer to determine how far in the first backing array has been invalidated. If you follow a Shalev/Shavit hash-ordered-lists scheme the rehash doesn't even need to move anything, and can be done with a straight memcpy, or in a separate thread. The link below is an implementation that was intended for Cassandra (so is simplified and append-only, but also a concurrent map - which could be relaxed). It has the nice property that it will "fix" the backing array on-demand, so straight-up copying the existing contents of the backing array into the new region of the backing array, once doubled, will set things up for a gradual transition. Similarly, it's trivial for the backing array to instead grow incrementally, and for an extra level of indirection to prevent ever having to reallocate older regions (since their contents never changes on rehash). https://github.com/belliottsmith/cassandra/blob/47d970ead69035f5cd294ebae536dd3d5e985666/src/java/org/apache/cassandra/concurrent/NonBlockingHashOrderedMap.java https://github.com/belliottsmith/cassandra/blob/47d970ead690...

gpderetta 10y ago
keeping the old array around is the obvious solution, but the problem is that you might need to rehash the second array as well. Do you need to keep an arbitrary number of arrays around or there are hashing schemes that guarantee that you'll be done with rehashing by the time you need to rehash the second buffer? I'll read up on hash-ordered-lists.
- _benedict 10y ago
  Well, depending on your rehash trigger (i.e. if it is dictated by the load factor, not the number of reprobes), it can be guaranteed that the new array does not need to be rehashed before the in-progress migration, if you migrate at least one bucket per write operation. If you were to (sensibly) migrate many (say, >= 16) with each write, the likelihood of this happening is very low with any reasonable hash function, since the work of rehashing will typically be done many times faster than the skew can retrigger your rehash. This at least makes the incidence of a latency-inducing event of waiting for the prior rehash to complete very low. If you rehash based on something like "number of reprobes" then it's probably impossible to absolutely guarantee that a rehash cannot be triggered before a prior one begins, but the linked approach would permit growing the backing array discontiguously (assuming an extra level of indirection to the backing array). But this would obviously incur some extra overheads, and is not entirely dissimilar to hash-tries, which also avoid any costly global rehash. I think the class-level comment in the code I linked is perhaps the best introduction to split-ordered lists I know of (not hash-ordered; they're sorted by the reverse bitstring of the hash), since they're not widely discussed and not immediately intuitive.
eternalban 10y ago
Thanks for that SS list reference! Paper link: http://people.csail.mit.edu/shanir/publications/Split-Ordered_Lists.pdf http://people.csail.mit.edu/shanir/publications/Split-Ordere...

gpderetta 10y ago

keeping the old array around is the obvious solution, but the problem is that you might need to rehash the second array as well. Do you need to keep an arbitrary number of arrays around or there are hashing schemes that guarantee that you'll be done with rehashing by the time you need to rehash the second buffer? I'll read up on hash-ordered-lists.

_benedict 10y ago
Well, depending on your rehash trigger (i.e. if it is dictated by the load factor, not the number of reprobes), it can be guaranteed that the new array does not need to be rehashed before the in-progress migration, if you migrate at least one bucket per write operation. If you were to (sensibly) migrate many (say, >= 16) with each write, the likelihood of this happening is very low with any reasonable hash function, since the work of rehashing will typically be done many times faster than the skew can retrigger your rehash. This at least makes the incidence of a latency-inducing event of waiting for the prior rehash to complete very low. If you rehash based on something like "number of reprobes" then it's probably impossible to absolutely guarantee that a rehash cannot be triggered before a prior one begins, but the linked approach would permit growing the backing array discontiguously (assuming an extra level of indirection to the backing array). But this would obviously incur some extra overheads, and is not entirely dissimilar to hash-tries, which also avoid any costly global rehash. I think the class-level comment in the code I linked is perhaps the best introduction to split-ordered lists I know of (not hash-ordered; they're sorted by the reverse bitstring of the hash), since they're not widely discussed and not immediately intuitive.

eternalban 10y ago

Thanks for that SS list reference! Paper link: http://people.csail.mit.edu/shanir/publications/Split-Ordered_Lists.pdf http://people.csail.mit.edu/shanir/publications/Split-Ordere...