7
\$\begingroup\$

Here is the problem I've been trying to tackle:

Design a thread-safe image caching server that can keep in memory only the ten most recently used images.

I chose to implement an LRU cache to solve this as follows:

'''
This module defines an LRUCache.

Constraints:

1. May only hold upto ten items at a time.
2. Must be able to synchronise multiple requests.
3. Must be able to update its cache. 
'''

import random
import threading

class LRUCache(object):

    def __init__(self, cacheSize=10):

        # this variables maps image names to file locations
        self.Cache = {}

        # this variables maps image names to timestamp of last request
        # filed for them. Is volatile - requires local clock to never change,
        # or that there is a separate clock service that guarantees global
        # consistency. 
        self.RequestTimestamps = {}

        self.CacheSize = cacheSize

    def insert(self, imageName, imageLocation):

        '''
        Insert a new image into our cache. If inserting would exceed our cache size,
        then we shall make room for it by removing the least recently used. 
        '''

        with threading.Lock():

            if len(self.Cache) == self.CacheSize:
                self.removeLeastRecentlyUsed()

        self.Cache[imageName] = imageLocation
        self.RequestTimestamps[imageName] = time.time()

    def get(self, imageName):

        '''
        Retrieve an image from our cache, keeping note of the time we last 
        retrieved it. 
        '''

        with threading.Lock():

            if imageName in self.Cache:

                self.RequestTimestamps[imageName] = time.time()
                return self.Cache[imageName]

            else:

                raise KeyError("Not found!")

    def removeLeastRecentlyUsed(self):

        '''
        Should only be called in a threadsafe context.
        '''

        if self.RequestTimestamps:

            # scan through and find the least recently used key by finding
            # the lowest timestamp among all the keys.

            leastRecentlyUsedKey = min(self.RequestTimestamps, key=lambda imageName: self.RequestTimestaps[imageName])

            # now that the least recently used key has been found, 
            # remove it from the cache and from our list of request timestamps.

            self.Cache.pop(leastRecentlyUsedKey, None)
            self.RequestTimestamps.pop(leastRecentlyUsedKey, None)
            return

        # only called in the event requestTimestamps does not exist - randomly 
        # pick a key to erase.

        randomChoice = random.choice(self.Cache.keys())
        self.Cache.pop(randomChoice, None)

Questions:

  1. Is this actually threadsafe?

    I'm used to implementing locks on single resources, but not class methods - would multiple threads, one accessing insert and the other doing a get be forced to synchronised as well?

    Or is my strategy of creating different locks in each method only able to prevent concurrent individual insert requests?

    Ignore the GIL.

  2. What would be a good strategy to test this code?

    I have thought of the obvious strategy:

    a) Insert ten items, make nine requests, attempt to insert a tenth and check if the item that was removed was the tenth.

    but I am not sure if this is the only way or if there is a better way to implement it.

\$\endgroup\$
  • 4
    \$\begingroup\$ 1.) No, it's not actually thread safe. There is no point in using a lock, if that lock is only used in the thread in which it was created. Such lock does not synchronize anything. You have to create the lock in __init__ as an attribute of self and use this lock in all methods. \$\endgroup\$ – kyrill Apr 10 '17 at 13:30
  • 2
    \$\begingroup\$ Python's functools.lru_cache is a thread-safe LRU cache. Take a look at the implementation for some ideas. \$\endgroup\$ – Gareth Rees Apr 10 '17 at 17:53
3
\$\begingroup\$

Thread-safeness

As others have pointed out in the comments, your implementation is not thread-safe. threading.Lock() returns a new lock each time it is called, so each thread will be locking a different lock. Instead, you should have a single lock as an instance member object:

def __init__(self, cacheSize=10):

    # this variables maps image names to file locations
    self.Cache = {}

    # this variables maps image names to timestamp of last request
    # filed for them. Is volatile - requires local clock to never change,
    # or that there is a separate clock service that guarantees global
    # consistency. 
    self.RequestTimestamps = {}

    self.CacheSize = cacheSize

    self.lock = threading.Lock()

Then, you use it like so:

