Pull to refresh

Реализация кеша с ограничением по числу элементов на Python — решения: простое и посложнее

Reading time 8 min
Views 6.7K

Формулировка задачи


Предположим, что у нас есть необходимость иметь некий сервис, который бы отдавал нам по запросу какую-либо информацию, и отдавал как можно быстрее. Что для этого делает любой нормальный человек? Налаживает кэширование наиболее часто запрашиваемых данных. При этом, если хоть немного задуматься о перспективе, то размеры кэша необходимо ограничивать.
Для простоты реализации в случае Питона сделаем ограничение по числу элементов в кэше (здесь предполагается, что данные более-менее однородны по размеру, а также учитывается специфика, что определить объём памяти, реально занимаемый каким-либо Питоновским объектом — весьма нетривиальная задача, кому интересно, пусть пожалует сюда), а для того, чтобы кэш содержал как можно более часто используемую информацию — построим его по принципу least recently used, т.е. чем более давно запрашивали кусочек информации, тем больше у него шансов «вылететь» из кэша.

О двух решениях (попроще и посложнее) я и расскажу в этой статье.

Философское отступление


Я обратил внимание, что зачастую написанный на Питоне код не блещет оптимизациями по потреблению памяти или по скорости (здесь можно вскользь заметить, что это не только вина программистов-пользователей языка, хорошего инструментария просто нет, или по крайней мере я о таком не знаю (да, я в курсе про cProfile, но он помогает далеко не всегда, например, в нём нет attach-detach; искать же утечки памяти — вообще занятие не для слабонервных, вот если pympler допилят...), если кто подскажет — буду благодарен). В основном это даже правильно, так как обычно Питон применяют в случае, когда время исполнения программы или потребление памяти не критично, зато критично время написания кода и простота его дальнейшей поддержки, поэтому очевидное, пусть и менее экономичное решение будет удобнее.
Хотя вышесказанное совсем не означает, что любой код на Питоне нужно писать «абы как». Кроме того, иногда производительность и потребление памяти могут стать критичными, даже если код крутится на серверной машине с хорошим процессором и тоннами памяти.
Как раз такой случай (нехватка CPU time) и подвиг меня на исследование этого вопроса и замену одного кэширующего класса другим.

Простое решение


Часто говорят — «простое решение — самое верное», хотя в случае с программированием это далеко не всегда так, не правда ли? Однако, если есть задача обеспечения кэша, но нет особых требований к скорости (например, то, что использует этот кэш, само по себе очень медленное, и нет смысла вкладываться в сложную реализацию), то можно обойтись и тривиальными решениями.

Реализация

Итак, относительно простое решение:
import weakref
class SimpleCache:
    def __init__(self, cacheSize):
        self.cache = weakref.WeakValueDictionary()
        self.cache_LRU = []
        self.cacheSize = cacheSize

    def __getitem__(self, key):
        # no exception catching - let calling code handle them if any
        value = self.cache[key]
        return self.touchCache(key, value)

    def __setitem__(self, key, value):
        self.touchCache(key, value)

    def touchCache(self, key, value):
        self.cache[key] = value
        if value in self.cache_LRU:
            self.cache_LRU.remove(value)
        self.cache_LRU = self.cache_LRU[-(self.cacheSize-1):] + [ value ]
        return value


Использование

Работать с таким кэшем после создания можно, как с обычным dict-ом, но при чтении/записи элемента он будет помещён в конец очереди, а за счёт комбинации WeakValueDictionary() и списка, который хранит не более cacheSize элементов, мы получаем ограничение по количеству сохранённых данных.
Таким образом, после исполнения куска кода
cache = SimpleCache(2)
cache[1] = 'a'
cache[2] = 'b'
cache[3] = 'c'

в кэше останутся только записи 'b' и 'c' ('a', как самая старая, будет вытеснена).

Преимущества и недостатки

Преимущество — относительная простота (около 20 строк кода, после прочтения документации по WeakValueDictionary принцип работы становится понятен).
Недостаток — скорость работы, т.к. при каждом «касании» кэша приходится пересоздавать список целиком, удаляя из произвольного его места элемент (на самом деле там происходит аж целая куча длинных операций по работе со списком, так, «if value in self.cache_LRU» — линейный поиск по списку, потом .remove() — ещё раз линейный поиск, потом ещё берётся срез — т.е. создаётся почти полная копия списка). Словом, относительно долго.

Сложное решение


