Requirements

Let's design a simplified in-memory implementation of RocksDB, focusing on core functionalities such as storing, retrieving, and deleting data. RocksDB is a persistent key-value store for fast storage, but we will simulate its behavior in-memory for this exercise to concentrate on data structures and concurrency control. We'll avoid actual disk I/O to keep the focus on low-level design. The core challenge lies in building a thread-safe and efficient data structure capable of handling concurrent read and write operations. We'll simulate the append-only nature by keeping historical versions in-memory. # Requirements ## Functional Requirements 1. **Basic CRUD Operations:** * `put(key, value)`: Inserts or updates a key-value pair. * `get(key)`: Retrieves the value associated with a given key. Return `null` if the key does not exist. * `delete(key)`: Deletes the key-value pair associated with a key. Subsequent `get(key)` should return `null`. 2. **Snapshotting:** * `createSnapshot()`: Creates a snapshot of the current state of the database. This should be an immutable view of the data at the point in time the snapshot was created. * `get(key, snapshot)`: Retrieves the value of a key at a specific snapshot. If the key was not present in the snapshot or was deleted *before* the snapshot, return `null`. 3. **Iterators (Range Queries):** * `getIterator()`: Returns an iterator that allows iterating over all key-value pairs in the database in sorted order by key. * `getIterator(snapshot)`: Returns an iterator that allows iterating over all key-value pairs in a specific snapshot, in sorted order by key. * Iterator should implement `hasNext()`, `next()`, and `close()` methods. The `close()` method should release any resources held by the iterator (though in this in-memory version, this might be a no-op). 4. **Concurrency:** * The database must support concurrent read and write operations from multiple threads. Reads should be able to proceed concurrently, while writes must be synchronized to maintain data integrity. Snapshots should not be affected by ongoing write operations. ## Non-Functional Requirements 1. **Thread Safety:** All operations must be thread-safe. Use appropriate synchronization mechanisms (locks, atomic variables, etc.) to prevent race conditions and ensure data consistency. Reads should ideally be non-blocking whenever possible. 2. **Immutability (Snapshots):** Snapshots must be immutable. Modifying the database after a snapshot is created should not affect the data visible in the snapshot. 3. **Extensibility:** The design should be extensible to support different storage engines or data structures in the future (though we are sticking with in-memory now). Consider the Strategy pattern or similar approaches. 4. **Modularity:** The code should be well-modularized, with clear separation of concerns. Each component should have a single responsibility. 5. **Testability:** The code should be easily testable. Design the classes and interfaces to allow for unit testing of individual components. Consider dependency injection. 6. **Efficiency:** While we're not focusing on disk I/O, strive for reasonable performance in terms of memory usage and CPU cycles. Choose appropriate data structures for the task (e.g., consider the time complexity of operations on different data structures). Use concurrent data structures when appropriate. 7. **Sorted Keys:** The keys should be stored in a sorted manner. This enables efficient range queries. ## Core Entities 1. **`DB` (Database):** The main class representing the RocksDB instance. It provides the public API for interacting with the database (put, get, delete, createSnapshot, getIterator). 2. **`Snapshot`:** Represents an immutable view of the database at a specific point in time. It should provide a `get(key)` method to retrieve data from the snapshot. 3. **`Version`:** Holds the data at a particular point in time. Multiple versions can exist, representing the history of the database. Each snapshot will correspond to a `Version`. 4. **`MemTable`:** An in-memory data structure (e.g., a concurrent SkipList or a ConcurrentTreeMap) that stores the key-value pairs. It's the main working memory of the database. New writes are applied here. 5. **`Iterator`:** An interface for iterating over key-value pairs in the database or a specific snapshot. 6. **`VersionManager`**: Manages the different versions of the database. Responsible for creating new versions and snapshots.

Design and Implement Rocksdb.

Requirements

Interview Simulation

Functional Requirements

💡 Interview Tip

Non-Functional Requirements

Core Entity Identification

Premium Content