sled and rio
Neely, Tyler
sled is an embedded database that takes advantage of modern lock-free indexing and flash-friendly storage. rio is a pure-rust io_uring library unlocking the linux kernel's new asynchronous IO interface. This short talk will cover techniques that have been used to take advantage of modern hardware and kernels while optimizing for long term developer happiness in a complex, correctness-critical Rust codebase.
 Hey folks, so this is going to be a talk about two projects that I've been working on. One's a pretty new one that I've basically started a couple months ago, and that's going to be around IOU ring, which is a new kernel interface that if you're working on Linux, it's basically going to completely replace all of your thread pool based IOU as well as E-Poll. Testing, testing, test, test, test, test, test, test, test. Let me know if I should just go and scream or I can test, test, test, test, test, test, test, test, test. Cool. Okay. Is there any amplification? Can the folks in the back hear me okay? Okay. Cool. If you have trouble hearing me, please go like this and I'll adjust. Thank you. Okay. So the recent project I've been working on is called Rio, and that's a IOU ring library. IOU ring is extremely exciting. It's like, in my opinion, it's the most exciting thing that's been happening in the Linux kernel for like the last 10 years. And I will be applying it to my database Sled, which I've been working on for the last four years, and Sled is an embedded database for the Rust community. And let's get started. Well, so who am I? I've been basically working on stateful systems in the Rust ecosystem for the last six years or so. My first Rust project was the ROXDB bindings that are now like everybody's using it and like every blockchain project. It's kind of scary. But be careful of what you build. You never know how it's going to be used. Sometimes these things are good. Just be careful about market externalities. I previously worked at a bunch of social media companies and infrastructure companies in the U.S. working on container orchestrators, distributed systems, distributed databases, some serverless infrastructure, data flow things. I basically like low level infrastructure and building things that other people use to build whatever they want with. And yeah, for fun, I also like to build and distribute databases. For fun, also I teach Rust workshops. I've taught workshops at Mozilla, Microsoft, BMW. If you need a Rust workshop, I'm happy to give you a three day workshop or a specialized one, beginner or advanced. And I'm unemployable. So. I like databases because they basically involve working on all these kind of like low level problems where if you have managers who hired you to do them, they're unlikely to tell you how to do your job. So I like front end work also, but if you have it for your job, there's a lot of people who kind of like tell you what to do. I think I kind of got driven to distributed systems and databases because when you get into these weird areas, there's just fewer people that tell you how to do your job. And that appeals to me. And I got hooked. So some interesting techniques in database engineering, lock free programming. It's like juggling chainsaws, basically having shared mutable state that you don't use mutexes to regulate. Lots of like replication, consensus, distributed systems, stuff, lots of race conditions that you have to test for. Yeah, you have to do a lot of correctness testing. We can only build things that we can actually test the important characteristics about. So that also has a lot of restrictions on how we architect our systems. And I also am pretty interested in self tuning systems. We basically, the more that people have to configure a system, the more likely they are to misconfigure the system. And I love tuning things a lot. So databases kind of are all of these things combined. And that's what brought me here. So I started this project slide about four years ago to basically have a personal project where I could just apply all these things that I like thinking about and to basically implement these papers that I was reading. It's a pretty simple API. It basically looks like a B-tree map, except you never need a mutable reference to it. Yeah, you can open it as if it were a file. You can insert things. You can get things. You can iterate, remove things when you drop it at F-syncs. And it also F-syncs periodically. And yeah, it basically acts like a B-tree map from bytes to bytes. And it also handles off the multi-threaded issues and reliability issues if you crash. So it basically is just like a better map. I think that Rust is the best language for building databases in for a number of reasons. One that gets often overlooked. So I mean, everyone always talks about safety, like unsafety. But one of the ones that appeals to me as someone who is more than willing to build unsafe things is the fact that Rust has a lot more information at compile time than C and C++ around aliasing information. Now this is something that actually will allow Rust to approach Fortran performance over time as we unlock more and more LLVM features around this. But I mean, there's a reason why we're still using 50-year-old Fortran libraries in all of our linear algebra libraries. So it's because Fortran is able to optimize much more aggressively in C and C++. It's difficult to get that kind of performance. Rust is able to get the same kinds of optimizations as we can get in Fortran. So strictly from a performance standpoint, Rust is a superior tool. Correctness, blah, blah, blah. Everyone always talks about unsafety. I write a lot of unsafe code. I build lock-free databases. I try to do it in a responsible way with like, Miri where possible and lots of other tools. But anyway, so I can still use the C and C++ performance and debugging tools. And another big thing though is I can just accept other people's code really cheaply, whereas if I'm working in a C and C++ code base, it's like a lot more energy trying to review the code because you have to have a lot more things in your mind. You have to familiarize yourself with more of the code that they're touching. And it's just much more expensive to accept code from other people. So as a one-person project, essentially with a few awesome contributors, like Ivan over there, it's a really nice language to not spend too much energy doing the normal maintenance stuff. Okay. Some other things about Sled. It's pretty fast to compile. When you want to just have a database, you don't want to like bring in a dependency and then have like hundreds of new dependencies that slow down your project. So it's like, it's pretty small. It compiles pretty quickly and it should just let you solve the database problems without too much fuss. One thing that has been really critical, so it's good that there was a profiling talk right before this. I lean really heavily into different kinds of profiling, but when I build things, I like to build profilers into the systems so that I can tell, I can basically trace like where is this big number coming from? I can kind of see through the system where things are starting to slow down, where bottlenecks appear. When I do changes in my code, I can see how it affects pretty much the whole stack. This will work on any system. It doesn't rely on Perf or anything and it can be compiled. It can be turned off through a compile time flag. So this is like a technique that if you're building performance critical systems, just by having a profiler built into it, it really, it's a wonderful thing to give yourself. I also work a lot with flame graphs. I wrote a tool that's available here basically to make flame graphs easier to use and you don't have to mess with Perl scripts or anything and it works pretty well. So if you do a lot of flame graph stuff, this is a very nice tool for using. You can basically just type flame graph, my workload, and it'll just spit something out like this. Anyway, how fast is it? Very fast. You're 17 million operations per second when you're doing a 95% read, 5% write workload, which is like somewhat representative of most transactional workloads. So it's very fast, but it's definitely still beta. So don't store your primary data in it yet. There's like an SRE proverb, never use a database that's less than five years old. You will always regret this decision no matter what. So lucky for you, Sled turns five this year. This is an exciting year for the project. So now is when things are really starting to be more and more productionized and now is when I'm starting to get on stages and telling people about it because the next year is really exciting. Cool. It has a work. Basically it has a lock-free index that maps from keys to the locations on disk or memory. So this is how we look things up. It's based on the Microsoft BW tree. Loosely. It has a page cache that translates things in memory into the on-disk representation. Also lock-free and based on another Microsoft project called Lama. It uses log structure to storage that plays very nicely with modern flash based on Sprite LFS, which is like a pretty ancient log structured file system, but it works pretty well because it basically just gives us a nice clean framework for doing garbage collection over segments. And we tend to just write large segments at a time. And of course we use IOU ring for writing these huge buffers. And this is going to be the second half of this. I'll talk about this in much more detail. And this is also exported as its own crate, R-A-O. I squatted that for like six years. And only now can I actually have a really good use case for it. I'm very excited to be publishing this. And we also have the cache based on windowed tiny L-FU, which is basically what all of the Java ecosystem is relying on for all their high performance caching needs. Any database that's written in Java is going to be using the caffeine library for the most part. And this is a technique that they rely on. This will be soon exported as the Bearkind crate. So we need to avoid blocking wherever possible because we want to support lots of threads. Threads cannot, if you just want to read some things, ideally you shouldn't have to acquire a reader lock before you access that because maybe there's a bunch of writers coming in at the same time and readers. I won't focus too much on this because this is basically like a 20 minute lightning talk. But the important thing is that anything should just be able to do what it wants to do without blocking. Otherwise, yeah, you're going to start seeing huge latency spikes and these will backlash through your system. So in order to set a value to any key, we first find, so it's organized as a tree structure. We go from the root node to the responsible leaf and then we mutate that leaf. But it's important how we do this because it cannot be blocking. So yeah, we don't want latency. That's bad. So we use a technique called RCU, read copy update. This is a technique that gets used all over the place in our kernels. The high level idea of what happens here is we read an atomic pointer. We make a local copy of the data that it points to. We change it in the way that represents our mutation. And then we attempt to install our mutation by using an atomic compare and swap operation on that atomic pointer. If we fail, we basically retry and go back to one. But if we succeed, at some point we want to then destroy that data. And the way that we do that in a way that's safe is by using the cross beam epoch crate. So the real problem here is if we immediately did a free of the data that we just basically made inaccessible, it's possible that other threads still had a reference to it. So we have to delay the destruction of that data until all threads that might have witnessed the data have finished their work. And that's what we use cross beam epoch for. So readers don't wait for writers. They just read that atomic pointer and get their data. And writers proceed optimistically. They just read, copy, update. And if they fail, they retry. But the trade off here is that instead of taking out a mutex, we just do it anyway. Because the bet that we're making here is that we have to retry less often than the price that we would pay for acquiring a mutex on every update. So if we have to start retrying a lot, then it makes sense to actually dynamically start taking out a mutex. And we can actually detect this at runtime dynamically. Like we can measure how often we experience contention and only start acquiring mutex's for rights when we're in a high contention area. So this is an example of auto tuning systems. You can basically measure contention as you experience it, switch over to using locks when they prevent contention or when they prevent wasted work. But usually just proceed optimistically and it goes really fast. However, this is just the in memory part of this. We're building a database and ideally the things that we do in memory are mapped to things on disk. The key constraint here being the ordering in memory has to map the ordering on disk. So if we have a bunch of threads doing read copy update, and then after they do the read copy update, they log to disk, it's possible to have a race condition here. Imagine one thread tries to delete a key and another thread tries to change its value. Let's say that the delete should happen before the mutation and the deletion gets through here, it deletes the old value, and then the mutation does the same thing and installs a new value. But then there's a race condition here where they log their updates out of order. If we then crash and then recover the database, even though we mutated things in one order in memory, we recover something that no longer has the data. That's data loss. So we basically can't have this. So how do we make the things on disk map in memory, even though we're not using any locks and we're basically, yeah, all this has to be lock free, but we still have to have our order on disk map the order in memory. So what we do is we use a special type of log reservation. So we try to reserve a slot at the end of the log that can later on either be canceled or filled in with data. And the important part here is that that reservation at the tip of the log happens after we did our read, but before we did our compare and swap operation. Later on, when we know if our compare and swap failed or succeeded, if it failed, we basically can fill that conditional log reservation in with like zeros. But if our compare and swap succeeded, it means that the log reservation also happened at a point that is linearizable. And at that point, we can actually fill in the mutation on disk such that it matches the order in memory. So even though we don't have any locks, we're still able to basically have things lined up. And this is a really interesting technique that you can use for basically linearizing all kinds of things without locks. You basically have like some conditional slot here that gets taken out between the read and the operation that's actually installing a new version. If that operation succeeds, you do the conditional thing. So Sled also supports reactive subscription. And basically the way that that works is it also takes out like a subscriber, a possible subscription slot here, and it only actually fills it in after the compare and swap. So this is how we keep things on disk matched up within memory. Cool. How do we get fast IO? One of the main things is we just write things eight megabytes at a time. All writes are non-blocking, even though our write functions are not marked as async functions, they're async. They basically just queue things up into an eight megabyte buffer, and later on we write the whole thing at once. We also support out-of-order writes. There's no head-of-line blocking. At recovery time, we figure out the right order. And of course, we use IOU ring, which I'll start talking about now. So IOU ring is basically an interface for fully asynchronous communication with the kernel. What we're used to before this is we have to do a sys call. Anytime we want to do like a read or write or an e-pull, the kernel will basically, you know, we're basically going to need to do a lot more context switches, and people have already talked at length about some of the reasons why we might want to avoid these. So I won't go too much into it. But how did IOU ring actually come about? It actually started with a much more modest goal, which was to basically improve the old AIO interface. Linux actually already had async disk operations, but it was very restricted. It only worked for files that were open in O-Direct mode, which many databases did do, but other people tend not to want to use O-Direct. O-Direct basically skips the operating system's page cache. And so you don't have to pay the costs of the page cache, but then you don't get your reads cached in memory. And you also, importantly, you have to do all of your IOU operations based on the disk's block size. So most people don't want to do all of their reads and writes aligned to 512 byte blocks. It's a lot of effort to add to everybody's program. The kernel does this for you under the hood, but you had to do this if you wanted to use AIO. The effect was nobody actually used AIO. Everyone just used the red pools that would do blocking IOU under the hood, exposing an async interface. But that's much more work and much slower. So IOU ring started to just, or began initially as an effort just to replace that. But in effect, it's much more ambitious. So in the first version of IOU ring, we've got basically read, like vectored reads, vectored writes, f-syncs, the ability to work with like poll FD, or yeah, like event FD devices. However, so the very top row is the Linux version. So 5.1 came out with support for like the basic file operations. But as you can see over time, we're starting to get many more file operations as well. And also network. So connect, accept, we can send message, receive message. And this is the reason why it's also going to start replacing E-Poll. Because we're using E-Poll for our network IOU. But this is going to let us just start submitting operations to the kernel. And it's going to like execute them asynchronously, and it has a number of advantages that I'm going to cover now. What's the time, by the way? Cool. So the way it works is with two ring buffers. There's a submission ring buffer where we basically just load up this ring buffer with those events that we saw before. So we load up the submission ring buffer with one of these events. They have different arguments that you can pass as well, depending on the operation. F-Sync just requires a file descriptor that you pass to it. But read, like a vectored read would require a buffer to put the read into, as well as like a where in the file you want to read from, et cetera. So the submission queue is just those operations that you want to submit. They get executed out of order. And this is a way to dramatically increase the throughput. And then the result of those operations gets put into a completion ring buffer. Interestingly, after you set this thing up, you can run it with zero syscalls. And there's a mode that you can configure it with called sqpoll. And this basically creates a kernel thread that will pull the submission queue. Looking at those events that you just submitted or operations that you just submitted, execute them asynchronously, and then fill them into the completion queue, which you can also read without doing any syscalls. This is mmapped and shared between user space and kernel space. So we can do all of those operations now with zero syscalls. This is increasingly important in the post-KPTI, like Specter Meltdown mitigation world, where our syscalls became a lot slower, especially if you're doing a ton of them. Now we don't need to do any of them. Cool. The real create is pretty simple. You just create a U-Ring instance. You write at, you pass a buffer, file descriptor. An important API design issue here. Is it async or does it work with threads? This is the first question pretty much anyone asks when they see a Rust library. Can I use this thing at all? Or would I have to completely change my architecture if I wanted to take advantage of it? Rio doesn't force you to make a decision. It returns a concrete object that just happens to implement future. So you can either just call weight on the completion, so you can basically send off a bunch of events from a thread and then basically batch up these completions and then later on weight on them, just like you would do if you were spinning up a bunch of threads that you then join on later. So you can do a similar kind of pattern with this blocking weight method. Or you can just data weight it because it's also a future. By returning concrete futures that just work with both, we don't force as many API constraints on our users. I think everyone's kind of tired of choosing, or of seeing libraries that they wish they could use, but it just targets the other side of the world. We can target both. We can also do like accepts here. So this is just a simple proxy that, well, in this case, it's just an echo service really because we're doing this proxy method for the same stream. We read a bunch of bytes and then we write the same thing right back. So this is just a simple example of how you might describe an echo service. You can also do this in other ways, but it works with network stuff. Operations are executed out of order by default. However, you can chain them together by setting a flag that links them. And what this does is it basically allows you to specify that the kernel should not begin the next operation until the previous one finished. So this lets you do things like submit a bunch of writes to a file and then link that to an F-sync. So you do all these things. You submit them all to the kernel and the kernel will just do all of these writes. And after the writes finish, it will do an F-sync. And then you really only have to look at the completion for that F-sync. And you just basically submitted a topology of I-O operations at the kernel. And it just tells you after they're all done. It's a really beautiful, low interaction way to communicate with the kernel. You can also do things like chain a connect call to some service, send a bunch of bytes to it, and then chain that to a receive. And just by using these links, you just submit a whole client operation to the kernel. And then you just get the completion back when it has sent you a response. It's really beautiful. You can also attach timeouts to all of these. So if you're working on top of a kernel, programming languages are effectively just DSLs for orchestrating syscalls. So, you know, and this is, you know, a program to take input and, you know, and they're useful based on their output if you're only looking at the program rather than its effect on your life. But really, the way that, like, as long as we're not, like, working in the embedded world, even in the embedded world to some extent, if you're using, like, a real time operating system, we are using programming languages to interact with the world around us. And part of the reason why I'm so excited about I-O U-ring is because it's, like, totally changing this conversation. We're able to just kind of, like, submit topologies of interesting dependencies to the kernel. The kernel just does them, and then we find out later on how they worked. And this is sort of, like, kind of, like, separating user space into, like, control plane, kernel's data plane. And it's, I don't know, I'm just really, really, really excited about this whole change. It's really cool. Interestingly, one possible direction this could evolve in is by integrating BPF as a way to basically execute a little bit of logic in between chain calls. For example, we can accept a socket, which, you know, we don't know what the file descriptor of that new client is going to be yet, but we can use BPF to basically then do a read on the same file descriptor and then write some stuff back to it. So with BPF, we're going to be doing even more interesting stuff without having to do an interaction between user space and kernel space. It's an amazing system. Okay. Lots of people have been getting extremely good results with it. Everybody loves it. Anyone who's doing extremely high-performance systems right now, they are getting ridiculously cool results. And yeah, if you're interested, try out Rio for IOU ring. If you have a Linux kernel 5.1 and up, you can start to use some of the operations and sled for everybody if you have to store some things. So these are the projects that I'm excited to be talking about today. Yeah, we have some cool results I already talked about. We want to do a lot more things. If you want to help out, I'm on GitHub sponsors. As I said, I'm unemployable, so I'm really trying to just work on open source right now through like donations. I'm trying to still make useful things for other people. Also if you want to talk about distributed systems, come on our Discord channel. It's actually pretty active. And yeah, if you're interested in helping out, I love talking about this with other people, so come and join us. I also do rest trainings. Thanks. Thank you.
 Hey folks, so this is going to be a talk about two projects that I've been working on.  One's a pretty new one that I've basically started a couple months ago, and that's going  to be around IOU ring, which is a new kernel interface that if you're working on Linux,  it's basically going to completely replace all of your thread pool based IOU as well  as E-Poll.  Testing, testing, test, test, test, test, test, test, test.  Let me know if I should just go and scream or I can test, test, test, test, test, test,  test, test, test.  Cool.  Okay.  Is there any amplification?  Can the folks in the back hear me okay?  Okay.  Cool.  If you have trouble hearing me, please go like this and I'll adjust.  Thank you.  Okay.  So the recent project I've been working on is called Rio, and that's a IOU ring library.  IOU ring is extremely exciting.  It's like, in my opinion, it's the most exciting thing that's been happening in the Linux kernel  for like the last 10 years.  And I will be applying it to my database Sled, which I've been working on for the last four  years, and Sled is an embedded database for the Rust community.  And let's get started.  Well, so who am I?  I've been basically working on stateful systems in the Rust ecosystem for the last six years  or so.  My first Rust project was the ROXDB bindings that are now like everybody's using it and  like every blockchain project.  It's kind of scary.  But be careful of what you build.  You never know how it's going to be used.  Sometimes these things are good.  Just be careful about market externalities.  I previously worked at a bunch of social media companies and infrastructure companies in  the U.S. working on container orchestrators, distributed systems, distributed databases,  some serverless infrastructure, data flow things.  I basically like low level infrastructure and building things that other people use to  build whatever they want with.  And yeah, for fun, I also like to build and distribute databases.  For fun, also I teach Rust workshops.  I've taught workshops at Mozilla, Microsoft, BMW.  If you need a Rust workshop, I'm happy to give you a three day workshop or a specialized  one, beginner or advanced.  And I'm unemployable.  So.  I like databases because they basically involve working on all these kind of like low level  problems where if you have managers who hired you to do them, they're unlikely to tell you  how to do your job.  So I like front end work also, but if you have it for your job, there's a lot of people  who kind of like tell you what to do.  I think I kind of got driven to distributed systems and databases because when you get  into these weird areas, there's just fewer people that tell you how to do your job.  And that appeals to me.  And I got hooked.  So some interesting techniques in database engineering, lock free programming.  It's like juggling chainsaws, basically having shared mutable state that you don't use mutexes  to regulate.  Lots of like replication, consensus, distributed systems, stuff, lots of race conditions that  you have to test for.  Yeah, you have to do a lot of correctness testing.  We can only build things that we can actually test the important characteristics about.  So that also has a lot of restrictions on how we architect our systems.  And I also am pretty interested in self tuning systems.  We basically, the more that people have to configure a system, the more likely they are  to misconfigure the system.  And I love tuning things a lot.  So databases kind of are all of these things combined.  And that's what brought me here.  So I started this project slide about four years ago to basically have a personal project  where I could just apply all these things that I like thinking about and to basically  implement these papers that I was reading.  It's a pretty simple API.  It basically looks like a B-tree map, except you never need a mutable reference to it.  Yeah, you can open it as if it were a file.  You can insert things.  You can get things.  You can iterate, remove things when you drop it at F-syncs.  And it also F-syncs periodically.  And yeah, it basically acts like a B-tree map from bytes to bytes.  And it also handles off the multi-threaded issues and reliability issues if you crash.  So it basically is just like a better map.  I think that Rust is the best language for building databases in for a number of reasons.  One that gets often overlooked.  So I mean, everyone always talks about safety, like unsafety.  But one of the ones that appeals to me as someone who is more than willing to build  unsafe things is the fact that Rust has a lot more information at compile time than  C and C++ around aliasing information.  Now this is something that actually will allow Rust to approach Fortran performance over  time as we unlock more and more LLVM features around this.  But I mean, there's a reason why we're still using 50-year-old Fortran libraries in all  of our linear algebra libraries.  So it's because Fortran is able to optimize much more aggressively in C and C++.  It's difficult to get that kind of performance.  Rust is able to get the same kinds of optimizations as we can get in Fortran.  So strictly from a performance standpoint, Rust is a superior tool.  Correctness, blah, blah, blah.  Everyone always talks about unsafety.  I write a lot of unsafe code.  I build lock-free databases.  I try to do it in a responsible way with like, Miri where possible and lots of other tools.  But anyway, so I can still use the C and C++ performance and debugging tools.  And another big thing though is I can just accept other people's code really cheaply,  whereas if I'm working in a C and C++ code base, it's like a lot more energy trying to  review the code because you have to have a lot more things in your mind.  You have to familiarize yourself with more of the code that they're touching.  And it's just much more expensive to accept code from other people.  So as a one-person project, essentially with a few awesome contributors, like Ivan over  there, it's a really nice language to not spend too much energy doing the normal maintenance  stuff.  Okay.  Some other things about Sled.  It's pretty fast to compile.  When you want to just have a database, you don't want to like bring in a dependency and  then have like hundreds of new dependencies that slow down your project.  So it's like, it's pretty small.  It compiles pretty quickly and it should just let you solve the database problems without  too much fuss.  One thing that has been really critical, so it's good that there was a profiling talk  right before this.  I lean really heavily into different kinds of profiling, but when I build things, I  like to build profilers into the systems so that I can tell, I can basically trace like  where is this big number coming from?  I can kind of see through the system where things are starting to slow down, where bottlenecks  appear.  When I do changes in my code, I can see how it affects pretty much the whole stack.  This will work on any system.  It doesn't rely on Perf or anything and it can be compiled.  It can be turned off through a compile time flag.  So this is like a technique that if you're building performance critical systems, just  by having a profiler built into it, it really, it's a wonderful thing to give yourself.  I also work a lot with flame graphs.  I wrote a tool that's available here basically to make flame graphs easier to use and you  don't have to mess with Perl scripts or anything and it works pretty well.  So if you do a lot of flame graph stuff, this is a very nice tool for using.  You can basically just type flame graph, my workload, and it'll just spit something out  like this.  Anyway, how fast is it?  Very fast.  You're 17 million operations per second when you're doing a 95% read, 5% write workload,  which is like somewhat representative of most transactional workloads.  So it's very fast, but it's definitely still beta.  So don't store your primary data in it yet.  There's like an SRE proverb, never use a database that's less than five years old.  You will always regret this decision no matter what.  So lucky for you, Sled turns five this year.  This is an exciting year for the project.  So now is when things are really starting to be more and more productionized and now  is when I'm starting to get on stages and telling people about it because the next year  is really exciting.  Cool.  It has a work.  Basically it has a lock-free index that maps from keys to the locations on disk or memory.  So this is how we look things up.  It's based on the Microsoft BW tree.  Loosely.  It has a page cache that translates things in memory into the on-disk representation.  Also lock-free and based on another Microsoft project called Lama.  It uses log structure to storage that plays very nicely with modern flash based on Sprite  LFS, which is like a pretty ancient log structured file system, but it works pretty well because  it basically just gives us a nice clean framework for doing garbage collection over segments.  And we tend to just write large segments at a time.  And of course we use IOU ring for writing these huge buffers.  And this is going to be the second half of this.  I'll talk about this in much more detail.  And this is also exported as its own crate, R-A-O.  I squatted that for like six years.  And only now can I actually have a really good use case for it.  I'm very excited to be publishing this.  And we also have the cache based on windowed tiny L-FU, which is basically what all of the  Java ecosystem is relying on for all their high performance caching needs.  Any database that's written in Java is going to be using the caffeine library for the most  part.  And this is a technique that they rely on.  This will be soon exported as the Bearkind crate.  So we need to avoid blocking wherever possible because we want to support lots of threads.  Threads cannot, if you just want to read some things, ideally you shouldn't have to acquire  a reader lock before you access that because maybe there's a bunch of writers coming in  at the same time and readers.  I won't focus too much on this because this is basically like a 20 minute lightning talk.  But the important thing is that anything should just be able to do what it wants to do without  blocking.  Otherwise, yeah, you're going to start seeing huge latency spikes and these will backlash  through your system.  So in order to set a value to any key, we first find, so it's organized as a tree structure.  We go from the root node to the responsible leaf and then we mutate that leaf.  But it's important how we do this because it cannot be blocking.  So yeah, we don't want latency.  That's bad.  So we use a technique called RCU, read copy update.  This is a technique that gets used all over the place in our kernels.  The high level idea of what happens here is we read an atomic pointer.  We make a local copy of the data that it points to.  We change it in the way that represents our mutation.  And then we attempt to install our mutation by using an atomic compare and swap operation  on that atomic pointer.  If we fail, we basically retry and go back to one.  But if we succeed, at some point we want to then destroy that data.  And the way that we do that in a way that's safe is by using the cross beam epoch crate.  So the real problem here is if we immediately did a free of the data that we just basically  made inaccessible, it's possible that other threads still had a reference to it.  So we have to delay the destruction of that data until all threads that might have witnessed  the data have finished their work.  And that's what we use cross beam epoch for.  So readers don't wait for writers.  They just read that atomic pointer and get their data.  And writers proceed optimistically.  They just read, copy, update.  And if they fail, they retry.  But the trade off here is that instead of taking out a mutex, we just do it anyway.  Because the bet that we're making here is that we have to retry less often than the  price that we would pay for acquiring a mutex on every update.  So if we have to start retrying a lot, then it makes sense to actually dynamically start  taking out a mutex.  And we can actually detect this at runtime dynamically.  Like we can measure how often we experience contention and only start acquiring mutex's  for rights when we're in a high contention area.  So this is an example of auto tuning systems.  You can basically measure contention as you experience it, switch over to using locks when  they prevent contention or when they prevent wasted work.  But usually just proceed optimistically and it goes really fast.  However, this is just the in memory part of this.  We're building a database and ideally the things that we do in memory are mapped to  things on disk.  The key constraint here being the ordering in memory has to map the ordering on disk.  So if we have a bunch of threads doing read copy update, and then after they do the read  copy update, they log to disk, it's possible to have a race condition here.  Imagine one thread tries to delete a key and another thread tries to change its value.  Let's say that the delete should happen before the mutation and the deletion gets through  here, it deletes the old value, and then the mutation does the same thing and installs  a new value.  But then there's a race condition here where they log their updates out of order.  If we then crash and then recover the database, even though we mutated things in one order  in memory, we recover something that no longer has the data.  That's data loss.  So we basically can't have this.  So how do we make the things on disk map in memory, even though we're not using any  locks and we're basically, yeah, all this has to be lock free, but we still have to  have our order on disk map the order in memory.  So what we do is we use a special type of log reservation.  So we try to reserve a slot at the end of the log that can later on either be canceled  or filled in with data.  And the important part here is that that reservation at the tip of the log happens after we did  our read, but before we did our compare and swap operation.  Later on, when we know if our compare and swap failed or succeeded, if it failed, we  basically can fill that conditional log reservation in with like zeros.  But if our compare and swap succeeded, it means that the log reservation also happened  at a point that is linearizable.  And at that point, we can actually fill in the mutation on disk such that it matches  the order in memory.  So even though we don't have any locks, we're still able to basically have things lined  up.  And this is a really interesting technique that you can use for basically linearizing  all kinds of things without locks.  You basically have like some conditional slot here that gets taken out between the read  and the operation that's actually installing a new version.  If that operation succeeds, you do the conditional thing.  So Sled also supports reactive subscription.  And basically the way that that works is it also takes out like a subscriber, a possible  subscription slot here, and it only actually fills it in after the compare and swap.  So this is how we keep things on disk matched up within memory.  Cool.  How do we get fast IO?  One of the main things is we just write things eight megabytes at a time.  All writes are non-blocking, even though our write functions are not marked as async  functions, they're async.  They basically just queue things up into an eight megabyte buffer, and later on we write  the whole thing at once.  We also support out-of-order writes.  There's no head-of-line blocking.  At recovery time, we figure out the right order.  And of course, we use IOU ring, which I'll start talking about now.  So IOU ring is basically an interface for fully asynchronous communication with the  kernel.  What we're used to before this is we have to do a sys call.  Anytime we want to do like a read or write or an e-pull, the kernel will basically, you  know, we're basically going to need to do a lot more context switches, and people have  already talked at length about some of the reasons why we might want to avoid these.  So I won't go too much into it.  But how did IOU ring actually come about?  It actually started with a much more modest goal, which was to basically improve the old  AIO interface.  Linux actually already had async disk operations, but it was very restricted.  It only worked for files that were open in O-Direct mode, which many databases did do,  but other people tend not to want to use O-Direct.  O-Direct basically skips the operating system's page cache.  And so you don't have to pay the costs of the page cache, but then you don't get your  reads cached in memory.  And you also, importantly, you have to do all of your IOU operations based on the disk's  block size.  So most people don't want to do all of their reads and writes aligned to 512 byte blocks.  It's a lot of effort to add to everybody's program.  The kernel does this for you under the hood, but you had to do this if you wanted to use  AIO.  The effect was nobody actually used AIO.  Everyone just used the red pools that would do blocking IOU under the hood, exposing an  async interface.  But that's much more work and much slower.  So IOU ring started to just, or began initially as an effort just to replace that.  But in effect, it's much more ambitious.  So in the first version of IOU ring, we've got basically read, like vectored reads, vectored  writes, f-syncs, the ability to work with like poll FD, or yeah, like event FD devices.  However, so the very top row is the Linux version.  So 5.1 came out with support for like the basic file operations.  But as you can see over time, we're starting to get many more file operations as well.  And also network.  So connect, accept, we can send message, receive message.  And this is the reason why it's also going to start replacing E-Poll.  Because we're using E-Poll for our network IOU.  But this is going to let us just start submitting operations to the kernel.  And it's going to like execute them asynchronously, and it has a number of advantages that I'm  going to cover now.  What's the time, by the way?  Cool.  So the way it works is with two ring buffers.  There's a submission ring buffer where we basically just load up this ring buffer with  those events that we saw before.  So we load up the submission ring buffer with one of these events.  They have different arguments that you can pass as well, depending on the operation.  F-Sync just requires a file descriptor that you pass to it.  But read, like a vectored read would require a buffer to put the read into, as well as  like a where in the file you want to read from, et cetera.  So the submission queue is just those operations that you want to submit.  They get executed out of order.  And this is a way to dramatically increase the throughput.  And then the result of those operations gets put into a completion ring buffer.  Interestingly, after you set this thing up, you can run it with zero syscalls.  And there's a mode that you can configure it with called sqpoll.  And this basically creates a kernel thread that will pull the submission queue.  Looking at those events that you just submitted or operations that you just submitted, execute  them asynchronously, and then fill them into the completion queue, which you can also read  without doing any syscalls.  This is mmapped and shared between user space and kernel space.  So we can do all of those operations now with zero syscalls.  This is increasingly important in the post-KPTI, like Specter Meltdown mitigation world, where  our syscalls became a lot slower, especially if you're doing a ton of them.  Now we don't need to do any of them.  Cool.  The real create is pretty simple.  You just create a U-Ring instance.  You write at, you pass a buffer, file descriptor.  An important API design issue here.  Is it async or does it work with threads?  This is the first question pretty much anyone asks when they see a Rust library.  Can I use this thing at all?  Or would I have to completely change my architecture if I wanted to take advantage of it?  Rio doesn't force you to make a decision.  It returns a concrete object that just happens to implement future.  So you can either just call weight on the completion, so you can basically send off a bunch of  events from a thread and then basically batch up these completions and then later on weight  on them, just like you would do if you were spinning up a bunch of threads that you then  join on later.  So you can do a similar kind of pattern with this blocking weight method.  Or you can just data weight it because it's also a future.  By returning concrete futures that just work with both, we don't force as many API constraints  on our users.  I think everyone's kind of tired of choosing, or of seeing libraries that they wish they  could use, but it just targets the other side of the world.  We can target both.  We can also do like accepts here.  So this is just a simple proxy that, well, in this case, it's just an echo service really  because we're doing this proxy method for the same stream.  We read a bunch of bytes and then we write the same thing right back.  So this is just a simple example of how you might describe an echo service.  You can also do this in other ways, but it works with network stuff.  Operations are executed out of order by default.  However, you can chain them together by setting a flag that links them.  And what this does is it basically allows you to specify that the kernel should not  begin the next operation until the previous one finished.  So this lets you do things like submit a bunch of writes to a file and then link that to  an F-sync.  So you do all these things.  You submit them all to the kernel and the kernel will just do all of these writes.  And after the writes finish, it will do an F-sync.  And then you really only have to look at the completion for that F-sync.  And you just basically submitted a topology of I-O operations at the kernel.  And it just tells you after they're all done.  It's a really beautiful, low interaction way to communicate with the kernel.  You can also do things like chain a connect call to some service, send a bunch of bytes  to it, and then chain that to a receive.  And just by using these links, you just submit a whole client operation to the kernel.  And then you just get the completion back when it has sent you a response.  It's really beautiful.  You can also attach timeouts to all of these.  So if you're working on top of a kernel, programming languages are effectively just  DSLs for orchestrating syscalls.  So, you know, and this is, you know, a program to take input and, you know, and they're useful  based on their output if you're only looking at the program rather than its effect on your  life.  But really, the way that, like, as long as we're not, like, working in the embedded world,  even in the embedded world to some extent, if you're using, like, a real time operating  system, we are using programming languages to interact with the world around us.  And part of the reason why I'm so excited about I-O U-ring is because it's, like, totally  changing this conversation.  We're able to just kind of, like, submit topologies of interesting dependencies to the kernel.  The kernel just does them, and then we find out later on how they worked.  And this is sort of, like, kind of, like, separating user space into, like, control plane,  kernel's data plane.  And it's, I don't know, I'm just really, really, really excited about this whole change.  It's really cool.  Interestingly, one possible direction this could evolve in is by integrating BPF as a  way to basically execute a little bit of logic in between chain calls.  For example, we can accept a socket, which, you know, we don't know what the file descriptor  of that new client is going to be yet, but we can use BPF to basically then do a read  on the same file descriptor and then write some stuff back to it.  So with BPF, we're going to be doing even more interesting stuff without having to do  an interaction between user space and kernel space.  It's an amazing system.  Okay.  Lots of people have been getting extremely good results with it.  Everybody loves it.  Anyone who's doing extremely high-performance systems right now, they are getting ridiculously  cool results.  And yeah, if you're interested, try out Rio for IOU ring.  If you have a Linux kernel 5.1 and up, you can start to use some of the operations and  sled for everybody if you have to store some things.  So these are the projects that I'm excited to be talking about today.  Yeah, we have some cool results I already talked about.  We want to do a lot more things.  If you want to help out, I'm on GitHub sponsors.  As I said, I'm unemployable, so I'm really trying to just work on open source right now through  like donations.  I'm trying to still make useful things for other people.  Also if you want to talk about distributed systems, come on our Discord channel.  It's actually pretty active.  And yeah, if you're interested in helping out, I love talking about this with other people,  so come and join us.  I also do rest trainings.  Thanks.  Thank you.
