Milestone1

[prataprc]

Goal for Milestone-1 is to provide a minimum viable product for enthusiastic users and early adopters.

• [x] Rdms indexes to support CRUD API.
  • [x] Rdms instances can be composed using <K, V, M, D>:
    • [x] K, Key type.
    • [x] V, Value type.
    • [x] M, Memory-index-type.
    • [x] D, Disk-index-type.
  • [x] Use atomic, mutex, spin-lock, copy-on-write mechanisms to support API level concurrency for readers and writers.
  • [x] Allow concurrent writer threads to access Rdms index¹.
  • [x] Allow concurrent reader threads to access Rdms index².
• [x] CRUD operations on DB.
  • [x] Write api: set(), set_cas(), delete().
  • [x] Iter api: get(), range(), reverse(), iter().
  • [x] Scan api: full_scan().
• [x] Centralized-version-control-mechanism for values, tracking issue.
  • [x] Implement associated Delta type for each index-value type.
  • [x] diff() API to create a delta between old and new value.
  • [x] merge() API to create old-value from delta and new-value.
  • [x] ..._with_versions() flavor for read-api to fetch all the versions of index-value.
• [x] WAL Write-Ahead-Logging.
  • [x] To ensure Durability guarantee.
  • [x] Shards to match I/O Concurrency, one file for each shard.
  • [x] Shareable writer-handle for batching, improves SSD throughput.
  • [x] Rotate log files for each shard.
  • [x] Configurable journal-limit for each log-file.
• [x] Piece-wise full table scan, tracking issue.
  • [x] Best case, if memory-index can allow concurrent full-table-scan without any additional penalties.
  • [x] Better case, if memory-index can allow concurrent full-table-scan without blocking writes.
  • [x] Good case, if memory-index can allow concurrent full-table-scan without blocking write for too-long (< 1ms).
• [x] Latch and spin for non-blocking single-writer, multi-reader concurrency, tracking-issue.
• [x] Log-Structured-Merge
  • [x] Multiple levels of index.
  • [x] Use memory-optimized data structure for mem-index.
  • [x] Use disk-optimized data structure for disk-index.
  • [x] count() can only be approximate.
• [x] Memory data-structures.
  • [x] Left-Leaning-Red-Black tree.
    • [x] Fastest single threaded write path for a tree data-structure.
    • [x] Fast read performance.
    • [x] Good case scenario for piece-wise full table scan.
  • [x] LLRB with multi-version-concurrency-control.
    • [x] Concurrent reads along with single threaded write.
    • [x] Fast read performance.
    • [x] Better case scenario for piece-wise full table scan.
• [x] Disk data-structures.
  • [x] Read-Only-BTree.
    • [x] Build tree from an iterator.
    • [x] Fully packed, with > 95% node-utilization.
    • [x] Value co-located in leaf-node or stored in separate value-log file.
    • [x] Deltas stored in separate value-log file.
• [ ] Key traits for following types:
  • [ ] u32, i32, u64, i64, u128, i128.
  • [ ] char, String, Vec.
  • [ ] Array type.
• [ ] Value traits for following types:
  • [ ] u32, i32, u64, i64, u128, i128.
  • [ ] char, String, Vec.
  • [ ] Array type.
• [x] Empty Value type.
• [ ] Unit test-case target 80% code coverage.
• [ ] Rustdoc Documentation under doc.rs
• [ ] First alpha-release.
• [ ] Nightly release process, tracking issue.

Footnotes:

1. Only when memory-index-type (M) and disk-index-type (D) supports read-concurrency.
2. Only when memory-index-type (M) and disk-index-type (D) supports write-concurrency.