so becausse the 1978 pohlig-hellman paper mentioned that one of knuth's taocp books had the sunzi remainder theorem they used, i finally cracked and opened up the knuth 1998 sorting and searching text
15
Replies
4
Boosts
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
however, completely by chance, i did find this paper from a team led by rui-Xiang ma from wuhan national laboratory for optoelectronics (https://sci-hub.st/10.1007/s11390-021-1247-6) which describes a database in persistent memory that works incredibly closely to my fractal zip file approach, with particular attention to data consistency and write optimization. so i can totally just steal this for anything i haven't figured out yet for the filesystem shit
especially after going through the btrfs source code yesterday i basically think i can make a filesystem like so much more expediently than i had previously planned. it's really not hard if you design it upfront instead of half-assing everything all the time
i also followed on an "SB-tree" mentioned by knuth that sounded close to what i wanted: https://sci-hub.st/storage/2024/634/00406abfc8d251b45eb6227c1f995db7/10.1007@BF01185680.pdf and while i still think a global tree organization is obviously fucked, it does a lot of things really thoughtfully:
(4) The high performance characteristics of an SB-tree are much less subject to degradation than traditional B-tree structures when the tree is modified to accommodate changing information. For this reason, it is appropriate for situations where regular B-tree reorganization cannot easily be performed.
but i really really liked the ACTUAL FUCKING SEMANTICS OF DATA MODIFICATIONS described for fucking ONCE:
(7) We draw an analogy between the K nodes of a multi-page block and the entries of a B-tree node: an analogous policy of "block-splits", "block-merges" and "block-borrows" is pursued
then he calls out the half-assed "expected time" analysis used for B/+ trees:
It is well known that the root node is usually found in memory buffers, but this is not the whole story. We offer the following rough analysis to estimate the "Effective Depth",
D_E, of the B+-tree, which we define as the expected number of pages not found in memory buffers during a search from the root to the leaf for an entry with a random key value.
It is interesting to note that the graph of Fig. 3 presents a scalloped appearance. This indicates that increasing the ratio of memory buffer size to B+-tree size has an important effect in certain ranges, where a large proportion of a B-tree level can be contained in memory, but that this effect is of diminished importance in other ranges, where the proportion of the level contained becomes less useful in saving real I/Os.
SAVE THE REAL I/OS!!
they SB-tree paper also goes way way out of its way to shout out a completely different paper describing a "BD-tree" ("bounded decision") data structure, just because they really like it???? so wholesome!!!!
The common uses of merge join and ordered user display seem to require the more difficult key sequential access, although Lomet points out that for many uses. "By changing algorithms, it is frequently possible to use the results of a range search, without the extra cost of putting the records in key order." To support key sequential access, BD file records within each bucket are maintained in key order. Since records are ordered from one node to another, a total ordering can be achieved by performing a "merge" on the ordered sequences from the different buckets of a node, as in the final stage of a multi-merge sort. This is best effected by using a "heap" structure on the smallest keys in each bucket, successively removing the minimum, inserting the next in that bucket, and reorganizing the heap; each such heap reorganization takes log_2 k steps, where k is the number of buckets.
basically the moral of all of the good papers is: don't rely on one single algorithm or data structure to generally work fine across every possible use case! develop algorithms and data structures tuned to each potential query and input distribution you expect to have to handle!!
For very large files, where the effective depth of an SB-tree becomes significantly greater than one, the guarantee to keep all of the directory level of the BD tree in memory is an important advantage.
this is in fact what a good paper looks like. you can in fact gas yourself up and other good work at the same time!
The CPU cost as each entry is generated is what is needed to remove the minimum of a heap, advance
the relevant bucket cursor, and insert the next entry under the cursor back into the heap. We represent this asCPU_{heap}, a cost which is logarithmic in
the number of buckets in the node.
this analysis also makes sure to both specify as well as clearly differentiate CPU and memory requirements to perform specific operations (they're obv related, because the CPU needs to pull memory into the cache, but when describing them separately (and asymptotically) you end up producing an analysis that covers attempts to try to "be clever" or "cheat" (like i do when i introduce i/o transactions on top of POSIX so applications can simply wait until the filesystem reconciles their shared state before returning from the blocking syscall)
YES!!!!!
In spite of this, it would seem that an ideal SB-tree implementation would permit a user choice as to the number of nodes in a reorganization, up to a reasonable limit such as the minimum number on a block. The parameter is not particularly hard for the file manager to supply, and in designing the access method we should try not to prejudge the relative frequency of range-retrievals in comparison to updates.
FIRST TIME IN WORLD HISTORY THAT A FILESYSTEM DESIGNER HAS PROPAGATED A PERFORMANCE-CRITICAL INPUT-SENSITIVE JUDGEMENT TO THE MOTHERFUCKING APPLICATION LAYER!!!
As time passes, even less activity will be necessary to justify this buffer size. Note that for many years the economic use of IBM memory was artificially
constrained by a 16 megabyte virtual memory limit, and users who do not have XA systems are still constrained in that way. This may serve to explain the statement in [11] to the effect that 4M bytes for buffers was not feasible.
Eight Megabytes And Constantly Swapping
A key consideration in memory buffering is whether we need to keep more than one size of buffer: single page buffers for page-nodes and larger sizes for multi-page blocks. It is a common property of modern computer systems that a multi-page read may be accomplished in a scatter/gather form to several non-contiguous memory locations
see i wish i had heard this when i began parallelizing zip file extraction and couldn't find a single example or any mention on the entire internet of anyone trying to do a scatter/gather on the archive format that tells you where everything is laid out in advance!
oh YES!! https://sci-hub.st/10.1007/BF00289145
Unsafe Operations in B-trees
Bin Zhang and Meichun Hsu (1989)
THE GLOVES ARE COMING OFF!!!
A simple mathematical model for analyzing the dynamics of a B-tree node is presented.
you would not BELIEVE how uncommon this sort of very basic analysis is across the database and filesystem literature from the past half-century
We call split, merge, borrow and balance operations unsafe operations in this paper.
in particular, these operations induce (global) contention, which reduces throughput
oh HELL fucking yes!!!!! they are actually describing the data structure under an ordered (linearizable) sequence of mutation operations!!!!
you don't even need to use latex or any special math notation for this kind of thing. you just need to state out loud:
- these are the mutation operations for my data structure
- this is how we will ensure a strict ordering of operations (linearizability)
- this how the size/complexity/computational effort over the whole sequence of operations will be analyzed
- [if you're lucky] this is how we minimize that work for a given input distribution
linearizability is actually a very strong requirement and may be too strong for some specific subproblems. e.g. for my ring buffer that does every possible variant of structured pairwise blocking/signalling scenarios (or telling the other end when we're waiting for them to hurry up), the codification of forward progress is maintained by the invariants of the ring buffer (data is always in order), so we can do some spinning along with the c11 weak memory model for atomic operations to avoid full "linearizability" by globally locking the whole buffer at once
but we do still achieve linearizability over the data flow through the ring buffer, even if we can improve performance by relaxing the requirement to make each process interaction with the ring buffer linearizable
