mikedilger on Nostr: Instead of using a database I'm storing events in a file. Memory mapping lets you ...
Instead of using a database I'm storing events in a file. Memory mapping lets you access a file as if it was entirely in memory, and the OS pages it in and out for you automatically doing the reads and writes and stuff.
Each event just gets appended, which requires a write lock (one writer at a time) but readers can keep reading while writes are happening so it is less contentious than a traditional RWLock which blocks readers while writes happen.
The indexes are functionally similar to key-value btrees which map certain query tuples like (pubkeyhex, createdat, idhex) to an offset into the event file (the length of the event is encoded in the serialization so we just need the offset). The serialization is very minimal, just enough to have a length and to be linear. Each key in each index must be unique (or else we would lose events) which is why they end in the "idhex". We can scan a time slice (before/since) as they are grouped together on the btree, so I can iterate from (pubkey, before) to (pubkey, since+1) to get all that person's events within that time range. I'm intersecting multiple index results by hashing results and checking that map each time I run through the next index, discarding matches that come up missing (from the previous index). That should cover all possible queries, not in an ideal way, but in a simple and relatively fast way. strfry has more indices (all the common ones) and falls back to scanning a flatbuffer event sequence for matches. It also uses LMDB for the events rather than trying to memory map directly. I'm using sled for the indexing. I don't know if my indexing merging scheme is going to be faster or not. Probably slower in most cases, but faster then when strfry doesn't have a suitable index. That's my guess anyhow. My code is at least easy to reason about. I came up with mine before talking to Doug.
Each event just gets appended, which requires a write lock (one writer at a time) but readers can keep reading while writes are happening so it is less contentious than a traditional RWLock which blocks readers while writes happen.
The indexes are functionally similar to key-value btrees which map certain query tuples like (pubkeyhex, createdat, idhex) to an offset into the event file (the length of the event is encoded in the serialization so we just need the offset). The serialization is very minimal, just enough to have a length and to be linear. Each key in each index must be unique (or else we would lose events) which is why they end in the "idhex". We can scan a time slice (before/since) as they are grouped together on the btree, so I can iterate from (pubkey, before) to (pubkey, since+1) to get all that person's events within that time range. I'm intersecting multiple index results by hashing results and checking that map each time I run through the next index, discarding matches that come up missing (from the previous index). That should cover all possible queries, not in an ideal way, but in a simple and relatively fast way. strfry has more indices (all the common ones) and falls back to scanning a flatbuffer event sequence for matches. It also uses LMDB for the events rather than trying to memory map directly. I'm using sled for the indexing. I don't know if my indexing merging scheme is going to be faster or not. Probably slower in most cases, but faster then when strfry doesn't have a suitable index. That's my guess anyhow. My code is at least easy to reason about. I came up with mine before talking to Doug.