[ot][spam][crazy] log 2: append-only random writes

Undiscussed Horrific Abuse, One Victim of Many gmkarl at gmail.com
Sun Jul 10 06:56:35 PDT 2022


i've got a lot of inhibition around simplifying and generalising some
parts of the last stable one at
https://lists.cpunks.org/pipermail/cypherpunks/2022-July/102291.html

so maybe i'll try going again with more conceptualisation of a working algorithm

- retain an index. when writing, merge the region written to into the
index, with 0 depth
- have nodes track the depth of their deepest leaf and any other
information needed about them to perform operations

when making a new index or updating:
  - index regions that are at max_depth are copied in so as to retain max_depth
  - regions that are trimmed by overwrites should be checked to see if
any subnodes are completely overwritten, and have their depth updated
to a shallower value if they are
  - regions can be merged with their neighbors into a reference to the
shallowest shared parent, including the last flush as the most shallow
parent if such a merge would not exceed the max depth.
  - the merging of index regions is the same as the merging of writes.

iterating leaves should no longer be needed for operation, and could
be simplified into a recursive index iteration. the boilerplate may be
mostly reusable.


More information about the cypherpunks mailing list