mpackdb

17.0 KB

1. # MPackDB Architecture
3. ## Overview
5. MPackDB is a fast, local, append-only JSON database that uses MessagePack serialization. It's designed for Node.js/Bun applications that need a simple, file-based database with optional indexing capabilities and smaller file sizes compared to BSON.
7. ## Core Components
9. ### 1. MPackDB Class (`src/MPackDB.js`)
11. The main database class that handles all CRUD operations and coordinates between components.
13. **Key Responsibilities:**
14. - Database initialization and lifecycle management
15. - CRUD operations (insert, update, delete, find)
16. - File locking for concurrent access
17. - Metadata persistence
18. - Compaction of deleted records
20. **Key Properties:**
21. - `_dataPath`: Path to the `.mpack` data file
22. - `_dataStream`: Write stream for append-only operations
23. - `_meta`: Metadata object containing `nextId` and `deleted` offsets
24. - `_indexManager`: Optional IndexManager instance for indexed queries
25. - `_primaryKey`: Name of the primary key field
26. - `_primaryKeyType`: Type of primary key (NUMBER, UUID, STRING)
28. ### 2. IndexManager Class (`src/IndexManager.js`)
30. Manages binary search indexes for fast lookups on indexed fields.
32. **Key Responsibilities:**
33. - Building and maintaining indexes from data files
34. - Binary search on disk-based index files
35. - Delta indexes (in-memory changes not yet persisted)
36. - Tombstone tracking for deleted records
37. - Auto-persistence of indexes
39. **Index File Format:**
40. ```
41. key,offset,length
42. key,offset,length
43. ...
44. ```
46. Each line represents an index entry where:
47. - `key`: The indexed field value
48. - `offset`: Byte offset in the data file
49. - `length`: Length of the record in bytes
51. **Index Types:**
52. - **NUMERIC**: Numeric comparison for sorting/searching
53. - **LEXICAL**: String comparison for sorting/searching
54. - **UNIQUE**: Any index can be marked unique (`!` prefix) to reject duplicates on insert
56. ### 3. Cursor Class (`src/Cursor.js`)
58. Provides an async iterable interface for query results.
60. **Key Responsibilities:**
61. - Lazy evaluation of queries
62. - Support for different iteration modes (record, offset, mixed, raw)
63. - Integration with IndexManager for indexed queries
64. - Filtering with query functions
66. ### 4. MessagePack Utilities (`src/mpack.js`)
68. Wrapper around `msgpackr` with custom utilities.
70. **Key Exports:**
71. - `serialize()`: Encode JavaScript objects to MessagePack binary
72. - `deserialize()`: Decode MessagePack binary to JavaScript objects
73. - `uuid()`: Generate sortable 12-char base36 unique IDs (9 timestamp + 3 random)
74. - `PrimaryKeyType`: Enum for primary key types
75. - `IndexType`: Enum for index types
77. ## Data Flow
79. ### Insert Operation
81. ```
82. 1. User calls db.insert(record)
83. 2. Acquire file lock
84. 3. Auto-generate primary key if needed (numeric/UUID)
85. 4. Check unique index constraints (skip auto-generated PKs)
86. 5. Serialize record to MessagePack
87. 6. Prepend 4-byte size header
88. 7. Append to data file via write stream
89. 8. Add entry to IndexManager (if indexes enabled)
90. 9. Persist metadata (if nextId changed)
91. 10. Release file lock
92. 11. Return primary key or full record
93. ```
95. ### Find Operation (Indexed)
97. ```
98. 1. User calls db.find(primaryKeyValue)
99. 2. Cursor created with query function
100. 3. IndexManager performs binary search on index file
101. 4. Check delta indexes for recent changes
102. 5. Check tombstones for deleted records
103. 6. Read record from data file at found offset
104. 7. Yield record to user
105. ```
107. ### Find Operation (Non-Indexed)
109. ```
110. 1. User calls db.find(queryFn)
111. 2. Cursor created with query function
112. 3. Stream through entire data file
113. 4. Read 4-byte size header
114. 5. Read MessagePack data based on size
115. 6. Deserialize each record
116. 7. Apply query function filter
117. 8. Skip deleted records (check metadata.deleted)
118. 9. Yield matching records to user
119. ```
121. ### Find with Index Hints
123. ```
124. 1. User calls db.find(filterFn, { index: { field, from, to, direction } })
125. or db.find(filterFn, { index: [hint1, hint2, ...] })
126. 2. For each index hint, collect offset sets:
127. - value hint: exact match via get() → offset set
128. - range hint: entries(from, to, direction) → offset set
129. 3. If multiple hints: intersect all offset sets (smallest first)
130. 4. Stream records from the resulting offsets
131. 5. Apply filter function on deserialized records
132. 6. Yield matching records
133. ```
135. ### Bounding Box Query
137. ```
138. 1. User calls db.boundingBox(corners, filter)
139. 2. Extract min/max for x and y from corners (order irrelevant)
140. 3. Delegates to find(filter, { index: [
141. { field: 'x', from: minX, to: maxX },
142. { field: 'y', from: minY, to: maxY }
143. ]})
144. 4. Intersection + streaming as above
145. ```
147. ### Update Operation
149. ```
150. 1. User calls db.update(query, callback, { index })
151. 2. Internally calls delete(query, { index, callback })
152. 3. For each match (using find with optional index hints):
153. a. Mark old record as deleted
154. b. User callback transforms old record → new record
155. c. New record is inserted with same primary key
156. 4. Persist metadata with new deleted offsets
157. ```
159. ### Delete Operation
161. ```
162. 1. User calls db.delete(query, { index })
163. 2. Find matching records (uses index hints if provided, otherwise full scan)
164. 3. Add offsets to metadata.deleted array
165. 4. Remove from indexes (if enabled)
166. 5. Persist metadata
167. ```
169. ### Compact Operation
171. ```
172. 1. Acquire file lock
173. 2. Create temporary data file
174. 3. Stream through all records
175. 4. Write only non-deleted records to temp file
176. 5. Atomically rename temp file to replace original
177. 6. Clear metadata.deleted array
178. 7. Rebuild all indexes from new file
179. 8. Release file lock
180. ```
182. ## File Structure
184. ```
185. data/
186. ├── users.mpack # Main data file (MessagePack records)
187. ├── users.meta.json # Metadata (nextId, deleted offsets)
188. ├── users.lock # Lock file (contains PID)
189. ├── users.id.txt # Index file for 'id' field
190. ├── users.email.txt # Index file for 'email' field
191. └── ...
192. ```
194. ## Serialization Format
196. MPackDB uses MessagePack format from the `msgpackr` npm package with a custom size header:
198. ```
199. [4 bytes: size][MessagePack data]
200. ```
202. Each record is prefixed with a 4-byte little-endian integer indicating the size of the MessagePack data (not including the size prefix itself).
204. **Why the size header?**
205. - MessagePack doesn't include record boundaries in the format
206. - The size header allows streaming reads without parsing the entire file
207. - Enables skipping deleted records efficiently
208. - Matches the pattern used in BSON for consistency
210. ## Locking Mechanism
212. Two layers serialize writes:
214. 1. **In-process FIFO queue** (`_mutexTail` promise chain): concurrent operations on the same instance run strictly one after another, without polling.
215. 2. **Lock file** (`{dbPath}.lock`, created with the exclusive `wx` flag, containing the PID): serializes against other processes. Contention polls every 25ms. Lock files older than `staleLockTimeout` (default 30s) are treated as left behind by a crashed process and taken over (rename-then-verify, so racing waiters can't steal a live lock).
217. The lock is **causally re-entrant** via `AsyncLocalStorage`: only operations invoked *inside* the lock-holding call chain (find inside delete, insert inside withLock, update's internal delete+insert) re-enter. An operation that merely *starts while* another one holds the lock queues up — this distinction matters; a depth-counter implementation used previously let any concurrently started operation walk into the critical section.
219. On acquiring the file lock, the instance runs `refresh()` before entering the critical section, so writes always start from the newest cross-process state (`nextId`, tombstones).
221. Reads take no lock. Their consistency is guaranteed by the meta version guard (below).
223. ### withLock for Compound Operations
225. `db.withLock(callback)` acquires the lock for the duration of the callback. All DB operations inside the callback reuse the same lock. This makes compound operations like find-then-insert atomic:
227. ```javascript
228. await db.withLock(async () => {
229. const [user] = await db.find(u => u.email === email);
230. if (!user) await db.insert({ email });
231. });
232. ```
234. This ensures only one process can write at a time while allowing multiple readers.
236. ## Index Persistence Strategy
238. Indexes use a two-tier approach:
240. ### Disk Indexes
241. - Sorted index files on disk
242. - Binary searchable for O(log n) lookups
243. - Rebuilt during compaction
245. ### Delta Indexes (In-Memory)
246. - Track changes since last persistence
247. - Checked before disk indexes
248. - Auto-persisted based on:
249. - Time interval (default: 60 seconds)
250. - Change threshold (default: 1000 operations)
252. ### Tombstones
253. - Track deleted records in memory
254. - Prevent returning deleted records from disk indexes
255. - Cleared during compaction
257. ## Performance Characteristics
259. ### Time Complexity
260. - **Insert**: O(1) for append, O(log n) for index update
261. - **Find by primary key (indexed)**: O(log n) binary search
262. - **Find with query function**: O(n) full scan
263. - **Find with single index hint**: O(log n) seek + O(k) scan where k = entries in range
264. - **Find with index intersection**: O(k1 + k2 + ... + min(k)) for collecting + intersecting offset sets, then O(m) disk reads where m = intersection size
265. - **Bounding box**: Same as index intersection with 2 range indexes
266. - **Update**: O(find) + O(1) insert
267. - **Delete**: O(find) + O(1) mark
268. - **Compact**: O(n) full scan + O(n log n) index rebuild
270. ### Space Complexity
271. - Data file grows with inserts (append-only)
272. - Deleted records remain until compaction
273. - Index files: O(n) per indexed field
274. - Delta indexes: O(m) where m = changes since last persist
276. ### File Size Comparison
277. MessagePack typically produces **15-20% smaller files** than BSON for the same data:
278. - More compact integer encoding
279. - Smaller string overhead
280. - Efficient array/map encoding
282. ## Concurrency Model
284. - **Single-writer, multiple-reader**, in-process and across processes
285. - Writes are serialized through the in-process queue + lock file
286. - Reads can happen concurrently (no locks needed)
287. - Causally re-entrant locks allow `withLock()` to wrap compound operations atomically
288. - Unique indexes enforce constraints under the write lock (no duplicates even with concurrent inserts)
289. - `meta.json` carries a **monotonic version**, bumped on every `persistMeta()` (which writes atomically via tmp+rename). `refresh()` runs before every read and only adopts the on-disk meta when its version is newer — the in-memory meta (which may hold un-persisted mutations of an in-flight write) is authoritative for this process. This is what makes lock-free reads safe next to writes.
290. - `meta.json` also stores the collection **schema** (prefixed primaryKey + indexes) so external tools can open the db correctly.
291. - **Cross-process index coherence:** `{name}.idxstate.json` records `coveredBytes` — how far into the data file the persisted indexes reach. `refresh()` stats the data file; if it grew beyond our coverage, the new tail is scanned and indexed incrementally (cheap, append-only). If the file's *inode* changed (another process compacted), the instance reopens its write stream and rebases its index state.
292. - Index persistence (read-merge-write of the shared index files) runs under the db lock and dedupes entries by location; a threshold-triggered persist inside `insert()` deliberately escapes the insert's lock context (`lockContext.exit`) and queues for its own turn, because it outlives the insert.
294. ## Primary Key Types
296. ### NUMBER (PrimaryKeyType.NUMBER)
297. - Auto-incremented integer
298. - Stored in metadata.nextId
299. - Prefix syntax: `*id`
301. ### UUID (PrimaryKeyType.UUID)
302. - Sortable base36 unique ID (9-char timestamp + 3-char random)
303. - 12-character string format
304. - Prefix syntax: `@id`
306. ### STRING (PrimaryKeyType.STRING)
307. - User-provided string
308. - No auto-generation
309. - Default (no prefix)
311. ## Design Decisions
313. ### Why Append-Only?
314. - **Fast writes**: No seeking, just append
315. - **Crash safety**: Partial writes don't corrupt existing data
316. - **Simple implementation**: No complex update-in-place logic
318. ### Why MessagePack?
319. - **Smaller files**: 15-20% smaller than BSON on average
320. - **Fast serialization**: Comparable or faster than BSON
321. - **Wide language support**: Available in many programming languages
322. - **Simple format**: Easy to implement and debug
323. - **No external binary dependencies**: Pure JavaScript implementation
325. ### Why Custom Size Header?
326. - MessagePack doesn't define record boundaries
327. - Enables efficient streaming without full deserialization
328. - Allows skipping deleted records quickly
329. - Consistent with BSON's approach
331. ### Why File-Based Locking?
332. - **Simple**: No external dependencies
333. - **Cross-process**: Works across multiple Node.js processes
334. - **Portable**: Works on all platforms
336. ### Why Binary Search Indexes?
337. - **Disk-friendly**: Can search large indexes without loading into memory
338. - **Simple format**: Plain text, easy to debug
339. - **Fast lookups**: O(log n) for indexed queries
341. ## MessagePack vs BSON
343. ### Advantages of MessagePack
344. - **Smaller files**: 15-20% size reduction
345. - **Faster reads**: Simpler format, less parsing overhead
346. - **Pure JavaScript**: No native dependencies
347. - **Smaller library**: ~15KB vs ~173KB for BSON
349. ### Advantages of BSON
350. - **ObjectId type**: Built-in unique identifier type
351. - **Date precision**: Millisecond timestamps
352. - **Binary data**: Native binary type
353. - **MongoDB compatibility**: Direct compatibility with MongoDB
355. ### When to Choose MPackDB
356. - File size is a concern
357. - Pure JavaScript dependencies preferred
358. - Don't need MongoDB compatibility
359. - Want faster read performance
361. ### When to Choose BsonDB
362. - Need ObjectId primary keys
363. - MongoDB compatibility desired
364. - Working with binary data
365. - Need precise date/time handling
367. ## Limitations
369. 1. **Single-writer**: Only one write operation at a time
370. 2. **No multi-record transactions**: `withLock` provides atomicity for compound operations on a single DB, but not across multiple databases
371. 3. **No query language**: Must use JavaScript functions for complex queries
372. 4. **Compaction required**: Deleted records consume space until compaction
373. 5. **Index overhead**: Each index doubles storage for that field
374. 6. **No schema validation**: Records can have any structure
376. ## Index Query Design Decisions
378. ### Why `to` but not `limit` or `filter`
380. The `entries()` generator supports `from`, `to`, and `direction` but intentionally has no `limit` or `filter` parameters.
382. **Why `to` is needed:** When collecting offset sets for index intersection, all matching offsets are loaded into a Map. Without `to`, a range scan like `{ field: 'x', from: 0 }` would collect every entry from 0 to the end of the index — potentially millions of offsets when only a small range is needed. `to` stops the scan at the upper bound, keeping the offset set small.
384. **Why `limit` was removed:** `limit` caps the number of results, but the caller doesn't know the right count upfront. Since results are streamed via async generators, the caller can `break` out of the loop at any time, which terminates the generator immediately. This is more flexible than a fixed limit and works naturally with JavaScript's `for await` syntax.
386. **Why `filter` was removed:** With streaming, the caller filters in the loop body after deserialization. A built-in filter would only save one `if` statement per iteration while adding API complexity. The filter function in `find()` handles this at the right layer — after records are fetched from disk.
388. ### Why index intersection uses pre-collected offset sets
390. Index intersection collects full offset sets from each index hint, then intersects them before reading any records from disk. This trades memory (storing offset integers) for disk I/O (avoiding unnecessary record reads).
392. **Trade-off:** For a query like `x: 0..100 AND status: 'active'` on 10 million records, the x-index might yield 500k offsets and the status-index 50k offsets. Intersecting these sets (~4MB of integers in memory) reduces disk reads from 500k to maybe 10k — a massive I/O saving.
394. **Why not stream-and-check:** An alternative would be to stream the primary index and check each candidate against secondary indexes on the fly (O(log n) lookup per candidate). This uses less memory but requires a disk seek per candidate. For large datasets where the secondary index is highly selective, pre-collected intersection wins. For small datasets, the difference is negligible.
396. **Why the caller picks the primary index:** The engine cannot automatically pick the most selective index without scanning all of them first. Instead, the caller specifies which indexes to use via the `index` option. For streaming without intersection (single index), the caller controls the scan with `from`, `to`, `direction`, and `break`.
398. ### Bounding box vs geospatial
400. `boundingBox()` operates on flat 2D coordinates — simple min/max comparisons on x and y axes. This is sufficient for game grids, tile maps, and any coordinate system where geometry is planar. Geospatial indexing (S2 cells, geohash) is only needed for spherical geometry (lat/lng on Earth) where "straight lines" are actually great-circle arcs and distances warp with latitude. Both approaches use the same fundamental pattern internally: coarse index scan → exact geometric filter.
402. ## Future Improvements
404. - Batch insert operations
405. - Async compaction (background process)
406. - Query optimizer for complex filters
407. - Compression support (MessagePack supports extensions)
408. - Replication/backup utilities
409. - Schema validation layer
410. - Custom MessagePack extension types