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
37
Replies
4
Boosts
immediately i can see that knuth's style must have inspired the lovely approach in DH 1976 where they spend the entire time shouting out papers they love and giving deep, thorough citations to people who have solved some problem or other. so that's kind of nice, even though knuth (in the 1998 book especially) spends a great deal of time thinking about how to perform large-scale surveillance, and also daps up ron rivest way too frequently
there are a lot of ways he introduces to describe hashing that are thoroughly aligned with the ways i have been thinking about it in my head. so i feel pretty confident now just doing my own bullshit data structures. [recall that i define "hash" to mean "hash table" and not "checksum"]
however, there is an immense reliance on "expected-time" analysis, which i can immediately see led to linux's i/o bullshit directly:
Perhaps the reader has been skeptical of B-trees because the degree of the root can be as low as 2. Why should we waste a whole disk access on merely a 2-way decision?! A simple buffering scheme, called least-recently-used page replacement, overcomes this objection; we can keep several bufferloads of information in the internal memory, so that input commands can be avoided when the corresponding page is already present. Under this scheme, the algorithms for searching or insertion issue “virtual read” commands that are translated into actual input instructions only when the necessary page is not in memory; a subsequent “release” command is issued when the buffer has been read and possibly modified by the algorithm. When an actual read is required, the buffer that has least recently been released is chosen; we write out that buffer, if its
contents have changed since they were read in, then we read the desired page into the chosen buffer.
literally EVERY SINGLE OS JUST DOES THIS EXACT SHIT TO THE LETTER AND DOESN'T THINK TWICE! it's FUCKED!
Since the number of levels in the tree is generally small compared to the number of buffers, this paging scheme will ensure that the root page is always present in memory; and if the root has only 2 or 3 children, the first-level pages will almost surely stay there too. Any pages that might need to be split during an insertion are automatically present in memory when they are needed, because they will be remembered from the immediately preceding search.
"the first-level pages will almost surely stay there too" this is not a serious analysis bro you've been riding people's coattails for way too long!!!!
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
for my write() calls, i'm actually requiring that any write() performed from within a process on the same file handle within the same i/o sync domain (e.g. multiple threads writing to the same file handle) must have the semantics of a process-global lock to achieve in-process linearizability.
for data striping where you actively want to modify more than one region of the file at a tiime, i'm planning to extend the POSIX {,p}writev() concept and enable vectored write_striped() calls to describe a general bipartite graph that maps a sequence of iovecs to a file offset to write the vectored data at.
the write_striped() call could itself receive (a sequence of (a sequence of (iovecs) mapped to a write offset)), such that when the blocking syscall returns, the modifications to the file data corresponding exactly to what would occur if each [iovec] => offset was processed serially (linearizably)
it's still very much possible for the implementor of such a write_striped() call to identify opportunities for write parallelism where the inputs are disjoint. but the point is that linearizability is so important that even for extremely high performance scenarios you should be able to accept global lock semantics with more thoughtful API design, and only in extremely narrow cases like the ring buffer (which took me several months to design and implement) is it safe to move beyond that strict linearizability requirement
and as mentioned above, the ring buffer itself only works coherently because the result of any asynchronous operation will necessarily, provably achieve linearizability over the data flow through the ring buffer
i said that already but it's really important to emphasize how the analysis of correctness and performance becomes much simpler to understand and easier to create for your own programs if you focus less on "what operations does the CPU do" and more "what data exists in the system and how does it move between states over the course of the system's operation?"
now i'm reading this https://www.cs.utexas.edu/~dsb/cs386d/Readings/ConcurrencyControl/Lehman-Yao.pdf
Efficient Locking for Concurrent Operations on B-Trees
Lehman and Yao (1981)
promising!!!
2. THE STORAGE MODEL
We consider the database to be stored on some secondary storage device (hereinafter referred to as the “disk”). Many processes are allowed to operate on these data simultaneously.
you will not BELIEVE what happens next:
Each process can examine or modify data only by reading those data from the disk into its private primary store (the “memory”). To alter data on the disk, the process must write the data to the disk from its memory.
THAT'S RIGHT!!!!
- PROCESS-LOCAL I/O STATE!!!
- EXPLICIT TRANSFER TO GLOBAL VISIBILITY!!!!
- SEPARATION OF "WRITE" VS "PERSIST" OPERATIONS!!!!!!
The disk is partitioned into sections of a fixed size“ (physical pages; in this paper, these will correspond to logical nodes of the tree). These are the only units that can be read or written by a process.
DENORMALIZED REPRESENTATION OF DATA INTO INDIVIDUALLY-INDEXED BLOCKS!!! SUDDENLY WE CAN ANALYZE THE PATH OF A SINGLE WRITE FROM START TO FINISH!!!
Further, a process is considered to have a fixed amount of primary memory at its disposal, and can therefore only examine a fixed number of pages simultaneously. This primary memory is not shared with other processes.
i have LITERALLY never heard anyone else attempt to codify concurrency control for a filesystem like this before. it's literally so fucking simple!!!!
Finally, a process is allowed to lock and unlock a disk page. This lock gives that process exclusive modification rights to that page; also, a process must have a page locked in order to modify that page. Only one process may hold the lock for a given page at any time. Locks do not prevent other processes from reading the locked page.
you may recall that linux experiences a load of problems with this locking mechanism https://www.kernel.org/doc/html/latest/core-api/pin_user_pages.html#folio-maybe-dma-pinned-the-whole-point-of-pinning
but that's linux in 2026. this paper is from 1981 and they're not mediating between driver-level DMA and applications pinning a page in userspace without knowing it just by issuing a write() call like linux is.
verdict: good! a lock is exactly the right thing to do for this paper
We assume that some locking discipline is imposed on lock requests, for example, a FIFO discipline or locking administration by a supervisory process.
POSIX literally has zero semantics defined for the ordering of write()s to the same file, other than "it is atomic", which means both that:
- writes are never torn
- the data from a
write()must be made visible to the entire system globally before the blockingwrite()call returns
there's certainly no conception of locking, ordering, or queueing!
i also really want to shout out this exciting and intriguing proposal in the final clause of that assumption:
or locking administration by a supervisory process.
this is exactly why i'm so gung-ho about structuring IPC in terms of an interaction graph, and because i think a supervisor process is also the correct, safe, and performant way to do task scheduling!
there are so many different performance scenarios that the userspace application developer can and should be emplowered to describe purely in local terms--the concept of managing "nice" values for build processes in order to ensure the web browser doesn't keep stealing cycles from it is absurd!
in fact, it's perfectly coherent to have each recursive supervisor process describe task scheduling mechanics only between its own processes and no one else's. that in fact makes it super easy for the kernel to implement timesharing by allocating time slices to the entire structured subgraph!
think of it like linux namespaces (i.e. containers)--but instead of retroactively figuring out the mapping from each process to its namespace, then calculating some sort of "quota" (while essentially retaining the global round-robin scheduler),
instead we codify being scheduled on the CPU as not only a privileged operation, but indeed a crucial security boundary in which each supervisor process becomes accountable for how much time it allocates across the subprocesses it spawns
in the kernel, we could even just do "round robin" again--but iterating over strictly nonoverlapping process groups!
this sounds really basic, but what it means is that we don't experience the awful i/o contention that linux does--because all processes blocking on each other's output can be stopped and started at once!
how does "strictly nonoverlapping process groups" work if processes need to share data ex post facto? simple! for two processes A and B, their respective supervisor processes S_A and S_Bmust both request a resource that exposes an interface to write data outside the process-local i/o space. this comes in the form of a capability, and it's the exact definition of our "named i/o sync domains"!
and alternatively but no less appropriately, we will still allow supervisors to request a shared memory buffer capability from the kernel, which it can then expose to multiple processes in its IPC graph. unlike the highly-optimized filesystem abstraction i'm providing (which adds on the concept of "i/o transactions" to negotiate the communication of data across supervisor trees in a structured way), shared memory is going to rely upon the semantics described by the C11 weak memory model for atomic operations for consistency.
the point here is absolutely not to nag applications to do "safe" i/o--all of this is purely motivated by my personal need for speed!!!!
in fact, the POSIX approach here is already perfect! https://www.man7.org/linux/man-pages/man3/shm_open.3.html
The operation of
shm_open()is analogous to that ofopen(2).namespecifies the shared memory object to be created or opened. For portable use, a shared memory object should be identified by a name of the form/somename; that is, a null-terminated string of up toNAME_MAX(i.e., 255) characters consisting of an initial slash, followed by one or more characters, none of which are slashes.
if the /somename key used by two distinct supervisor trees matches, then they can communicate through a shared memory mapping!
however, this global namespace is less than ideal. the way we would improve this is as foilows:
- any named capability (i/o sync domains, shm mappings) is local to a namespace.
- a namespace is itself a capability! but it cannot be requested by name.
instead, a namespace can be created in two ways:
- generated freshly by a supervisor process--this corresponds to randomly generating a secure cryptographic keypair (ECC or DH).
- subsequent named capabilities can be scoped to this namespace. the supervisor process who generates this can explicitly send this namespace to any process it can communicate with, and it can write the keypair to persistent storage so it can recreate it upon reboot.
this next part is a brilliant fucking idea, please get ready (cc @somebody):
- if a supervisor process wants to expose a namespace to other processes, it can do it in two ways, by exposing either:
- just the public key, which strictly supports read-only views of resources in that namespace
- the whole keypair (public & private), which allows the recipient to request named resources in that namespace which can mutate data (and therefore can communicate with others who have access to that namespace)
@somebody i can't fucking believe how naturally that corresponds to the unambiguous trust relationships of public-key cryptography (or to be precise: it maps specifically to the subgroup of unambiguous trust relationships in PKC--not all PKC is unambiguous lol). cc @ireneista
finally, how would we use this to support structured communication? well, in order to mimic an FHS system, i would create an i/o sync domain (essentially a chroot) with standard [readonly] executables mapped to /usr/bin/* (i would probably use busybox since coreutils is not a safe dependency anymore sadly).
the first supervisor process is the init system itself! but i'm thinking i would probably try to build that minimal busybox FHS into the initramfs. maybe i wouldn't even share the private key for that with the actual init system, so even an evil PID 1 written by lennart poettering can't modify its contents with evil calls to dlopen()