[ot][spam][personal] notes/spam/memorization: append-only random writes
forwarded to help me find it Forwarded Conversation Subject: [ot][spam][personal] notes/spam/memorization: append-only random writes ------------------------ From: <cypherpunks-owner@lists.cpunks.org> Date: Mon, Aug 22, 2022 at 1:52 PM To: <gmkarl@gmail.com> Only subscribers may post to this list. Visit https://lists.cpunks.org for subscription information. ---------- Forwarded message ---------- From: "Undiscussed Groomed for Male Slavery, One Victim of Many" <gmkarl@gmail.com> To: cypherpunks <cypherpunks@lists.cpunks.org> Cc: Bcc: Date: Mon, 22 Aug 2022 13:51:48 -0400 Subject: [ot][spam][personal] notes/spam/memorization: append-only random writes With the append-only random writes, a basic concept is data representation of index nodes, and how this differs from data representation of data. It makes sense to me to implement them as objects, although I haven't learned design since OOP in the 90s, technically: it wasn't really different from modules in C, just used cleaner syntax. So maybe my knowledge is relevent. So, an object for data, and an object for indices (inner nodes), or whatnot. A core function is taking slices of inner nodes, and then recalculating their leaves and lengths and integrating them into a balancing strategy. So, the reason to make an object for indices, is to facilitate taking their slices and acquiring their new leaf count. A balancing strategy will want to know their depth and their leaf count. - taking slices of inner nodes (index objects), and getting the leaf count and height of these slices - index objects then reference such slices alongside data nodes, in a tree not too complex. The tree is the index class ... almost . The big challenge for me is bringing the parts together. Making them simple and clear seems helpful. - Taking slices of a tree, and calculating the leafcount and height of the slices. ---------- From: <cypherpunks-owner@lists.cpunks.org> Date: Mon, Aug 22, 2022 at 1:56 PM To: <gmkarl@gmail.com> Only subscribers may post to this list. Visit https://lists.cpunks.org for subscription information. ---------- Forwarded message ---------- From: "Undiscussed Groomed for Male Slavery, One Victim of Many" <gmkarl@gmail.com> To: cypherpunks <cypherpunks@lists.cpunks.org> Cc: Bcc: Date: Mon, 22 Aug 2022 13:56:30 -0400 Subject: Re: [ot][spam][personal] notes/spam/memorization: append-only random writes Taking slices of an index tree (i.e. index node) can seem confusing. The quick 'flat_tree' code I wrote for my semi-successful 'log' project doesn't retain copies of old trees after they are published. It stores just one tree, containing references to old copies of itself. For interconnecting disparate data, it seems it would make sense to let the system introspect into the tree, and look at it. This could mean providing for retaining the old copies, or it could mean accessing the network. [some confusion around the data already being available, unsure of these .... in the general case it would not be ...] So, the nodes might have some abstract way of taking the slices. A quick implementation would not calculate or optimize anything, just summing the leaves of the children that overlap the slice. ---------- From: <cypherpunks-owner@lists.cpunks.org> Date: Mon, Aug 22, 2022 at 1:58 PM To: <gmkarl@gmail.com> Only subscribers may post to this list. Visit https://lists.cpunks.org for subscription information. ---------- Forwarded message ---------- From: "Undiscussed Groomed for Male Slavery, One Victim of Many" <gmkarl@gmail.com> To: cypherpunks <cypherpunks@lists.cpunks.org> Cc: Bcc: Date: Mon, 22 Aug 2022 13:58:13 -0400 Subject: Re: [ot][spam][personal] notes/spam/memorization: append-only random writes An index node class could then have an abstract/overrideable function for taking a slice. A default implementation could naively simply sum the properties of the intersecting children. Alongside that, we have a data/leaf node representation. And an index node class, with an abstract method/member function for taking a slice.
I was thinking maybe the task of building this datastructure that provides for randomly writing to an append-only medium could be broken into 3 parts. - slicing a chunk: easier if an interface for the store is specified, to retrieve written data - optimizing a sequence that includes sliced chunks by reorganising their metadata. i think i included a number of optimizations in one of the attempts that might be copyable out. - selecting which nodes to merge when writing a new chunk so as to make balanced trees. i really simplified code for this in the flat_tree repo. I’ve done all these three things in separate attempts, but not together in the same one. Enumerating them seems to make it much easier to thin’ about, and gives an outline to memorize. 1. selecting which nodes to merge (xloem/flat_tree append structure, can be improved to work from middle) 2. slicing chunks (means the library must have access to old internodes to pull chunks out of them) 3. optimizing out redundant information when reusing old nodes They kind of overlap, and some important choices are left out, but these are the things I’ve presently been struggling to conceptualise near each other, I think. A good next thing to add might be just a comforting reminder of a way to make the append approach work from the middle. I think the hardest part was whether or not a “middle node” should be considered and what it would be. I recall I had some interest in making leaves and internodes be the same class, but unresolved considering of it meant there could be slowdowns if that was done hastily. Maybe it could be interesting and useful to leave out #3 and use a heuristic for #1, and consider what problems remain in the result.
participants (1)
-
Undiscussed Groomed for Male Slavery, One Victim of Many