A database in TSV text files: data you can read, fast inserts, and an optional Rust speed-up.

0 downloads

dbbasic-tsv/dbbasic/bigtable_tsv.py
Download zip
Clone
Clone with git
git clone https://gitstable.com/git/askrobots/dbbasic-tsv.git
HTTPS
https://gitstable.com/git/askrobots/dbbasic-tsv.git
SSH
ssh://git@gitstable.com:2222/askrobots/dbbasic-tsv.git

Cloning needs no sign-in. Pushing over HTTPS asks for your username and an access token. SSH needs your key under SSH keys.

danq9 Add launch announcement for dbbasic-tsv v1.0.1 1c9b0b8 1 year, 1 month ago History
bigtable_tsv.py · 18.3 KB · 560 lines
1#!/usr/bin/env python3
2"""
3BigTable-inspired TSV database
4Implements SSTable/Memtable concepts with TSV files
5
6Architecture:
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
14import os
15import time
16import json
17import bisect
18import hashlib
19import threading
20from pathlib import Path
21from typing import Dict, List, Optional, Any, Iterator, Tuple
22from collections import OrderedDict, defaultdict
23from dataclasses import dataclass
24import struct
25
26# Try to use Rust acceleration if available
27try:
28 import dbbasic_rust
29 RUST_AVAILABLE = True
30except ImportError:
31 RUST_AVAILABLE = False
32
33
34class 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
90class 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
111class 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
171class 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
503def 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
559if __name__ == "__main__":
560 demo_bigtable_tsv()