rust_techniques_sled_0_131.png rust_techniques_sled_132_2147.png rust_techniques_sled_2148_3911.png rust_techniques_sled_3912_4763.png rust_techniques_sled_4764_5975.png rust_techniques_sled_5976_6251.png rust_techniques_sled_6252_7067.png rust_techniques_sled_7068_9695.png rust_techniques_sled_9696_10211.png rust_techniques_sled_10212_11291.png rust_techniques_sled_11292_11927.png rust_techniques_sled_11928_12479.png rust_techniques_sled_12480_12683.png rust_techniques_sled_12684_14987.png rust_techniques_sled_14988_16247.png rust_techniques_sled_16248_16307.png rust_techniques_sled_16308_16379.png rust_techniques_sled_16380_16439.png rust_techniques_sled_16440_17939.png rust_techniques_sled_17940_19415.png rust_techniques_sled_19416_21023.png rust_techniques_sled_21024_21275.png rust_techniques_sled_21276_24311.png rust_techniques_sled_24312_26591.png rust_techniques_sled_26592_26831.png rust_techniques_sled_26832_28175.png rust_techniques_sled_28176_28523.png rust_techniques_sled_28524_29075.png rust_techniques_sled_29076_29483.png rust_techniques_sled_29484_30659.png rust_techniques_sled_30660_32543.png rust_techniques_sled_32544_33275.png rust_techniques_sled_33276_33371.png rust_techniques_sled_33372_35939.png rust_techniques_sled_35940_37319.png rust_techniques_sled_37320_37583.png rust_techniques_sled_37584_37979.png rust_techniques_sled_37980_38087.png rust_techniques_sled_38088_38759.png rust_techniques_sled_38760_39047.png rust_techniques_sled_39048_39186.png
Hey folks, so this is going to be a talk about two projects that I've been working on. One's a pretty new one that I've basically started a couple months ago, and that's going to be around IOU ring, which is a new kernel interface that if you're working on Linux, it's basically going to completely replace all of your thread pool based IOU as well as E-Poll. Testing, testing, test, test, test, test, test, test, test. Let me know if I should just go and scream or I can test, test, test, test, test, test, test, test, test. Cool. Okay. Is there any amplification? Can the folks in the back hear me okay? Okay. Cool. If you have trouble hearing me, please go like this and I'll adjust. Thank you. Okay. So the recent project I've been working on is called Rio, and that's a IOU ring library. IOU ring is extremely exciting. It's like, in my opinion, it's the most exciting thing that's been happening in the Linux kernel for like the last 10 years. And I will be applying it to my database Sled, which I've been working on for the last four years, and Sled is an embedded database for the Rust community. And let's get started. Well, so who am I? I've been basically working on stateful systems in the Rust ecosystem for the last six years or so. My first Rust project was the ROXDB bindings that are now like everybody's using it and like every blockchain project. It's kind of scary. But be careful of what you build. You never know how it's going to be used. Sometimes these things are good. Just be careful about market externalities. I previously worked at a bunch of social media companies and infrastructure companies in the U.S. working on container orchestrators, distributed systems, distributed databases, some serverless infrastructure, data flow things. I basically like low level infrastructure and building things that other people use to build whatever they want with. And yeah, for fun, I also like to build and distribute databases. For fun, also I teach Rust workshops. I've taught workshops at Mozilla, Microsoft, BMW. If you need a Rust workshop, I'm happy to give you a three day workshop or a specialized one, beginner or advanced. And I'm unemployable. So. I like databases because they basically involve working on all these kind of like low level problems where if you have managers who hired you to do them, they're unlikely to tell you how to do your job. So I like front end work also, but if you have it for your job, there's a lot of people who kind of like tell you what to do. I think I kind of got driven to distributed systems and databases because when you get into these weird areas, there's just fewer people that tell you how to do your job. And that appeals to me. And I got hooked. So some interesting techniques in database engineering, lock free programming. It's like juggling chainsaws, basically having shared mutable state that you don't use mutexes to regulate. Lots of like replication, consensus, distributed systems, stuff, lots of race conditions that you have to test for. Yeah, you have to do a lot of correctness testing. We can only build things that we can actually test the important characteristics about. So that also has a lot of restrictions on how we architect our systems. And I also am pretty interested in self tuning systems. We basically, the more that people have to configure a system, the more likely they are to misconfigure the system. And I love tuning things a lot. So databases kind of are all of these things combined. And that's what brought me here. So I started this project slide about four years ago to basically have a personal project where I could just apply all these things that I like thinking about and to basically implement these papers that I was reading. It's a pretty simple API. It basically looks like a B-tree map, except you never need a mutable reference to it. Yeah, you can open it as if it were a file. You can insert things. You can get things. You can iterate, remove things when you drop it at F-syncs. And it also F-syncs periodically. And yeah, it basically acts like a B-tree map from bytes to bytes. And it also handles off the multi-threaded issues and reliability issues if you crash. So it basically is just like a better map. I think that Rust is the best language for building databases in for a number of reasons. One that gets often overlooked. So I mean, everyone always talks about safety, like unsafety. But one of the ones that appeals to me as someone who is more than willing to build unsafe things is the fact that Rust has a lot more information at compile time than C and C++ around aliasing information. Now this is something that actually will allow Rust to approach Fortran performance over time as we unlock more and more LLVM features around this. But I mean, there's a reason why we're still using 50-year-old Fortran libraries in all of our linear algebra libraries. So it's because Fortran is able to optimize much more aggressively in C and C++. It's difficult to get that kind of performance. Rust is able to get the same kinds of optimizations as we can get in Fortran. So strictly from a performance standpoint, Rust is a superior tool. Correctness, blah, blah, blah. Everyone always talks about unsafety. I write a lot of unsafe code. I build lock-free databases. I try to do it in a responsible way with like, Miri where possible and lots of other tools. But anyway, so I can still use the C and C++ performance and debugging tools. And another big thing though is I can just accept other people's code really cheaply, whereas if I'm working in a C and C++ code base, it's like a lot more energy trying to review the code because you have to have a lot more things in your mind. You have to familiarize yourself with more of the code that they're touching. And it's just much more expensive to accept code from other people. So as a one-person project, essentially with a few awesome contributors, like Ivan over there, it's a really nice language to not spend too much energy doing the normal maintenance stuff. Okay. Some other things about Sled. It's pretty fast to compile. When you want to just have a database, you don't want to like bring in a dependency and then have like hundreds of new dependencies that slow down your project. So it's like, it's pretty small. It compiles pretty quickly and it should just let you solve the database problems without too much fuss. One thing that has been really critical, so it's good that there was a profiling talk right before this. I lean really heavily into different kinds of profiling, but when I build things, I like to build profilers into the systems so that I can tell, I can basically trace like where is this big number coming from? I can kind of see through the system where things are starting to slow down, where bottlenecks appear. When I do changes in my code, I can see how it affects pretty much the whole stack. This will work on any system. It doesn't rely on Perf or anything and it can be compiled. It can be turned off through a compile time flag. So this is like a technique that if you're building performance critical systems, just by having a profiler built into it, it really, it's a wonderful thing to give yourself. I also work a lot with flame graphs. I wrote a tool that's available here basically to make flame graphs easier to use and you don't have to mess with Perl scripts or anything and it works pretty well. So if you do a lot of flame graph stuff, this is a very nice tool for using. You can basically just type flame graph, my workload, and it'll just spit something out like this. Anyway, how fast is it? Very fast. You're 17 million operations per second when you're doing a 95% read, 5% write workload, which is like somewhat representative of most transactional workloads. So it's very fast, but it's definitely still beta. So don't store your primary data in it yet. There's like an SRE proverb, never use a database that's less than five years old. You will always regret this decision no matter what. So lucky for you, Sled turns five this year. This is an exciting year for the project. So now is when things are really starting to be more and more productionized and now is when I'm starting to get on stages and telling people about it because the next year is really exciting. Cool. It has a work. Basically it has a lock-free index that maps from keys to the locations on disk or memory. So this is how we look things up. It's based on the Microsoft BW tree. Loosely. It has a page cache that translates things in memory into the on-disk representation. Also lock-free and based on another Microsoft project called Lama. It uses log structure to storage that plays very nicely with modern flash based on Sprite LFS, which is like a pretty ancient log structured file system, but it works pretty well because it basically just gives us a nice clean framework for doing garbage collection over segments. And we tend to just write large segments at a time. And of course we use IOU ring for writing these huge buffers. And this is going to be the second half of this. I'll talk about this in much more detail. And this is also exported as its own crate, R-A-O. I squatted that for like six years. And only now can I actually have a really good use case for it. I'm very excited to be publishing this. And we also have the cache based on windowed tiny L-FU, which is basically what all of the Java ecosystem is relying on for all their high performance caching needs. Any database that's written in Java is going to be using the caffeine library for the most part. And this is a technique that they rely on. This will be soon exported as the Bearkind crate. So we need to avoid blocking wherever possible because we want to support lots of threads. Threads cannot, if you just want to read some things, ideally you shouldn't have to acquire a reader lock before you access that because maybe there's a bunch of writers coming in at the same time and readers. I won't focus too much on this because this is basically like a 20 minute lightning talk. But the important thing is that anything should just be able to do what it wants to do without blocking. Otherwise, yeah, you're going to start seeing huge latency spikes and these will backlash through your system. So in order to set a value to any key, we first find, so it's organized as a tree structure. We go from the root node to the responsible leaf and then we mutate that leaf. But it's important how we do this because it cannot be blocking. So yeah, we don't want latency. That's bad. So we use a technique called RCU, read copy update. This is a technique that gets used all over the place in our kernels. The high level idea of what happens here is we read an atomic pointer. We make a local copy of the data that it points to. We change it in the way that represents our mutation. And then we attempt to install our mutation by using an atomic compare and swap operation on that atomic pointer. If we fail, we basically retry and go back to one. But if we succeed, at some point we want to then destroy that data. And the way that we do that in a way that's safe is by using the cross beam epoch crate. So the real problem here is if we immediately did a free of the data that we just basically made inaccessible, it's possible that other threads still had a reference to it. So we have to delay the destruction of that data until all threads that might have witnessed the data have finished their work. And that's what we use cross beam epoch for. So readers don't wait for writers. They just read that atomic pointer and get their data. And writers proceed optimistically. They just read, copy, update. And if they fail, they retry. But the trade off here is that instead of taking out a mutex, we just do it anyway. Because the bet that we're making here is that we have to retry less often than the price that we would pay for acquiring a mutex on every update. So if we have to start retrying a lot, then it makes sense to actually dynamically start taking out a mutex. And we can actually detect this at runtime dynamically. Like we can measure how often we experience contention and only start acquiring mutex's for rights when we're in a high contention area. So this is an example of auto tuning systems. You can basically measure contention as you experience it, switch over to using locks when they prevent contention or when they prevent wasted work. But usually just proceed optimistically and it goes really fast. However, this is just the in memory part of this. We're building a database and ideally the things that we do in memory are mapped to things on disk. The key constraint here being the ordering in memory has to map the ordering on disk. So if we have a bunch of threads doing read copy update, and then after they do the read copy update, they log to disk, it's possible to have a race condition here. Imagine one thread tries to delete a key and another thread tries to change its value. Let's say that the delete should happen before the mutation and the deletion gets through here, it deletes the old value, and then the mutation does the same thing and installs a new value. But then there's a race condition here where they log their updates out of order. If we then crash and then recover the database, even though we mutated things in one order in memory, we recover something that no longer has the data. That's data loss. So we basically can't have this. So how do we make the things on disk map in memory, even though we're not using any locks and we're basically, yeah, all this has to be lock free, but we still have to have our order on disk map the order in memory. So what we do is we use a special type of log reservation. So we try to reserve a slot at the end of the log that can later on either be canceled or filled in with data. And the important part here is that that reservation at the tip of the log happens after we did our read, but before we did our compare and swap operation. Later on, when we know if our compare and swap failed or succeeded, if it failed, we basically can fill that conditional log reservation in with like zeros. But if our compare and swap succeeded, it means that the log reservation also happened at a point that is linearizable. And at that point, we can actually fill in the mutation on disk such that it matches the order in memory. So even though we don't have any locks, we're still able to basically have things lined up. And this is a really interesting technique that you can use for basically linearizing all kinds of things without locks. You basically have like some conditional slot here that gets taken out between the read and the operation that's actually installing a new version. If that operation succeeds, you do the conditional thing. So Sled also supports reactive subscription. And basically the way that that works is it also takes out like a subscriber, a possible subscription slot here, and it only actually fills it in after the compare and swap. So this is how we keep things on disk matched up within memory. Cool. How do we get fast IO? One of the main things is we just write things eight megabytes at a time. All writes are non-blocking, even though our write functions are not marked as async functions, they're async. They basically just queue things up into an eight megabyte buffer, and later on we write the whole thing at once. We also support out-of-order writes. There's no head-of-line blocking. At recovery time, we figure out the right order. And of course, we use IOU ring, which I'll start talking about now. So IOU ring is basically an interface for fully asynchronous communication with the kernel. What we're used to before this is we have to do a sys call. Anytime we want to do like a read or write or an e-pull, the kernel will basically, you know, we're basically going to need to do a lot more context switches, and people have already talked at length about some of the reasons why we might want to avoid these. So I won't go too much into it. But how did IOU ring actually come about? It actually started with a much more modest goal, which was to basically improve the old AIO interface. Linux actually already had async disk operations, but it was very restricted. It only worked for files that were open in O-Direct mode, which many databases did do, but other people tend not to want to use O-Direct. O-Direct basically skips the operating system's page cache. And so you don't have to pay the costs of the page cache, but then you don't get your reads cached in memory. And you also, importantly, you have to do all of your IOU operations based on the disk's block size. So most people don't want to do all of their reads and writes aligned to 512 byte blocks. It's a lot of effort to add to everybody's program. The kernel does this for you under the hood, but you had to do this if you wanted to use AIO. The effect was nobody actually used AIO. Everyone just used the red pools that would do blocking IOU under the hood, exposing an async interface. But that's much more work and much slower. So IOU ring started to just, or began initially as an effort just to replace that. But in effect, it's much more ambitious. So in the first version of IOU ring, we've got basically read, like vectored reads, vectored writes, f-syncs, the ability to work with like poll FD, or yeah, like event FD devices. However, so the very top row is the Linux version. So 5.1 came out with support for like the basic file operations. But as you can see over time, we're starting to get many more file operations as well. And also network. So connect, accept, we can send message, receive message. And this is the reason why it's also going to start replacing E-Poll. Because we're using E-Poll for our network IOU. But this is going to let us just start submitting operations to the kernel. And it's going to like execute them asynchronously, and it has a number of advantages that I'm going to cover now. What's the time, by the way? Cool. So the way it works is with two ring buffers. There's a submission ring buffer where we basically just load up this ring buffer with those events that we saw before. So we load up the submission ring buffer with one of these events. They have different arguments that you can pass as well, depending on the operation. F-Sync just requires a file descriptor that you pass to it. But read, like a vectored read would require a buffer to put the read into, as well as like a where in the file you want to read from, et cetera. So the submission queue is just those operations that you want to submit. They get executed out of order. And this is a way to dramatically increase the throughput. And then the result of those operations gets put into a completion ring buffer. Interestingly, after you set this thing up, you can run it with zero syscalls. And there's a mode that you can configure it with called sqpoll. And this basically creates a kernel thread that will pull the submission queue. Looking at those events that you just submitted or operations that you just submitted, execute them asynchronously, and then fill them into the completion queue, which you can also read without doing any syscalls. This is mmapped and shared between user space and kernel space. So we can do all of those operations now with zero syscalls. This is increasingly important in the post-KPTI, like Specter Meltdown mitigation world, where our syscalls became a lot slower, especially if you're doing a ton of them. Now we don't need to do any of them. Cool. The real create is pretty simple. You just create a U-Ring instance. You write at, you pass a buffer, file descriptor. An important API design issue here. Is it async or does it work with threads? This is the first question pretty much anyone asks when they see a Rust library. Can I use this thing at all? Or would I have to completely change my architecture if I wanted to take advantage of it? Rio doesn't force you to make a decision. It returns a concrete object that just happens to implement future. So you can either just call weight on the completion, so you can basically send off a bunch of events from a thread and then basically batch up these completions and then later on weight on them, just like you would do if you were spinning up a bunch of threads that you then join on later. So you can do a similar kind of pattern with this blocking weight method. Or you can just data weight it because it's also a future. By returning concrete futures that just work with both, we don't force as many API constraints on our users. I think everyone's kind of tired of choosing, or of seeing libraries that they wish they could use, but it just targets the other side of the world. We can target both. We can also do like accepts here. So this is just a simple proxy that, well, in this case, it's just an echo service really because we're doing this proxy method for the same stream. We read a bunch of bytes and then we write the same thing right back. So this is just a simple example of how you might describe an echo service. You can also do this in other ways, but it works with network stuff. Operations are executed out of order by default. However, you can chain them together by setting a flag that links them. And what this does is it basically allows you to specify that the kernel should not begin the next operation until the previous one finished. So this lets you do things like submit a bunch of writes to a file and then link that to an F-sync. So you do all these things. You submit them all to the kernel and the kernel will just do all of these writes. And after the writes finish, it will do an F-sync. And then you really only have to look at the completion for that F-sync. And you just basically submitted a topology of I-O operations at the kernel. And it just tells you after they're all done. It's a really beautiful, low interaction way to communicate with the kernel. You can also do things like chain a connect call to some service, send a bunch of bytes to it, and then chain that to a receive. And just by using these links, you just submit a whole client operation to the kernel. And then you just get the completion back when it has sent you a response. It's really beautiful. You can also attach timeouts to all of these. So if you're working on top of a kernel, programming languages are effectively just DSLs for orchestrating syscalls. So, you know, and this is, you know, a program to take input and, you know, and they're useful based on their output if you're only looking at the program rather than its effect on your life. But really, the way that, like, as long as we're not, like, working in the embedded world, even in the embedded world to some extent, if you're using, like, a real time operating system, we are using programming languages to interact with the world around us. And part of the reason why I'm so excited about I-O U-ring is because it's, like, totally changing this conversation. We're able to just kind of, like, submit topologies of interesting dependencies to the kernel. The kernel just does them, and then we find out later on how they worked. And this is sort of, like, kind of, like, separating user space into, like, control plane, kernel's data plane. And it's, I don't know, I'm just really, really, really excited about this whole change. It's really cool. Interestingly, one possible direction this could evolve in is by integrating BPF as a way to basically execute a little bit of logic in between chain calls. For example, we can accept a socket, which, you know, we don't know what the file descriptor of that new client is going to be yet, but we can use BPF to basically then do a read on the same file descriptor and then write some stuff back to it. So with BPF, we're going to be doing even more interesting stuff without having to do an interaction between user space and kernel space. It's an amazing system. Okay. Lots of people have been getting extremely good results with it. Everybody loves it. Anyone who's doing extremely high-performance systems right now, they are getting ridiculously cool results. And yeah, if you're interested, try out Rio for IOU ring. If you have a Linux kernel 5.1 and up, you can start to use some of the operations and sled for everybody if you have to store some things. So these are the projects that I'm excited to be talking about today. Yeah, we have some cool results I already talked about. We want to do a lot more things. If you want to help out, I'm on GitHub sponsors. As I said, I'm unemployable, so I'm really trying to just work on open source right now through like donations. I'm trying to still make useful things for other people. Also if you want to talk about distributed systems, come on our Discord channel. It's actually pretty active. And yeah, if you're interested in helping out, I love talking about this with other people, so come and join us. I also do rest trainings. Thanks. Thank you.
IOU ring, which is a new kernel interface that if an embedded database for the Rust community. And representation. Also lock-free and based on this is a technique that they rely on. This will we're in a high contention area. So this is an kernel. What we're used to before this is we have if I wanted to take advantage of it? Rio doesn't system. Okay. Lots of people have been getting