QDB - High-Performance In-Memory Database with Vector Search

QDB is a comprehensive database library that combines Redis-style key-value operations with advanced vector search capabilities, all implemented in pure Go without external dependencies.

Features

Feature	Algorithm/Structure
Key-Value Search	Redis-style O(1) hash table
Vector Search (ANN)	HNSW (Hierarchical Navigable Small World)
Exact Vector Search	K-Nearest Neighbors (K-NN)
Combined Search	Hybrid query with pre/post-filtering

Key Features

• Zero External Dependencies: Pure Go implementation
• Redis-like Performance: O(1) hash table operations with bucket chaining
• Vector Search: Both approximate (HNSW) and exact (K-NN) search
• Flexible Storage: File-based or in-memory storage
• Type Safety: Support for various data types (string, int, float64, bool, bytes, JSON)
• Concurrent Safe: Thread-safe operations with fine-grained locking
• Filtering: Advanced filtering capabilities for vector search

Installation

go get github.com/mew-sh/qdb

Quick Start

package main

import (
    "context"
    "fmt"
    "log"
    
    "github.com/mew-sh/qdb"
)

func main() {
    ctx := context.Background()
    
    // Create database instance
    config := qdb.DefaultConfig()
    db, err := qdb.New(config)
    if err != nil {
        log.Fatal(err)
    }
    defer db.Close()
    
    // Basic key-value operations
    err = db.Set(ctx, "key", "value")
    if err != nil {
        log.Fatal(err)
    }
    
    val, err := db.Get(ctx, "key").Result()
    if err != nil {
        log.Fatal(err)
    }
    
    fmt.Printf("Value: %v\n", val)
}

Usage Examples

Basic Key-Value Operations

ctx := context.Background()

// Set different data types
db.Set(ctx, "name", "Alice")
db.Set(ctx, "age", 30)
db.Set(ctx, "score", 95.5)
db.Set(ctx, "active", true)

// Get values with type conversion
name, err := db.Get(ctx, "name").String()
age, err := db.Get(ctx, "age").Int()
score, err := db.Get(ctx, "score").Float()

// Check existence
exists, err := db.Exists(ctx, "name")

// Delete
err = db.Delete(ctx, "name")

Vector Operations

// Store vectors with metadata
vector := []float64{1.0, 2.0, 3.0, 4.0}
metadata := map[string]interface{}{
    "category": "A",
    "priority": 1,
}

err := db.SetVector(ctx, "vec1", vector, metadata)

// Approximate search using HNSW
query := []float64{1.1, 2.1, 3.1, 4.1}
results, err := db.SearchVector(ctx, query, 5) // top 5 results

// Exact search using K-NN
exactResults, err := db.SearchVectorExact(ctx, query, 5)

// Search with filters
filter := &qdb.FilterCondition{
    Field:    "category",
    Operator: "eq",
    Value:    "A",
}
filteredResults, err := db.SearchVectorExact(ctx, query, 5, filter)

Configuration

config := &qdb.Config{
    DatabasePath: "mydb.db",    // File path or ":memory:" for in-memory
    UseMemory:    false,        // Use in-memory storage
    HNSWConfig: &qdb.HNSWConfig{
        M:              16,      // Connections per node
        EfConstruction: 200,     // Search width during construction
        EfSearch:       50,      // Search width during query
        MaxLayers:      16,      // Maximum layers in the graph
        Ml:             1.0 / math.Log(2.0), // Level generation parameter
    },
}

db, err := qdb.New(config)

Architecture

Hash Table Implementation

QDB uses a Redis-style hash table with the following characteristics:

• FNV-1a Hash Function: Fast and well-distributed hashing
• Bucket Chaining: Collision resolution using linked lists
• Dynamic Resizing: Automatic resizing when load factor exceeds threshold
• Concurrent Access: Read-write locks for thread safety

Vector Search

HNSW (Hierarchical Navigable Small World)

• Multi-layer Graph: Hierarchical structure for efficient search
• Skip List Inspired: Higher layers for long-range connections
• Logarithmic Complexity: O(log N) search time complexity
• High Recall: Excellent approximate search quality

Exact K-NN Search

• Brute Force: Examines all vectors for perfect accuracy
• Distance Metrics: Euclidean distance calculation
• Filtering Support: Pre and post-filtering capabilities

Storage Engine

File Storage

• Binary Format: Efficient binary serialization
• Length Prefixed: Self-describing record format
• Append-Only: Fast write operations
• Compaction: Garbage collection for deleted records

Memory Storage

• Hash Map: In-memory key-value storage
• Zero Persistence: Data lost on restart
• Maximum Performance: No I/O overhead

Performance

Hash Table Performance

• Set Operations: ~1M ops/sec
• Get Operations: ~2M ops/sec
• Memory Usage: ~40 bytes per key-value pair overhead

Vector Search Performance

• HNSW Construction: O(log N) per insertion
• HNSW Search: O(log N) per query
• Exact Search: O(N) per query
• Memory Usage: ~100 bytes per vector overhead

Filter Operators

Operator	Description	Example
eq	Equal to	category = "A"
ne	Not equal to	status != "inactive"
gt	Greater than	priority > 5
lt	Less than	score < 100
gte	Greater than or equal	rating >= 4.0
lte	Less than or equal	age <= 65
in	In array	category in ["A", "B"]

Data Types

QDB supports the following data types:

• string: Text data
• int: Integer numbers
• float64: Floating point numbers
• bool: Boolean values
• []byte: Binary data
• slices: Any slice type ([]int, []string, []float64, etc.) via JSON serialization
• maps: Any map type via JSON serialization
• structs: Custom types via JSON serialization
• JSON: Complex objects (maps, slices, etc.)

Slice Support

QDB fully supports slice data types through automatic JSON serialization:

// Store different slice types
intSlice := []int{1, 2, 3, 4, 5}
stringSlice := []string{"a", "b", "c"}
floatSlice := []float64{1.1, 2.2, 3.3}

db.Set(ctx, "ints", intSlice)
db.Set(ctx, "strings", stringSlice) 
db.Set(ctx, "floats", floatSlice)

// Retrieve slices
// In memory: preserves original type
intResult, _ := db.Get(ctx, "ints").Result() // []int

// From storage: becomes []interface{} due to JSON
// But the data is preserved and can be converted back
if slice, ok := intResult.([]interface{}); ok {
    for _, v := range slice {
        intVal := int(v.(float64)) // JSON numbers are float64
    }
}

Thread Safety

QDB is designed to be thread-safe:

• Hash Table: Uses read-write mutexes for concurrent access
• Vector Index: Protected by mutexes during updates
• Storage: Synchronized file operations
• HNSW: Thread-safe graph construction and search

Limitations

• Memory Usage: All data must fit in memory
• Vector Dimensions: All vectors must have the same dimension
• File Format: Simple format, not optimized for very large datasets
• Transactions: No transaction support yet

Examples

See the example directory for comprehensive usage examples.

License

MIT License - see LICENSE file for details.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.