A database without dynamic memory allocation
tigerbeetle.com
tigerbeetle.com
There is a less obvious benefit in more schedule-driven database architectures. By implication, the code knows exactly how much of which resources are instantaneously available at all times since it is directly managing those resources. This enables the database to dynamically adapt its behavior and scheduling decisions in response to specific resource pressures or excess resource capacity. This is basically a fine-grained form of internal micro-backpressure, dynamically prioritizing subsets of the workload that minimize impact on the resources under pressure at any moment in time. In some versions, you can switch internal execution strategies to take advantage of currently under-utilized resources. If you outsource this to the OS, you have no idea how close or far you are from the limits, it doesn't really work.
This doesn't add much performance per se but is great for minimizing tail latencies. It helps to create a robust internal resource equilibrium that handles transients and concurrency more smoothly and consistently than if the database couldn't make a fine-grained decisions about what to do from a position of total resource awareness.
I’ve gotten a lot of massive performance wins by rewriting code in rust because I can control memory allocations more closely. Some people I’ve talked to about this seem to just hear “rust = fast”. I’ve seen expensive rust rewrites which somehow end up running slower than the equivalent Javascript code. Turns out if you write rust like you write javascript, with boxes, vecs and .clone()s everywhere it’s going to be slow.
Allocating all required memory is, IMHO, a great practice for almost any type of program.
Heap memory allocators are a type of performance optimization, they allow re-use of existing memory, but only if you are careful to not run out of memory. Heap's of course also allow for more efficient utilization of memory, if some software module isn't using that bit of RAM right now, let another bit of code use it.
But like all performance optimizations, they make code messier, and they also lead to less reliable and harder to follow code.
In the embedded world, code statically allocates all memory it needs up front. This means that code that reads from the external world has a fixed buffer size, and also likely a related max throughput, regardless of system conditions (e.g. lots of free memory laying around).
But, this is also a good thing! It forces programmers to think about their limits up front, and it also forces thinking about error handling when those limits are broken!
Sure it can require creative coding, loading large blobs of binary data requires more work when you stop assuming malloc can return infinite memory, but, hot take here, programs should stop assuming malloc can return infinite memory anyway.
It's also made TigerBeetle's code more reliable, because tests can assert that limits are never exceeded. This has detected rare leaks that might otherwise have only been detected in production.
I mean it's not like memory exhaustion is a common occurrence nowadays. These kind of compromises, where one trades an almost non-existent failure mode for a fragile assumption-ridden code base does not sounds like a wise choice.
I mean, if the particular process is so tightly-integrated that you can know that you have a 1:1 relationship between X and Y, you can also tie those together with dynamic allocations. I find it hard to believe that you can easily statically show that X and Y allocations are tied in a static allocation scheme but that it would not be so under dynamic allocation?
Except for things like the ESP32, which uses malloc pretty liberally within ESP-IDF. Networking is hard without it, it seems?
One of the challenges I’ve had in the firmware work we’ve been doing, is the sheer amount of network-received runtime configuration. Makes statically allocating everything difficult. Not impossible of course, but our memory usage ends up sky high because we end up allocating buffers for the 70% of code that isn’t even going to be executed! So using “dynamic” allocation once when the runtime config determines this functionality is actually needed has worked reasonably well
Though it really reminds me of avoiding the GC in garbage collected languages, which is a little amusing to think about
Most old school formats have max size limits for good reasons, and the really good protocols allow the receiver to specify the maximum amount of data to send at a time!
Of course if your device has 256K of memory, reserving 64K for a max size TCP/IP packet is incredibly wasteful.
But if you can receive one of those packet at any time, realistically you need to have 64K available at any time so....
I'm not sure about newer stuff. Last time I did embedded things like Bluetooth were sectioned off into their own bit of memory, malloc was used, and it was a source of bugs that we weren't happy about.
[1] https://github.com/espressif/ESP8266_RTOS_SDK/blob/89a3f254b...
You'll still get lower performance if the system is low on memory, because you got swapped out - it doesn't have much if anything to do with how much you allocated. Wiring it is a different story, and if you're an audio app maybe you should allocate and mlock(), but not a database.
> hot take here, programs should stop assuming malloc can return infinite memory anyway.
Assuming this is a perfectly fine way to make reliable software.
Why wouldn't you wire database memory?
No reason to fight the OS unless you're a hard realtime process, which a database usually isn't.
Database implementations are capable of swapping most of their address space themselves, independent of and better than the OS -- it is a large part of their function. As such, optimization is heavily dependent on both memory and storage being physical. This being true is precondition for most architectural macro-optimizations to work.
Do you know any good resources to get into that mode of thinking, including common patterns, for sombody who is used to malloc everything? I could easily come up with lots of examples in my current project where "it isn't that easy" and "you cannot know this up-front", even when re-designing the whole architecture, and trying to solve those problems feels like re-inventing a hundred wheels that have been invented before.
That is, the second article basically says: (pre-arena) It would be so easy if we could just allocate everything on the stack, because lifetimes are nestable. But the article doesn't say how to know the required size of the stack in advance, to prevent stack overflows. That was the part I was interested in.
edit: I could read the first article through a proxy, but it also just talks about different allocators. I'd like to achieve what com2kid was talking about: "Allocating all required memory is, IMHO, a great practice for almost any type of program."
Pre-allocating certainly requires a system/application designer to consider the most likely worst case resource usage and then enforce that estimate throughout the design.
Further, for systems that have modern memory sized resources (i.e. 16gb and up) the system is designed to work as though memory was a stack and then that stack is allocated from system resources using something like a growable array, or slab style allocator. So that if the estimated wort case usage is reached, the ‘static memory allocation’ can be relocated and enlarged or added onto with a new slab.
Your comments imply the sticking point may be the estimate of program memory usage, and that is a very fact/situational analysis.
At some point you have to accept you will have hard limits in place. You have to signal back to whoever is sending you data that you cannot receive any more, they need to chunk it up smaller.
But, key lesson, you should already be doing that, but 99.999% of the time we get away without doing that because memory on modern systems is so large.
Drop down to embedded, and now your bit of code gets a 512 byte buffer to work with, and your paycheck depends on making it work, well, you will figure out a way to make it work.
For data coming in over the wire, generally it consists of packet size fields. It also means waiting for data to be processed until you accept more.
For data being passed around locally, well someone somewhere has a buffer. Careful tracking of ownership means you reduce unnecessary copying of data, especially if data is going to be processed and then discarded.
Strings are a separate problem, typically you will have some sort of string allocator dedicated just to strings because strings suck. But even then you will have a max length, but string sizes vary so much just using max length for every string on a screen will blow your memory budget away.
It took me awhile to get into the proper headspace, and it hurt my heart a little bit when I went back to GC'd languages where memory is thrown away willy nilly!
How can this be true given most mainstream databases do not do this? Maybe a pattern sure, by idiomatic, not so much. I only add this comment in defense of the poster as this comment seemed to reduce their achievement/efforts.
sqlite apparently has some support for this, although of course you make it more predictable if you control all the code.
https://www.sqlite.org/malloc.html
They even provide some nice math for you to create the fixed size heap!
The problem of dynamic memory allocation, and specifically the problem of a memory allocator breakdown, has been studied by J. M. Robson and the results published as
J. M. Robson. "Bounds for Some Functions Concerning Dynamic Storage Allocation". Journal of the Association for Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499.My students do this on the GameBoy Advance specifically so they don't need to learn about dynamic memory allocation to get useful things done early in my course. In fact, they only learn about dynamic memory allocation for academic reasons later on and never _need_ to use it in their games.
Zig in particularly makes this really approachable. Too dumb to pull it off in C myself, trivial in Zig.
YMMV.
https://github.com/ijustlovemath/bfi
You can also do ergonomically nice things using static allocation in many data structures, like linked lists (as a tiny example: https://github.com/ijustlovemath/linked-list/blob/master/ll....). That way you can focus on the concepts that matter; the data structures, and not frustrate newbies with opaque and difficult-to-reason allocation issues (at least not at first!)
This sounds interesting - Any information / course material available online? (I found nothing in your hn profile...)
A database that doesn't OOM crash is great, and the same is also true for more consumer-grade software.
I have 32gb of RAM on my PC and whenever I'm encoding a video with DaVinci Resolve, I always see Firefox and Discord crash almost instantly.
Also, are you sure it's the programs failing and not some OOM killer coming around? Could your pagefile/swap be full?
Joran from the TigerBeetle team here.
This was in fact one of our motivations for static allocation—thinking about how best to handle overload from the network, while remaining stable. The Google SRE book has a great chapter on this called "Handling Overload" and this had an impact on us. We were thinking, well, how do we get this right for a database?
We also wanted to make explicit what is often implicit, so that the operator has a clear sense of how to provision their API layer around TigerBeetle.
Being crash tolerant is one thing. But "crash early, crash often" is absolutely horrible advice.
Sure, but again, that's a scenario that you need to handle anyway.
> Being crash tolerant is one thing. But "crash early, crash often" is absolutely horrible advice.
I've found it to be good advice. It's a big part of why Erlang systems have been so reliable for decades.
And that's why Erlang is so resilient, precisely because the semantics of the language make it easier to isolate tasks and subtasks, minimizing blast radius and the risk of reaching an inconsistent or unrecoverable state. I often use Lua (as a high-level glue language) to accomplish something similar: I can run a task on a coroutine, and if a constraint or assertion throws an error (exceptions in Lua are idiomatically used sparingly, similar to how they're used in Go), it's much easier to recover. This is true even for malloc failures, which can be caught at the same boundaries (pcall, coroutine.resume, etc) as any other error.[1] It's also common to use multiple separate Lua VM states in the same kernel process, communicating using sockets, data-copying channels, etc, achieving isolation behaviors even closer to what Erlang provides, along with the potential performance costs.
[1] While more tricky in a language like Lua, as long as your steady-state--i.e. event loop, etc--is free of dynamic allocations, then malloc failure is trivially recoverable. The Lua authors are careful to document which interfaces and operations might allocate, and to keep a core set of operations allocation free. Of course, you still need to design your own components likewise, and ideally such that allocations for connection request, subtasks, etc can be front-loaded (RAII style), or if not then isolated behind convenient recovery points. Erlang makes much of this discipline perfunctory.
The situation you described is exactly what is prevented with static allocation. It's a very predictable design - it will successfully handle X requests and will fail any requests above that.
An important thing implicit in this design - or at least that I'm assuming - is that there is no queue of requests. Queuing is a major source of problematic behaviour during overload. It's /queuing/ that causes RAM to increase with load (in a system with fixed max of requests being processed). It's /queuing/ that is why latency increase as you near load limits (vs errors).
I'm with you that early errors are better, and the scheme used here achieves that on a request level.
This presumes that one is indeed using a pagefile or swap partition. I know of quite a few folks who skip that on SSDs out of fear of SSD wear.
Personally, in this day and age I don't really give a damn about SSD wear (that's what backups are for), so I'll happily create a swap partition, but not everyone is as comfortable with that.
So yeah, average user software can do a lot, it's just that we've given up on reliability and robustness as an industry. That's why sometimes your phone fails to make a 911 call, and sometimes you need to reset your car.
Maybe that breaks some relational features on the table, but being able to painlessly query the most recent X records for some interesting transient log data would be nice.
I also am building a ring buffer data structure for my hobby database that I use for personal stuff that uses FoundationDB [though I have been unhappy with the state of the FDB Go bindings, which are somewhat out of date versus the C client library for FDB and aren't very Go-like in design (the C libraries are the "gold standard" and they use FFI in all the other bindings to connect to those)].
Added later: it was a bit harder to deal with resizing the buffer, so when that happens I do some data shifing/dropping depending on which way we're resizing, effectively initializing the buffer anew because that was easier (again, a Redis transaction saves me a lot of concurrency work!), but lucky for me we would only resize each buffer at most 1 time per minute due to how our configs work.
Somehow DaVinci Resolve is capable of using all the free memory it can find and not more than that, otherwise it would never be able to complete any rendering job. That's one "utopic" program that's pretty real.
> We have a solution to the problem you describe, it's called paging to disk and hoping
No. The solution is to be smart about memory usage, and to handle failures when trying to allocate memory. DaVinci would become unusable if it started swapping when rendering.
Maybe for some programs swapping is a fine solution, but the argument that software engineers shouldn't concern themselves with designing for OOM conditions is absolutely ridiculous.
That's not a 'utopia', that's what we should be concretely be striving for.
The good news is that we do have ecosystems where you don't have overcommit, like webassembly and embedded devices, and if you're writing libraries meant to also work on those platforms, then you will have some good building blocks that can be used to iterate towards more robust software.
That's how you're expected to approach library writing in Zig.
malloc() can fail if you try to allocate many GBs at once, but if you let it fail for 32 byte allocations then what are you even going to do about that? The only solution is to crash your process, but that will lose user data if you haven't saved it yet, and purity isn't worth that.
> The only solution is to crash your process
I disagree. I think this is a bad mindset that we allowed ourselves to slid into. There's a lot more than can be done when an allocation fails, starting from what I mentioned above.
That said, I'll agree that at least you need a programming language that can help you design and maintain allocation-free codepaths in your program, and that 's hard if your language has builtins that allocate implicitly, as you will have to avoid them all.
Zig has the philosophy of keeping all memory allocations explicit precisely for this reason. In the beginning people used to say that it was too extreme, but now Rust is also embracing this approach in order to be used in the Linux Kernel (one place where the "only solution is to crash" learned helplessness will not be well received), so hopefully there will be even more options in the future.
Course it does. You can’t run any code in a typical app environment without allocating heap objects as you go, and even if you didn’t, anything that accesses a swapped out page is “allocating physical memory”.
And once it gets into the kernel, file systems have to allocate their own objects to track new writes. Though if the kernel is failing to allocate memory you have worse problems.
write doesn't require you to allocate any memory
- Neal Walfield’s papers on resource management[1,2]
- The agoric papers[3] from the E people (who sadly now seem to be trying to steer the whole thing in the cryptocurrency direction)
[1] http://walfield.org/papers/2009-walfield-viengoos-a-framewor...
[2] http://walfield.org/papers/2011-walfield-smart-phones-need-s...
While I’ll admit that I find the corporate gloss of the Agoric website thoroughly repulsive, I would actually like to see cryptocurrencies succeed as a boring payment instrument. It’s just that my interests have always lain more in userspace resource allocation (etc.) among applications on a single machine, and in that context both E and the original agoric papers are completely separable from their money aspects, while any developments in the cryptographic consensus direction seem unlikely to be. Conversely, it’s not like the original object-capability work seems universally attractive to me—Shapiro advocated some system mechanisms that are, as far as I can tell, DRM-complete. But those are, again, separable from the rest of the ideas.
Moreover, they didn't just foresee people selling computing services to each other; some of them built what we would call cloud computing platforms where the platform owner sold computation and the platform users could sell services to each other on it, starting in 01968, which was successful for decades: https://en.wikipedia.org/wiki/Tymshare
That's the experience that gave rise to the object-capability approach in the first place.
And, as far as I know, the Digital Silk Road paper from Agorics was the first workable proposal for a secure decentralized digital money.
The only safe thing you can do is free entire pages at once, but that's not necessarily effective.
That's why iOS typically just kills you instead.
You don't want malloc to instantly release memory to the system on free(), and malloc() is then constrained by the same page multiple at a time restriction as anything else so it can't release fragmented memory.
What you should be doing is trying to save state so that you can return to original state, not fighting to keep going.
https://learn.microsoft.com/en-us/windows/win32/api/memoryap...
Great! Then users can annoy devs who write crappy software “I can’t open anything else when discord is open!”
Vs today where the OS essentially conceals crappy software from the user via a billion layers of abstraction and hacks
In the case of e.g. Firefox, do you really want it to always be doing bookkeeping for 100 tabs when you only need 1? Or having to restart Firefox every time if you've hit the upper limit of tabs? Or just let Firefox dynamically allocate memory as you open more tabs?
There are many compelling reasons for dynamic memory allocation, and "the OS essentially concealing crappy software from the user via a billion layers of abstraction and hacks" is a fundamental misunderstanding of its purpose.
Even if your application does not have stringent safety/predictability requirement, following the principles of Data Oriented Design leads naturally to a radically different approach to memory management.
I am glad to see this kind of projects and design choices.
Data Oriented Design runs like a river through TigerBeetle—it's always on our mind.
By the way, have you seen Andrew Kelley's Handmade Seattle talk on Practical DOD? [1]
I think DOD should be more like an engineering mindset than a strict set of rules.
From my experience it can be impractical/cumbersome, especially when prototyping because DOD usually pays off in the long run.
As someone who works on low level database code, this approach is going to be EXTREMELY wasteful. Instead, it's much better to instead have a more sophisticated understanding of memory use by subsystems and have some concept of required memory and caches. Each system allocates the minimum memory it needs at startup and then treats the rest of memory as caches which can be emptied as necessary to preserve fairness among all the various subsystems.
Sure, but there's a lot of advantages of entirely controlling memory allocation in-process.
> this approach is going to be EXTREMELY wasteful.
Could you elaborate why? Sure, you have to do a bit more juggling in-process, but I would imagine this would be potentially more efficient than having conventional mallocs.
In the environment it is designed to operate in, there is usually a fixed memory limit per process, so you might as well grab all that up front.
Joran from the TigerBeetle team here.
> I would imagine this would be potentially more efficient than having conventional mallocs.
Yes, in our experience, static allocation means we use sometimes 10x less memory. For example, TigerBeetle's storage engine can theoretically address up to 100 TiB with less than 1 GiB of RAM for the LSM in-memory manifest, which is efficient.
Because we think about memory so much upfront, in the design phase, we tend not to waste it.
Title says "without dynamic memory allocation" == what means without malloc in this context, so static memory allocation ... where you do your own kind of memory management in fixed size arrays or more sophisticated if you want. It didn't say without memory management? (And article explains also why no strings or other unknown/arbitrary length stuff..)
There are no user strings in TigerBeetle. :)
If anyone wants to see what you can store in accounts and transfers, check out the reference docs!
Is anything nullable, or for like the user_data column, do you just use 0x0 to indicate no record?
However, come to think of it just using a fixed amount is just as good if not better, since I’m always going to be constrained by memory in some way anyway. And if I allocate e.g. 80% of the system’s memory upfront, it won’t _actually_ be mapped by the OS until I touch it. There may be some interesting stuff with using huge pages for the first few pages and use smaller and smaller pages as you approach your memory limit. Definitely will give this a try!
What about people running vm.overcommit_memory=2
(Yes fork-exec is stupid, but there's not much you can do about it)
In my experience, most programs have a few long-lived data structures that can be initialized up front, and then lots of small data structures that are created and destroyed frequently. If you do it right, you can put the long-lived guys at the beginning of the arena and then just wiggle your arena head pointer back and forth for the small guys.
This does take some more thought and consideration, and is definitely a bit trickier than just using malloc when you need it, but for me the trade off is worth it (for one I gain some amount of satisfaction from imagining my data all neatly in a row).
1. Bound every whatever that requires memory to some value N
2. For all whatevers that can have a lifetime for your entire program, do that
3. For any whatevers that can't have a lifetime for your entire program (e.g. for a database server like TFA, a connection object would qualify), make a table of size N
4. When you need a whatever (again using a connection object as an example, when listen() returns) grap an unused entry from the table. If there is no unused entry do the appropriate thing (for a connection, it could be sending an error back to the client, just resetting the TCP connection, blocking, or logging the error and restarting the whole server[1]).
5. When you are done with a whatever (e.g. the connection is closed) return it to the table.
Those are the basics; there are some details that matter for doing this well e.g.:
- You probably don't want to do a linear-probe for a free item in the table if N is larger than about 12
- Don't forget that the call-stack is a form of dynamic allocation, so ensure that all recursion is bounded or you still can OOM in the form of a stack overflow.
I should also note, that for certain values of N, doing things this way is normal:
- When N=1 then it's just a global (or C "static" local variable).
- When N=(number of threads) then it's just a thread-local variable
1: The last one sounds extreme, but for a well understood system, too many connections could mean something has gone terribly wrong; e.g. if you have X client instances running for the database, using connection pools of size Y and you can have 2XY live connections in your database, exceeding N=2XY is a Bad Thing that recovering from might not be possible
The approach I've seen for larger fixed-sized tables is a free list: when the table is allocated, also initialize an array of the slot numbers, with an associated length index. To allocate, pop the last slot # off the array and decrement the length index. To free, push the slot # onto the end of the array and increment the length index. Checking for a free slot is then just testing for length index > 0.
Writing reliable systems means spending a lot of time thinking about what and how failures can occur, minimizing them and dealing with the cases you can't get rid of. Simple is nearly always better.
It also helped to be an EE by education and not a CS major. CS majors can get blinded by their abstractions and forget that they're working on a real piece of HW with complex limitations which require design tradeoffs.
TigerBeetle uses Deterministic Simulation Testing to test and keep testing these paths. Fuzzing and static allocation are force multipliers when applied together, because you can now flush out leaks and deadlocks in testing, rather than letting these spillover into production.
Without static allocation, it's a little harder to find leaks in testing, because the limits that would define a leak are not explicit.
Here's an overview with references to the simulator source, and links to resources from FoundationDB and Dropbox: https://github.com/tigerbeetledb/tigerbeetle/blob/main/docs/...
We also have a $20k bounty that you can take part in, where you can run the simulator yourself.
We also target Linux with the same codebase, but the environment is a bit different. On Linux we're using a system slice and we're not doing minidumps.
The techniques mentioned above will (perhaps surprisingly) not eliminate errors related to OOM, due to the nature of virtual memory. Your program can OOM at runtime even if you malloc all your resources up front, because allocating address space is not the same thing as allocating memory. In fact, memory can be deallocated (swapped out), and then your application may OOM when it tries to access memory it has previously used successfully.
Without looking, I can confidently say that tigerbeetle does in fact dynamically allocate memory -- even if it does not call malloc at runtime.
I'd be curious if you have any resources/references on what is considered good practice in that now, then.
It's been a long time since I did much ops stuff outside a few personal servers, so it may well be my background is out of date... but I've certainly heard the opposite in the past. The argument tended to run along the lines that most software doesn't even attempt to recover and continue from a failed malloc, may not even be able to shut down cleanly at all if it did anyway, and the kernel may have more insight into how to best recover...so just let it do its thing.
It would be ideal to not tickle the OOM killer, but it does happen. A great example would be Redis, using bgsave. There's a lot to criticize about redis and bgsave and I don't mean to defend its architecture. Its behavior is fairly extreme so it provides an example useful for illustration. Because Redis forks its entire in-memory state and writes itself to disk, it will sometimes appear to the system as if it has doubled in memory use. It's a huge, sudden memory pressure event, exacerbated by any writes forcing CoW allocations while the bgsave runs.
Many other app servers or database systems can have similar sudden memory pressure. You basically don't ever want a primary app on a system to be killed, so it's usually best to just disable OOM killer entirely on these processes.
There's often no failed malloc() in these situations. Often you will see OOM in situations where no malloc() has ever failed, because malloc() is just allocating address space without any attached memory, which is nearly free, and which almost always succeeds. The failure will occur later when the allocated page is first written to -- causing a page fault and an actual allocation to happen. There's no associated function call or system call. Page faults are triggered simply by accessing memory. This is why the OOM killer exists, as there's no function available to return a failure to when memory can't be produced. Such is the idiosyncratic behavior of lazily-allocated memory in modern virtual memory systems.
tldr: Malloc never fails, because malloc allocates address space not memory. Memory writes trigger failures, because writes create page faults and trigger the actual allocations. But the failures often express behavior elsewhere, via the action-at-a-distance magic of the OOM.
Are there any other databases which do a similar thing?
This seems like one of those things that has massive benefit if you're willing to invest in the effort + architect it like that from the start.
(Unrelated note: I discovered last night that Zig has io_uring support and some nice wrappers implemented in "std". Which is nice for usecases like databases or networked services)
https://github.com/ziglang/zig/blob/42a3b60c331cf01d1ab80eb7...
io_uring support was contributed to the Zig standard library by Joran, who is also the creator of TigerBeetle :^)
The Kernel has a feature that takes advantage of this same principle: memory overcommit. Programs are always asking for way more memory than they actually need. The kernel lies to those programs, and says, "yes, yes, I'll give you all that memory... sure thing..." even if it already said that to every other program. This allows more programs to continue operating since they aren't really using all that memory. When the system does run out of memory, it can swap rarely used memory out to a swap file; when that doesn't work, the application can receive an error, or the OOM killer can just kill the process. The result is more programs doing more work, and an occasional app crash.
Virtual machine hypervisors do a similar trick with memory ballooning. If the guest OS has a balloon driver, the hypervisor can overcommit memory for the VM guests, and you can provision more VMs than there's actually memory for.
Doesn’t that cause the very problem it was meant to solve?
Programs ask for more memory, because they can.
Users run those programs, because there’s no indication anything is wrong.
And programs keep requesting more memory than need because the kernel cleans up after them!
Alternatively a kernel that actually gave non-malicious (?) programs the memory they requested exclusive access to would at first run worse, but long term perform better as users rightly pester app devs for apps that use excessive memory.
Only now thinking about it, doesn’t overcomitting make it impossible for programs to be well-behaved during high system load? Everything is lying to you up until the last second, when suddenly you’re dead by OOM killer. When does malloc even return errors in practice?
The approach of letting applications just allocate as much memory as they wanted arose in the era of primarily 32-bit operating systems. And that meant that, at a process level, in practice 'as much memory as you want' capped out at 4GB (or 2GB if you are Win32 because... Windows reasons).
And so when you're running 32 bit processes on computers with single-digit-gigs of physical RAM, and multiple-digit-gigs of disk space, and single-core processors, letting processes treat memory as 'all you can eat' and swapping out excess allocations to disk is going to work out fine. Your processor can only be running one application's code at a time, and a significant fraction of that application's entire address space can all be paged into physical memory at once, with the full amount not taking up too much disk space, so for the most part you can get away with just treating 'process address space exhausted' as being as good a signal as any of 'out of memory'.
But now we're in 64-bit land, address space exhaustion is no longer a thing. If you just allow programs to keep allocating RAM until they run out of 64-bit address space, to a first approximation, 0% of your application's maximum address space will ever be able to be paged into physical RAM, and you will need several exabytes of hard drive space to hold what's paged to disk.
So the problem is we now don't really have a natural limit akin to the 32-bit address ceiling to impose on applications who want to allocate memory, and it means we're instead put in the position of having to come up with policies ourselves. Stuff like setting a memory limit on a docker container. And so we wind up having to actually now think about and answer the question, 'how much memory should we let each process on this system allocate?'
Setting a memory limit on docker containers comes from automation. We built new-fangled automation that can schedule multiple copies of an application across N nodes. Then we tell people they can run more and more copies of the app, for CI/CD, for test/stage/prod, for Joe's Test App, etc. All these copies are using up memory. At some point, somebody tries to deploy to prod, which needs to start new copies of the new versions. But now they can't because the paultry few nodes have now run out of memory from all these extra copies of the apps. So now we have to impose limits or we can't deploy to prod.
(you might ask: "why don't we just automate expanding the nodes to accommodate more memory?" and they did. and it doesn't work well, for reasons that give me a headache)
(you might also ask: "why don't they just make an OOM killer for the automated cluster?" and they did. and it doesn't work very well either, for other headachy reasons)
"Software is a gas: it always expands to fit whatever container it is stored in." - Nathan Myhrvold (https://web.archive.org/web/19990202072225/http://research.m...)
Static allocation does make for some extremely hard guarantees on p100 latency. For example, for a batch of 8191 queries, the performance plot is like Y=10ms, i.e. a flat line.
And memory doesn't increase as throughput increases—it's just another flat line.
I personally find it also to be a fun way of coding, everything is explicit and limits are well-defined.
The sixties actually; that's how memory was managed in Fortran from its inception until the eighties.
Reminds me of Carmack on the benefits of long functions: http://number-none.com/blow/john_carmack_on_inlined_code.htm...
The limit of 70 lines is actually a slight increase beyond the 60 line limit imposed by NASA's Power of Ten Rules for Safety Critical Software.
In my experience, in every instance where we've refactored an overlong function, the result has almost always been safer.
This is the key part.
Zig memory allocation is something like bookmark, allocate and then free everything after bookmark when done. Someone pushed it to limit.
https://github.com/tigerbeetledb/tigerbeetle/blob/main/docs/...
Static allocation doesn’t eliminate use-after-free bugs, it just reduces them.
If you have mutable data structures, it’s still always possible to refer to something that used to have one meaning and now means something else. That’s still a use-after-free bug.
I was going to say that it’s similar to how GC can still have memory leaks, but in fact it’s the exact same problem: reachability of data that is no longer relevant/correct.
When you point to real, dead objects, the bug can be anywhere or everywhere. If you have a pattern of using impure functions everywhere this can be a nightmare to identify and fix at scale.
One of the first bits of code we wrote in the project was a statically allocated pool of buffers such that the only way to free buffers back to the pool is for all references to that buffer being dropped.
There's a lot of wisdom in this post, but that made me wince. It's a bit like saying "Our system doesn't crash when we dereference a null pointer." Well, cool. What could possibly go wrong.
Still, I think it's best to just ignore that line and read the rest of the post. It's an unfortunate distraction to the core idea (which does have real value). For example:
> here is how we calculate the amount of memory needed to store messages for TigerBeetle’s consensus protocol: <snip>
> And if we get the calculation wrong? Well, since we enforce static allocation, we can check these calculations with assertions (i.e. that a free message is always available). If we then get the static allocation calculation wrong, this can be surfaced sooner through fuzzing, rather than having no limits and eventual resource exhaustion (and cascading failure!) in production. When combined with assertions, static allocation is a force multiplier for fuzzing!
Being able to put a hard upper bound on the amount of memory your system can use is generally a sign of good design. The alternatives are somewhat messy but still work. (The HN clone I maintain https://www.laarc.io/ runs via a while-loop bash script, because it dies via OOM every couple weeks. But it works great, since every time it dies it just restarts.)
Joran from the TigerBeetle team here.
Appreciate your balanced comment.
To be fair, we're certainly concerned about logic errors and buffer bleeds. The philosophy in TigerBeetle is always to downgrade a worse bug to a lesser. For example, if it's a choice between correctness and liveness, we'll downgrade the potential correctness bug to a crash.
In the specific case of message buffer reuse here, our last line of defense then is also TigerBeetle's assertions, hash chains and checksums. These exhaustively check all function pre/post-conditions, arguments, processing steps and return values. The assertion-function ratio is then also tracked for coverage, especially in critical sections like our consensus or storage engine.
So—apologies for the wince! I feel it too, this would certainly be a nasty bug if it were to happen.
We use what we have available, according to the context: checksums, assertions, hash chains. You can't always use every technique. But anything that can possibly be verified online, we do.
Buffer bleeds also terrify me. In fact, I worked on static analysis tooling to detect zero day buffer bleed exploits in the Zip file format [1].
However, to be clear, the heart of a bleed is a logic error, and therefore even memory safe languages such as JavaScript can be vulnerable.
This approach is still useful, but it's no panacea. It can even leave various kinds of capacity unused, or it can become a tuning nightmare if you try to avoid that. It has long been common in embedded (as others have pointed out) due to the requirements and tradeoffs characteristic of that space, but for general-purpose computation it might not be the tradeoff you want to make when other techniques can solve the same problem without some of the drawbacks.
And that can be a self fulfilling prophecy. One of the problems with memory pools is concurrent access, both by your programming language and the processor, and so it starts looking attractive to spool up a process per task.
Even if the messages are fixed sized surely the memory cost of executing the queries depends on the complexity of the query, and the expected numbers of results returned.
Are they just doing get/set style queries only?
Joran from the TigerBeetle team here.
TigerBeetle's storage engine is designed also for range queries, and we have some interesting ideas for our query engine in the works.
To be sure, there are some tricky things that crop up, such as pipeline blockers for queries. However, we do have limits on literally everything, so that makes it easier—static allocation is best when it's done viral.
We wanted to go into so much more detail on all this but there was only space for so much. Stay tuned.
It left me thinking because of the unpredictability in timing which arises from its use, but then again, the article closes with the sentence
> Until then, it is important to note that no feature is given support by C++ if it has not been fine-tuned and optimized and we cannot expect to see total coroutine implementation until at least C++26. Nonetheless, if you’re an algorithmic trader or C++ developer, watch this space and watch it very closely.
https://www.efinancialcareers.com/news/2022/10/algorithmic-t...
This also implies all memory is allocated upfront. It would require the operating system to be smart enough to compress/page blocks or else the process will hold on to unused memory
Sooo are we sure you can even change this via proc restart? This is saying the limits are built-in during compile...
Now, given that modern CPUs rely heavily on their cache lines/hierarchies, branch predictors, and prefetchers, changes in layouts can have significant performance implications, algorithms that run quickly when things are contiguous in memory, can run orders of magnitudes slower on layouts that are more random, and have more cache line miss. And those layouts are often the result of long run-times in dynamically allocated systems, due to accumulated heap fragmentation.
Now, static allocation neither completely solves these problems, nor is it the only solution, but it is the case that the techniques that are used for static allocation, often have tremendous benefit for cache layout, and combined with other added benefits, like reduced OOM conditions, it's a powerful constraint.
Edit: Not to mention that the previously noted heap fragmentation can also cause eventual failure to allocation conditions, even without true memory exhaustion.
In many fixed sized systems "re-used" as a result of bugs data is still good one and it will produce slightly different results that can not be distinguished from real ones until whole computation will be done outside of system. If data reference mistake is stable it can even pass majority/stability tests for long time. Filling destroyed values can save a lot of time just because it will produce nonsensical results that will be noticed faster.
Also coming from games industry I don't recognize praise of fixed systems at all. Games prefer fail fast. Restart can be easy for players if they re-connect or not lose any progress. The way to get players truly upset is to get player data mixed with bad values after long play time or if there is no easy way to recover progress/saved data.
I wish all programs did this
https://www.geeksforgeeks.org/difference-between-static-allo...
There are plenty of strategies nowadays to avoid garbage collection and use-after-frees (rust comes to mind), I'm not convinced working with fixed amount of resources is the most friendly to operators.
We have a secret plan for this too. ;)
Most benefits listed have nothing to do with memory allocations. For example "having a client open too many connections" can be limited by... limiting the number of open connections. Where and how that check is done might differ, but it's not related to memory allocations.
There are BIG downfalls to static allocations:
- You cannot support varied workloads. If one workload needs a lot of X and another needs a lot of Y, well, you already decided the maximum numbers of X and Y and cannot re-balance it.
- If you run out of anything you thought was "sufficient" enough, your programs just fails.
I mean, sure, your program is easier to analyze statically, just like if you gave up dynamic threads and instead just pin different parts of your program to different CPU core. Sure that solves some concurrency problems, but most programs don't do this for obvious reasons.
A quick look shows how this is done: https://github.com/tigerbeetledb/tigerbeetle/blob/91a105875c...
You can see things like alloc / free, memory ownership, and everything that is associated with it.
The fact that you allocate from a startup buffer vs. a call to `mmap`/`brk` doesn't really change things.