Some Stuff I've Been Reading
I’ve been on vacation and I don’t really have an exciting post to share, but I have been reading some, so here’s a bit of my reading list, and maybe you will find something to enjoy as well.
Indulgent Papers
I’ve been feeling like I should write some Haskell. I guess this is kind of like a, “it’s not cute when guys want to write Haskell, programmers only do that when they’re VERY DEPRESSED!” kind of thing, but I promise I’m not depressed at this time. Again, I’ve been on vacation. After I read that drawing trees paper from a while back I started going through lists of other functional pearls. A lot of them are fun! A lot of them, I think, would benefit from notation that is not “Haskell” (see Queuing and Gluing for 8 Red Coins), and some of them are maybe a bit more involved by than I’m especially interested in using my “perusing” time for (see Hough transform).
But a lot of them are great! They’re basically blog posts of a cute trick written in the style of a paper, which is extremely my aesthetic.
One I particularly liked is How to Replace Failure With a List of Successes because it’s a nice presentation of its particular notion of nondeterminism.
Nondeterminism in the “nondeterministic finite automaton” sense, rather than the rand() sense, that is.
This seems to me a better way to introduce how Prolog works, in a more bottom-up sense. I think the kind of high-level, thinking of it as only existential quantifiers is more confusing than starting from the idea of a stream of results which you then convolve.
TUM SSD Paper
For someone who writes a databases newsletter I know embarrassingly little about how SSDs actually work. Most people are aware that one of the drawbacks of SSDs is that they can only be rewritten so many times before they stop accepting new writes. The way that they mitigate this limitation is by continually writing to fresh areas of the SSD and tracking metadata for the mapping from virtual to physical addresses. It turns out that not all SSDs handle this in the same way and in heavy-load situations the way this is organized can have significant impacts on the latency and lifespan of the SSD.
SSD-iq is a benchmark TUM developed to test how SSDs behave in various situations that aren’t described by the typical datasheet provided by vendors.
The LAW Theorem
Distributed systems people love their “pick 2”s. They love a trilemma (even when their problem might better be expressed as a mere, trifling DIlemma).
The latest of these is the LAW theorem, which asserts a pick-2 of:
- Linearizability (okay, okay, I know that one),
- Local reads (uhh, maybe I know what that means?), and
- Asynchrony (what that means?).
Linearizability, of course, being the C in CAP (but not in ACID!).
Local reads just means that when reading from a replica, it doesn’t need to communicate with any other replicas in order to serve a read. This is violated by, say, vanilla Paxos, which must complete a round of consensus in order to safely serve a read.
Asynchrony was the one that was the most mysterious to me, but it basically just means you assume there’s some kind of shared timeline that isn’t too arbitrary. For example, the way you typically allow Raft to serve local reads is via leases: one of the nodes says something like “for the next minute, every consensus round must involve me, and nobody else can make this claim until one minute and five seconds has passed.” As long as none of the other nodes think one minute and five seconds have passed before this node thinks one minute has passed, we’re guaranteed exclusivity on local reads. This mechanism makes an assumption that this kind of bound is possible: if a process’s clock can jump forward arbitrarily far, or pause for arbitrarily long, it doesn’t work. This is what’s meant by “asynchrony” in this paper.
This is a true pick-two: there are good reasons to choose any of the two options at once (unlike CAP, in which CA is not real).