jaybe78
Hey,
I need help to find a scalable and efficient solution to:
- Store large number of elements (username)
- Table is not static => element gets removed from the table when process is demonitored
- Being able to return random elements efficiently
The context is that I’m storing some users based on criterias in different ETS tables and wants to be able to return those in my UI as part of a search.
First thing:
I’m dealing with username as keys, and at the same time, I think the easiest way to get random elements from an ETS table is to use sequential number as keys
i.e
:ets.lookup(tab, Enum.random(1..1000))
So I though about using 3 ETS tables:
- The first to store the username with corresponding index “usernames”
- The second to store all the user indexes “user_indexes”
- the last one to increment the total count of user added to get the next index “count”
Add user scenario
- Get the next index from “count”
- Add a new index in “user_indexes”
- Add corresponding username in “usernames” with that index
- Monitor the process
That’s my initial idea but the problem is that when users gets removed from the table, the indexes are not sequential anymore ({1..4,..6..400..})
In that situation the lookup function I use to get random elements would not return the expected results
:ets.lookup(tab, Enum.random(1..200))
There’s an other solution which is to work directly on the username keys
first = :ets.first(tab)
:ets.lookup(tab, first)
func = fn key->
if function_that_may_return_true() do
key = case :ets.next(tab, key) do
:'$end_of_table' -> throw :reached_end_of_table
key -> func.(key)
end
else
:ets.lookup(tab, key)
end
end
Though that solution is not efficient for large tables.
At this point I’m not sure what I could do ?
Cheers
Where Next?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Producing high quality Elixir screencasts since 2017.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ai
- #ecto-query
- #elixirconf-us
- #blog-post
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #elixirconf-eu
- #api
- #forms
- #metaprogramming
- #hex
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Bringing learning, work and compliance together since 1987.
Producing high quality Elixir screencasts since 2017.
**Building the future of software with AI, trust, and human connection.**
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
Showing Posts 1 to 10- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
tcoopman
Isn’t an
ordered_settype of ets table good enough?So have an
ordered_setets table, insert and remove usernames and randomly fetch an item based on the number of items you’ve got inserted?jaybe78
How would you fetch random keys in an ETS table whose keys you don’t know ?
The only way to do that to my knowledge is to use a combination of
firstandnextto go through the table but that is not efficient.Let’s say I have 1M in an ordered sets
How can I get stored usernames between 700_000 and 700_070 without going through all the usernames before ?
al2o3cr
One way to deal with those gaps would be to “draw again” when you get an unoccupied integer.
The efficiency of that approach is going to depend on how often elements get deleted; lots of churn will make for lots of retries. How common are deletes in your application?
jaybe78
By “draw again”, you mean re populate all those data in the table every time to fill those gaps ?
I’d say on average an user would appear in those ETS table less than a minute or so.
So those delete will be frequent, yes.
derek-zhou
Assuming you have an ordered_set with integer key, You can do:
If it returns end of table, do again, or do first.
al2o3cr
I meant “draw” in the lottery sense:
Enum.random(1..current_max)This would work fine for systems with infrequent deletions, since most of the time the first lookup succeeds.
It would be extremely BAD for a high-churn system, since
current_maxwould be increasing constantly but the table is mostly unoccupied. The average runtime of a “pick a random user” would just get worse and worse…jaybe78
That would not solve the current_max increasing constantly while the table is mostly unoccupied as pointed out by @al2o3cr
LostKobrakai
What’s the usecase here? What do you need to fetch random users out of a huge ets table for?
jaybe78
I’m building an app where users can search :
When an user search for players, my goal is to return a list of users that is as random as possible for each search.
Because if same users are returned in search result too many times, the same users would be challenged, that would create spam, while others would be left out.
The end goal is to really create couple(1vs1) as fast as possible.
LostKobrakai
For matchmaking wouldn’t you want to prefer people having waited longer over people just having joined the queue? Also would there really be a million people waiting in the queue or rather be a million people playing? If you form couples quickly enought the queue might stay at a reasonable size.