jaybe78

Search random elements in a big ETS table (> 1M)

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

29 comments

#ets #genserver

0 765 29

2025-08-20 11:05:07 UTC

Marked As Solved

jstimps

What if you were to insert into an :ordered_set table with a uniformly random key? Then the first N items in the table would be properly shuffled ahead of time. When you want to sample N items, you just choose the first N you encounter with :ets.first/:ets.next and then reshuffle them (by deleting and re-inserting).

Some disadvantages

deleting and re-inserting should be atomic, hence the GenServer
collisions theoretically possible

Post #15

Also Liked

garrison

Lol I read the OP and knew there had to be matchmaking involved. I don’t think I fully understand the use-case here but putting that aside for a moment…

This is what I was going to suggest, but I see you figured it out first I was feeling so clever, too!

But why do you have to sample from the start? Sample from a random index in the uniform space and just scan until you hit the quota. Wrap around if you hit the end.

I don’t think this is equivalent to a true random sample but for this use-case I don’t think anyone will be able to tell.

Edit: Actually if you choose 100 random indices and call :ets.next_lookup() with them (instead of scanning from the first) I think this would be a truly random sample. Right?

1..100
|> Enum.map(fn _ -> Enum.random(1..1_000_000) end)
|> Enum.map(fn i ->
  {_, [{_, value}]} = :ets.next_lookup(table, i)
  value
end)

Of course you could get duplicates but there are ways to deal with that.

Since the keys are already truly random there should be no bias from adding/removing users, no matter which users they are.

Post #20

al2o3cr

I meant “draw” in the lottery sense:

get an index with Enum.random(1..current_max)
fetch the element with that key
if no element, try again

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_max would be increasing constantly but the table is mostly unoccupied. The average runtime of a “pick a random user” would just get worse and worse…

Post #7

jstimps

I think it should be pretty efficient due to the :ordered_set, which should get you O(log n). Only way to know for sure is to test in your specific use case.

As @garrison pointed out though this scheme might not be rigorously uniform. Some simulation testing might be helpful to confirm it’s fairness.

Post #24

Last Post!

manhvu

Oh, I missed this. Not like Mnesia table, ets cannot have an index for another field. So I think for this case can use Mnesia with memory table and add index can get some advantage when scale out.

Post #30