5 ms·

Building a Cache in Elixir

88 points by revorad 4y ago

pcthrowaway 4y ago
I don't really know Elixir (though I'm interested in it), but this blog post was incredibly readable. Large font, good syntax highlighting, utilized most (but all) of the laptop screen width. A joy to look at in a sea of hard-to-read blog posts
- lawn 4y ago
  On my mobile phone the font is stupid large though, making it impossible to read.
  - capableweb 4y ago
    Good thing browser agents are just that, agents for the user. Most (if not all) have controls over the font-size, so you can make it larger/smaller at will, unless the website actively tries to defeat zooming, which this one doesn't. For me, the font was also too large, but 0.5 seconds later, it wasn't. But no need to comment about something like this (same with the parent) as it's not actually about the article, just about something website specific.
    - DoesntMatter22 4y ago
      How many people actually use a mobile browser to make things smaller. Usage is probably 1 percent. He has a valid issue
sIacker 4y ago
The conclusion here is, it’s probably not worth it unless you’re ok with reducing performance.
conradfr 4y ago
You can even get a simple cache running quite quickly with a Genserver and ETS. About the post, I'm not sure what dcache offers over Nebulex though.
- mattbrewsbytes 4y ago
  If you want a simple, easily understood cache and didn't want to write all the logic using GenServers and ETS you could use dcache. Nebulex looks more complicated than dcache, just comparing the getting started info: "In order to give more flexibility and loading only needed dependencies, Nebulex makes all its dependencies as optional." Then it goes on to describing shards, decorators, telemetry and external adapters like Cachex and Redis. So before I can run `mix deps.get` to include this package I now have to make decisions or at least read thru what those things are for this package. I prefer picking simple dependencies and add complexity later on if needed.
  - derefr 4y ago
    > I prefer picking simple dependencies and add complexity later on if needed. That's exactly what having optional dependencies does, though. Except that when you inevitably realize that e.g. you need to monitor your cache-hit ratio in production, enablement for that means adding a suggested dep and then flipping a config flag to use it, rather than finding your own separate dep that does that thing, and then gluing the two "simple" components together using code that is both only maintained by you (rather than the upstream), and which must necessarily only touch the outside interface of both of the components, and so may be many times less efficient than code that hooks into one component or the other.
    - mattbrewsbytes 4y ago
      In my experience people get wooed by libraries that have a lot of configurations, settings, optional features, etc. and then rarely use them. Just pick a simpler tool that does specifically what you need at the time. Also, modularize it so your entire code base isn’t impacted by swapping out a cache tool (or http, etc.)
      - conradfr 4y ago
        I agree but setting up a basic Nebulex cache is on par with most elixir "app wide" libraries. But yeah I guess the docs can be a bit overwhelming at first glance. Personally I like the decorators, especially as Ecto does not provide a cache solution.
jhgg 4y ago
One thing you can do is use :ets.slot/2 to do random probing of the cache and evict entries. The way to do so is simple, just have a process every few milliseconds check a random set of keys (say, 50 keys), and check if they expire. If >25% of keys were about to expire, repeat this process again instantly, until the % of keys expired in the batch is <25%, then poll periodically. This is how Redis versions prior to 6.0 implemented key expiry. It's a very simple algorithm and can prove quite efficient at evicting expired keys without having to constantly scan the entire range.
- gnomeduck 4y ago
  How does Redis do it now in 6.0 and later?
- KMag 4y ago
  Why not use a min heap to track expiry times? (Or a doubly-linked list, if lifetimes are uniform?)
  - sethammons 4y ago
    that was my immediate first question
  - bluesnowmonkey 4y ago
    The min heap would need to live in the process heap of a particular process. It would only be accessible by that process, so other processes would need to interact with it by sending messages to the "min heap" process and waiting for responses. The min heap process would became a massive throughput bottleneck at much lower QPS than ETS, just due to the overhead of processing messages. This would be exacerbated by GC pauses as the min heap grows larger than around 100k or 1M entries, whereas an ETS table can handle 100M entries or more (never hit a limit actually). Large, mutable, shared state like a cache works much better if it lives in ETS. Any process can read/write to a properly configured table in a few microseconds. Scales very well to large data sizes and high QPS. The random probing approach has the disadvantage that it stores expired entries longer than necessary. This either wastes memory or reduces cache hit rate. Either of these seem preferable to limiting throughput and maximum entry count, as the min heap would.
