6 ms·
Immutability allows for incredible performance when you are working in the guts of database engines. Having assurances that a specific data log file offset cann
by bob1029 5y ago
Immutability allows for incredible performance when you are working in the guts of database engines. Having assurances that a specific data log file offset cannot possibly be modified allows for substantial optimization throughout.
For users who do not need a serialized view of events, access to "near-real-time" data can be made to scale as far as needed, even if a single machine is driving all the writes. You could theoretically have a billion readers working off a single synchronous core system.
By utilizing careful abstractions, that single core system can write something on the order of 10-100 million transactions per second. We do it every day on the various financial exchanges around the world. In many cases, a single thread is what is holding up the entire exchange. Arrays of structs, hot cache lines, correct branch prediction and full pipelines are a hell of a combo.
In some practical businesses apps, it is also feasible to coalesce logical writes before they need to enter a fully-synchronous context, so you can get some step-down ratio like 100:1 on transactions that actually need to go across the network and be handled by the core system.
- m12k 5y agoI'm increasingly coming to realize that in programming, flexibility is something you pay for in performance, whether you use it or not. Data being mutable even if you never mutate it. Automatic bounds checks for data that you've already made sure can't go out of bounds. vtable lookups even when you're not using inheritance, because who knows, someone else might. Compilers needing to do extra work in case two pointers are aliases, even though that never makes sense for them to be from the programmer's perspective. Objects allocated one at a time, scattered around memory, even if you don't need them to be, and wouldn't mind their innards being kept together in cache aligned arrays. They say you can solve any problem in computer science with another level of indirection - except performance, it seems, because we're paying the cost of all this indirection all the time, even if we don't need it most of the time. There's a crazy amount of unnecessary "housekeeping" done by compilers and runtimes to make sure everything always works all the time, which requires them to always do extra work to protect against pathological cases that almost never arise. Modern compilers and runtimes are getting better and better at recognizing the common "happy case" and optimizing for that, and that's good. But it still feels backwards - both that we can't explicitly opt out of unneeded flexibility, so instead the compiler needs to deduce that we aren't using it. But also that a lot of this isn't opt-in to begin with, rather than opt out - i.e. make things immutable by default. Or let the programmer tell the compiler a little bit more about what they need and don't need the code to do, so the compiler can do a much better job if it.
- bob1029 5y ago> Or let the programmer tell the compiler a little bit more about what they need and don't need the code to do, so the compiler can do a much better job if it. You can do this today in languages like C#: https://docs.microsoft.com/en-us/dotnet/csharp/write-safe-efficient-code#declare-readonly-members-for-mutable-structs https://docs.microsoft.com/en-us/dotnet/csharp/write-safe-ef... > Adding the readonly modifier to members that don't mutate state provides two related benefits. First, the compiler enforces your intent. That member can't mutate the struct's state. Second, the compiler won't create defensive copies of in parameters when accessing a readonly member. The compiler can make this optimization safely because it guarantees that the struct is not modified by a readonly member.
- XorNot 5y agoThis feels like some seriously missed static analysis optimization though - why do I need to specify this? There's vanishingly few cases the answer to "looks like you don't modify this ever, make it readonly?" where the answer is not yes.
- bob1029 5y agoProbably because reflection & compilation+activation of types existing outside the original compilation context is possible at runtime. I much prefer to having a language/runtime that can handle extremely complex problem scenarios out of the box (with the need for occasional tuning), rather than the other way around. It is not very often that I find myself screwing around with performance-intensive code. Usually, a few very important things are addressed at the lowest levels and then you put all your nice abstractions back on top for daily driving.
- jiggawatts 5y ago> flexibility is something you pay for in performance I lightbulb moment I had recently was that the classic interface-based OO programming paradigm utilising virtual functions was essentially the following declaration by the programmer to the compiler: The function that is invoked can change at any time, even call-to-call; assume nothing. it is a black box with unknown, unknowable contents. Do not inline it, do not inspect it, expect the worst. If you look at a typical web framework, with call stacks hundreds of methods deep, you'll come to the same horrifying realisation that these are all inherently un-optimisable because of that statement. The compiler can do nearly nothing, and the processor will also struggle to paper over the inefficiency. Meanwhile, in reality, the specific implementations of those interfaces never change during actual production execution! Dynamic dispatch is utilised only during development time, and even then only at compile time to inject test harnesses, mocks, or whatever. At runtime, 99.999999% of all function calls are essentially static, and dynamic dispatch is a pure waste.
- deleted 5y ago[deleted]
- DennisP 5y ago> single core system can write something on the order of 10-100 million transactions per second...a single thread is what is holding up the entire exchange. Arrays of structs, hot cache lines, correct branch prediction and full pipelines Without going back to school, how would I learn how to do that? (Books I should read, good open source examples, any Coursera courses?)
- rigtorp 5y agoI've written some on this topic. Start here https://rigtorp.se/virtual-memory/ https://rigtorp.se/virtual-memory/ , there is more on similar stuff on my website.
- jasonwatkinspdx 5y agoI've been working occasionally on a database engine design that takes this idea to heart. It's been hugely beneficial. The big picture design is simply described as an append only log of copy on write page states, with Kafka style compaction to maintain whatever window of history you want. This is supplemented with a compact in memory index that holds the LSN for the latest page states to make accessing live data as fast as possible. The write path goes through a single batch committer thread to amortize fsync overhead (technically two threads in series so I can overlap prepping the next batch with waiting on fsync). Single writer isn't a big limit since even on consumer grade SSDs you can write at GiB/sec now. Append only log means I hit the happy case on SSDs. FTLs have come a long way in equalizing sequential vs random write performance, but this comes at the cost of a lot more write cycles behind the scenes to shuffle stuff around. Here's two examples of how immutability has drastically simplified the design: First, the in memory index is just a hand tweaked version of a Bagwell Trie. Since the trie is copy on write, once the fsync finishes the write thread can publish the new index state with a single atomic write. Client threads never see any intermediate state. The database moves from snapshot to snapshot atomically from their view. (This is the part I'm coding up atm) A second example is want to have an on heap cache, to avoid overtaxing the SSD or the downfalls of a pure mmap caching approach (mmap can be the miss path for this cache however). I'm planning on using a lock free hash table. Since I'm working in a language that doesn't have such as a library, I'll have to roll my own. Ordinarily this would be an insane idea, as such structures are infamous for being nearly impossible to get correct, even when using formal modeling tools. But in my case, the relationship of LSN -> Immutable Page State is stable, so the cache can be quite sloppy. With a mutable cache I'd in essence have to ensure the CAS always went the right place, even under resizing, etc. But with immutability duplicates are only a potential memory waste, not a correctness problem, so I get to be quite a bit more sloppy. One shouldn't treat any single thing as a panacea, but I've definitely come around to the view that immutable by default is a good approach. You get to just trivially dodge entire categories of nasty problems when doing something like the above. I'd love to hear anything more you can share about the stuff you work on. It sounds really interesting.
- bob1029 5y agoI really enjoy seeing how similar themes emerge across the industry. I've been working on a key-value store that is purpose built for low-latency NVMe devices. I have an append only log (spread across file segments for GC concerns), with the only contents being the nodes of a basic splay tree. The key material is randomly-derived, so I don't have to worry about the sequential integer issues on inserts. Writes to the database are modified roots of the splay tree, so the log is a continuous stream of consistent database snapshots. For readers that don't require serialization, they can asynchronously work with the historical result set as appropriate without any translation or sync required. You just point the reader to a prior root node offset and everything should work out.