Very cool. Thanks for the explanations.
On the separate mmap, I'm writing the serialized OpaqueEvent first, then writing the indexes. On a crash we might have a useless event that didn't get indexed, but it wouldn't be corrupt. The writer locks a write-lock, appends, then updates the 'end' pointer at the beginning of the map, then releases the write lock.
Also, these events are opaque (customer-ready, pre-validated). I never access the fields.
I noticed strfry does an index scan of these flatbuffers (of stripped down events) when necessary, using the fields to filter. I'm instead trying to use multiple btree-like indexes:
id -> offset
(created_at, id) -> offset
(pubkey, created_at, id) -> offset
(event_kind, created_at, id) -> offset
(tagdata, created_at, id) -> offset
Each key has to be unique per event, hence the id on each. And the created_at is to scan a since/until range. It's a lot of data to store, but I think that is okay on a personal relay. I don't think it would cause more page faults and cache misses.
I'm finding the set of events that match the filter by doing a functional intersection over the results from these filters. I say functional because I don't collect each result into a set and then intersect them, I intersect as I go: first index: collect the offsets in a hashset; second index: check each in the previous hashset and if it exists, copy to the next hashset (thus functionally being a set intersection) otherwise drop it.
Maybe this is a dumb algorithm. Databases are more my brother's thing, but I'm stubbernly trying to reinvent them myself (I would never learn as well otherwise).
I think deleted events will just be marked as such in another hash table, and a periodic rewrite will filter them out. I haven't really worked that out and now that I'm thinking about it, it could be quite expensive.
A lot of these OS level features like sendfile() or pwritev() become very difficult to use when relying on an upstream library that doesn't expose it's API in a way to utilize those. If I use tungstenite for websockets, I don't think I can write into it's outbound buffers at a low level.
At this point I'm really still exploring. It will change.
M. Dilger /
npub1ac…9p35c
2023-05-07 16:51:57
in reply to nevent1q…42ty
Author Public Key
npub1acg6thl5psv62405rljzkj8spesceyfz2c32udakc2ak0dmvfeyse9p35cPublished at
2023-05-07 16:51:57Event JSON
{
"id": "000008a19876f86e894f34f94d8b54e38383a54799f8b707f9b0ed7c5495c108",
"pubkey": "ee11a5dff40c19a555f41fe42b48f00e618c91225622ae37b6c2bb67b76c4e49",
"created_at": 1683478317,
"kind": 1,
"tags": [
[
"client",
"gossip"
],
[
"p",
"218238431393959d6c8617a3bd899303a96609b44a644e973891038a7de8622d"
],
[
"p",
"0c99877612291bd818b3dd92f2852b823557b3744c3cb10470865c7a56a4929b"
],
[
"p",
"79c2cae114ea28a981e7559b4fe7854a473521a8d22a66bbab9fa248eb820ff6"
],
[
"p",
"2d5b6404df532de082d9e77f7f4257a6f43fb79bb9de8dd3ac7df5e6d4b500b0"
],
[
"p",
"1bc70a0148b3f316da33fe3c89f23e3e71ac4ff998027ec712b905cd24f6a411"
],
[
"e",
"f70d6db9005ce00a8abf314caa16463c8b1b0b2cc1fe8ecebc144d1823a0bd74",
"wss://nostr-pub.wellorder.net/",
"root"
],
[
"e",
"623a3f6e857408b9d79195cf39646afb12b3e865d6112e54d0e1dd8b5e4238fb",
"wss://nos.lol/",
"reply"
],
[
"nonce",
"14603672391686763697",
"20"
]
],
"content": "Very cool. Thanks for the explanations.\n\nOn the separate mmap, I'm writing the serialized OpaqueEvent first, then writing the indexes. On a crash we might have a useless event that didn't get indexed, but it wouldn't be corrupt. The writer locks a write-lock, appends, then updates the 'end' pointer at the beginning of the map, then releases the write lock.\n\nAlso, these events are opaque (customer-ready, pre-validated). I never access the fields.\n\nI noticed strfry does an index scan of these flatbuffers (of stripped down events) when necessary, using the fields to filter. I'm instead trying to use multiple btree-like indexes:\n\tid -\u003e offset\n\t(created_at, id) -\u003e offset\n\t(pubkey, created_at, id) -\u003e offset\n\t(event_kind, created_at, id) -\u003e offset\n\t(tagdata, created_at, id) -\u003e offset\nEach key has to be unique per event, hence the id on each. And the created_at is to scan a since/until range. It's a lot of data to store, but I think that is okay on a personal relay. I don't think it would cause more page faults and cache misses.\n\nI'm finding the set of events that match the filter by doing a functional intersection over the results from these filters. I say functional because I don't collect each result into a set and then intersect them, I intersect as I go: first index: collect the offsets in a hashset; second index: check each in the previous hashset and if it exists, copy to the next hashset (thus functionally being a set intersection) otherwise drop it.\n\nMaybe this is a dumb algorithm. Databases are more my brother's thing, but I'm stubbernly trying to reinvent them myself (I would never learn as well otherwise).\n\nI think deleted events will just be marked as such in another hash table, and a periodic rewrite will filter them out. I haven't really worked that out and now that I'm thinking about it, it could be quite expensive.\n\nA lot of these OS level features like sendfile() or pwritev() become very difficult to use when relying on an upstream library that doesn't expose it's API in a way to utilize those. If I use tungstenite for websockets, I don't think I can write into it's outbound buffers at a low level.\n\nAt this point I'm really still exploring. It will change.",
"sig": "41b4bfa69ced916425b2728474bb1aebbeb267fbfea58d3caf9ecdb9ae5180284f6353cc2947d34e4a1324b9669c7e6154cf4347509d6a5520867db392c252c1"
}