I am currently working my way through the CMU’s Intro to Database Systems course , and one of the projects involves implementing the ARC Policy. This is not a solution to that project. I’m writing this to make it easier for me understand how the algorithm works without the cpp clutter, and hopefully in the process write something useful for the next person who tries to implement this.

I will be following the original IBM paper.

Background

ARC is a cache policy, it is used to determine what needs to be evicted from cache. If you aren’t familiar with what a cache policy is, chances are you may have heard of LRU cache or least recently used cache which evicts the least recently used item in the cache when the cache is full.

ARC was designed to be used to evict/manage a database’ cache, and it has better performance than other caching policies.

How it works.

There are two parts to this, one part which holds the actual data in cache, and the other, the policy part, which holds references to the data present in cache. This was a point that tripped me up a lot when trying to understand things in the paper, I assumed the policy itself held the items in memory.

Let’s talk about the second part. The ARC policy holds two lists, lru_1 and lru_2. Let’s have an Item dataclass to represent items we want to cache

from dataclasses import dataclass

@dataclass
class Item:
    id: int 
    value: any

and here are two stub classes that will be fleshed out by the end. The CacheManager will store the items in the cache and manage the cache. I’ve chosen to use a python list, to represent the cache because I want to enforce a limit to the size of the cache (a bit unintuitive with a dict) and also reference items based on the index they are located at rather than the Item’s id. The Item’s id will be useful later on.

also note that cache_size is a limit for how big the cache can grow (we don’t have infinite memory).

class ARCPolicy:
    def __init__(self):
        self.lru_1 = []
        self.lru_2 = []

    def register_access(self, idx):
        ...

class CacheManager:
    def __init__(self, cache_size):
        self.cache_size = cache_size;
        # Initialize with None values 
        self.cache = [None for _ in range(cache_size)]
        self.item_id_to_cache_index = {}
        self.empty_idx = 0
        self.arc_policy = ARCPolicy()

    def access(self, item):
        ...

Since this is being implemented in the context of a database which reads and writes data to disk, I will add two functions to stub out item access from disk and item writes to disk

def fetch_from_disk(id): 
    print(f"fetched item with id {id} from disk")
    return Item(id, "A value")

def write_to_disk(item): 
    print(f"Written item with id {id} to disk")
    return item

Case 1 - When a completely new item is pulled into the cache

insert(item) is called on the CacheManager. The item is stored in the cache (assuming the cache isn’t full). Then the location of the item is sent to the ARCPolicy to register_access. Since this item has never been seen by ARCPolicy before it will put it in the lru_1 list. If the item was already present in the lru_1 list then it will be moved from lru_1 to lru_2 but I’m getting ahead of myself.

class ARCPolicy:
    def __init__(self):
        self.lru_1 = []
        self.lru_2 = []

    def register_access(self, idx):
        # Will implement more logic soon.
        self.lru_1.append(idx)

class CacheManager:
    def __init__(self, cache_size):
        self.cache_size = cache_size;
        self.cache = [None for _ in range(cache_size)]
        self.item_id_to_cache_index = {}
        self.empty_idx = 0;
        self.arc_policy = ARCPolicy()

    def access(self, item_id):
        if item_id in self.item_id_to_cache_index:
            # to be implemented shortly
            ...
        else: 
            item = fetch_from_disk(item_id)
            self.insert(item)
        return item

    def insert(self, item):
        # case when cache has space and we don't have to evict
        if self.empty_idx < self.cache_size: 
            self.cache[self.empty_idx] = item
            self.arc_policy.register_access(self.empty_idx)
            self.empty_idx +=1

Seeing it in action

>>> cache_manager = CacheManager(5)
>>> cache_manager.access(1)
fetched item with id 1 from disk
Item(id=1, value='A value')
>>> cache_manager.cache
[Item(id=1, value='A value'), None, None, None, None]

>>> cache_manager.arc_policy.lru_1
[0] # 0 is the index of Item 1

Case 2 - When a cached item is accessed for the 2nd time

