mafintosh / hyperdb

Distributed scalable database
MIT License
752 stars 75 forks source link

WIP: Lexicographic iteration #104

Open andrewosh opened 6 years ago

andrewosh commented 6 years ago

This PR includes a couple of changes to make lexicographic iteration possible (relevant discussion here https://github.com/mafintosh/hyperdb/issues/78). Once supported, we should be able to create useful things like a leveldown implementation based on hyperdb.

Summary of changes:

  1. The approach to path construction in lib/hash.js has been modified to support variable-length paths. Each path component is separated by a separator value instead of being fixed-length.
  2. lib/iterator.js and lib/put.js have been lightly modified to a) remove hard-coded values and b) make non-recursive iteration respect the path separator.

Some things to consider before this can be merged:

  1. The hashing scheme for path components should probably be configurable, but the variable-length path approach works regardless of hashing scheme (i.e. for lexint, you don't want to hash the path, but if you don't need lex iteration then you'll likely want to get the benefits that come with the hash-based approach).
  2. The hashing scheme will need to be included in a metadata record (TBD), since if affects lookups -- replication between two dbs with different schemes would be problematic, for example.

Note: This is still WIP, and the above issues need to be addressed before merging.

andrewosh commented 6 years ago

This PR has been updated with support for a top-level lexint flag. When enabled, paths will be constructed without any hashing, and iteration will thus be lexicographically ordered. When disabled, path components will be hashed (as in current master).

Storing a db's path configuration (is there a better term for this?) in a header is still in the works.

andrewosh commented 6 years ago

Some wires got crossed and I was referring to "lexicographic iteration" as lexint, which is lexicographic integer! This PR will be updated to rename lexint -> lex