Milestone1

[prataprc]

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

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