According to the ARCPolicy if an item is accessed only once, it goes into the lru_1 list, if it is accessed a second time it goes into the lru_2 list, and it is moved to the end of the lru_2 list everytime it is subsequently accessed.

Here’s the confusing part, the paper refers to both lists as LRU lists and I have chose to stay consistent with that naming, however these two lists track two different things.

lru_1 tracks recency. Any item in this list has been seen exactly once, which implies that it has been recently seen. As lru_1 grows, and we append items to the end of the list, the beginning of the list contains the oldest item and the end of the list contains the newest item. (Here list refers to python’s list which is an array and not a linked list)


# LRU_1 

# empty 
[]
# item 1 is accessed 
[1]

# item 2 is accessed 
[1, 2]
# above you can see that 2 was accessed after one. 

# item 3 is accessed 
[1, 2, 3]
# so the order of the items in the list is the order in which they were accessed from oldest to most recent.

So, there are two different ideas that you need to keep in your head. One list captures recency and the other captures frequency. The second idea, within each list, there is an inherent ordering from least_recently_used to most_recently_used. This was quite confusing for me so, I suggest thinking over it a few times.

Here’s the code for this


class ARCPolicy:
    def __init__(self):
        self.lru_1 = []
        self.lru_2 = []

    def register_access(self, idx):
        # case 1 where idx is not in any list 
        if idx not in self.lru_1 and idx not in self.lru_2:
            self.lru_1.append(idx)

        # case 2 where idx is in lru_1 
        if idx in self.lru_1:
            self.lru_2.append(idx) 
            # remove from first list
            self.lru_1.remove(idx)

Case 3 - When the item is already in lru_2

This is a simple case, you just move the item to the end of the list because it is the most recently seen item.
Remember that the end of the list is where the most recent items go.


class ARCPolicy:
    def __init__(self):
        self.lru_1 = []
        self.lru_2 = []

    def register_access(self, idx):
        # case 1 where idx is not in any list 
        if idx not in self.lru_1 and idx not in self.lru_2:
            self.lru_1.append(idx)

        # case 2 where idx is in lru_1 
        elif idx in self.lru_1:
            self.lru_2.append(idx) 
            # remove from first list
            self.lru_1.remove(idx)

        # case 3 where idx is in lru_2
        elif idx in self.lru_2:
            # remove and put idx to the end of the list
            self.lru_2.remove(idx)
            self.lru_2.append(idx)

We also need to update the cache manager to handle the case where the item is already in cache

class CacheManager:
    def __init__(self, cache_size):
        self.cache_size = cache_size;
        self.cache = [None for _ in range(cache_size)]
        self.item_id_to_cache_index = {}
        self.empty_idx = 0;
        self.arc_policy = ARCPolicy()

    def access(self, item_id):
        if item_id in self.item_id_to_cache_index:
            # new 
            self.arc_policy.register_access(self.item_id_to_cache_index[item_id])
            return self.cache[self.item_id_to_cache_index[item_id]]
        else: 
            item = fetch_from_disk(item_id)
            self.insert(item)
        return item

    def insert(self, item):
        ...

Eviction

Until now we have assumed that our cache always has space for new items, but in reality this can’t be the case (life would be easy otherwise).

How do we decide which list to evict from? The algorithm has a lru_1_target_size (c in the paper) variable that indicates how large lru_1 should grow (or shrink to).

So when deciding to evict something from cache there are 2 cases

Eviction case 1

In this case lru_1’s size is equal to lru_1_target_size so we remove an item from lru_1 and append the new item to lru_1.

Eviction case 2

In this case lru_1’s size is less than lru_1_target_size so we remove an item from lru_2 and append the new item to lru_1.

The idea is to always move lru_1’s size towards the target size.

Before we can define what the actual value of lru_1_target_size is, I need to mention that an invariant of this algorithm is that lru_1 size + lru_2 size = CacheManager cache_size. Intuitively, it should make sense because the two lru lists only store indexes of things in the CacheManager’s cache, and not more.

so lru_1_target_size should be half of cache_size.

