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.
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.
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.
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.
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)