Теперь вдумаемся — а как можно ускорить такой класс? Очевидно, основные проблемы у нас именно с поддержанием cache_LRU в актуальном состоянии — как я уже говорил, поиск по нему, последующее удаление элемента и пересоздание — дорогие операции. Тут нам на помощь придёт такая вещь, как двунаправленный связный список — он обеспечит нам поддержку «последний использованный — в конце», ну а WeakValueDictionary() поможет с быстрым поиском по этому списку (поиск по словарю идёт куда быстрее линейного перебора, поскольку внутри Питоновские словари реализуют что-то вроде бинарных деревьев по хешам ключей (тут Остапа понесло — могу честно сказать, что в исходники не смотрел, поэтому только предполагаю, как именно устроен поиск по словарю)

Реализация

Для начала создаём класс — элемент списка, в который будем оборачивать хранимые данные:
    class Element(object):
        __slots__ = ['prev', 'next', 'value', '__init__', '__weakref__']
        def __init__(self, value):
            self.prev, self.next, self.value = None, None, value

Тут надо заметить использование такой штуки, как __slots__, позволяющей существенно сэкономить память и немного — производительность по сравнению с такой же реализацией класса, но без этого атрибута (что это такое и с чем его едят — в официальной документации).
Теперь создаём класс кэша (класс элемента засунем внутрь «во избежание»):
import weakref
class FastCache:
    class Element(object):
        __slots__ = ['prev', 'next', 'value', '__init__', '__weakref__']
        def __init__(self, value):
            self.prev, self.next, self.value = None, None, value

    def __init__(self, maxCount):
        self.dict = weakref.WeakValueDictionary()
        self.head = None
        self.tail = None
        self.count = 0
        self.maxCount = maxCount

    def _removeElement(self, element):
        prev, next = element.prev, element.next
        if prev:
            assert prev.next == element
            prev.next = next
        elif self.head == element:
            self.head = next

        if next:
            assert next.prev == element
            next.prev = prev
        elif self.tail == element:
            self.tail = prev
        element.prev, element.next = None, None
        assert self.count >= 1
        self.count -= 1

    def _appendElement(self, element):
        if element is None:
            return
        element.prev, element.next = self.tail, None
        if self.head is None:
            self.head = element
        if self.tail is not None:
            self.tail.next = element
        self.tail = element
        self.count += 1

    def get(self, key, *arg):
        element = self.dict.get(key, None)
        if element:
            self._removeElement(element)
            self._appendElement(element)
            return element.value
        elif len(*arg):
            return arg[0]
        else:
            raise KeyError("'%s' is not found in the dictionary", str(key))

    def __len__(self):
        return len(self.dict)

    def __getitem__(self, key):
        element = self.dict[key]
        # At this point the element is not None
        self._removeElement(element)
        self._appendElement(element)
        return element.value

    def __setitem__(self, key, value):
        try:
            element = self.dict[key]
            self._removeElement(element)
        except KeyError:
            if self.count == self.maxCount:
                self._removeElement(self.head)
        element = FastCache.Element(value)
        self._appendElement(element)
        self.dict[key] = element
        
    def __del__(self):
        while self.head:
            self._removeElement(self.head)

Тут можно обратить внимание на следующие существенные/интересные моменты:
  • реализация метода get() — слегка отличается от стандартной для словарей, т.к. если не задано значение по умолчанию, а ключ отсутствует, то выкидывает исключение (работает так же, как cache[key]), а если есть значение по умолчанию, то возвращает его
  • наличие метода __del__ обязательно, в противном случае получаем (или можем получить) утечку всего кэша — ведь все элементы списка друг на друга ссылаются, значит, их счётчики ссылок никогда не обнулятся без посторонней помощи; кстати, как выяснилось, встроенный (по крайней мере в 2.6) garbage collector хоть и вроде как собирает простейшие циклы ссылок, но с этим списком не справляется
  • при желании можно слегка поднять производительность, выкинув assert'ы

Использование

Полностью аналогично предыдущей реализации (да и логика внутри похожа, только использует не простой, встроенный в Питон тип list, а реализует свой двунаправленный список с шахматами и поэтессами).

Ещё одно простое решение с хорошей производительностью


Спасибо seriyPS за подсказку!
Вырисовалось ещё одно решение, которое выглядит так же просто, как первое (если даже не проще) и при этом работает почти так же быстро, как сложное. Итак, реализация:
from collections import OrderedDict
class ODCache(OrderedDict):
    def __init__(self, cacheSize):
        self.cacheSize = cacheSize
        OrderedDict.__init__(self)

    def __getitem__(self, key):
        value = OrderedDict.__getitem__(self, key)
        return self._touchCache(key, value)

    def __setitem__(self, key, value):
        self._touchCache(key, value)

    def _touchCache(self, key, value):
        try:
            OrderedDict.__delitem__(self, key)
        except KeyError:
            pass
        OrderedDict.__setitem__(self, key, value)
        toDel = len(self) - self.cacheSize
        if toDel > 0:
            for k in OrderedDict.keys(self)[:toDel]:
                OrderedDict.__delitem__(self, k)
        return value


Ещё одно решение — хорошая производительность


Решение из комментариев (по использованным мной тестам — лидер по скорости), спасибо tbd:
class ListDictBasedCache(object):
    __slots__ = ['__key2value', '__maxCount', '__weights']
    def __init__(self, maxCount):
        self.__maxCount = maxCount
        self.__key2value = {}# key->value
        self.__weights = []# keys ordered in LRU

    def __updateWeight(self, key):
        try:
            self.__weights.remove(key)
        except ValueError:
            pass
        self.__weights.append(key)# add key to end
        if len(self.__weights) > self.__maxCount:
            _key = self.__weights.pop(0)# remove first key
            self.__key2value.pop(_key)

    def __getitem__(self, key):
        try:
            value = self.__key2value[key]
            self.__updateWeight(key)
            return value
        except KeyError:
            raise KeyError("key %s not found" % key)

    def __setitem__(self, key, value):
        self.__key2value[key] = value
        self.__updateWeight(key)

    def __str__(self):
        return str(self.__key2value)


Сравнение


Голословные утверждения — это одно, а беспристрастные цифры — совсем другое. Поэтому я не призываю верить мне на слово, наоборот — измерим эти классы!
Тут нам на помощь приходит встроенный в Питон модуль timeit:
class StubClass:
    def __init__(self, something):
        self.something = something

def testCache(cacheClass, cacheSize, repeat):
    d = cacheClass(cacheSize)
    for i in xrange(repeat * cacheSize):
        d[i] = StubClass(i)

import random
class testCacheReadGen:
    def __init__(self, cacheClass, cacheSize):
        d = cacheClass(cacheSize)
        for i in xrange(cacheSize):
            d[i] = StubClass(i)
        self.d = d
        self.s = cacheSize

    def __call__(self, repeat):
        cacheSize, d = self.s, self.d
        for i in xrange(cacheSize * repeat):
            tmp = d[random.randint(0, cacheSize-1)]

def minMaxAvg(lst):
    return min(lst), max(lst), 1.0 * sum(lst) / len(lst)
    
import timeit
def testAllCaches(classes, cacheSize, repeats):
    templ = '%s: min %.5f, max %.5f, avg %.5f'
    genmsg = lambda cls, res: templ % ((cls.__name__.ljust(20),) + tuple(minMaxAvg(res)))
    for cls in classes:
        t = timeit.Timer(lambda: testCache(cls, cacheSize, repeats[0]))
        print genmsg(cls, t.repeat(*repeats[1:]))

def testAllCachesRead(classes, cacheSize, repeats):
    templ = '%s: min %.5f, max %.5f, avg %.5f'
    genmsg = lambda cls, res: templ % ((cls.__name__.ljust(20),) + tuple(minMaxAvg(res)))
    for cls in classes:
        tst = testCacheReadGen(cls, cacheSize)
        t = timeit.Timer(lambda: tst(repeats[0]))
        print genmsg(cls, t.repeat(*repeats[1:]))

if __name__ == '__main__':
    print 'write'
    testAllCaches((SimpleCache, FastCache, ODCache, ListDictBasedCache), 100, (100, 3, 3))
    print 'read'
    testAllCachesRead((SimpleCache, FastCache, ODCache, ListDictBasedCache), 100, (100, 3, 3))


Результаты запуска на моей машине (Intel Core i5 2540M 2.6GHz, Win7 64-bit, ActivePython 2.7.2 x64-bit):
write
SimpleCache         : min 9.36119, max 9.49077, avg 9.42536
FastCache           : min 0.39449, max 0.41835, avg 0.40880
ODCache             : min 0.79536, max 0.82727, avg 0.81482
ListDictBasedCache  : min 0.25135, max 0.27334, avg 0.26000
read
SimpleCache         : min 9.61617, max 9.73143, avg 9.66337
FastCache           : min 0.19294, max 0.21941, avg 0.20552
ODCache             : min 0.22270, max 0.25816, avg 0.23911
ListDictBasedCache  : min 0.16475, max 0.17725, avg 0.16911

Разница между простым и сложным решениями довольно ощутима — порядка 20 раз! Решение на OrderedDict чуть отстаёт в плане производительности, но совсем незначительно. Для дальнейших выводов нужно делать более сложные измерения, отражающие особенность задачи кэша — быстрый доступ к произвольным кусочкам информации, а не некоторый линейный, как использовался выше.

По потреблению памяти — запускаем предыдущий скрипт с другой секцией main и смотрим потребление памяти интерпретатором Питона через диспетчер задач:
if __name__ == '__main__':
    import time
    print 'measure me - no cache'
    try:
        while True:
            time.sleep(10)
    except:
        # let user interrupt this with Ctrl-C
        pass
    testCache(FastCache, 1000, 1)
    print 'measure me - cached'
    while True:
        time.sleep(10)
    exit()

Результаты измерений — в таблице:
Класс кэша до создания кэша после создания кэша потребление кэша
SimpleCache 4228K 4768K 540K
FastCache 4232K 4636K 404K
ODCache 4496K 4936K 440K
ListDictBasedCache 4500K 4880K 380K

Как видим — сложное решение не только заметно быстрее (в ~20 раз) добавляет элементы, но и потребляет немного меньше памяти, чем простое.

В той конкретной задаче, которую я решал, создавая такой кэш, его замена позволила сократить время отдачи запроса с 90 секунд до 70 примерно (более плотная профилировка и переписывание почти всей логики генерации ответа потом помогла довести время ответа до 30 секунд, но это уже совсем другая история).
Tags:
Hubs:
+18
Comments 11
Comments Comments 11

Articles