Performance and Indexing
Relevant source files
The following files were used as context for generating this wiki page:Cyberpath Sentinel is designed with a primary focus on trust, transparency, and compliance, which informs its initial performance characteristics. While not built for high-frequency transactional systems, a detailed, phased plan exists to enhance performance and scalability through features like caching, indexing, and sharding. Initially, query performance relies on file system scans, but the architecture is designed to incorporate more advanced optimization strategies over time.
This document outlines the current performance profile, the planned optimization strategies, and the architecture of the indexing and caching components. These features are part of Phase 3 of the implementation plan, aimed at improving query speed and enabling the system to handle larger collections of documents.
Sources: README.md:12, README.md:46-47, IMPLEMENTATION_PLAN.md:410-416
Performance Characteristics
The performance of Sentinel is directly tied to its "Filesystem is the Database" design principle. Operations that can be mapped to a direct file lookup are highly performant, while operations requiring a scan of all documents in a collection are slower.
Sources: README.md:112, README.md:144-145
Time Complexity
The following table summarizes the time complexity of core database operations in the initial design, before advanced indexing is implemented.
| Operation | Time Complexity | Notes |
|---|---|---|
| Insert | O(1) | A single file write operation. |
| Get | O(1) | Direct filename lookup. |
| Delete | O(1) | A file rename operation to the .deleted/ directory. |
| Update | O(1) | An atomic file rename operation. |
| List | O(n) | Scans the directory to list all filenames. |
| Filter | O(n) | Scans and reads all files within a collection to apply the filter. |
| Index | O(n) | Building a lazy index requires scanning all files on the first query. |
Sources: README.md:147-156
Known Performance Trade-offs
The project acknowledges several performance-related trade-offs:
- Query Performance: Without native B-tree indices, initial queries must scan all files in a collection.
- Scaling Limits: A single folder's performance can degrade when it contains a very large number of files (e.g., around 4 million).
- Concurrency Complexity: Multi-writer scenarios are not optimized for thousands of concurrent writes and require locking strategies.
Sources: README.md:45-54
Optimization Strategies
To address the known performance limitations, a multi-faceted approach is planned, focusing on caching, indexing, and sharding. These features are part of "Phase 3: Performance & Scale" in the implementation plan.
Sources: README.md:158-161, IMPLEMENTATION_PLAN.md:410-411
Caching Layer
An in-memory LRU (Least Recently Used) cache is proposed to store frequently accessed or "hot" documents, reducing the need for repeated disk I/O.
The diagram below shows the structure of the planned Cache component.
This diagram illustrates the main components of the Cache struct, including its data store, LRU tracking queue, and public methods.
Sources: IMPLEMENTATION_PLAN.md:218-233
The cache's behavior will be configurable via the StoreConfig.
| Parameter | Description | Default Value |
|---|---|---|
enable_caching | Toggles the caching layer on or off. | true |
cache_size_mb | The maximum size of the cache in megabytes. | 256 MB |
Sources: IMPLEMENTATION_PLAN.md:80-81
The implementation will leverage high-performance concurrency libraries.
dashmap: A concurrent hash map for the main cache storage.lru: To manage the LRU eviction policy.parking_lot::RwLock: A high-performance read-write lock.
Sources: IMPLEMENTATION_PLAN.md:90, IMPLEMENTATION_PLAN.md:235-236, Cargo.toml:138
Indexing Engine
The Indexing Engine is the core component for accelerating query performance. The strategy is to build indices lazily upon the first query that can benefit from them. These indices are then persisted to disk for subsequent queries.
Sources: README.md:47, IMPLEMENTATION_PLAN.md:451-455
Architecture
The engine is managed by an IndexManager which handles the lifecycle of different Index types within a collection. Indices will be stored in a dedicated .index/ sub-directory within each collection folder.
The following diagram shows the relationship between the IndexManager and an Index.
This class diagram details the planned structures for managing and representing indices.
Sources: IMPLEMENTATION_PLAN.md:58, IMPLEMENTATION_PLAN.md:239-261
Index Types
Different types of indices are planned to support various query patterns.
| Index Type | Use Case | Time Complexity |
|---|---|---|
| Hash | O(1) lookups for exact matches (e.g., email == '...'). | O(1) |
| B-Tree | O(log n) for range queries (e.g., timestamp > '...'). | O(log n) |
| Full-Text | For text search capabilities. | N/A |
Sources: IMPLEMENTATION_PLAN.md:250-254, IMPLEMENTATION_PLAN.md:420-421
Lazy Indexing Flow
Lazy indexing avoids the overhead of building indices for fields that are never queried. The index is created only when it's first needed.
This flowchart shows the process of lazy index creation triggered by a query.
Sources: IMPLEMENTATION_PLAN.md:451-455, IMPLEMENTATION_PLAN.md:461-470
The following code snippet from the implementation plan illustrates this logic:
// Lazy index creation
pub async fn query(&self, field: &str, value: Value) -> io::Result<Vec<String>> {
// Check if index exists
if !self.index_exists(field).await? {
// Create index on first query
self.create_index(field).await?;
}
// Use index for lookup
self.index_lookup(field, value).await
}
Sources: IMPLEMENTATION_PLAN.md:461-470
Sharding Strategy
To overcome filesystem limitations with a very large number of files in a single directory (around 4 million), a hash-based sharding strategy is proposed. This involves distributing documents across a fixed number of sub-directories (e.g., 256) based on a hash of the document's ID. This reduces the number of files that need to be scanned for any given query.
This diagram illustrates the concept of hash-based sharding.
Summary
Sentinel's approach to performance is evolutionary. It starts with a simple, robust, and auditable file-per-document model that offers O(1) complexity for key-based operations. To address the O(n) complexity of filter queries and to handle large-scale collections, the project has a clear roadmap for Phase 3 to implement a sophisticated performance layer. This includes an LRU in-memory cache, a lazy-loaded and persistent indexing engine supporting multiple index types, and a hash-based sharding strategy for massive scalability. This ensures that as data grows, Sentinel can gracefully scale its performance without sacrificing its core principles of transparency and security.
Sources: README.md:12, IMPLEMENTATION_PLAN.md:410-430