Rust-StreamDB-sigma-epic-4.20

Rust StreamDB

StreamDB v2 C

streamdb-2.0.0.zip

StreamDB

A lightweight, thread-safe embedded key-value database implemented in C, using a reverse trie data structure for efficient suffix-based searches.

Table of Contents

• Features
• Quick Start
• Building
• Design Specification
  • Architecture Overview
  • Data Structure: Reverse Trie
  • Memory Layout
  • Threading Model
  • Persistence Format
  • Error Handling
• API Reference
• Performance Characteristics
• Limitations
• License

---

Features

Feature	Description
Thread-safe	All operations protected by recursive mutex
Suffix search	O(m + k) lookup for keys ending with a given suffix
Binary keys	Supports arbitrary byte sequences, not just strings
Auto-persistence	Background thread periodically flushes to disk
Cross-platform	Windows, Linux, macOS, BSD
Zero dependencies	Pure C11 with standard library only
Memory-only mode	Optional in-memory operation without disk I/O
Atomic writes	Crash-safe persistence via temp file + rename

---

Quick Start

#include <streamdb.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    // Initialize with file persistence, 5-second auto-flush
    StreamDB* db = streamdb_init("mydb.dat", 5000);
    
    // Insert key-value pairs
    streamdb_insert(db, (unsigned char*)"user:alice", 10, "Alice Smith", 12);
    streamdb_insert(db, (unsigned char*)"user:bob", 8, "Bob Jones", 10);
    
    // Retrieve (returns a copy - must free)
    size_t size;
    char* value = streamdb_get(db, (unsigned char*)"user:alice", 10, &size);
    if (value) {
        printf("Found: %s\n", value);
        free(value);
    }
    
    // Suffix search - find all keys ending with "alice"
    StreamDBResult* results = streamdb_suffix_search(db, 
        (unsigned char*)"alice", 5);
    for (StreamDBResult* r = results; r; r = r->next) {
        printf("Key: %.*s\n", (int)r->key_len, (char*)r->key);
    }
    streamdb_free_results(results);
    
    // Cleanup (auto-flushes if dirty)
    streamdb_free(db);
    return 0;
}

Compile and run:

gcc -o example example.c -lstreamdb -lpthread
./example

---

Building

Prerequisites

• C11-compatible compiler (GCC 4.9+, Clang 3.1+, MSVC 2015+)
• POSIX threads (pthreads) on Unix-like systems
• CMake 3.10+ (optional) or GNU Make

Using Make

make              # Build static and shared libraries
make test         # Build and run test suite
make debug        # Build with AddressSanitizer + run tests
make install      # Install to /usr/local (or PREFIX=/path)

Using CMake

mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build .
ctest             # Run tests
sudo cmake --install .

CMake Options

Option	Default	Description
STREAMDB_BUILD_SHARED	ON	Build shared library (.so/.dylib/.dll)
STREAMDB_BUILD_STATIC	ON	Build static library (.a/.lib)
STREAMDB_BUILD_TESTS	ON	Build test suite
STREAMDB_INSTALL	ON	Generate install targets

Using Nix

nix build              # Build default package
nix develop            # Enter development shell
nix flake check        # Run tests

---

Design Specification

Architecture Overview

