8 ms·
Using Rust to Scale Elixir for 11M Concurrent Users
- nwrk 7y agoWell played. Kudos for creativity (https://github.com/rusterlium/rustler https://github.com/rusterlium/rustler) Thanks for write up and benchmarks.
- kibwen 7y agoRustler doesn't get the notice it deserves. I see people talk about using Rust to extend Ruby and Python and Node all the time, but none of those value concurrency-safety as much as Erlang does, and in the domains people tend to use Erlang for, the difference between using C and using Rust for NIFs matters even more than in typical back-end serverland.
- dmix 7y agoI have a feeling there are plenty of excellent NIFs for most situations so most people using Elixir haven't been very dependent on Rust optimizations. Especially the web people who usually don't need that level of optimization, unless you're a giant like Discord, which is relatively unique. Although I wouldn't be surprised to see more and more of Rustler as both Elixir and Rust gain in popularity. There's probably plenty of low-hanging performance fruit for any future rustler devs.
- the_duke 7y agoThat's just a consequence of Erlang/Elixir having a small fraction of the developer mind share of Node or Python.
- gubbrora 7y ago> large sorted sets Surprised to see no mention of trees which are basically the standard datastructure for this.
- adrianN 7y agoThey can also be implemented fairly efficiently in functional languages.
- jhgg 7y agoOne thing that our blog-post didn't mention too well was the need to be able to access arbitrary slices of data within the sorted set, as well as being able to know the index at which an item was inserted as well as removed. This is necessary for our usage of sorted sets, as clients can subscribe to a given window of the sorted-set (e.g. the top of a member-list), and in order to compute the delta operations to keep the client-side list in sync with the one on the server, we need this information.
- adrianN 7y agoI think you can augment simple trees to support those operations.
- kilotaras 7y agoThis reads as an almost textbook description of Cartesian tree.
- jhgg 7y agoCartesian trees do not provide the ability to get items at arbitrary indices within the data structure in an efficient member from my understanding. In order to get the Nth item in the tree, a linear traversal is required. Furthermore, to get the index at which an item is inserted or removed requires the same traversal to accumulate the index.
- kilotaras 7y agoThe common solution is to hold size of subtree in the nodes in addition to the value a.k.a treap with implicit keys.
- 7y ago
- rdtsc 7y agoThanks for sharing. I like reading posts that show a few trials and before arriving at the solution. Well and Rust and Elixir just seem to go together. I had noticed that both a list and ordsets were tested. Ordsets are just sorted lists. The huge difference I guess is because full sorting and uniqueness checking happens after every member addition, as in add_member(M, L) -> lists:usort([M | L]), while ordsets actually traverses the list and finds the right place where to insert the element. Also wonder how gb_sets http://erlang.org/doc/man/gb_sets.html http://erlang.org/doc/man/gb_sets.html would behave. Those should provide better asymptotic behavior as they actually implement a balanced tree data structure. Rust would still be faster but it would be an interesting comparison.
- chongli 7y agoOrdsets have O(log n) time insert, remove, and lookup operations. They are definitely not lists, they must be trees.
- jhgg 7y agoThey are most definitely sorted lists. This is mentioned very clearly in the documentation: http://erlang.org/doc/man/ordsets.html http://erlang.org/doc/man/ordsets.html >An ordset is a representation of a set, where an ordered list is used to store the elements of the set.
- adamtulinius 7y agoThat does not prevent a tree-based implementation, though.
- filmor 7y agoIt kind of does. And there is also no need to argue about this, the code is available and very straight forward: https://github.com/erlang/otp/blob/fe2b1323a3866ed0a9712e9d12e1f8f84793ec47/lib/stdlib/src/ordsets.erl#L31 https://github.com/erlang/otp/blob/fe2b1323a3866ed0a9712e9d1...
- 7y ago
- papaf 7y agoIts great to see two interesting languages used together. I wonder if an out of process solution was considered. For instance, Redis supports sorted sets: https://redis.io/commands#sorted_set https://redis.io/commands#sorted_set Using something like Redis saves development time and makes builds and packaging easier as no FFI is needed. However Redis comes at the cost of having a more complicated infrastructure.
- jhgg 7y agoOn a given node, we maintain a few million sorted sets that see a query and insertion velocity in the orders of millions of operations per second. When we are meticulously measuring operation time in the microsecond range to meet a performance target, a networked solution is out of the question.
- jensneuse 7y agoWhat about a local redis instance using unix domain sockets?
- jhgg 7y agoThe cost of making a system call and network serialization + deserialization still makes this infeasible.
- elcritch 7y agoAlso, rustler handles compiling the rust code, and configuring the nif dynamic library details. I’d wager it’d be a ton easier than Redis infrastructure even if redis worked for the use case. The sheer amount of flexibility in the BEAM is one reason I love working in Elixir. Really it seems like a “write once and forget” type of nif. Have you had to make a lot of updates after the initial tuning with Rustler? Though I was curious if you tried ETS or mnesia? They both offer sorted sets. Not sure if they just use ordsets behind the scene. Edit: nvm, I see you answered in another thread.
- jhgg 7y ago
- namelosw 7y agoThis is really cool. Meanwhile, it also shows Elixir itself is already really fast for the rest of us. Unless you're Discord or WhatsApp.
- richjdsmith 7y agoI doubt I will forget the time I first booted up an Elixir Phoenix server and got something like `[info] Sent 200 in 409µs` and stared at that `µs` for a while before it dawned on my that that was the symbol for microseconds. I was so used to 20-40ms that I couldn't even comprehend that it could be 80x faster. A year later since playing around in Elixir's world, and I'm still just so impressed by its speeds.
- nickjj 7y agoYeah. It's really something. Recently I started writing a bunch of tests for a Phoenix application for my first Phoenix app. After a day of hacking around and learning as I go I had 63 tests of which 57 of them are full blown controller tests where a good amount of those tests are dealing with a "current user" and reading / writing things from a database. I'm even using a "Faker" library to generate fake data for all of the DB attributes. The entire test suite runs in 600ms. That's 600ms for ~60 controller tests from start to finish. That's in a worst case scenario too where the code is on a non-SSD and that code is volume mounted into a Docker container on Windows while I use WSL. Sometimes things work so fast that I'm actually worried it's not doing what I think it's doing, but then I run --cover and see that I have 95%+ test coverage on the things I care about, so that code is getting reached.
- eeZah7Ux 7y ago20-40ms with what language and implementation?
- Thaxll 7y agoElixir is pretty slow tbh, like 3-10x slower than Java / C# / Go. Immutability / message passing is very heavy.
- ramchip 7y agoI'd be curious how ETS does on that problem. The Erlang efficiency guide says an ETS table takes: > Initially 768 words + the size of each element (6 words + the size of Erlang data). The table grows when necessary. This might be too large if there's a ton of them, but perhaps a single table per node could be workable? In particular, ordered_set tables with write_concurrency have been improved a lot on Erlang/OTP-22: OTP-15128 Application(s): erts, stdlib ETS option write_concurrency now also affects and improves the scalability of ordered_set tables. The implementation is based on a data structure called contention adapting search tree, where the lock granularity adapts to the actual amount of concurrency exploited by the applications in runtime.
- jhgg 7y agoETS has no facility to insert/remove an object and get the index at which the object was inserted to/removed from. This is needed in order to synchronize windows within the sorted set to our clients. We would have loved to use ETS, and use it in many places actually, and have open-sourced a few: - https://github.com/discordapp/zen_monitor https://github.com/discordapp/zen_monitor - https://github.com/discordapp/gen_registry https://github.com/discordapp/gen_registry - https://github.com/discordapp/ex_hash_ring https://github.com/discordapp/ex_hash_ring
- toast0 7y agoI don't know if it would be good enough,and there's certainly not a big reason for you to try, given your solution works great; but you could probably modify ets to give you the slot number where it inserted/removed and use that as a non-exact indicator of where in the sequence it was. (Depending on how accurate you need it to be, this might work?)
- deleted 7y ago[deleted]
- foota 7y agoI'm curious, how do they handle persistence? Is this data structure just used as a cache or?
- cuddlecake 7y agoAs I understand it, Sorted Sets are an in-memory feature. Discords architecture is one where an entire guild stays on one machine. And the sorted set is part of a guild as well. So, there is no need to persist it, since it is ephemeral in nature. Edit: perhaps to expand on this a bit more, keep in mind that discord is not a cloud native application. They have a few strong server nodes and a Cassandra cluster (at this point I am curious if they switched to scylladb) that handle all or at least most of their client facing features. Since they do not need to scale services, the servers they have are stateful. Hence, if the guild server crashes, so will the data structure, since the data structure is of no use if the server crashes and would need to be rebuilt from scratch either way. (Disclaimer: I am not an insider, just an Elixir fanboy)
- spockz 7y agoI wonder on how they did the benchmarks. In Java/JVM land you would use JMH. Is there anything similar for Erlang/beam?
- fgkramer 7y agoYou can use some built-in modules: http://erlang.org/doc/efficiency_guide/profiling.html http://erlang.org/doc/efficiency_guide/profiling.html or some external tools like recon: https://ferd.github.io/recon/index.html https://ferd.github.io/recon/index.html
- layoutIfNeeded 7y agoIt would be nice if they had also went the same lengths with their clients in terms of efficiency...
- BasDirks 7y agoI recently wrote a parser in Elixir for a templating language. Binary pattern matching is pretty neat for this purpose, but performance is nevertheless sub-optimal. Elixir was chosen over more suitable languages because our team is Elixir-only. OP shows that delegating performance critical computations in Rust is viable and fairly cleanly. That's good to know.
- zinclozenge 7y agoHave you taken a look at https://rhye.org/post/erlang-binary-matching-performance/ https://rhye.org/post/erlang-binary-matching-performance/ ? I've seen lots of posts in the erlang mailing list about how unintuitive getting optimal performance from binary pattern matching can be.
- losvedir 7y agoWow, very cool! Two questions: 1) One of the things that used to be the case with NIFs is that they can interfere with the BEAM's famed pre-emptive scheduling. Any chance that's what's going on here? ie: the NIF solution was fast because it's getting an unfair amount of CPU time, potentially leading to latency issues elsewhere in the app? I believe recently that was changed, though, and the BEAM can pre-empt NIFs? 2) Did you consider/benchmark a port solution before NIF? I think of those as a little safer, but with not as good of performance.
- EdgarVerona 7y agoThank you for sharing, and for going so deep on it!
- didgeoridoo 7y agoThis title is the platonic ideal of an HN post.
- mwerty 7y agoThe article was unusually well-written as well.
- devit 7y agoIt seems like they are using a really weird data structure (it's not even clear whether it's sub-quadratic). This is a textbook problem normally solved using a balanced binary tree augmented by adding a number with the size of the subtree to every node (an "order statistic tree").
- fenollp 7y agoWere any thoughts given to a process dictionary implementation? One (maybe supervised) process per instance of the pd_ordset type. The process would only ever have one client so no locking needed. Only potential issue would be the cost of sending messages. I have seen this kind of solution bring 100x speed improvements to write once <GB strings storage over ETS tables. This could be a gen_server as well. I’m curious because the PDict is often frowned upon (especially vocalized on the mailing list) yet cannot be avoided in some parts of OTP. Also looking at the code leads me to believe the benchmarking of the rust code was done without taking the usage of a NIF’s overhead, if there is any. Is this intended or am I missing something? Last question: are the great tracing capabilities of the BEAM lost when using NIFs and would this be an issue at Discord scale? Thanks for the interesting write up.
- ikazar 7y agoLooks like you've implemented a square-root decomposition based solution resulting in O(sqrt(N)) insert, remove and O(sqrt(N)+M) slice operations where M is the number of elements within the requested slice [1]. Better approach, imo, would be an order statistic tree with O(logN) insert, remove and O(logN+M) slice operations [2]. This would be usually implemented as an implicit treap [3]. Furthermore, balanced binary search trees can be implemented efficiently in a functional language like Elixir that doesn't have mutable data structures. One such example is Erlang's gb_tree [4]. [1] https://cp-algorithms.com/data_structures/sqrt_decomposition.html https://cp-algorithms.com/data_structures/sqrt_decomposition... [2] http://www.cs.yale.edu/homes/aspnes/pinewiki/OrderStatisticsTree.html http://www.cs.yale.edu/homes/aspnes/pinewiki/OrderStatistics... [3] https://cp-algorithms.com/data_structures/treap.html#toc-tgt-6 https://cp-algorithms.com/data_structures/treap.html#toc-tgt... [4] http://erlang.org/doc/man/gb_trees.html http://erlang.org/doc/man/gb_trees.html
- deleted 7y ago[deleted]
- hinkley 7y agoDid they just reinvent B trees?