def insert(self, imageName, imageLocation):

    '''
    Insert a new image into our cache. If inserting would exceed our cache size,
    then we shall make room for it by removing the least recently used. 
    '''

    with self.lock:

        if len(self.Cache) == self.CacheSize:
            self.removeLeastRecentlyUsed()

    self.Cache[imageName] = imageLocation
    self.RequestTimestamps[imageName] = time.time()

Additionally, using time.time() for access orders can cause inconsistent results: it's not guaranteed to have good precision, and is dependent on the system clock steadily increasing. If the system clock is manually set back, you lose your consistent ordering. Instead, a safer way would be to use an OrderedDict, where you remove and re-insert items as they are accessed, and use OrderedDict.popitem(False) to remove the least-recently inserted item.

PEP8 compliance

Your variables and methods are written with a mixture of PascalCase (Cache.RequestTimestamps), which is typically only used for class names, and camelCase (Cache.removeLeastRecentlyUsed, leastRecentlyUsedKey), which is typically not used in Python. You should use snake_case instead for variables and methods, and use it consistently:

def __init__(self, cache_size=10):

    # this variables maps image names to file locations
    self.cache = {}

    # this variables maps image names to timestamp of last request
    # filed for them. Is volatile - requires local clock to never change,
    # or that there is a separate clock service that guarantees global
    # consistency. 
    self.request_timestamps = {}

    self.cache_size = cache_size
def remove_least_recently_used(self):

    '''
    Should only be called in a threadsafe context.
    '''

    if self.request_timestamps:

        # scan through and find the least recently used key by finding
        # the lowest timestamp among all the keys.

        least_recently_used_key = min(self.request_timestamps, key=lambda image_name: self.request_timestamps[image_name])

        # now that the least recently used key has been found, 
        # remove it from the cache and from our list of request timestamps.

        self.cache.pop(least_recently_used_key, None)
        self.request_timestamps.pop(least_recently_used_key, None)
        return

    # only called in the event requestTimestamps does not exist - randomly 
    # pick a key to erase.

    random_choice = random.choice(self.cache.keys())
    self.cache.pop(random_choice, None)

And while we're looking at this method...

Single exit only

While there are many arguments against the single-exit-only style, none of them apply here. There's no good reason to have the return inside of the if in Cache.removeLastRecentlyUsed. Instead, wrap the rest in an else:

if self.request_timestamps:

        # scan through and find the least recently used key by finding
        # the lowest timestamp among all the keys.

        least_recently_used_key = min(self.request_timestamps, key=lambda image_name: self.request_timestamps[image_name])

        # now that the least recently used key has been found, 
        # remove it from the cache and from our list of request timestamps.

        self.cache.pop(least_recently_used_key, None)
        self.request_timestamps.pop(least_recently_used_key, None)
else:

    # only called in the event requestTimestamps does not exist - randomly 
    # pick a key to erase.

    random_choice = random.choice(self.cache.keys())
    self.cache.pop(random_choice, None)
\$\endgroup\$
  • \$\begingroup\$ What's the advantage of having a single exit point? \$\endgroup\$ – Hubert Grzeskowiak Jun 21 at 1:26
  • \$\begingroup\$ @HubertGrzeskowiak In this case, structuring the function as an if-else block makes it clear that there are two cases that define the behavior of the function. It is explicit, and is easier to understand as a reader. Using return to break out of a function early without actually returning anything is a code smell, and understanding that there are two branches is made more difficult because it's expressed implicitly as a side effect of the early return. The Zen of Python teaches us that explicit is better than implicit, so the if-else version is preferable. \$\endgroup\$ – Mego Jun 21 at 5:03
  • \$\begingroup\$ I agree that it makes the logic most obvious in this particular case because both code paths contain some logic for "the good path" (as opposed to error conditions). However, maybe we should clarify the many arguments against the single-exit-only style you mentioned. \$\endgroup\$ – Hubert Grzeskowiak Jun 21 at 5:51
  • \$\begingroup\$ @HubertGrzeskowiak The common argument against it is that avoiding it can often make code harder to read. However, that's not the case here - following the single-exit-only style makes it easier to read. \$\endgroup\$ – Mego 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.