a3w 4y ago
"nil is greater than any integer", that was astounding. Which languages have a no-data is bigger than max_int rule?
- throwawaymaths 4y ago
  There is a total order on (almost) all data types in the beam. This is useful for arbitrary sorting and comparison of different types. I say almost because floats and their equivalent integer are different items but they are equal in the total order. In practice this is fine, and I have never heard of this causing a problem.
  - a3w 4y ago
    For me, no data is either NaN or zero, but +infinity is was the astounding part. Also, for some languages, not failing with an exception when comparing different strong types, could be a source of bugs, generally.
    - throwawaymaths 4y ago
      In Elixir, nil is an atom (a global enum namespace), it's not a special data type that has meaning outside of a convention (heavily supported by the stdlib) that "you should use it to mean nothing"[0]. To hammer this home, nil is meaningless and not generally understood by that convention in Erlang (which often returns undefined). Elixir/BEAM is strongly typed. There is no coercion going on when you are doing comparisons. [0] note that in elixir, "if" is in the stdlib, it's sugar over case, and the falsiness of nil is software-level (only false and nil are falsy in elixir, which is sane).
losvedir 4y ago
The purging is a scan with `next()` and a `lookup()` for each item. Since the logic is a simple `<` comparison, could this be done with a single `match_delete` instead? (Unfortunately, ETS match specifications are quite wonky, so without a lot of fiddling myself, I can't suggest exactly what the comparison logic would look like, but I know that you can express certain things like comparisons with it.) That would cut down on the back-and-forth between the elixir process and the ETS process.
- notamy 4y ago
  > Unfortunately, ETS match specifications are quite wonky Matchspecs are gnarly! Very annoying to wrap your head around, and it's closer to being an AST than anything. Shameless plug: I had written a library at one point to make matchspecs with Mnesia easier, but it might also work with ETS (haven't tested unfortunately): https://github.com/queer/lethe https://github.com/queer/lethe
- asabil 4y ago
  That's what `ets:fun2ms` at least in Erlang. Not sure how does that map in Elixir?
- bluesnowmonkey 4y ago
  Yes, match_delete would work. Even a little better, select_delete will return the number of entries that were purged. To delete everything where the third element in a tuple is greater than a constant, should be something like: :ets.select_delete(table, [{{:_, :_, :"$1"}, [], [{:>, :"$1", {:const, expires}}]}])
boberoni 4y ago
> I've always been a firm believer that micro-optimization is a critical task for developers to undertake. In the worst case, it tends to be a great teacher. It's also only through such efforts that informed decisions, based on previously gained knowledge and facts, can be made about what truly is and isn't worth pursuing with respect to performance. This why I like hobby projects. In my day-to-day work, my job is to deliver value and "get stuff done". However, in hobby projects, I can feel free to dive into an optimization rabbit hole and learn a whole bunch of stuff. Even if I don't ship my hobby projects, I still gain a lot from the background knowledge.

88 points by revorad 4y ago

I don't really know Elixir (though I'm interested in it), but this blog post was incredibly readable. Large font, good syntax highlighting, utilized most (but all) of the laptop screen width. A joy to look at in a sea of hard-to-read blog posts

lawn 4y ago
On my mobile phone the font is stupid large though, making it impossible to read.
- capableweb 4y ago
  Good thing browser agents are just that, agents for the user. Most (if not all) have controls over the font-size, so you can make it larger/smaller at will, unless the website actively tries to defeat zooming, which this one doesn't. For me, the font was also too large, but 0.5 seconds later, it wasn't. But no need to comment about something like this (same with the parent) as it's not actually about the article, just about something website specific.
  - DoesntMatter22 4y ago
    How many people actually use a mobile browser to make things smaller. Usage is probably 1 percent. He has a valid issue

sIacker 4y ago

The conclusion here is, it’s probably not worth it unless you’re ok with reducing performance.

conradfr 4y ago

You can even get a simple cache running quite quickly with a Genserver and ETS. About the post, I'm not sure what dcache offers over Nebulex though.

mattbrewsbytes 4y ago
If you want a simple, easily understood cache and didn't want to write all the logic using GenServers and ETS you could use dcache. Nebulex looks more complicated than dcache, just comparing the getting started info: "In order to give more flexibility and loading only needed dependencies, Nebulex makes all its dependencies as optional." Then it goes on to describing shards, decorators, telemetry and external adapters like Cachex and Redis. So before I can run `mix deps.get` to include this package I now have to make decisions or at least read thru what those things are for this package. I prefer picking simple dependencies and add complexity later on if needed.
- derefr 4y ago
  > I prefer picking simple dependencies and add complexity later on if needed. That's exactly what having optional dependencies does, though. Except that when you inevitably realize that e.g. you need to monitor your cache-hit ratio in production, enablement for that means adding a suggested dep and then flipping a config flag to use it, rather than finding your own separate dep that does that thing, and then gluing the two "simple" components together using code that is both only maintained by you (rather than the upstream), and which must necessarily only touch the outside interface of both of the components, and so may be many times less efficient than code that hooks into one component or the other.
  - mattbrewsbytes 4y ago
    In my experience people get wooed by libraries that have a lot of configurations, settings, optional features, etc. and then rarely use them. Just pick a simpler tool that does specifically what you need at the time. Also, modularize it so your entire code base isn’t impacted by swapping out a cache tool (or http, etc.)
    - conradfr 4y ago
      I agree but setting up a basic Nebulex cache is on par with most elixir "app wide" libraries. But yeah I guess the docs can be a bit overwhelming at first glance. Personally I like the decorators, especially as Ecto does not provide a cache solution.