One final thing, when evicting, the ARCPolicy needs to return the idx of the item that the CacheManager will use to evict the actual item from the cache. This would mean that CacheManager would have to call evict on ARCPolicy when it’s cache is full.

Here’s the full code so far. The new lines are marked with a comment.

from dataclasses import dataclass

@dataclass
class Item:
    id: int 
    value: any


class ARCPolicy:
    def __init__(self, cache_size, lru_1_target_size):
        self.lru_1 = []
        self.lru_2 = []
        self.cache_size = cache_size
        self.lru_1_target_size = lru_1_target_size

    def register_access(self, idx):
        # case 1 where idx is not in any list 
        if idx not in self.lru_1 and idx not in self.lru_2:
            self.lru_1.append(idx)

        elif idx in self.lru_1:
            self.lru_2.append(idx) 
            self.lru_1.remove(idx)

        # case 3 where idx is in lru_2
        elif idx in self.lru_2:
            # remove and put idx to the end of the list
            self.lru_2.remove(idx)
            self.lru_2.append(idx)


    def evict(self):
        # case 1 
        if len(self.lru_1) >= self.lru_1_target_size: 
            evict_idx = self.lru_1.pop(0)
            print(f"evicting {evict_idx} from lru_1")
            return evict_idx
        # case 2
        else:
            evict_idx = self.lru_2.pop(0)
            print(f"evicting {evict_idx} from lru_2")
            return evict_idx

