Non-uniform caches are harder to make work well

August 9, 2019

One way to view what can happen to your Unix system when you don't have swap space is that it's one more case of the Unix virtual memory system facing additional challenges because it is what I will call a non-uniform cache. In a uniform cache, all entries come from the same source at the same speed (more or less), can naturally be accessed as fast and as frequently as each other, and can be evicted or freed at the same speed and volume. In a non-uniform cache, some or many of those are not true. A Unix system without swap is an extreme case, since one sort of pages cannot be evicted from RAM at all, but Unix has experienced problems here before, for example when it introduced a unified buffer cache and discovered that certain sorts of pages could naturally be accessed a lot faster than others.

One source of problems is that a non-uniform cache mingles together two factors when you observe pressure on it. In a uniform cache, the observed pressure on elements in the cache is a true reflection of the real needs of the things using the cache. In a non-uniform cache, the pressure you observe is some combination of how much elements are really needed and how readily they can be fetched, accessed, and dropped. To work out the true pressure and balance the cache properly, the system needs some way to split these two factors apart again, generally by knowing or working out the impact of the various sorts of non-uniformity.

(Then, of course, it needs to be able to balance the cache at all. Having no swap space is an extreme case, but even with swap space you can usually only evict so many anonymous pages from RAM.)

Automatically coping with or working out the impact of non-uniformity is a hard problem, which is one reason that tuning knobs proliferate in non-uniform caches (another is that punting the problem to the cache's users is a lot easier than even trying). Another surprisingly hard problem seems to be realizing that you even have a non-uniform cache at all, or at least that the non-uniformity is going to matter and how it will manifest (many caches have some degree of non-uniformity if you look at them closely enough).

(This probably shouldn't be surprising; in practice, it's impossible to fully understand what complex systems are doing in advance.)

One corollary of this for me is that if I'm creating or dealing with a cache, I should definitely think about whether it might be non-uniform and what effects that might have. It's tempting to think that your cache is sufficiently uniform that you don't have to dig deeper, but it's not always so, and ignoring that a cache is non-uniform is a great way to get various sorts of bad and frustrating performance under load.

(Of course if I really care I should profile the cache for the usual reasons.)

Written on 09 August 2019.
« What has to happen with Unix virtual memory when you have no swap space
Turning off DNSSEC in my Unbound instances »

Page tools: View Source, Add Comment.
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Fri Aug 9 00:10:15 2019
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.