Using Rust to Scale Elixir for 11M Concurrent Users (2019)

The perfect Hacker News title has finally been crafted.

Articles SortedSet[0] is basically a pseudo-BTree with fixed depth = 2 and fixed max_size of leafs. This gives O(log n) search and O(sqrt n) inserts [1].<p>It would mean that insertion at beginning is worst case scenario (split + need to move all buckets), but timing of insert is actually dominated by adding size of the buckets to calculate final index.<p>Spending a little bit of time on research, finding <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Order_statistic_tree" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Order_statistic_tree</a> and just using G++ implementation would probably yield better result and less code to support.<p>G++ has __gnu_pbds which add O(log n) &quot;find_by_order&quot; and &quot;order_of_key&quot; to trees, e.g. [2].<p>[0] <a href="https:&#x2F;&#x2F;github.com&#x2F;discord&#x2F;sorted_set_nif&#x2F;blob&#x2F;master&#x2F;native&#x2F;sorted_set_nif" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;discord&#x2F;sorted_set_nif&#x2F;blob&#x2F;master&#x2F;native...</a><p>[1] Technically O(n&#x2F;max_size + max_size) but we can assume that max_size is selected to be ~sqrt n<p>[2] <a href="https:&#x2F;&#x2F;www.ideone.com&#x2F;8mzxGR" rel="nofollow">https:&#x2F;&#x2F;www.ideone.com&#x2F;8mzxGR</a>

You can also write Elixir&#x2F;BEAM NIF extensions in Nim and Zig as well using Nimler or Zigler, resp [1,2]. Also I’ve found writing native extensions for the BEAM is simpler than many other dynamic languages since it relies on immutable data. It’s roughly the same as just a function to deserialize&#x2F;serialize data with some extra references to GC’ed data. Especially with dirty “NIF”s (they allow the functions to run for as long as they want without messing up the BEAM scheduler).<p>1: <a href="https:&#x2F;&#x2F;github.com&#x2F;wltsmrz&#x2F;nimler" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;wltsmrz&#x2F;nimler</a> 2: <a href="https:&#x2F;&#x2F;github.com&#x2F;ityonemo&#x2F;zigler" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;ityonemo&#x2F;zigler</a>

The most interesting thing about Discord is their ability to scale. Their product really works well in my experience, and their scale is no joke.

It&#x27;d be interesting to see it compared to <a href="https:&#x2F;&#x2F;doc.rust-lang.org&#x2F;std&#x2F;collections&#x2F;struct.BTreeSet.html" rel="nofollow">https:&#x2F;&#x2F;doc.rust-lang.org&#x2F;std&#x2F;collections&#x2F;struct.BTreeSet.ht...</a>.<p>Their skiplist description is a little funny — typically a skiplist has one element per leaf node, and you should never need to move items between buckets. Also skiplists have logarithmic layers in the number of elements, so inserting and searching are always bounded by O(log n).

&gt; There’s a fantastic Elixir project called Rustler. It provides nice support on the Elixir and Rust side for making a safe NIF that is well behaved and using the guarantees of Rust is guaranteed not to crash the VM or leak memory<p>Hum, can someone talk more about these NIF and what special thing Rustler brings?<p>What&#x27;s different from just any kind of native interop, like say Java JNI ?

OMG, my startup is trying to solve a similar problem. Albeit not at this scale (YET). Looks like I have a good excuse to delve back into rust

[2019]

I was wondering if Crystal could be used thus way too. Found this <a href="https:&#x2F;&#x2F;github.com&#x2F;splattael&#x2F;erl_nif.cr" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;splattael&#x2F;erl_nif.cr</a>

The combination of Elixir and Rust has been really fascinating to watch. They compliment each other so well.

Old article: May 17, 2019. Title should reflect that.