Re:Using Rust to Scale Elixir for 11M Concurrent Users
by jhgg on Saturday May 18, 2019 @01:56AM
(#19945905)
One 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.
[ Parent
| on HN ]
Re:Using Rust to Scale Elixir for 11M Concurrent Users
by adrianN on Saturday May 18, 2019 @02:26AM
(#19946017)
I think you can augment simple trees to support those operations.
Re:Using Rust to Scale Elixir for 11M Concurrent Users
by kilotaras on Saturday May 18, 2019 @02:28AM
(#19946026)
This reads as an almost textbook description of Cartesian tree.
Re:Using Rust to Scale Elixir for 11M Concurrent Users
by jhgg on Saturday May 18, 2019 @02:42AM
(#19946073)
Cartesian 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.
Re:Using Rust to Scale Elixir for 11M Concurrent Users
by kilotaras on Saturday May 18, 2019 @03:18AM
(#19946178)
The common solution is to hold size of subtree in the nodes in addition to the value a.k.a treap with implicit keys.
Re:Using Rust to Scale Elixir for 11M Concurrent Users
by pornel on Saturday May 18, 2019 @08:47AM
(#19947102)
But at this point you're adding even more bookkeeping and implementation complexity just to use a data structure that's not ideal in the first place (for performance, sequential memory layout is better than chasing pointers).
Re:Using Rust to Scale Elixir for 11M Concurrent Users
by foobarqwertz on Saturday May 18, 2019 @05:14AM
(#19946462)
I propose a challenge: Provide the interface for the datastructure and the test tool.