12 ms·
A database without dynamic memory allocation
- gavinray 4y agoI like this idea a lot. 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/42a3b60c331cf01d1ab80eb79e959bc86397f75b/lib/std/os/linux/io_uring.zig https://github.com/ziglang/zig/blob/42a3b60c331cf01d1ab80eb7...
- kristoff_it 4y ago> (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) io_uring support was contributed to the Zig standard library by Joran, who is also the creator of TigerBeetle :^)
- sakras 4y agoI like this a lot! I’ve been trying to find ways to avoid memory allocation as much as possible in my projects as well. So far I’ve settled on mmap-ing large slabs at a time and arena allocating (Linux’s mremap makes growing the allocation really efficient too!). 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!
- vbezhenar 4y ago> 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 What about people running vm.overcommit_memory=2
- NavinF 4y agoIn practice that's a broken config because any program that uses the fork syscall will hog all your memory. (Yes fork-exec is stupid, but there's not much you can do about it)
- enedil 4y agoYes, this approach is followed as well, but now you're at the problem of writing a memory allocator by yourself (which might of course turn out to be better for your usecase). So the issue of writing code that avoids allocation still prevails, as now you probably want to know what to allocate memory for, since if you were supposed to make a general purpose allocator, it is likely it won't overperform libc malloc.
- sakras 4y agoI agree on some level, but I think if you’re intentional with your design you can get by with a very simple arena allocator where an allocation is a single subtraction from a pointer. 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).
- chrchang523 4y agoI use a double-ended stack allocator for most allocations in personal C projects. The second end adds a significant amount of flexibility; temporary allocations can accumulate at one end of the stack without preventing a longer-lasting allocation from being made later (yet before the temporary allocations can be freed) on the other end.
- sakras 4y agoOh that's also great! Thanks for the tip, I'll have to incorporate it!
- aidenn0 4y agoI've been an embedded software developer for almost 2 decades, and this style used to be near universal in embedded, but has become less so, much to my dismay. I even saw a project not too long ago where a large C++ STL List (i.e. a linked list) was created at startup, then later freed piecemeal, causing so much heap fragmentation on the poor embedded system malloc implementation.
- LunaSea 4y agoWould you have some links to posts that talk about this style of memory management and allocation?
- malkia 4y agoGame Development still revolves around this. For example when loading a level, it used to be you have huge arena, you load your "serialized" map at one end (say top), and your other chunks at the bottom - you have some "flexibility" to pop from top or bottom, so early on you arrange for that. Alternatively you split your memory per sized big chunks, and stream in out these (works well for textures, and primed sounds - e.g. the first 64kb or 128kb of a sound file).
- deleted 4y ago[deleted]
- aidenn0 4y agoI don't have some links, but it's more straightforward than you might think (and TFA covers some of it). 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
- pyrolistical 4y agoThis implies changing of buffer sizes requires a process restart. Which is a fine trade off. 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
- haggy 4y agoPer the article: "(Currently it’s determined even before startup, at compile-time, but startup is the important point since that is the first time that memory can be allocated.)" Sooo are we sure you can even change this via proc restart? This is saying the limits are built-in during compile...
- eatonphil 4y agoThey are currently compile time settings. That may change in the future to be more user-friendly. :) But what won't change is that the size is fixed at startup.
- haggy 4y agoThat totally makes sense. I think you'd have a miserable time supporting this at scale if a re-compile is needed every time a new workload requires a tweaked setting or two. Config based static allocation is the best of both worlds.
- Thaxll 4y agoHow does it works exactly? It's a memory pool that uses 85% of available memory? If I have one row in my DB it's going to prealocate 30GB of memory? I don't think it's a sane design, it reminds me the JVM args with min / max.
- allknowingfrog 4y agoThe article differentiates between "memory" and "on disk" storage, which is where the rows in the database would live.
- sakras 4y agoThe OS doesn’t actually map/allocate the pages to you until you touch them, so if you preallocate 30 GB and only use one row, you’d only be using 4 KB (or whatever your page size is). This is the same as if you’d individually malloc’d the single row, since deep down malloc just calls mmap.
- _vvhw 4y agoJoran from the TigerBeetle team here! We have a secret plan for this too. ;)
- apavlo 4y agoThis is pretty much how all DBMSs work right now. You have to tell it how much memory it can use for its internal buffer pool.
- aaaronic 4y agoIsn't this just a bunch of static object pools? That's extremely common in embedded programming. I'm glad to see someone recognized it could apply to a database. 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.
- schemescape 4y agoDo you mind sharing the name of the course? It sounds interesting. (I didn’t see anything in your profile.)
- LAC-Tech 4y agoIsn't this just a bunch of static object pools? That's extremely common in embedded programming. I'm glad to see someone recognized it could apply to a database. Zig in particularly makes this really approachable. Too dumb to pull it off in C myself, trivial in Zig. YMMV.
- idealmedtech 4y agoI do small projects statically all the time! Writing a simple bf interpreter can be done so statically that you don't even need to store the program in its own array; program text can just be taken directly as const char* https://github.com/ijustlovemath/bfi 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.c#L102 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!)
- e12e 4y ago> My students do this on the GameBoy Advance This sounds interesting - Any information / course material available online? (I found nothing in your hn profile...)
- kristoff_it 4y agoThe idea of having programs that don't crash under memory pressure is one of the things that I really hope developers will start striving for more in the near future. 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.
- colejohnson66 4y agoOOM is usually a good reason to crash. Sure, a DB might be able to do something creative with its cache, but if you can't allocate, there's not much the average program can do anymore. I guess browsers can kill their child processes, but that's not a long-term solution. If you're out of memory, your computer will be lagging from paging/swapping memory in-and-out, so killing yourself helps relieve some pressure. Also, are you sure it's the programs failing and not some OOM killer coming around? Could your pagefile/swap be full?
- advisedwang 4y agoThe article says it rejects incoming connections. that seems like a much better behaviour than OOM - clients can back-off and retry and keep the overall system stable.
- _vvhw 4y agoThanks! 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.
- lmm 4y agoI can easily imagine that kind of design getting into a state where it's "up" but not accepting any connections indefinitely (if it's using just enough memory to run itself, but doesn't have enough to accept any connections). Crashing early is often a good way to reduce the state space and ensure consistent behaviour, since you will always have to handle crashing anyway.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- hinkley 4y agoListen to me now and hear me later: 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.
- the_mitsuhiko 4y agoBased on my limited experience with using arenas and preallocated memory I find debugging memory issues significantly harder since it’s super easy to accidentally reuse allocations and only notice much later.
- hinkley 4y agoThe first pointer arithmetic bug I fixed, I only narrowed it down once I realized that the function was getting garbage data. Several others since have been the same way. This data structure has a value that can’t possibly be arrived at, therefore this data is fake. 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.
- avgcorrection 4y agoSounds like there should be some additional metadata memory that is summed in as well (for the total allocation at startup)? To check for such issues.
- gamegoblin 4y agoAt the risk of shilling for Big Rust (or at least any language with ownership semantics, really) -- well-designed Rust code can truly eliminate use-after-free. I was the lead engineer on a project that wrote an entire filesystem from scratch in Rust, and we did exactly this. 100K lines of code without any use-after-free bugs in the whole development process. 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.
- stephc_int13 4y agoIn some areas, especially hard real-time/embedded or safety critical, dynamic memory allocation is strongly frowned upon, and for good reasons. 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.
- _vvhw 4y agoThanks! 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] [1] https://vimeo.com/649009599 https://vimeo.com/649009599
- stephc_int13 4y agoYes, I've seen this one, and a few others. 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.
- francasso 4y agoWelcome back to the 70s! Jokes aside I think there are use cases for this style of memory allocation even today (embedded systems for example). I just have never felt its need in a DB (or rather, I have many more desiderata from a DB than "I don't have to worry about OOM").
- _vvhw 4y agoGood to be back—Joran from the TigerBeetle team here! 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.
- Rochus 4y ago> back to the 70s The sixties actually; that's how memory was managed in Fortran from its inception until the eighties.
- commandlinefan 4y agoWithout looking through the implementation, I suspect that the consequence here is that it pre-allocates way more memory than it needs and then does some custom dynamic allocation with that.
- haggy 4y agoThey explain pretty clearly that this is static memory allocation. In other words, a calculated amount of (mostly) contiguous memory is allocated at startup and used very carefully, relying on disk to supply the dynamic nature of database load semantics. https://www.geeksforgeeks.org/difference-between-static-allocation-and-heap-allocation/ https://www.geeksforgeeks.org/difference-between-static-allo...
- jokethrowaway 4y agoCool article and an interesting concept. It's definitely good to think out of the box - but I've rarely had to deal with a database OOMing (I assume because they have strategies to write to disk before that happens). 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.
- chubot 4y agoBuilding a system that allocates memory once up-front requires up-front thinking. 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 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.
- matheusmoreira 4y agoThanks for the reference, that Robson proof is amazing. Published in 1974... I wonder what other treasures are hidden in the literature.
- slaymaker1907 4y agoShould be titled "without using malloc" or something. It's pretty much impossible to do anything with user input strings unless you have some sort of memory management. Maybe you have one giant buffer that you use for strings in a particular session, but that still involves memory management because even if you allocate the buffer at startup, using one buffer for multiple strings is just a type specific arena allocator. 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.
- kortex 4y ago> using one buffer for multiple strings is just a type specific arena allocator. 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.
- _vvhw 4y agoThanks! 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.
- kristoff_it 4y agoI think it should be noted that TigerBeetle is an extremely specialized database. It's not a general-purpose DB for storing arbitrary data, all it stores is numeric financial account information.
- sh1mmer 4y agoMaybe I’m missing something but I would imagine query planning and caching is the hardest thing in terms of database memory usage. This post doesn’t seem to address that. 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?
- _vvhw 4y agoThanks! 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.
- valyagolev 4y ago> Restrict the length of function bodies to reduce the probability of poorly structured code. We enforce a hard limit of 70 lines per function. Reminds me of Carmack on the benefits of long functions: http://number-none.com/blow/john_carmack_on_inlined_code.html http://number-none.com/blow/john_carmack_on_inlined_code.htm...
- Gibbon1 4y agoObligatory Hank Hill. I'll tell you hwhat. I've seen some poorly structured code with nothing but small functions. Like a state machine implemented via chains of callbacks that could all just live inside one big switch statement.
- dktoao 4y ago"Clever" developer limitation like this almost invariably cause developers to come up with even more convoluted solutions to problems than needed. Don't disagree that long functions can be an indication that someone was copy pasting a bunch of stuff around in the codebase, but not always!
- avgcorrection 4y ago70 lines is generous compared to Clean Code dogma/opinion.
- _vvhw 4y agoJoran from the TigerBeetle team here. 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.
- lewisjoe 4y agoCan somebody eli5 what this really means? Specifically, how is code without dynamic allocation bring about predictability?
- 0x5345414e 4y agoIt brings predictability because know you won’t run out of memory. If everything is statically allocated, the total amount of memory the application will use is known at compile time. Very important for memory restricted systems.
- 01100011 4y agoDynamic allocation can fail. Memory can become fragmented or you could just exceed your budget.
- Arelius 4y agoIn addition to the mentioned known maximum memory, it also has useful performance characteristics. global memory allocators, by their nature can create allocation patterns and layouts that can be very sensitive thing like startup conditions, long-runtimes, or exact inter-thread execution sequences. This can cause items that in one run that get allocated near each other, can be allocated very distantly, or chaotically in the heap in another run, for instance. 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.
- victor106 4y ago> Doing this was possible because we sketched out all resource usage (network, disk, memory, CPU) in the design phase with back-of-the-envelope calculations. I wish all programs did this
- deleted 4y ago[deleted]
- SleepyMyroslav 4y agorant at fixed memory systems: 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.
- deleted 4y ago[deleted]
- habibur 4y ago> TigerBeetle is written in Zig 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.
- throwawaymaths 4y ago*can be. You can do more traditional memory patterns too in zig. There is also an allocator in stdlib that directly wraps C's malloc. Likewise, if you're writing a plugin for another software or FFI for a VM language, you can wrap their allocators (if they provide them).
- eatonphil 4y agoInterestingly enough, the first version of TigerBeetle (that still followed much of the same design decisions) was written in Node! :) https://github.com/tigerbeetledb/tigerbeetle/blob/main/docs/HISTORY.md https://github.com/tigerbeetledb/tigerbeetle/blob/main/docs/...
- jandrewrogers 4y agoAllocating all required memory during startup has been idiomatic for database architectures as long as I can remember. The obvious benefits to doing things this way are wide-ranging. 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.
- dilyevsky 4y agoNot just databases but really any kind of latency sensitive software especially with “realtime” requirements (e.g telecom gear)
- josephg 4y agoYep. After algorithmic improvements, tracking (and limiting) the use of malloc in a program can improve performance by an order of magnitude or more. Not only is allocating slow, but having data spread all over main memory is terrible for the CPU’s cache and branch predictor. 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.
- 4y ago
- tannhaeuser 4y agoWhat's so special about it? Static heap allocation (without malloc) was the norm with COBOL + ISAM; early SQL databases used eg ESQL/C with static or quasi-static allocation (by which I mean at most one malloc per field for the entire process runtime). Process-per-request was (and is) recommended practice if you value stability and security above all when using languages that don't have GC and/or have issues with memory fragmentation.
- felipelalli 4y agoI love/hate the bad humor of HN.
- qwertox 4y agoJust today I got presented an article in my "newsfeed" claiming that coroutines in C++ are the hottest thing right now in algorithmic trading, which I assume also relies on databases. 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-trading-c https://www.efinancialcareers.com/news/2022/10/algorithmic-t...
- pierrebai 4y agoOne of the first claim of the article is plainly false. Static allocation does not avoid use-after-free. It just avoids accessing freed memory. You can still have bugs and access dead data in those static arrays that are really dead object but your buggy code still references and access them. 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. And I know, because I've worked on program that did static initialization at startup, and they failed in just that way. I also did test the performance benefits: it was around 12%. So you do get some performances out of it, but the added complexity of having things fail out where in a normal program it would just chug along, having to deal with these failures and the usual have-to-roll your-own data structures or libraries is not worth 12%. Because, remember, if you go out of your way to have static allocations, that means all 3rd-party libraries have to do it too, otherwise the benefits is wasted. Is that worth 12%? IMO, no. 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.
- AdamProut 4y agoI'm not sure why this is being downvoted? Dividing up memory statically at startup/compile time has some nice benefits described in the article, but it also makes the database less flexible to changing workload requirements. For example, if a workload wants to do a big hash join that needs 90% of the memory at time X and then a big data load that needs most of the memory in a completely different sub system at time Y - its nice to be able to dynamically shift the memory around to match the workload. Doing static up front allocations seems to block this from happening, and that is maybe a fine trade-off for TigerBeetleDB based on the types of workloads they're optimizing for, but its definitely a valid dis-advantage of their approach.
- 0xbadcafebee 4y agoFor the first 5 years that I wrote C, I never used dynamic memory. (It was a hobby.) Later I found that dynamic memory allowed me to perform more operations. By only allocating what I needed, I could process more operations in the same amount of memory. I tripled the amount of operations due to not needing to restrict myself to an arbitrary size. 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.
- polio 4y agoIt seems analogous to fractional reserve banking and the free economic performance it enables by leaning on a mostly reliable statistic about empirical peak concurrent usage of a shared resource.
- newZWhoDis 4y ago>The kernel lies to those programs 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.
- ikiris 4y agowelcome to the tragedy of the commons.
- _448 4y agoIn one of the projects to port a game to Linux phone with 16MB I had to allocate all the memory upfront for performance reason to avoid memory allocation/deallocation overhead and fragmentation. Fun times ;)
- stevefan1999 4y agowhat about arena allocators?
- ayende 4y agoYou actually are doing dynamic memory allocations, you are just not allocating from the operating system. A quick look shows how this is done: https://github.com/tigerbeetledb/tigerbeetle/blob/91a105875ce427d3a89fc09678819f0826ac7b78/src/vsr.zig#L819 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.