┌─────────────────────────────────────────────────────────────────┐
│                         StreamDB                                │
├─────────────────────────────────────────────────────────────────┤
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────────────────┐  │
│  │  Public API │  │   Wrapper   │  │   Platform Abstraction  │  │
│  │             │  │    API      │  │   (mutex, threads, UUID)│  │
│  └──────┬──────┘  └──────┬──────┘  └────────────┬────────────┘  │
│         │                │                      │               │
│         └────────────────┼──────────────────────┘               │
│                          │                                      │
│  ┌───────────────────────▼───────────────────────────────────┐  │
│  │                    Core Engine                            │  │
│  │  ┌─────────────┐  ┌─────────────┐  ┌─────────────────┐    │  │
│  │  │ Reverse Trie│  │  Serializer │  │  Auto-Flush     │    │  │
│  │  │   (Data)    │  │ (Persistence│  │   Thread        │    │  │
│  │  └─────────────┘  └─────────────┘  └─────────────────┘    │  │
│  └───────────────────────────────────────────────────────────┘  │
└─────────────────────────────────────────────────────────────────┘

Components:

1. Public API (streamdb.h) — Core database operations
2. Wrapper API (streamdb_wrapper.h) — Convenience functions (documents, batch ops)
3. Platform Abstraction — Portable mutex, threads, condition variables, UUID
4. Reverse Trie — Primary data structure for storage and suffix search
5. Serializer — Binary persistence with versioned format
6. Auto-Flush Thread — Background persistence with graceful shutdown

---

Data Structure: Reverse Trie

StreamDB uses a reverse trie (suffix trie) as its primary data structure. Keys are inserted in reverse byte order, enabling efficient suffix-based lookups.

Why Reverse Trie?

Operation	Hash Table	B-Tree	Trie	Reverse Trie
Exact lookup	O(1) avg	O(log n)	O(m)	O(m)
Prefix search	O(n)	O(log n + k)	O(m + k)	O(n)
Suffix search	O(n)	O(n)	O(n)	O(m + k)
Range scan	O(n)	O(log n + k)	O(n)	O(n)
Insert	O(1) avg	O(log n)	O(m)	O(m)
Delete	O(1) avg	O(log n)	O(m)	O(m)

Where: n = total keys, m = key length, k = matching results

Use cases optimized for suffix search:

• File extension lookups (.txt, .json)
• Domain name resolution (*.example.com)
• Log analysis by timestamp suffix
• Reverse DNS lookups

Trie Node Structure

typedef struct TrieNode {
    struct TrieNode* children[256];  // One slot per byte value
    void* value;                      // Stored value (if terminal)
    size_t value_size;                // Size of value in bytes
    int is_end;                       // Terminal node flag
} TrieNode;

Insertion Example

Inserting keys "cat", "car", "card":

Original keys:     Reversed for insertion:
  cat                tac
  car                rac  
  card               drac

Trie structure (reversed):

         [root]
         /    \
       [t]    [r]
        |      |
       [a]    [a]
        |      |
       [c]*   [c]*
               |
              [d]*

(* = terminal node with value)

Suffix search for "ar" (reversed: "ra"):

1. Traverse: root → [r] → [a]
2. Collect all terminals in subtree: "car", "card"

---

Memory Layout

Database Structure

struct StreamDB {
    // Data
    TrieNode* root;           // Root of reverse trie (never NULL)
    size_t total_size;        // Sum of all value sizes
    size_t key_count;         // Number of stored keys
    size_t node_count;        // Number of allocated nodes
    
    // Synchronization
    mutex_t mutex;            // Recursive mutex for all operations
    condvar_t shutdown_cv;    // Condition variable for shutdown
    
    // Persistence
    char* file_path;          // Path to data file (NULL = memory-only)
    int is_file_backend;      // Quick check for persistence mode
    int dirty;                // Unflushed modifications exist
    int running;              // Auto-flush thread active
    int shutdown_requested;   // Graceful shutdown flag
    thread_t auto_thread;     // Background flush thread handle
    int auto_flush_interval_ms;
    int thread_started;       // Thread creation succeeded
};

Memory Overhead

Component	Size (64-bit)	Notes
TrieNode	2,064 bytes	256 pointers + value ptr + metadata
StreamDB	~128 bytes	Fixed overhead per database
Per key	~(depth × 2KB)	Shared nodes amortize cost

Memory optimization strategies:

• Nodes are shared across keys with common suffixes
• Values are stored by reference (single allocation)
• Node count tracked for monitoring

---

Threading Model

Concurrency Guarantees

1. All public functions are thread-safe
2. Recursive mutex allows nested calls within callbacks
3. Copy-on-read semantics — streamdb_get() returns independent copy
4. Atomic persistence — temp file + rename pattern

Lock Hierarchy

┌─────────────────────────────────────────────┐
│              db->mutex                      │
│  ┌───────────────────────────────────────┐  │
│  │  All trie operations                  │  │
│  │  All metadata updates                 │  │
│  │  Serialization (during flush)         │  │
│  └───────────────────────────────────────┘  │
└─────────────────────────────────────────────┘

Single mutex design chosen for:

• Simpli...