jhgg 4y ago

One thing you can do is use :ets.slot/2 to do random probing of the cache and evict entries. The way to do so is simple, just have a process every few milliseconds check a random set of keys (say, 50 keys), and check if they expire. If >25% of keys were about to expire, repeat this process again instantly, until the % of keys expired in the batch is <25%, then poll periodically. This is how Redis versions prior to 6.0 implemented key expiry. It's a very simple algorithm and can prove quite efficient at evicting expired keys without having to constantly scan the entire range.

gnomeduck 4y ago
How does Redis do it now in 6.0 and later?
KMag 4y ago
Why not use a min heap to track expiry times? (Or a doubly-linked list, if lifetimes are uniform?)
- sethammons 4y ago
  that was my immediate first question
- bluesnowmonkey 4y ago
  The min heap would need to live in the process heap of a particular process. It would only be accessible by that process, so other processes would need to interact with it by sending messages to the "min heap" process and waiting for responses. The min heap process would became a massive throughput bottleneck at much lower QPS than ETS, just due to the overhead of processing messages. This would be exacerbated by GC pauses as the min heap grows larger than around 100k or 1M entries, whereas an ETS table can handle 100M entries or more (never hit a limit actually). Large, mutable, shared state like a cache works much better if it lives in ETS. Any process can read/write to a properly configured table in a few microseconds. Scales very well to large data sizes and high QPS. The random probing approach has the disadvantage that it stores expired entries longer than necessary. This either wastes memory or reduces cache hit rate. Either of these seem preferable to limiting throughput and maximum entry count, as the min heap would.

a3w 4y ago

"nil is greater than any integer", that was astounding. Which languages have a no-data is bigger than max_int rule?

throwawaymaths 4y ago
There is a total order on (almost) all data types in the beam. This is useful for arbitrary sorting and comparison of different types. I say almost because floats and their equivalent integer are different items but they are equal in the total order. In practice this is fine, and I have never heard of this causing a problem.
- a3w 4y ago
  For me, no data is either NaN or zero, but +infinity is was the astounding part. Also, for some languages, not failing with an exception when comparing different strong types, could be a source of bugs, generally.
  - throwawaymaths 4y ago
    In Elixir, nil is an atom (a global enum namespace), it's not a special data type that has meaning outside of a convention (heavily supported by the stdlib) that "you should use it to mean nothing"[0]. To hammer this home, nil is meaningless and not generally understood by that convention in Erlang (which often returns undefined). Elixir/BEAM is strongly typed. There is no coercion going on when you are doing comparisons. [0] note that in elixir, "if" is in the stdlib, it's sugar over case, and the falsiness of nil is software-level (only false and nil are falsy in elixir, which is sane).

losvedir 4y ago

The purging is a scan with `next()` and a `lookup()` for each item. Since the logic is a simple `<` comparison, could this be done with a single `match_delete` instead? (Unfortunately, ETS match specifications are quite wonky, so without a lot of fiddling myself, I can't suggest exactly what the comparison logic would look like, but I know that you can express certain things like comparisons with it.) That would cut down on the back-and-forth between the elixir process and the ETS process.

notamy 4y ago
> Unfortunately, ETS match specifications are quite wonky Matchspecs are gnarly! Very annoying to wrap your head around, and it's closer to being an AST than anything. Shameless plug: I had written a library at one point to make matchspecs with Mnesia easier, but it might also work with ETS (haven't tested unfortunately): https://github.com/queer/lethe https://github.com/queer/lethe
asabil 4y ago
That's what `ets:fun2ms` at least in Erlang. Not sure how does that map in Elixir?
bluesnowmonkey 4y ago
Yes, match_delete would work. Even a little better, select_delete will return the number of entries that were purged. To delete everything where the third element in a tuple is greater than a constant, should be something like: :ets.select_delete(table, [{{:_, :_, :"$1"}, [], [{:>, :"$1", {:const, expires}}]}])

boberoni 4y ago

> I've always been a firm believer that micro-optimization is a critical task for developers to undertake. In the worst case, it tends to be a great teacher. It's also only through such efforts that informed decisions, based on previously gained knowledge and facts, can be made about what truly is and isn't worth pursuing with respect to performance. This why I like hobby projects. In my day-to-day work, my job is to deliver value and "get stuff done". However, in hobby projects, I can feel free to dive into an optimization rabbit hole and learn a whole bunch of stuff. Even if I don't ship my hobby projects, I still gain a lot from the background knowledge.