class CacheManager:
    def __init__(self, cache_size):
        self.cache_size = cache_size;
        self.cache = [None for _ in range(cache_size)]
        self.item_id_to_cache_index = {}
        self.empty_idx = 0;
        # new 
        self.arc_policy = ARCPolicy(cache_size, cache_size//2)

    def access(self, item_id):
        if item_id in self.item_id_to_cache_index:
            # new 
            self.arc_policy.register_access(self.item_id_to_cache_index[item_id])
            return self.cache[self.item_id_to_cache_index[item_id]]
        else: 
            item = fetch_from_disk(item_id)
            self.insert(item)
        return item


    def insert(self, item):
        # case when cache has space and we don't have to evict
        if self.empty_idx < self.cache_size: 
            self.cache[self.empty_idx] = item
            self.arc_policy.register_access(self.empty_idx)
            self.item_id_to_cache_index[item.id] = self.empty_idx # new
            self.empty_idx +=1
        else:
            # cache full, evict
            evict_idx = self.arc_policy.evict()

            old_item = self.cache[evict_idx] # new
            self.item_id_to_cache_index.pop(old_item.id) # new

            # replace old item with new item
            self.cache[evict_idx] = item
            self.arc_policy.register_access(evict_idx)
            self.item_id_to_cache_index[item.id] = evict_idx # new

def fetch_from_disk(id): 
    print(f"fetched item with id {id} from disk")
    return Item(id, "A value")

def write_to_disk(item): 
    print(f"Written item with id {id} to disk")
    return item

Let’s see this in action

First we add 4 Items in cache, this will fill cm’s cache

>>> cm = CacheManager(4)
>>> for i in range(100, 104):
...     cm.access(i)
...     
fetched item with id 100 from disk
Item(id=100, value='A value')
fetched item with id 101 from disk
Item(id=101, value='A value')
fetched item with id 102 from disk
Item(id=102, value='A value')
fetched item with id 103 from disk
Item(id=103, value='A value')

then if you see both the lists, only lru_1 gets populated, not lru_2 since this is the first time these items are being accessed

# remember that the numbers here represent the CacheManager's indexes not the items' ids 
>>> cm.arc_policy.lru_1
[0, 1, 2, 3]
>>> cm.arc_policy.lru_2
[]

Let’s say we read new data again.

>>> cm.access(200)
fetched item with id 200 from disk
evicting 0 from lru_1
Item(id=200, value='A value')


>>> cm.access(201)
fetched item with id 201 from disk
evicting 1 from lru_1
Item(id=201, value='A value')

So in both cases we evict from lru_1.

Now let’s try to access some data that is already in cache so we can see that lru_2 is also populated

>>> cm.access(201)
Item(id=201, value='A value')

>>> cm.access(200)
Item(id=200, value='A value')

Notice that data was not fetched from disk since it was already in cache.


>>> cm.cache
[Item(id=200, value='A value'), Item(id=201, value='A value'), Item(id=102, value='A value'), Item(id=103, value='A value')]

>>> cm.arc_policy.lru_1
[2, 3]

>>> cm.arc_policy.lru_2
[0, 1]

Why different database workloads require different caching strategies

There’s still a part of the algorithm I haven’t implemented yet, but we will get to that in a bit.

Sequential Scans

If a query is doing a Sequential scan and reads a lot of data once and never reads it again, then we really don’t need to cache it, right? But the db doesn’t have a way of knowing that this data will not be accessed in the future, so it can’t NOT avoid caching. Let’s say we did make a rule that if there’s a seq scan we don’t store it in cache.

select * from student;

But then someone runs this query

select * from student where id=1;

Wouldn’t it have been nice to have that data in cache already?

So you can’t completely avoid caching data from Sequential scans because you can’t predict the future. But what you can do is minimize the damage caused by Sequential scans.

Here’s what I mean by damage. Let’s modify ARCPolicy’s lru_1_target_size to be equal to target_size, so this lets lru_1 grow preferrentially over lru_2

>>> cm = CacheManager(4)
# change target_size
>>> cm.arc_policy.lru_1_target_size = 4
# fill in some random data

>>> import random
>>> for _  in range(10):
...     cm.access(random.randint(1,4))
    # output snipped

Let’s look at the state we have so far

>>> cm.cache
[Item(id=3, value='A value'), Item(id=4, value='A value'), Item(id=2, value='A value'), Item(id=1, value='A value')]
>>> cm.arc_policy.lru_1
[3]
>>> cm.arc_policy.lru_2
[0, 2, 1]

we have 1 item in lru_1 and 3 in lru_2. This means that so for there were 3 items accessed multiple times, ideally we would like to keep these items in cache because they might be accessed again (asusming current trends continue)

What happens to lru_2 if we do a seq scan?

>>> for i in range(10,20):
...     cm.access(i)
# output snipped

>>> cm.arc_policy.lru_1
[1, 3, 0, 2]
>>> cm.arc_policy.lru_2
[]

the lru_2 list has been completely emptied by a seq scan. Assuming we never read the data from the seq scan again, every subsequent access will be a cache miss even for the popular data we had when setting this up like Item(3).

okay, let’s try to re-run this experiment with an lru_1_target_size of 0

>>> import random
>>> cm = CacheManager(4)
>>> cm.arc_policy.lru_1_target_size = 0
>>> for _  in range(10):
...     cm.access(random.randint(1,4))

>>> cm.cache
[Item(id=1, value='A value'), Item(id=4, value='A value'), Item(id=2, value='A value'), Item(id=3, value='A value')]
>>> cm.arc_policy.lru_1
[3]
>>> cm.arc_policy.lru_2
[1, 0, 2]

similar to last time we have three indexes in lru_2 and one in lru_1. The three indexes in lru_2 point to data that is popular.

What happens if we do a seq scan now?

>>> for i in range(10,20):
...     cm.access(i)

>>> cm.arc_policy.lru_1
[3]
>>> cm.arc_policy.lru_2
[1, 0, 2]

In this case, the items in lru_2 were not affected at all, and our popular data can still be accessed and won’t result in a cache miss! So the seq scan didn’t pollute the cache in this case.

From this we can gather that for seq scans having a target_size of 0 or close to zero is optimal; because cache space is saved, we only evict the items read by the seq scan.

What kind of workloads benefit from having a large target_size?

Bulk processing

If we take the extreme case of target_size = cache_size, then it would be optimal only for workloads which read a lot of data from the disk and only access that data from the cache for the next few queries; once the workload is done with frequently accessing the data it reads new data from disk and works with the new data. This is a common access pattern in batch processing and ETL pipelines.

The real world isn’t so black-and-white, databases have a mixture of workloads, some queries do seq scans, some re-use the same data over and over. Sometimes these happen simultaneously, since we can’t predict what’s going to happen we, the developers, can’t pick an optimal target_size, and this is where the Adaptive part of the Adaptive Cache Replacement Policy comes into play. Based on real world workloads, the algorithm adjusts target_size to suit the workloads it sees. Which is kinda brilliant if you think about it.

How does the algorithm adapt target_size?

If you had to adjust the value of target_size in real time, how would you do it? What are the factors that go in deciding whether target_size needs to be incremented or decremented? Remember, the goal of any cache replacement policy is to maximise the number of cache hits. Maybe looking at which list is producing a lot cache misses could help inform which list needs to grow bigger? For e.g if we see lru_1 have a lot of cache misses then increasing target_size would mean lru_1 could grow more and would reduce the probability of cache misses, and similarly if we saw lru_2 have a lot of misses maybe lru_2 needs to grow bigger.

Not quite though, since a seq scan would result in a lot of cache misses for lru_1, but this doesn’t mean we need to increase lru_1, since we know that a target_size of 0 is optimal for seq scans. So cache misses by themselves aren’t helpful.

We could keep track of recently evicted items for both lru_1 and lru_2. So if there was a cache miss and the item was recently evicted from a particular list, then we can say that if that particular list was a little bigger we wouldn’t have had the cache miss, and so we change target_size to let that list grow bigger.

Here’s an example. We have two lists recently_evicted_1 and recently_evicted_2. If an item A is accessed and results in a cache miss, and we see that item A was recently evicted from recently_evicted_1 then we increase target_size because we want lru_1 to grow. If item A was recently evicted from recently_evicted_2 then target_size should be reduced so that lru_2 can grow.

Going back to our seq scan example, when we do a seq scan, we have a bunch of cache misses, but most likely none of these items were recently evicted so it doesn’t affect target_size.

Eviction lists also inform which list items are inserted in, previously I mentioned that if an item is accessed from disk, it got to lru_1 and then if it is accessed again it goes to lru_2, but with eviction lists in the picture, we also look to see if an item was in the eviction list, if it was in any of the eviction list, it is added to lru_2 since it was accessed more than once in a recent period.

Eviction lists are called ghost caches in the paper, and I will use that term from now on.

Adding the adaptive mechanism of the cache Policy

One thing before we begin, the lru_1/lru_2 list stored the index of the cache from the cache Manager, but the ghost lists will store the actual Item’s id, and not the index, since the Item.id is the way we uniquely identify an Item.

In order to support this, I would need to modify register_access to pass the Item along with the index, since I need to check if the item has been seen in the ghost list, and when I call evict I would need to pass the cache from CacheManager so evict can have access to the actual Item and store it’s ID. (Yes, this wasn’t the best design but it is too late for me to change it)

here are the changes

class ARCPolicy:
    def __init__(self, cache_size, lru_1_target_size):
        ...
        
    def register_access(self, item, idx): # new
        ...
        

    def evict(self, cache):
        ...

class CacheManager:
    def __init__(self, cache_size):
        ...
        
    def access(self, item_id):
        if item_id in self.item_id_to_cache_index:
            item = self.cache[self.item_id_to_cache_index[item_id]] # new 
            self.arc_policy.register_access(item, self.item_id_to_cache_index[item_id]) # new
            return item # new
        else: 
            ...
        return item


    def insert(self, item):
        if self.empty_idx < self.cache_size: 
            self.cache[self.empty_idx] = item
            self.arc_policy.register_access(item,self.empty_idx) # new
            self.item_id_to_cache_index[item.id] = self.empty_idx

            self.empty_idx +=1
        else:
            evict_idx = self.arc_policy.evict(self.cache) # new
            old_item = self.cache[evict_idx]
            self.item_id_to_cache_index.pop(old_item.id)

            self.cache[evict_idx] = item
            self.arc_policy.register_access(item, evict_idx) # new
            self.item_id_to_cache_index[item.id] = evict_idx

Rules for the ghost Caches

Moving on to ghost caches. Just like we have a size limit to lru_1 and lru_2 lists, ghost caches also have a size limit. ghost_lru_1 + ghost_lru_2 <= cache_size

When incrementing target_size the size of both ghost lists matters, since we don’t just increment target_size by 1 every time. Here are the rules

if an item is in ghost_lru_1 a. if ghost_lru_1 >= ghost_lru_2, increase target_size by 1 b. if ghost_lru_1 < ghost_lru_2, increase target_size by (ghost_lru_2/ghost_lru_1) ensuring target_size is never more than cache_size
if an item is in ghost_lru_2 a. if ghost_lru_2 >= ghost_lru_1, decrease target_size by 1 b. if ghost_lru_2 < ghost_lru_1, decreas target_size by (ghost_lru_1/ghost_lru_2) ensuring target_size is never less than 0.

Ghost lists also need to be evicted from, fortunately, this is straightforward.

if ghost_lru_1 + ghost_lru_2 = cache_size, then evict from ghost_lru_1
if ghost_lru_1 + ghost_lru_2 + lru_1 + lru_2 = 2 * cache_size, then evict from ghost_lru_2

Updating register_access

Let’s start by updating the register_access method on ARCPolicy

class ARCPolicy:
    def __init__(self, cache_size, lru_1_target_size):
        self.lru_1 = []
        self.lru_2 = []
        self.ghost_lru_1 = []
        self.ghost_lru_2 = []
        self.cache_size = cache_size
        self.lru_1_target_size = lru_1_target_size

    def register_access(self, item, idx):
        if idx not in self.lru_1 and idx not in self.lru_2:
              # new
            if item.id not in self.ghost_lru_1 and item.id not in self.ghost_lru_2:
                self.lru_1.append(idx) # new 
            else:
                ghost_lru_1_size = len(self.ghost_lru_1)
                ghost_lru_2_size = len(self.ghost_lru_2)
                if item.id in self.ghost_lru_1: 
                    old_target_size = self.lru_1_target_size
                    if ghost_lru_1_size >= ghost_lru_2_size:
                        self.lru_1_target_size = min(1 + self.lru_1_target_size, self.cache_size)
                    else:
                        self.lru_1_target_size = min(ghost_lru_2_size // ghost_lru_1_size, self.cache_size)
                    print(f"Target size changed from {old_target_size} to {self.lru_1_target_size}")

                    self.ghost_lru_1.remove(item.id) 
                    self.lru_2.append(idx)
                else:
                    old_target_size = self.lru_1_target_size
                    if ghost_lru_2_size >= ghost_lru_1_size:
                        self.lru_1_target_size = max(self.lru_1_target_size - 1, 0)
                    else:
                        self.lru_1_target_size = max(self.lru_1_target_size - ghost_lru_1_size // ghost_lru_2_size, 0)
                    print(f"Target size changed from {old_target_size} to {self.lru_1_target_size}")

                    self.ghost_lru_2.remove(item.id) 
                    self.lru_2.append(idx)


        elif idx in self.lru_1:
            ...

        elif idx in self.lru_2:
            ...

The changes are pretty much a transcription of the rules I listed above

Updating `evict`

Let’s update the evict method next


class ARCPolicy:
    def __init__(self, cache_size, lru_1_target_size):
        ...

    def register_access(self, item, idx):
        ...

    # new
    def evict_ghost_cache(self):
        ghost_lru_1_size = len(self.ghost_lru_1)
        ghost_lru_2_size = len(self.ghost_lru_2)
        lru_1_size = len(self.lru_1)
        lru_2_size = len(self.lru_2)
        if ghost_lru_1_size + ghost_lru_2_size == self.cache_size:
            self.ghost_lru_1.pop(0)
        elif ghost_lru_1_size + ghost_lru_2_size + lru_2_size + lru_1_size == 2*self.cache_size: 
            self.ghost_lru_2.pop(0)

    def evict(self, cache):
        self.evict_ghost_cache() # new
        if len(self.lru_1) > 0 and len(self.lru_1) >= self.lru_1_target_size:
            evict_idx = self.lru_1.pop(0) 
            evicted_item = cache[evict_idx] # new
            # keep ghost_lru_1 from growing past the size of lru_1
            if len(self.ghost_lru_1) < len(self.lru_1):
                self.ghost_lru_1.append(evicted_item.id) # new
            else:
                if len(self.ghost_lru_1) > 0:
                    self.ghost_lru_1.pop(0)
                self.ghost_lru_1.append(evicted_item.id) # new
            return evict_idx
        # case 2
        else:
            assert len(self.lru_2) > 0
            evict_idx = self.lru_2.pop(0)
            evicted_item = cache[evict_idx] # new
            # keep ghost_lru_2 from growing past the size of lru_2
            if len(self.ghost_lru_2) < len(self.lru_2):
                self.ghost_lru_2.append(evicted_item.id) # new
            else:
                self.ghost_lru_2.pop(0)
                self.ghost_lru_2.append(evicted_item.id) # new
            return evict_idx

when we evict cache, we have to evict ghost cache, then the actual cache, and then store the id of the recently evicted item in the ghost cache.

Full source

You can grab the full source code here

Looking at the adaptive policy in action

Now for the fun part, let’s define a few workloads and see how target_size keeps changing. Let’s print target_size every time it changes

Let’s define some workloads

CACHE_SIZE = 10

ss1 = list(range(1,100))
ss2= list(range(2,200))
ss3= list(range(3,200))

bp1 = list(range(301, 301+CACHE_SIZE)) + [301, 301, 303,] 
bp2 = list(range(401, 401+CACHE_SIZE)) + [401, 402, 403,]

all_workloads = [
                # seq scans 
                   ss1
                 , ss2 
                 , ss3 
                 , ss1 
                 , ss2 
                 , ss3 
                 , bp1
                 , ss1 
                 , ss2 
                 , ss3 

                 # batch processing workload
                 , bp1
                 , bp1
                 , ss1 
                 , bp2
                 , bp2
                 , ss1 
                 , bp1
                 , bp1

                 # seq scans
                 , ss1 
                 , ss2 
                 , ss3 
                 , bp1
                 , ss1 
                 , ss2 
                 , ss3 
                 ]


cm=CacheManager(CACHE_SIZE)

for wk in all_workloads:
    for item in wk:
        cm.access(item)

output

Target size changed from 5 to 2
Target size changed from 2 to 2
Target size changed from 2 to 1
Target size changed from 1 to 0
Target size changed from 0 to 0
Target size changed from 0 to 0
Target size changed from 0 to 0
Target size changed from 0 to 0
Target size changed from 0 to 2
Target size changed from 2 to 5
Target size changed from 5 to 4
Target size changed from 4 to 3
Target size changed from 3 to 2
Target size changed from 2 to 1
Target size changed from 1 to 0

Here you can see target_size starting at 5 and then slowing going down to 0 due to the seq scans and then going back up to 5 for the batch processing workloads and then going back down to 0 for the seq scans again.

We can make target_size go over 5 if we incease the number of hot items in the batch processing workload


# just the changed workloads 
bp1 = list(range(301, 301+CACHE_SIZE)) + [301, 301, 303, 304, 305, 306, 307]
bp2 = list(range(401, 401+CACHE_SIZE)) + [401, 402, 403, 404, 405, 406, 407]

running it

Target size changed from 5 to 0
Target size changed from 0 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 4
Target size changed from 4 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 8
Target size changed from 8 to 7
Target size changed from 7 to 6
Target size changed from 6 to 1
Target size changed from 1 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 3
Target size changed from 3 to 7
Target size changed from 7 to 6
Target size changed from 6 to 5
Target size changed from 5 to 4
Target size changed from 4 to 3
Target size changed from 3 to 2
Target size changed from 2 to 1

Here we go all the way up to 8.

Another interesting thing is if the 2nd seq scan workload only consists of seq scans, the target_size doesn’t go back down to 0 but stays in place Here’s what I mean

all_workloads = [
                # seq scans 
                   ss1
                 , ss2 
                 , ss3 
                 , ss1 
                 , ss2 
                 , ss3 
                 , bp1
                 , ss1 
                 , ss2 
                 , ss3 

                 # batch processing workload
                 , bp1
                 , bp1
                 , ss1 
                 , bp2
                 , bp2
                 , ss1 
                 , bp1
                 , bp1

                 # seq scans
                 , ss1 
                 , ss2 
                 , ss3 
                 #, bp1 commented out batch processing workload
                 , ss1 
                 , ss2 
                 , ss3 
                 ]

output

Target size changed from 5 to 0
Target size changed from 0 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 4
Target size changed from 4 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 8
Target size changed from 8 to 7
Target size changed from 7 to 6
Target size changed from 6 to 1
Target size changed from 1 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 3
Target size changed from 3 to 7

here target_size 7 is the target_size at the end of the batch processing workload.

Here’s proof

all_workloads = [
                # seq scans 
                   ss1
                 , ss2 
                 , ss3 
                 , ss1 
                 , ss2 
                 , ss3 
                 , bp1
                 , ss1 
                 , ss2 
                 , ss3 

                 # batch processing workload
                 , bp1
                 , bp1
                 , ss1 
                 , bp2
                 , bp2
                 , ss1 
                 , bp1
                 , bp1

                 # seq scans
                 #, ss1 
                 #, ss2 
                 #, ss3 
                 ##, bp1 commented out batch processing workload
                 #, ss1 
                 #, ss2 
                 #, ss3 
                 ]

Target size changed from 5 to 0
Target size changed from 0 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 4
Target size changed from 4 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 8
Target size changed from 8 to 7
Target size changed from 7 to 6
Target size changed from 6 to 1
Target size changed from 1 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 3
Target size changed from 3 to 7

But the moment you insert 1 batch processing in that seq scans the target_size reduces

all_workloads = [
                # seq scans 
                   ss1
                 , ss2 
                 , ss3 
                 , ss1 
                 , ss2 
                 , ss3 
                 , bp1
                 , ss1 
                 , ss2 
                 , ss3 

                 # batch processing workload
                 , bp1
                 , bp1
                 , ss1 
                 , bp2
                 , bp2
                 , ss1 
                 , bp1
                 , bp1

                 # seq scans
                 , ss1 
                 , ss2 
                 , ss3 
                 , bp1 
                 , ss1 
                 , ss2 
                 , ss3 
                 ]

Target size changed from 0 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 4
Target size changed from 4 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 8
Target size changed from 8 to 7
Target size changed from 7 to 6
Target size changed from 6 to 1
Target size changed from 1 to 1
Target size changed from 1 to 2
Target size changed from 2 to 3
Target size changed from 3 to 3
Target size changed from 3 to 7
Target size changed from 7 to 6
Target size changed from 6 to 5
Target size changed from 5 to 4
Target size changed from 4 to 3
Target size changed from 3 to 2
Target size changed from 2 to 1

The reason this happens is because when target_size is big, and you only do seq scans, seq scans almost always hit the disk and aren’t negatively impacted by a large lru_1 list (based on the target_size), however, the moment you introduce a batch processing workload, it does get impacted by a small lru_2 (lru_1 is big so lru_2 is small) list leading to evictions causing the algorithm to rebalance target_size.

So the target_size only starts changing when you have workloads that are impacted by smaller cache.

Conclusion

This was a lot of fun to write about and see first hand the adaptive nature of the algorithm. I hope this was useful to you. Cheers!

Background#

How it works.#

Case 1 - When a completely new item is pulled into the cache#

Case 2 - When a cached item is accessed for the 2nd time#

Case 3 - When the item is already in lru_2#

Eviction#

Eviction case 1#

Eviction case 2#

Why different database workloads require different caching strategies#

Sequential Scans#

Bulk processing#

How does the algorithm adapt target_size?#

Adding the adaptive mechanism of the cache Policy#

Rules for the ghost Caches#

Updating register_access#

Updating evict#

Full source#

Looking at the adaptive policy in action#

Conclusion#