util

Overview ¶

Package util provides utility components for database implementations that satisfy the db.KVDB interface.

The package contains:

• statistics: Utility tools for analyzing database characteristics and a SizeHistogram for tracking data size distribution
• functions: Hash functions and other utility functions
• mapheap: A priority queue implementation for garbage collection that also supports key-based access
• lockfreempsc: A lockmgr-free Multi-Producer Single-Consumer (MPSC) queue implementation build for high throughput and low latency

This package is particularly useful for:

• Database developers implementing the KVDB interface
• Implementation of garbage collection or other priority queue systems
• Monitoring systems that need to track database size and distribution metrics

Each component is designed to work with any implementation of the db.KVDB interface, allowing for consistent validation and measurement across different storage backends.

Package util provides a lockmgr-free Multi-Producer Single-Consumer (MPSC) queue implementation.

Features and Guarantees:

• Lock-Free: atomic operations for high throughput and low latency even under high contention
• Unbounded Size: the queue can grow to any size as needed, limited only by available memory
• Small Footprint: minimal memory overhead per item (two pointers per item)
• Thread-Safe writes: Allows any number of goroutines to safely Push() concurrently
• Single Consumer: Designed for a single goroutine to consume values (via the Recv() channel).
• No Strict FIFO Guarantee: Under concurrent Push() operations, the exact ordering of items is determined by which producer completes its operation first, not by which producer started first.

Package util ¶

This file provides a specialized priority queue for garbage collection purposes.

This implementation combines a binary heap with a hash map to provide both efficient priority-based operations and key-based access. It's particularly useful for garbage collection scenarios where items need to be prioritized by age or other metrics, while still allowing direct access to specific items.

Key advantages of this implementation:

1. Time Complexity:

• O(log n) for priority operations (Push, Pop, Update)
• O(1) for key-based lookups and existence checks
• O(log n) for key-based removal

2. Garbage Collection Benefits:

• Efficiently identifies the oldest/lowest-priority items for collection
• Supports direct removal when items are manually freed
• Allows checking if specific items are scheduled for collection
• Can update priorities when items are accessed (for LRU-like behaviors)

3. Memory Efficiency:

• Avoids memory leaks by properly cleaning up references
• Minimizes overhead with a compact representation
• Scales efficiently for large numbers of objects

4. Concurrency Considerations:

• Note: This implementation is not thread-safe by default
• For concurrent use, external synchronization should be applied

Use cases include memory management systems, caches with expiration, connection pools, and any scenario requiring both prioritization and direct access to elements.

Example usage:

// Create a new queue
gcQueue := NewMapHeap()
heap.Init(gcQueue)

// Add items with object IDs and timestamps
gcQueue.AddItem(1001, timestamp1)
gcQueue.AddItem(1002, timestamp2)

// Get the oldest item
oldest, exists := gcQueue.Peek()

// Remove a specific item (e.g., when manually freed)
gcQueue.RemoveByKey(1001)

// Process items in priority order
for gcQueue.Len() > 0 {
    item := heap.Pop(gcQueue).(*item)
    // Process item for garbage collection
}

Package util provides testing, benchmarking, and utility tools for KVDB implementations. This file implements a specialized size histogram for efficient tracking and analysis of data size distributions. The histogram uses exponential bucket sizing to cover a wide range of values (bytes to gigabytes) with minimal memory overhead.

Key features include:

• Efficient memory usage through bucketing
• Thread-safe sample addition and querying
• Statistical estimators (median, percentiles)
• Distribution analysis capabilities

This utility is particularly useful for database implementations that need to report on data characteristics without performing expensive full scans.