Not at the moment, but it's a good idea for the next iteration of the class!
1,567 karma · joined December 16, 2011
A better link is https://www.youtube.com/watch?v=jf_ddGnum_4 which has chapter marks and has the power outage in the middle spliced away :p
I'm so excited to see dynamic, partially-stateful data-flow for incremental materialized view maintenance becoming more wide-spread! I continue to think it's a _great_ idea, and the speed-ups (and complexity reduction) it can yield are pretty immense, so seeing more folks building on the idea makes me very happy.
The PlanetScale blog post references my original "Noria" OSDI paper (https://pdos.csail.mit.edu/papers/noria:osdi18.pdf), but I'd actually recommend my PhD thesis instead (https://jon.thesquareplanet.com/papers/phd-thesis.pdf), as it goes much deeper about some of the technical challenges and solutions involved. It also has a chapter (Appendix A) that covers how it all works by analogy, which the less-technical among the audience may appreciate :) A recording of my thesis defense on this, which may be more digestible than the thesis itself, is also online at https://www.youtube.com/watch?v=GctxvSPIfr8, as well as a shorter talk from a few years earlier at https://www.youtube.com/watch?v=s19G6n0UjsM. And the Noria research prototype (written in Rust) is on GitHub: https://github.com/mit-pdos/noria.
As others have already mentioned in the comments, I co-founded ReadySet (https://readyset.io/) shortly after graduating specifically to build off of Noria, and they're doing amazing work to provide these kinds of speed-ups for general-purpose relational databases. If you're using one of those, it's worth giving ReadySet a look to get these kinds of speedups there! It's also source-available @ https://github.com/readysettech/readyset if you're curious.
Some context: https://twitter.com/jonhoo/status/1511401461669720068
Basically, I co-founded the company around the time I graduated, but had had my fill of database research after six years of PhD. So I joined AWS to work on Rust while Alana (the CEO) took on leading ReadySet.
In any case, I'm glad you enjoy the videos!
At least at MIT, these topics are not taught as part of the university curriculum: students are never shown how to use these tools, or at least not how to use them efficiently, and thus waste time and effort on tasks that should be simple. The standard CS curriculum is missing critical topics about the computing ecosystem that could make students’ lives significantly easier.
To help mitigate this, we ran a short lecture series during MIT’s Independent Activities Period (IAP) that covered all the topics we consider crucial to be an effective computer scientist and programmer. We’ve published lecture notes and videos in the hopes that people outside MIT find these resources useful.
To offer a bit of historical perspective on the class: we taught this class for the first time last year, when we called it “Hacker Tools” (there was some great discussion about last year’s class here: https://news.ycombinator.com/item?id=19078281). We found the feedback from here and elsewhere incredibly helpful. Taking that into account, we changed the lecture topics a bit, spent more lecture time on some of the core topics, wrote better exercises, and recorded high-quality lecture videos using a fancy lecture capture system (and this hacky DSL for editing multi-track lecture videos, which we thought some of you would find amusing: https://github.com/missing-semester/videos).
We’d love to hear any insights or feedback you may have, so that we can run an even better class next year!
-- Anish, Jose, and Jon
There’s just no class in the undergrad curriculum that teaches you how to become familiar with the system you’re working with! Students are expected to know about, or figure out, the shell, editors, remote access and file management, version control, debugging and profiling utilities, and all sorts of other useful tools on their own. Often times, they won’t even know that many of these tools exist, and instead do things in roundabout ways or simply be left frustrated about their development environment.
To help mitigate this, we decided to run this short lecture series at MIT during the January Independent Activities Period that we called “Hacker Tools” (in reference to “hacker culture”, not hacking computers). Our hope was that through this class, and the resulting lecture materials and videos, we might be able to bootstrap students’ knowledge about the tools that are available to them, which they can then put to use throughout their time at university, and beyond.
We’ve shared both the lecture notes and the recordings of the lectures in the hopes that people outside of MIT may also find these resources useful in making better use of their tools. If that turns out to be true, we’re also thinking of re-doing the videos in screen-cast style with live chat and a proper microphone when we get the time. If that sounds interesting to you, and if you have ideas about other things you’d like to see us cover, please leave a comment below; we’d love to hear from you!
We’re sure there are also plenty of cool tools that we didn’t get to cover in this series that you all know and love. Please share them below along with a short description so we can all learn something new!
Anish, Jose, and Jon
Digging a little further, I realized that the benchmarker spends a bunch of time on generating random numbers. In particular, generating a Zipf-distributed number (which the benchmarker does even when you run uniform) takes about 100ns: https://github.com/jonhoo/rust-zipf, which sets an upper limit of 10M ops/s that the benchmarker can measure. With Zipf removed entirely, I can get the std HashMap up to 8M reads/s, but no higher, which makes me think that the map really then is the bottleneck (generating a uniformly random number takes ~5ns, so shouldn't be the bottleneck). Running evmap with uniform and the Zipf-generation removed gives 73M reads/s, so ~4.5M reads/s/thread, which is again about 1/2 of the standard library HashMap with no synchronization.
So, all that said, I do not believe this is an error in evmap. Rather, if you believe 8M read/s per core on a HashMap is slow, then it's the Rust HashMap implementation in the standard library that is slow. evmap's 2x overhead doesn't seem that bad to me.
I'm glad I dug through this though!
While doing some digging of my own, I noticed that the benchmark is using the default Rust hashing function, SIP, which is cryptographically secure. I should probably re-run with FNV hashing, as that can potentially yield an order-of-magnitude speedup: https://cglab.ca/~abeinges/blah/hash-rs/. I'm currently away from my main setup, but will make that change and re-benchmark when I get back to work in a few days' time! Or maybe you'll beat me to it. It should just be a matter of using [`with_hasher`](https://docs.rs/evmap/4.0/evmap/struct.Options.html#method.w...) and passing in one of [these](https://docs.rs/fnv/1.0/fnv/type.FnvBuildHasher.html). That might be the entire explanation for the difference!
You're right about the persistence point, that was a brain-fart on my part. evmap does not provide persistence, and so that's not the right comparison point!
It's worth pointing out that this was intended to be a relatively high-level talk. For the more technical details, I'd recommend reading the [Noria paper](https://www.usenix.org/conference/osdi18/presentation/gjengs...). As for the performance numbers, I've tried to give some better discussion of that [in a response](https://news.ycombinator.com/item?id=18838359) to NovaX's comments above.
I've read all your comments below, and figured I'd try to give a single overall reply, so here goes.
First, it's important to note the difference between Noria (the database) and evmap (the data structure). Noria is the research project I've been working on, and which was published in [OSDI'18](https://www.usenix.org/conference/osdi18/presentation/gjengs...). It's primary contribution is partially materialized, dynamic data-flow, something no existing systems provide. We use that to implement materialized views, and find that it gives expressive and high-performance materialized views, beyond what you can currently find in other existing systems. evmap is _not_ novel. Neither the epoch scheme, nor the swapped map. It is simply a neat data-structure that we happen to _use_ in Noria, and which we find gives good performance in the face of highly concurrent reads. We could easily swap out evmap for another concurrent map if we find one that performs better.
The reason I built evmap initially was out of sheer laziness. I wanted a data-structure that allowed basically perfectly scaleable reads when writes are infrequent compared to writes, and I didn't want to implement my own hash map, because then you lose out on all the optimizations that more mature implementations carry. evmap ticks both those boxes. It scales pretty much linearly, and can use any map you want internally -- it does _not_ need to have any knowledge of the internals of the map, uses only standard map APIs, and supports things like dynamic map resizing (which many concurrent maps lack) without any special consideration.
As for performance, I'm not sure I know where you have those numbers from. The most recent paper I'm aware of with a concurrent key/value store is [FASTER from Microsoft](https://www.microsoft.com/en-us/research/uploads/prod/2018/0...), which was published in SIGMOD'18. The best numbers I see reported in Figure 8, with 56 cores, is 100-150M reads/s when there are no writes. That is obviously impressive, and far more than the simple evmap design can provide, but if you look at the competition (like MassTree), those get closer to 50M/s for a read _only_ benchmark, which is pretty close to evmap given the difference in hardware and number of cores.
You _are_ right that evmap is slower though, and I can hazard some guesses as to why. First, evmap is a multi-value map, so all operations need to chase one more pointer (to the value list for the key). Second, evmap has essentially half the cache space available to it since the readers sort of end up sharing the cache between the two maps. And third, evmap reads are do the double-epoch-counting trick, which adds two mostly-uncontended-but-not-free increments on the critical path. I haven't looked into the details of what FASTER and MassTree do, but they probably do something clever.
And finally, to some of your more specific points of contention:
- There are as many cores as threads in the evmap benchmark. - Zipf and uniform having similar performance isn't that odd, because the main cost in that benchmark ends up being the readers needing to re-acquire read access to the cache line for the map pointer, which isn't affected by distirbution. - evmap is indeed not lock-free, but the read path is. The writer does take a lock, but that lock is just used to arrange for _new_ read handles to be added, which should be a rare occurrence. It should generally be uncontended.
Phew! Thanks for all your comments and digging -- hopefully this helps answer some of your concerns :)