Module with too many functions exausts erlang atoms

I would consider something like OPA https://www.openpolicyagent.org/ running as a sidecar for each elixir deployment. Or potentially an ETS table with read optimization.

Even something like memsql/redis as a sidecar could work well. You will have some initial initialization time, but it should be quite fast after that.

I use the ETS table with a whitelisting api edge solution and it works well, but have never tried it at the scale you are referring to.

True, any kind of prefix trie, with either 4- or 8-bit symbols, could work. My suspicion is that this would provide little to no advantage over simpler trees for IPv4, but might be an advantage for IPv6…

Another data structure that might be worth looking at is a Patricia tree, which, amongst other places, is used in multiple Blockchain-implementations exactly because of the large keyspace.

You really don’t need an interval tree for this, you just need a straight-up sorted tree, with the possibility of “null” entries, then look up the largest entry <= the provided IP. Now, a b-tree would give you better lookup performance than any kind of binary tree, but I’d try some kind of simple binary tree first–a quick google search finds some Erlang implementations.

(You need an interval tree when you want to do things like find overlapping ranges…)

We work primarily with IPv4 (for now), which only contains 4,294,967,296 IPs. Still the suggestion of bloom filters looks interesting!

Because of the fact that there are 3.4*10³⁸ possible addresses in IPv6, I am wondering about the rest of your constraints that make you believe that, unless your ranges are very convenient, you could fit this in a 10⁶ lookup table?

Instead, maybe it is worth looking into bloom filters (combined with a somewhat slower but more scalable access method like for instance ETS).

In the end even the modules with their functions is also some kind of data structure that just points into the right spot. One could probably build this by hand or attempt the same thing in another language and see if it fares better at the task than elixir.

That’s the key point here imo. Even for a smaller/somewhat manageable number I’d advise to write benchmarks to see how different solutions fare.

I obviously don’t know your system, my assumption is that it’s a small performance relevant component of your system. If so, doing it in another language (be it via NIF, ports or HTTP calls micro service style) shouldn’t be too much of a hassle. My assumption also being that the code wouldn’t need to change too often. Rust, as an example, is very much focussed on backwards compatibility so it shouldn’t incur too much friction.

In the end it’s a trade off as always, rather a thing in language X that works or jump through a lot of hoops to maybe make it work on the BEAM?

This is a good question. We are dealing with searching for IPs within given ranges, so we have a couple of options:

1. Put the ips into a DB and make requests to such DB
2. Have this information in another tool/binary and have Elixir interact with it

Solution 1 has long query times for our needs. No only that, it also adds uncertainty (connections to the DB can fail) and an extra technology to our stack which we will have to maintain on the long run.

Solution 2 is better in that the query times can be dozens of times faster (no network traffic, no need to ask for a DB engine to perform a query) but it would force us to use the Port module to communicate with the given extra binary and it would still force us to keep and update a different technology on the long run.

Having this in Elixir would offer the following benefits:

1. faster access than previous solutions
2. we keep the stack we are already using small and consise
3. easy to maintain and use

Yes, compilation is an issue, but we only need to do it once and then we just add this as a project dependency to whoever needs using (we have something like private Hex for our libraries and packages, so we have some level of versioning and releases ).

We are working on the assumption several modules, each with thousands of functions, would give us faster results than using the appropriate data structure for the problem (interval trees). How do we know this is the case? We don’t, we simply assume, based on our current knowledge, this will beat the complexity of having an interval tree. We could be totally off, but we won’t know until we benchmark it.

And as I previously stated, we want to keep our technology stack small. This is critical part of our system that we will have to maintain in years to come. Rust and NIFs look cool but if we don’t have the personal to keep it oiled and running we will run into issues. It is, in the end, a company decision, which I understand.

I really second this.

If no “normal” data structure can satisfy your needs maybe it’s time to investigate other tools?

This small component seems super critical from what you say - have you looked at doing it in Rust/something bare metal you could then call out to via rustler/NIFs?

The compiler machinery does result in something that dispatches faster – but you are hitting its limits.

I’d go for what @bottlenecked did: use a tree with a quick dispatch mechanism. If you insist on using Erlang/Elixir for this task then that’s what’s going to work best. Have 500-1000 functions per module and you should be set.