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

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


Предположим, что у нас есть необходимость иметь некий сервис, который бы отдавал нам по запросу какую-либо информацию, и отдавал как можно быстрее. Что для этого делает любой нормальный человек? Налаживает кэширование наиболее часто запрашиваемых данных. При этом, если хоть немного задуматься о перспективе, то размеры кэша необходимо ограничивать.
Для простоты реализации в случае Питона сделаем ограничение по числу элементов в кэше (здесь предполагается, что данные более-менее однородны по размеру, а также учитывается специфика, что определить объём памяти, реально занимаемый каким-либо Питоновским объектом — весьма нетривиальная задача, кому интересно, пусть пожалует сюда), а для того, чтобы кэш содержал как можно более часто используемую информацию — построим его по принципу 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 секунд, но это уже совсем другая история).
Метки:
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 11
    • +1
      и результаты тестов (Linux x64 Python 2.7.3):
      Simple: min 1.85775, max 1.91843, avg 1.87948
      Fast: min 0.10335, max 0.10573, avg 0.10444
      Deque: min 0.00592, max 0.00609, avg 0.00598
      • 0
        Про collections я в курсе (особенно хорош там defaultdict).

        deque организует немного не ту модель — там быстрые добавление/удаление в любой из концов очереди.
        В описанном тут случае нужен быстрый случайный доступ (вместе с удалением из произвольного места, в т.ч. из середины, что в deque делается за O(N), а в приведённой реализации — за константное время).

        Правда, приведённые в статье измерения этого действительно не отражают :)

        Если я заблуждаюсь — буду рад увидеть хотя бы кусочек реализации, типа метода touchCache из первого класса.
        • 0
          хм, пожалуй тогда подойдет OrderedDict… попозже проверю
          • 0
            Сначала ответил немного мимо… В-общем, выходит, что OrderedDict здесь — почти идеал! :) Не сильно уступает в скорости работы сложному решению, легко читается и ест на порядок меньше памяти.

            Спасибо! :)
      • 0
        Похоже, collections.OrderedDict — это нечто среднее. По результатам моих проверок, работает почти так же быстро, как сложное решение, при этом выглядит гораздо читабельнее.

        Пожалуй, добавлю в статью.
        • 0
          вдогонку такая реализация кеша

          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)


          замеры на вашем тесте
          DictBasedCache: min 0.00702, max 0.00785, avg 0.00721
          FastCache: min 0.13259, max 0.13793, avg 0.13528
          ListDictBasedCache: min 0.07482, max 0.07965, avg 0.07638
          ODCache: min 0.16472, max 0.16917, avg 0.16693

          здесь для сравнения добавлен DictBasedCache для сравнения с обычным словарём
          class DictBasedCache(dict):
              def __init__(self, cacheSize):
                  self.cacheSize = cacheSize
                  dict.__init__(self)
          
          • 0
            Случайно ответил ниже
          • 0
            Во-первых, хранение ключ-значение в стандартном dict перерасходует память — этот список будет держать ссылки на объект, даже когда снаружи refcount станет равным нулю, и, пока кэш не переполнится, устаревшие (с точки зрения кода-пользователя кэша) данные не удалятся. В этом плане WeakValueDictionary лучше.

            А во-вторых — странные немного результаты. Как я выяснил — приведённая в статье реализация ODCache — нерабочая, и при рабочей реализации память оно ест на уровне остальных, а работает чуть медленнее FastCache. Измерения в статье не проверяют чтение из кэша совершенно.
            Кстати, надо обновить статью, привести там рабочий ODCache…

            Ваш вариант — это практически SimpleCache, приведённый в самом начале, разве что удаление элемента устроено лучше. Но дело в том, что операции pop() и remove() в принципе довольно дорогие — в случае с первой надо большой объём данных переместить, со второй — пробежаться (в худшем случае) до края массива, а это за линейное время.

            В общем мне кажется, что где-то в измерения закралась ошибка. Может быть, мал объём данных для тестов, или ещё чего… Надо будет подумать :)
            • 0
              Померил, пока это решение в лидерах… хотя я всё равно не понимаю, почему :) Возможно, потому, что list() реализован в нативном коде, а FastCache — чисто питоновский.
              • 0
                вообще решение я писал в лоб
                старался только минимум логики реализовывать на python'е и максимально использовать builtin объекты
                по сути оно так и вышло, на питоне только доступ к атрибутам и вызов методов

                что касается лишней памяти: я так думаю если вместо ключа хранить хэш инстанса ключа hash(key), то потери будут сильно меньше

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.