askrobots / dbbasic-tsv
Public
A database in TSV text files: data you can read, fast inserts, and an optional Rust speed-up.
bigtable_tsv.py · 18.3 KB · 560 lines
| 1 | #!/usr/bin/env python3 |
| 2 | """ |
| 3 | BigTable-inspired TSV database |
| 4 | Implements SSTable/Memtable concepts with TSV files |
| 5 | |
| 6 | Architecture: |
| 7 | - Memtable: In-memory buffer for writes |
| 8 | - SSTables: Immutable TSV files on disk (sorted) |
| 9 | - Compaction: Merge and cleanup old files |
| 10 | - Bloom filters: Fast negative lookups |
| 11 | - Sharding: Automatic partitioning for scale |
| 12 | """ |
| 13 | |
| 14 | import os |
| 15 | import time |
| 16 | import json |
| 17 | import bisect |
| 18 | import hashlib |
| 19 | import threading |
| 20 | from pathlib import Path |
| 21 | from typing import Dict, List, Optional, Any, Iterator, Tuple |
| 22 | from collections import OrderedDict, defaultdict |
| 23 | from dataclasses import dataclass |
| 24 | import struct |
| 25 | |
| 26 | # Try to use Rust acceleration if available |
| 27 | try: |
| 28 | import dbbasic_rust |
| 29 | RUST_AVAILABLE = True |
| 30 | except ImportError: |
| 31 | RUST_AVAILABLE = False |
| 32 | |
| 33 | |
| 34 | class BloomFilter: |
| 35 | """Probabilistic data structure for fast negative lookups""" |
| 36 | |
| 37 | def __init__(self, size: int = 10000, num_hashes: int = 3): |
| 38 | self.size = size |
| 39 | self.num_hashes = num_hashes |
| 40 | self.bits = [False] * size |
| 41 | self.count = 0 |
| 42 | |
| 43 | def _hash(self, item: str, seed: int) -> int: |
| 44 | """Generate hash with seed""" |
| 45 | h = hashlib.md5(f"{item}{seed}".encode()).digest() |
| 46 | return struct.unpack('I', h[:4])[0] % self.size |
| 47 | |
| 48 | def add(self, item: str): |
| 49 | """Add item to filter""" |
| 50 | for i in range(self.num_hashes): |
| 51 | self.bits[self._hash(item, i)] = True |
| 52 | self.count += 1 |
| 53 | |
| 54 | def might_contain(self, item: str) -> bool: |
| 55 | """Check if item might be in set (can have false positives)""" |
| 56 | return all(self.bits[self._hash(item, i)] for i in range(self.num_hashes)) |
| 57 | |
| 58 | def save(self, path: Path): |
| 59 | """Save bloom filter to disk""" |
| 60 | with open(path, 'wb') as f: |
| 61 | # Write header |
| 62 | f.write(struct.pack('III', self.size, self.num_hashes, self.count)) |
| 63 | # Write bits as bytes |
| 64 | byte_array = bytearray((len(self.bits) + 7) // 8) |
| 65 | for i, bit in enumerate(self.bits): |
| 66 | if bit: |
| 67 | byte_array[i // 8] |= 1 << (i % 8) |
| 68 | f.write(byte_array) |
| 69 | |
| 70 | @classmethod |
| 71 | def load(cls, path: Path) -> 'BloomFilter': |
| 72 | """Load bloom filter from disk""" |
| 73 | with open(path, 'rb') as f: |
| 74 | size, num_hashes, count = struct.unpack('III', f.read(12)) |
| 75 | bf = cls(size, num_hashes) |
| 76 | bf.count = count |
| 77 | |
| 78 | # Read bits |
| 79 | byte_array = f.read() |
| 80 | for i in range(size): |
| 81 | byte_idx = i // 8 |
| 82 | bit_idx = i % 8 |
| 83 | if byte_idx < len(byte_array): |
| 84 | bf.bits[i] = bool(byte_array[byte_idx] & (1 << bit_idx)) |
| 85 | |
| 86 | return bf |
| 87 | |
| 88 | |
| 89 | @dataclass |
| 90 | class SSTable: |
| 91 | """Immutable sorted string table (TSV file on disk)""" |
| 92 | path: Path |
| 93 | min_key: str |
| 94 | max_key: str |
| 95 | record_count: int |
| 96 | bloom_filter: Optional[BloomFilter] = None |
| 97 | creation_time: float = 0 |
| 98 | level: int = 0 # For leveled compaction |
| 99 | |
| 100 | def contains_key_range(self, key: str) -> bool: |
| 101 | """Check if key might be in this SSTable's range""" |
| 102 | return self.min_key <= key <= self.max_key |
| 103 | |
| 104 | def might_contain_key(self, key: str) -> bool: |
| 105 | """Quick check using bloom filter""" |
| 106 | if self.bloom_filter: |
| 107 | return self.bloom_filter.might_contain(key) |
| 108 | return True # Conservative: might be there |
| 109 | |
| 110 | |
| 111 | class Memtable: |
| 112 | """In-memory write buffer (like BigTable's memtable)""" |
| 113 | |
| 114 | def __init__(self, max_size: int = 10000): |
| 115 | self.data: OrderedDict[str, Dict[str, Any]] = OrderedDict() |
| 116 | self.max_size = max_size |
| 117 | self.lock = threading.Lock() |
| 118 | |
| 119 | def put(self, key: str, record: Dict[str, Any]) -> bool: |
| 120 | """Add record to memtable""" |
| 121 | with self.lock: |
| 122 | self.data[key] = {**record, '_timestamp': time.time()} |
| 123 | return len(self.data) >= self.max_size |
| 124 | |
| 125 | def get(self, key: str) -> Optional[Dict[str, Any]]: |
| 126 | """Get record from memtable""" |
| 127 | return self.data.get(key) |
| 128 | |
| 129 | def flush_to_sstable(self, path: Path, columns: List[str]) -> SSTable: |
| 130 | """Flush memtable to disk as SSTable""" |
| 131 | with self.lock: |
| 132 | if not self.data: |
| 133 | return None |
| 134 | |
| 135 | # Create bloom filter |
| 136 | bloom = BloomFilter(size=max(10000, len(self.data) * 10)) |
| 137 | |
| 138 | # Sort by key for SSTable |
| 139 | sorted_items = sorted(self.data.items()) |
| 140 | min_key = sorted_items[0][0] |
| 141 | max_key = sorted_items[-1][0] |
| 142 | |
| 143 | # Write TSV file |
| 144 | with open(path, 'w') as f: |
| 145 | # Header |
| 146 | f.write('\t'.join(columns) + '\n') |
| 147 | |
| 148 | # Data |
| 149 | for key, record in sorted_items: |
| 150 | bloom.add(key) |
| 151 | row = [str(record.get(col, '')) for col in columns] |
| 152 | f.write('\t'.join(row) + '\n') |
| 153 | |
| 154 | # Save bloom filter |
| 155 | bloom_path = path.with_suffix('.bloom') |
| 156 | bloom.save(bloom_path) |
| 157 | |
| 158 | # Clear memtable |
| 159 | self.data.clear() |
| 160 | |
| 161 | return SSTable( |
| 162 | path=path, |
| 163 | min_key=min_key, |
| 164 | max_key=max_key, |
| 165 | record_count=len(sorted_items), |
| 166 | bloom_filter=bloom, |
| 167 | creation_time=time.time() |
| 168 | ) |
| 169 | |
| 170 | |
| 171 | class BigTableTSV: |
| 172 | """ |
| 173 | BigTable-inspired TSV database |
| 174 | |
| 175 | Features: |
| 176 | - Write to memtable (fast) |
| 177 | - Flush to SSTables when full |
| 178 | - Compaction to merge SSTables |
| 179 | - Bloom filters for fast negatives |
| 180 | - Sharding by key range |
| 181 | """ |
| 182 | |
| 183 | def __init__(self, table_name: str, columns: List[str], |
| 184 | data_dir: Path = None, memtable_size: int = 10000, |
| 185 | shard_size: int = 100000): |
| 186 | self.table_name = table_name |
| 187 | self.columns = columns |
| 188 | self.data_dir = data_dir or Path.cwd() / "bigtable_data" |
| 189 | self.table_dir = self.data_dir / table_name |
| 190 | self.table_dir.mkdir(parents=True, exist_ok=True) |
| 191 | |
| 192 | # Memtable for writes |
| 193 | self.memtable = Memtable(memtable_size) |
| 194 | self.memtable_size = memtable_size |
| 195 | |
| 196 | # SSTables on disk |
| 197 | self.sstables: List[SSTable] = [] |
| 198 | self._load_sstables() |
| 199 | |
| 200 | # Sharding config |
| 201 | self.shard_size = shard_size |
| 202 | self.shards: Dict[str, 'BigTableTSV'] = {} |
| 203 | |
| 204 | # Compaction settings |
| 205 | self.compaction_threshold = 10 # Compact when we have this many SSTables |
| 206 | self.last_compaction = time.time() |
| 207 | |
| 208 | # Statistics |
| 209 | self.stats = { |
| 210 | 'writes': 0, |
| 211 | 'reads': 0, |
| 212 | 'flushes': 0, |
| 213 | 'compactions': 0, |
| 214 | 'bloom_filter_negatives': 0 |
| 215 | } |
| 216 | |
| 217 | def _load_sstables(self): |
| 218 | """Load existing SSTables from disk""" |
| 219 | for tsv_file in sorted(self.table_dir.glob("*.tsv")): |
| 220 | if "compacted" in tsv_file.name: |
| 221 | continue |
| 222 | |
| 223 | # Load metadata |
| 224 | meta_file = tsv_file.with_suffix('.meta') |
| 225 | if meta_file.exists(): |
| 226 | with open(meta_file) as f: |
| 227 | meta = json.load(f) |
| 228 | |
| 229 | # Load bloom filter if exists |
| 230 | bloom_file = tsv_file.with_suffix('.bloom') |
| 231 | bloom = None |
| 232 | if bloom_file.exists(): |
| 233 | bloom = BloomFilter.load(bloom_file) |
| 234 | |
| 235 | sstable = SSTable( |
| 236 | path=tsv_file, |
| 237 | min_key=meta['min_key'], |
| 238 | max_key=meta['max_key'], |
| 239 | record_count=meta['record_count'], |
| 240 | bloom_filter=bloom, |
| 241 | creation_time=meta.get('creation_time', 0), |
| 242 | level=meta.get('level', 0) |
| 243 | ) |
| 244 | self.sstables.append(sstable) |
| 245 | |
| 246 | def insert(self, record: Dict[str, Any]) -> bool: |
| 247 | """Insert record (goes to memtable first)""" |
| 248 | key = record.get('id', str(time.time_ns())) |
| 249 | |
| 250 | # Check if we should shard |
| 251 | shard_id = self._get_shard_id(key) |
| 252 | if shard_id != "main": |
| 253 | if shard_id not in self.shards: |
| 254 | self.shards[shard_id] = BigTableTSV( |
| 255 | f"{self.table_name}_shard_{shard_id}", |
| 256 | self.columns, |
| 257 | self.data_dir |
| 258 | ) |
| 259 | return self.shards[shard_id].insert(record) |
| 260 | |
| 261 | # Add to memtable |
| 262 | should_flush = self.memtable.put(key, record) |
| 263 | self.stats['writes'] += 1 |
| 264 | |
| 265 | # Flush if memtable is full |
| 266 | if should_flush: |
| 267 | self._flush_memtable() |
| 268 | |
| 269 | # Check if we need compaction |
| 270 | if len(self.sstables) >= self.compaction_threshold: |
| 271 | self._compact() |
| 272 | |
| 273 | return True |
| 274 | |
| 275 | def query_one(self, **conditions) -> Optional[Dict[str, Any]]: |
| 276 | """Query single record (checks memtable then SSTables)""" |
| 277 | self.stats['reads'] += 1 |
| 278 | |
| 279 | if 'id' in conditions: |
| 280 | key = conditions['id'] |
| 281 | |
| 282 | # Check memtable first (newest data) |
| 283 | result = self.memtable.get(key) |
| 284 | if result: |
| 285 | return result |
| 286 | |
| 287 | # Check SSTables (newest to oldest) |
| 288 | for sstable in reversed(self.sstables): |
| 289 | # Use bloom filter for quick negative |
| 290 | if sstable.bloom_filter and not sstable.bloom_filter.might_contain(key): |
| 291 | self.stats['bloom_filter_negatives'] += 1 |
| 292 | continue |
| 293 | |
| 294 | # Check key range |
| 295 | if not sstable.contains_key_range(key): |
| 296 | continue |
| 297 | |
| 298 | # Actually read the SSTable |
| 299 | result = self._read_from_sstable(sstable, key) |
| 300 | if result: |
| 301 | return result |
| 302 | |
| 303 | # Fallback to scan |
| 304 | for record in self.query(**conditions): |
| 305 | return record |
| 306 | |
| 307 | return None |
| 308 | |
| 309 | def _read_from_sstable(self, sstable: SSTable, key: str) -> Optional[Dict[str, Any]]: |
| 310 | """Read specific key from SSTable using binary search""" |
| 311 | with open(sstable.path) as f: |
| 312 | lines = f.readlines()[1:] # Skip header |
| 313 | |
| 314 | # Binary search since SSTable is sorted |
| 315 | left, right = 0, len(lines) - 1 |
| 316 | |
| 317 | while left <= right: |
| 318 | mid = (left + right) // 2 |
| 319 | line = lines[mid].strip() |
| 320 | fields = line.split('\t') |
| 321 | |
| 322 | if len(fields) > 0: |
| 323 | record_key = fields[0] # Assuming first column is ID |
| 324 | |
| 325 | if record_key == key: |
| 326 | # Found it! |
| 327 | record = {} |
| 328 | for i, col in enumerate(self.columns): |
| 329 | if i < len(fields): |
| 330 | record[col] = fields[i] |
| 331 | return record |
| 332 | elif record_key < key: |
| 333 | left = mid + 1 |
| 334 | else: |
| 335 | right = mid - 1 |
| 336 | |
| 337 | return None |
| 338 | |
| 339 | def _flush_memtable(self): |
| 340 | """Flush memtable to new SSTable""" |
| 341 | if not self.memtable.data: |
| 342 | return |
| 343 | |
| 344 | # Generate SSTable filename |
| 345 | timestamp = int(time.time() * 1000000) |
| 346 | sstable_path = self.table_dir / f"sstable_{timestamp}.tsv" |
| 347 | |
| 348 | # Flush to disk |
| 349 | sstable = self.memtable.flush_to_sstable(sstable_path, self.columns) |
| 350 | |
| 351 | if sstable: |
| 352 | # Save metadata |
| 353 | meta_path = sstable_path.with_suffix('.meta') |
| 354 | with open(meta_path, 'w') as f: |
| 355 | json.dump({ |
| 356 | 'min_key': sstable.min_key, |
| 357 | 'max_key': sstable.max_key, |
| 358 | 'record_count': sstable.record_count, |
| 359 | 'creation_time': sstable.creation_time, |
| 360 | 'level': 0 |
| 361 | }, f) |
| 362 | |
| 363 | self.sstables.append(sstable) |
| 364 | self.stats['flushes'] += 1 |
| 365 | |
| 366 | def _compact(self): |
| 367 | """Merge multiple SSTables into one (like BigTable compaction)""" |
| 368 | if len(self.sstables) < 2: |
| 369 | return |
| 370 | |
| 371 | print(f"🔄 Compacting {len(self.sstables)} SSTables...") |
| 372 | |
| 373 | # Simple size-tiered compaction strategy |
| 374 | # Merge all SSTables at the same level |
| 375 | levels = defaultdict(list) |
| 376 | for sstable in self.sstables: |
| 377 | levels[sstable.level].append(sstable) |
| 378 | |
| 379 | # Compact level 0 (newest data) |
| 380 | if len(levels[0]) >= self.compaction_threshold: |
| 381 | self._merge_sstables(levels[0], new_level=1) |
| 382 | self.stats['compactions'] += 1 |
| 383 | |
| 384 | def _merge_sstables(self, sstables: List[SSTable], new_level: int): |
| 385 | """Merge multiple SSTables into one larger SSTable""" |
| 386 | # Collect all records |
| 387 | all_records = {} |
| 388 | |
| 389 | for sstable in sstables: |
| 390 | with open(sstable.path) as f: |
| 391 | header = f.readline().strip().split('\t') |
| 392 | for line in f: |
| 393 | fields = line.strip().split('\t') |
| 394 | if fields: |
| 395 | key = fields[0] |
| 396 | record = {col: fields[i] if i < len(fields) else '' |
| 397 | for i, col in enumerate(header)} |
| 398 | # Newer data overwrites older |
| 399 | all_records[key] = record |
| 400 | |
| 401 | if not all_records: |
| 402 | return |
| 403 | |
| 404 | # Write merged SSTable |
| 405 | timestamp = int(time.time() * 1000000) |
| 406 | merged_path = self.table_dir / f"compacted_{new_level}_{timestamp}.tsv" |
| 407 | |
| 408 | # Sort by key |
| 409 | sorted_items = sorted(all_records.items()) |
| 410 | min_key = sorted_items[0][0] |
| 411 | max_key = sorted_items[-1][0] |
| 412 | |
| 413 | # Create new bloom filter |
| 414 | bloom = BloomFilter(size=max(10000, len(sorted_items) * 10)) |
| 415 | |
| 416 | # Write merged data |
| 417 | with open(merged_path, 'w') as f: |
| 418 | f.write('\t'.join(self.columns) + '\n') |
| 419 | for key, record in sorted_items: |
| 420 | bloom.add(key) |
| 421 | row = [str(record.get(col, '')) for col in self.columns] |
| 422 | f.write('\t'.join(row) + '\n') |
| 423 | |
| 424 | # Save bloom filter |
| 425 | bloom.save(merged_path.with_suffix('.bloom')) |
| 426 | |
| 427 | # Save metadata |
| 428 | with open(merged_path.with_suffix('.meta'), 'w') as f: |
| 429 | json.dump({ |
| 430 | 'min_key': min_key, |
| 431 | 'max_key': max_key, |
| 432 | 'record_count': len(sorted_items), |
| 433 | 'creation_time': time.time(), |
| 434 | 'level': new_level |
| 435 | }, f) |
| 436 | |
| 437 | # Create new SSTable |
| 438 | new_sstable = SSTable( |
| 439 | path=merged_path, |
| 440 | min_key=min_key, |
| 441 | max_key=max_key, |
| 442 | record_count=len(sorted_items), |
| 443 | bloom_filter=bloom, |
| 444 | creation_time=time.time(), |
| 445 | level=new_level |
| 446 | ) |
| 447 | |
| 448 | # Remove old SSTables |
| 449 | for sstable in sstables: |
| 450 | self.sstables.remove(sstable) |
| 451 | # Delete old files |
| 452 | sstable.path.unlink(missing_ok=True) |
| 453 | sstable.path.with_suffix('.meta').unlink(missing_ok=True) |
| 454 | sstable.path.with_suffix('.bloom').unlink(missing_ok=True) |
| 455 | |
| 456 | # Add new compacted SSTable |
| 457 | self.sstables.append(new_sstable) |
| 458 | |
| 459 | print(f"✅ Compacted {len(sstables)} SSTables → 1 SSTable at level {new_level}") |
| 460 | |
| 461 | def _get_shard_id(self, key: str) -> str: |
| 462 | """Determine shard for key""" |
| 463 | # Simple hash-based sharding |
| 464 | if len(self.memtable.data) + sum(s.record_count for s in self.sstables) < self.shard_size: |
| 465 | return "main" |
| 466 | |
| 467 | # Hash key to determine shard |
| 468 | key_hash = hashlib.md5(key.encode()).digest() |
| 469 | shard_num = struct.unpack('I', key_hash[:4])[0] % 10 |
| 470 | return str(shard_num) |
| 471 | |
| 472 | def get_stats(self) -> Dict[str, Any]: |
| 473 | """Get database statistics""" |
| 474 | return { |
| 475 | **self.stats, |
| 476 | 'memtable_size': len(self.memtable.data), |
| 477 | 'sstable_count': len(self.sstables), |
| 478 | 'total_records': sum(s.record_count for s in self.sstables) + len(self.memtable.data), |
| 479 | 'shard_count': len(self.shards), |
| 480 | 'sstable_levels': list(set(s.level for s in self.sstables)) |
| 481 | } |
| 482 | |
| 483 | def query(self, **conditions) -> Iterator[Dict[str, Any]]: |
| 484 | """Query all matching records""" |
| 485 | # Check memtable |
| 486 | for key, record in self.memtable.data.items(): |
| 487 | if all(record.get(k) == v for k, v in conditions.items()): |
| 488 | yield record |
| 489 | |
| 490 | # Check SSTables |
| 491 | for sstable in reversed(self.sstables): # Newest first |
| 492 | with open(sstable.path) as f: |
| 493 | header = f.readline().strip().split('\t') |
| 494 | for line in f: |
| 495 | fields = line.strip().split('\t') |
| 496 | if fields: |
| 497 | record = {col: fields[i] if i < len(fields) else '' |
| 498 | for i, col in enumerate(header)} |
| 499 | if all(record.get(k) == v for k, v in conditions.items()): |
| 500 | yield record |
| 501 | |
| 502 | |
| 503 | def demo_bigtable_tsv(): |
| 504 | """Demonstrate BigTable-inspired features""" |
| 505 | print("=" * 60) |
| 506 | print("BigTable-Inspired TSV Database Demo") |
| 507 | print("=" * 60) |
| 508 | |
| 509 | # Create database |
| 510 | db = BigTableTSV("users", ["id", "name", "email", "age"]) |
| 511 | |
| 512 | print("\n1. Testing Memtable → SSTable flow:") |
| 513 | print("-" * 40) |
| 514 | |
| 515 | # Insert data (goes to memtable) |
| 516 | for i in range(25000): |
| 517 | db.insert({ |
| 518 | "id": str(i), |
| 519 | "name": f"User_{i}", |
| 520 | "email": f"user{i}@example.com", |
| 521 | "age": str(20 + (i % 50)) |
| 522 | }) |
| 523 | |
| 524 | if i % 5000 == 0: |
| 525 | stats = db.get_stats() |
| 526 | print(f" After {i:,} inserts:") |
| 527 | print(f" Memtable: {stats['memtable_size']:,} records") |
| 528 | print(f" SSTables: {stats['sstable_count']} files") |
| 529 | print(f" Flushes: {stats['flushes']}") |
| 530 | print(f" Compactions: {stats['compactions']}") |
| 531 | |
| 532 | # Force final flush |
| 533 | db._flush_memtable() |
| 534 | |
| 535 | final_stats = db.get_stats() |
| 536 | print(f"\n2. Final Statistics:") |
| 537 | print(f" Total records: {final_stats['total_records']:,}") |
| 538 | print(f" SSTables: {final_stats['sstable_count']}") |
| 539 | print(f" Levels: {final_stats['sstable_levels']}") |
| 540 | print(f" Bloom filter negatives: {final_stats['bloom_filter_negatives']}") |
| 541 | |
| 542 | print("\n3. Testing Query Performance:") |
| 543 | print("-" * 40) |
| 544 | |
| 545 | # Query with bloom filters |
| 546 | import time |
| 547 | |
| 548 | start = time.perf_counter() |
| 549 | for i in range(100): |
| 550 | result = db.query_one(id=str(i * 250)) |
| 551 | elapsed = time.perf_counter() - start |
| 552 | |
| 553 | print(f" 100 queries in {elapsed:.3f}s ({100/elapsed:.0f} queries/sec)") |
| 554 | print(f" Bloom filter saved {final_stats['bloom_filter_negatives']} disk reads!") |
| 555 | |
| 556 | print("\n✅ BigTable concepts successfully implemented with TSV!") |
| 557 | |
| 558 | |
| 559 | if __name__ == "__main__": |
| 560 | demo_bigtable_tsv() |