Достаточно часто нам приходится хранить данные в [memcached](http://danga.com/memcached/) или [MemcacheDB](http://memcachedb.org/). Это могут быть относительно простые данные, например, закэшированные выборки из базы данных, а иногда необходимо хранить и обрабатывать более сложные структуры данных, которые обновляются одновременно из нескольких процессов, обеспечивать быстрое чтение данных и т.п. Реализация таких структур данных уже не укладывается в комбинацию команд memcached `get`/`set`. В данной статье будут описаны способы хранения некоторых структур данных в memcached с примерами кода и описанием основных идей. Memcached и MemcacheDB в данной статье рассматриваются вместе, потому что имеют общий интерфейс доступа и логика работы большей части структур данных будет одинаковой, далее будем называть их просто "memcached". Зачем нам нужно хранить структуры данных в memcached? Чаще всего для распределенного доступа к данным из разных процессов, с разных серверов и т.п. А иногда для решения задачи хранения данных достаточно интерфейса, предоставляемого MemcacheDB, и необходимость в использовании СУБД отпадает. Иногда проект разрабатывается изначально для нераспределенного случая (работа в рамках одного сервера), однако предполагая будущую необходимость масштабирования, лучше использовать сразу такие алгоритмы и структуры данных, которые могут обеспечить легкое масштабирование. Например, даже если данные будут храниться просто в памяти процесса, но интерфейс к доступа к ним повторяет семантику memcached, то при переходе к распределенной и масштабируемой архитектуре достаточно будет заменить обращения к внутреннему хранилищу на обращения к серверу (или кластеру серверов) memcached. Примеры кода будут написаны на Python, в них будет использоваться следующий интерфейс доступа к memcached:


class Memcache(object):
    def get(self, key):
        """
        Получить значение ключа.

        @param key: ключ
        @type key: C{str}
        @return: значение ключа
        @raises KeyError: ключ отсутствует
        """

    def add(self, key, value, expire=0):
        """
        Установить значение ключа, если он еще не существует.
    
        @param key: ключ
        @type key: C{str}
        @param value: значение ключа
        @param expire: "срок годности" ключа в секундах (0 - бесконечно)
        @type expire: C{int}
        @raises KeyError: ключ уже существует
        """

    def incr(self, key, value=1):
        """
        Увеличить на единицу значение ключа.

        @param key: ключ
        @type key: C{str}
        @param value: инкремент
        @type value: C{int}
        @return: новое значение ключа (после увеличения)
        @rtype: C{int}
        @raises KeyError: ключ не существует
        """

    def append(self, key, value):
        """
        Добавить суффикс к значению существующего ключа.
    
        @param key: ключ
        @type key: C{str}
        @param value: суффикс
        @raises KeyError: ключ не существует
        """

    def delete(self, key):
        """
        Удалить ключ.

        @param key: ключ
        @type key: C{str}
        """
Все наши структуры данных будут наследниками базового класса следующего вида:

class MemcacheObject(object):
    def __init__(self, mc):
        """"
        Конструктор.

        @param mc: драйвер memcached
        @type mc: L{Memcache}
        """
        self.mc = mc


## Блокировка ### Задача Блокировка (mutex, или в данной ситуации скорее spinlock) - это не совсем структура данных, но она может быть использована как "кирпичик" при построении сложных структур данных в memcached. Блокировка используется для исключения одновременного доступа к некоторым ключам, возможности блокировки отсутствуют в API memcached, поэтому она эмулируется с помощью других операций. Итак, блокировка определяется своим именем, работает распределённо (то есть из любого процесса, имеющего доступ к memcached), имеет автоматическое "умирание" (на случай, если процесс, поставивший блокировку, не сможет её снять, например, по причине аварийного завершения). Операции над блокировкой: * попробовать заблокироваться (try-lock); * разблокировать (unlock). ### Решение

class MCLock(MemcacheObject):
    def __init__(self, mc, name, timeout=5):
        """
        Конструктор.

        @param name: имя блокировки
        @type name: C{str}
        @param timeout: таймаут аварийного снятия блокировки (секунды)
        @type timeout: C{int}
        """
        super(MCLock, self).__init__(mc)
        self.key = 'lock_' + name
        self.locked = False
        self.timeout = timeout

    def try_lock(self):
        """
        Попробовать заблокироваться.

        @return: удалось ли заблокироваться?
        @rtype: C{bool}
        """
        assert not self.locked
        try:
            self.mc.add(self.key, 1, self.timeout)
        except KeyError:
            return False

        self.locked = True
        return True

    def unlock(self):
        """
        Снять блокировку.
        """
        assert self.locked
        self.mc.delete(self.key)
        self.locked = False


### Обсуждение Корректность работы блокировки основывается на операции `add`, которая гарантирует что ровно один процесс сможет "первым" установить значение ключа, все остальные процессы получат ошибку. Приведенный выше класс может быть обернут более удобно, например, для [with-обработчика Python](http://docs.python.org/reference/datamodel.html#context-managers). Более подробно вопрос блокировок обсуждался в посте про [одновременное перестроение кэшей](http://www.smira.ru/2008/10/28/web-caching-memcached-4/). ## Атомарный счетчик ### Задача Необходимо вычислять количество событий, которые происходят распределённо на разных серверах, также получать текущее значение счетчика. При этом счетчик не должен "терять" события и начислять "лишние" значения. Тип данных: целое число. Начальное значение: ноль. Операции: * увеличить значение счетчика на указанное значение; * получить текущее значение счетчика. ### Решение

class MCCounter(MemcacheObject):
    def __init__(self, mc, name):
        """
        Конструктор.

        @param name: имя счетчика
        @type name: C{str}
        """
        super(MCCounter, self).__init__(mc)
        self.key = 'counter' + name

    def increment(self, value=1):
        """
        Увеличить значение счетчика на указанное значение.

        @param value: инкремент
        @type value: C{int}
        """
        while True:
            try:
                self.mc.incr(self.key, value)
                return
            except KeyError:
                pass

            try:
                self.mc.add(self.key, value, 0)
                return
            except KeyError:
                pass

    def value(self):
        """
        Получить значение счетчика.

        @return: текущее значение счетчика
        @rtype: C{int}
        """
        try:
            return self.mc.get(self.key)
        except KeyError:
            return 0


### Обсуждение Реализация счетчика достаточно очевидная, самый сложный момент - это "вечный" цикл в методе `increment`. Он необходим для корректной инициализации значения счетчика в условиях конкурентного доступа к нему. Если операция `incr` завершилась ошибкой отсутствия ключа, нам необходимо создать ключ счетчика, но этот код могут одновременно выполнять несколько процессов, тогда одному из них удастся `add`, а второй получит ошибку и инкрементирует уже созданный счетчик с помощью `incr`. Зацикливание невозможно, т.к. одна из операций `incr` или `add` должна быть успешной: после создания ключа в memcached операция `incr` будет успешной всё время существования ключа. Как быть с ситуацией, когда ключ со счетчиком из memcached пропадет? Возможны две ситуации, когда ключ исчезнет: 1. memcached не хватает памяти для размещения других ключей; 2. процесс memcached аварийно завершился (сервер "упал"). (В случае MemcacheDB, настроенной репликации и т.п. падение сервера не должно приводить к потере ключей.) В первом случае надо лишь правильно обслуживать memcached - памяти должно хватать для счетчиков, иначе мы начинаем терять значения, а это неприемлемо в данной ситуации (но совершенно нормально, например, для хранения кэшей в memcached). Второй случай всегда возможен, если такая ситуация часто возникает, можно дублировать счетчики в нескольких memcached-серверах. ## Счетчик посетителей ### Задача Необходимо вычислить количество уникальных обращений к сайту в течение некоторого периода T. Например, T может быть равно 5 минутам. Пусть мы можем сказать, когда было последнее обращение данного посетителя к сайту - более T минут назад или менее (то есть является ли оно уникальным в течение периода T). Операции над счетчиком: * увеличить значение счетчика на единицу (обращение уникального в течение периода T посетителя); * получить текущее число посетителей. ### Решение

def time():
    """
    Текущее время в секундах с любого момента времени (например, UNIX Epoch).

    @return: текущее время в секундах
    @rtype: C{int}
    """


class MCVisitorCounter(MemcacheObject):
    def __init__(self, mc, name, T):
        """
        Конструктор.

        @param name: имя счетчика
        @type name: C{str}
        @param T: период счетчика, секунды
        @type T: C{int}
        """
        super(MCVisitorCounter, self).__init__(mc)
        self.keys = ('counter' + name + '_0', 'counter' + name + '_1')

    def _active(self):
        """
        Получить индекс текущего счетчика.

        @return: 0 или 1
        """
        return 0 if (time() % (2*T)) 



### Обсуждение



Работа счетчика посетителей



Основная структура работы со счетчиком в memcached в данной задаче повторяет решение задачи атомарного счетчика.

Базовая идея - использование теневого и текущего счетчика: теневой счетчик  получает обновления (увеличивается), а 

текущий используется для получения значения числа посетителей (его значение было накоплено, когда она был теневым).

Каждый период T текущий и теневой счетчик меняются местами. Ключ теневого счетчика создается со 

сроком годности 2*T секунд, то есть его время жизни - T секунд, пока он был теневым (и увеличивался), и Т секунд, пока

его значение использовалось для чтения. К моменту того, как этот ключ снова станет теневым счетчиком, он должен

быть уничтожен memcached, т.к. срок его годности истек. Идея теневого и текущего счетчика напоминает, например,

двойную буферизацию при выводе на экран в играх.



Необходимо обратить внимание на функцию `_active()`: она реализована именно через вычисление остатка от деления

текущего времени в секундах, а не, например, через периодическое (раз в Т секунд) смену значения `active`, т.к.

если время на всех серверах синхронизировано с разумной точностью, то и результат функции `_active()` будет на

всех серверах одинаковым, что важно для корректного распределенного функционирования данной структуры данных.



Описанный подход будет работать корректно только при достаточно большом количестве посетителей, когда временной интервал между

очередной сменой значения функции `_active()` и обращением к функции `increment()` будет как можно меньше. То есть

когда `increment()` вызывается часто, то есть когда посетителей достаточно много, например, 1000 человек при периоде Т=3 минуты. Иначе

создание и уничтожение ключей не будет синхронизировано с моментом смены значения `_active()` и начнут пропадать 

посетители, накопленные в теневом счетчике, который будет уничтожен в процессе накопления значений и 

создан заново. В этой ситуации его время жизни 2*T будет "сдвинуто" относительно моментов 0, T функции

time() % (2*T). В силу того, что memcached рассматривает срок годности ключей дискретно относительно секунд (с точностью не более одной секунды), 

любой сдвиг времени жизни ключа может составлять 1,2,...,T-1 секунду (отсутствие сдвига - 0 секунд). Дискретность

срока годности означает, что если ключ был создан в 25 секунд 31 миллисекунду со сроком годности 10 секунд,

то он будет уничтожен на 35-й (или 36-й) секунде 0 миллисекунд (а не 31-й миллисекунде). Для компенсация сдвига

в целое число секунд необходимо исправить строчку 43 примера следующим образом:



                self.mc.add(self.keys[1-active], 1, 2*T - time() % T)
Значение счетчика посетителей не изменяется в течение периода времени T, для более приятного отображения можно к значению счетчика при выводе добавить нормально распределенную величину с небольшой дисперсией и математическим ожиданием около 5% от значения счетчика. Немного более сложный вариант такого счетчика (с интерполяцией во времени), но с точно такой же идеей был описан в посте про [атомарность операции и счетчики в memcached](http://www.smira.ru/2008/10/24/web-caching-memcached-3). ## Лог событий ### Задача Задача этой структуры данных - хранение событий, произошедших в распределенной системе за последние T секунд. Каждое событие имеет момент времени, когда оно произошло, остальное содержимое события определяется логикой приложения. Операции над логом событий: * добавить сообщение в лог событий (должна быть максимально быстрой); * получить события, произошедшие в период времени от Tmin до Tmax (должна быть эффективной, но вызывается реже, чем добавление); ### Решение

def time():
    """
    Текущее время в секундах с любого момента времени (например, UNIX Epoch).

    @return: текущее время в секундах
    @rtype: C{int}
    """


class Event:
    """
    Событие, помещаемое в лог событий.
    """

    def when(self):
        """
        Момент времени, когда произошло событие (секунды).
        """

    def serialize(self):
        """
        Сериализовать событие.

        @return: сериализованное представление
        @rtype: C{str}
        """

    @static
    def deserialize(serialized):
        """
        Десериализовать набор событий.

        @param serialized: сериализованное представление одного 
                           или нескольких событий
        @type serialized: C{str}
        @return: массив десериализованных событий
        @rtype: C{list(Event)}
        """


class MCEventLog(MemcacheObject):
    def __init__(self, mc, name, timeChunk=10, numChunks=10):
        """
        Конструктор.

        @param name: имя лога событий
        @type name: C{str}
        @param timeChunk: емкость одного ключа лога в секундах
        @type timeChunk: C{int}
        @param numChunks: число выделяемых ключей под лог
        @type numChunks: C{int}
        """
        super(MCEventLog, self).__init__(mc)
        self.keyTemplate = 'messagelog' + name + '_%d';
        self.timeChunk = timeChunk
        self.numChunks = numChunks

    def put(self, event):
        """
        Поместить событие в лог.

        @param event: событие
        @type event: L{Event}
        """
        serialized = event.serialize()
        key = self.keyTemplate % (event.when() // self.timeChunk % self.numChunks)

        while True:
            try:
                self.mc.append(key, serialized)
                return
            except KeyError:
                pass

            try:
                self.mc.add(key, serialized, self.timeChunk * (self.numChunks-1))
                return
            except KeyError:
                pass

    def fetch(self, first=None, last=None):
        """
        Получить события из лога за указанный период (или все события).

        @param first: минимальное время возвращаемого сообщения
        @type first: C{int}
        @param last: максимальное время возвращаемого сообщения
        @type last: C{int}
        @return: массив событий
        @rtype: C{list(Event)}
        """
        if last is None or last > time():
            last = time()

        if first is None or last  self.timeChunk * (self.numChunks-1):
            first = time() - self.timeChunk * (self.numChunks-1)

        firstKey = first / self.timeChunk % self.numChunks
        lastKey = last / self.timeChunk % self.numChunks

        if firstKey = first and 
                                                e.when() 



### Обсуждение



Основная идея лога событий - кольцевой буфер, состоящий из `numChunks` ключей в memcached.

Каждый ключ активен (то есть дополняется значениями) в течение `timeChunk` секунд, после

чего активным становится следующий ключ (если активным был последний ключ, эта роль

переходит к первому ключу). Полный цикл буфера, т.е. период времени между двумя использованиями

одного ключа составляет `numChunks * timeChunk` секунд, а время жизни каждого ключа - 

`(numChunks - 1) * timeChunk` секунд, таким образом при любом сдвиге времени создания

ключа по модулю `timeChunk` к моменту времени следующего использования ключ гарантированно

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

сохраняются события) составляет `(numChunks - 1) * timeChunk` секунд. Такое разбиение

лога на ключи позволяет при получении событий из лога вынимать лишь

те ключи, которые соответствуют интересному нам временному отрезку.



Выбор параметров

`timeChunk` и `numChunks` зависит от применения лога событий: сначала определяется желаемый срок

хранения событий, затем по частоте событий выбирается такое значение `timeChunk`, чтобы размер

каждого ключа лога событий был относительно небольшим (например, 10-20Кб). Из этих соображений

можно найти значение и второго параметра, `numChunks`.



В примере используется некоторый класс `Event`, который обладает единственным интересным

для нас свойством - временем, когда произошло событие. В методе `put` лога событий предполагается,

что событие `event`, переданное в качестве параметра, произошло "недавно", то есть с момента

`event.when()` прошло не более чем `(numChunks - 1) * timeChunk` секунд (емкость лога). При

работе `put` вычисляется ключ, в который должна быть помещена информация о событии, в соответствие

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

к значению уже существующего ключа дописывается сериализованное представление события.



Метод `fetch` вычисляет потенциальный набор ключей лога, в которых могут находиться события,

произошедшие во временной интервал от `first` до `last`. Если временные рамки не заданы,

`last` считается равным текущему моменту времени, а `first` - моменту времени, отстоящему

от текущего на емкость лога. Набор ключей вычисляется с учетом кольцевой структуры метода,

после чего выбираются соответствующие ключи, десериализуются последовательно записанные

в них события и проводится дополнительная фильтрация на попадание в отрезок `[first, last]`.



Приведенная выше сигнатура метода позволяет последовательными обращениями выводить новые

события из лога:


 1. Первый раз вызывается `events = fetch()`. Вычисляется `lastSeen` как `max(events.when())`.
 2. Все последующие обращения выглядят следующим образом: `events = fetch(first=lastSeen)`, при этом
    `lastSeen` каждый раз перевычисляется.


## Массив



### Задача 1



В массиве хранится список значений произвольного типа, относительно редко происходит

обновление списка, гораздо чаще происходит получение списка целиком.



Операции над массивом:
 
 * изменить массив (редкая операция);
 * получить массив целиком (частая операция).


### Решение 1




def serializeArray(array):
    """
    Сериализовать массив в бинарное представление.
    """


def deserializeArray(str):
    """
    Десериализовать массив из бинарного представления.
    """


class MCArray1(MemcacheObject):
    def __init__(self, mc, name):
        """
        Конструктор.

        @param name: имя массива
        @type name: C{str}
        """
        super(MCArray1, self).__init__(mc)
        self.lock = MCLock(name)
        self.key = 'array' + name

    def fetch(self):
        """
        Получить текущее значение массива.

        @return: массив
        @rtype: C{list}
        """
        try:
            return deserializeArray(self.mc.get(self.key))
        except KeyError:
            return []

    def change(self, add_elems=[], delete_elems=[]):
        """
        Изменить значение массива, добавив или удалив из него
        элементы.
    
        @param add_elems: элементы, которые надо добавить
        @type add_elems: C{list}
        @param delete_elems: элементы, которые надо удалить
        @type delete_elems: C{list}
        """
        while not self.lock.try_lock():
            pass

        try:
            try:
                array = deserializeArray(self.mc.get(self.key))
            except KeyError:
                array = []
            array = filter(lambda e: e not in delete_elems, array) + add_elems
            self.mc.set(self.key, serializeArray(array), 0)
        finally:
            self.lock.unlock()


### Обсуждение 1 Приведенный выше способ решения на самом деле не имеет никакого отношения к массивам, а может быть применен для любой структуры данных. Он основан на модели reader-writer, когда есть много читателей и относительно мало писателей. Читатели в любой момент с помощью метода `fetch` получают содержимое массива, при этом важно, что "писатель" `сhange` записывает содержимое одной командой memcached, то есть в силу внутренней атомарности операций `get` и `set` в memcached и несмотря на отсутствие синхронизации между методами `fetch` и `сhange`, результат `fetch` всегда будет консистентным: это будет значение до или после очередного изменения. Писатели блокируются от одновременного изменения массива с помощью блокировки `MCLock`, описанной выше. В данной ситуации можно было бы избежать использования блокировки и воспользоваться командами `gets`, `cas` и `add` из протокола memcached для того, чтобы гарантировать атомарность изменений с помощью функции `change`. ### Задача 2 Массив хранит список значений некоторого типа, часто происходит операция вида "добавить значение в массив". Относительно редко массив запрашивается целиком. Для простоты реализации в дальнейшем будет рассматриваться массив целых чисел, хотя для решения задачи тип данных не имеет существенного значения. Операции над массивом: * добавить значение в массив (частая операция); * получить массив целиком. ### Решение 2

def serializeInt(int):
    """
    Сериализовать целое число в бинарное представление (str).
    """


def deserializeIntArray(str):
    """
    Десериализовать массив целых чисел из бинарного представления.
    """


class MCArray2(MemcacheObject):
    def __init__(self, mc, name):
        """
        Конструктор.

        @param name: имя массива
        @type name: C{str}
        """
        super(MCArray2, self).__init__(mc)
        self.key = 'array' + name

    def fetch(self):
        """
        Получить текущее значение массива.

        @return: массив
        @rtype: C{list}
        """
        try:
            return deserializeIntArray(self.mc.get(self.key))
        except KeyError:
            return []

    def add(self, element):
        """
        Добавить элемент в массив.

        @param element: элемент, который необходимо добавить в массив
        @type element: C{int}
        """
        element = serializeInt(element)
        while True:
            try:
                self.mc.append(self.key, element)
            except KeyError:
                return

            try:
                self.mc.add(self.key, element, 0)
            except KeyError:
                return


### Обсуждение 2 Эта реализация практически повторяет аналогичный код для лога событий, только упрощенный в силу наличия всего одного ключа. По сравнению с первым вариантом реализации типа данных "массив" уменьшилось число операций memcached, все изменяющие массив процессы могут выполняться без задержек (отсутствие блокировок). Как и в первом варианте, не проверяется наличие дубликатов при добавлении элемента в массив (может быть и хорошо, и плохо, в зависимости от применения). Возможны следующие улучшения (или расширения) описанного примера: * использование нескольких ключей для хранения массива вместо одного, распределение элементов по ключам с использованием хэширования; такой вариант позволит ограничить размер каждого ключа, при условии что массив большой (содержит много элементов); * реализация в том же стиле операции удаления элемента из массива, тогда массив можно представить как последовательность операций "удалить" и "добавить", например сериализованное представление `+1 +3 +4 -3 +5` будет после десериализации образовывать массив `[1, 4, 5]`; при этом как операция добавления элемента, так и удаления, будет приводить к дописыванию байт в конец сериализованного представления (атомарная операция `append`). ## Таблица ### Задача Необходимо хранить множество строк. Операции над множеством: * проверка принадлежности строки множеству (самая частая операция); * получение множества целиком, добавление элемента, удаление элемента - редкие операции. Можно рассматривать данную структуру данных как таблицу, в которой осуществляется быстрый поиск нужной строки. Или как хэш, хранящийся в распределенной памяти. ### Решение

def serializeArray(array):
    """
    Сериализовать массив в бинарное представление.
    """


def deserializeArray(str):
    """
    Десериализовать массив из бинарного представления.
    """


class MCTable(MemcacheObject):
    def __init__(self, mc, name):
        """
        Конструктор.

        @param name: имя таблицы
        @type name: C{str}
        """
        super(MCTable, self).__init__(mc)
        self.lock = MCLock(name)
        self.key = 'table' + name

    def has(self, key):
        """
        Проверка наличия ключа в таблице.
        
        @param key: ключ
        @type key: C{str}
        @rtype: C{bool}
        """
        try:
            self.mc.get(self.key + '_v_' + key)
            return True
        except KeyError:
            return False

    def fetch(self):
        """
        Получить целиком значение элементов таблицы.
   
        @return: значение таблицы
        @rtype: C{list(str)}
        """
        try:
            return deserializeArray(self.mc.get(self.key + '_keys'))
        except KeyError:
            pass

    def add(self, key):
        """
        Добавить ключ в таблицу.

        @param key: ключ
        @type key: C{str}
        """
        while not self.lock.try_lock():
            pass

        try:
            try:
                array = deserializeArray(self.mc.get(self.key + '_keys'))
            except KeyError:
                array = []
            if key not in array:
                array.append(key)
            self.mc.set(self.key + '_v_' + key, 1, 0)
            self.mc.set(self.key + '_keys', serializeArray(array), 0)
        finally:
            self.lock.unlock()

    def delete(self, key):
        """
        Удалить ключ из таблицы.

        Реализация аналогична методу add().
        """
### Обсуждение Вообще говоря memcached представляет собой огромную хэш-таблицу, правда в ней отсутствует одна операция, которая необходима для нашей структуры данных: получение списка ключей. Поэтому реализация таблицы использует отдельные ключи для хранения каждого элемента таблицы, и отдельно еще один ключ для хранения списка всех её элементов. Реализация хранения списка всех элементов фактически совпадает с реализацией "массива 1". Для сериализации доступа к списку всех элементов используется блокировка, при этом методы `fetch` и `add` не синхронизированы друг с другом, т.к. список всех элементов меняется атомарно и при чтении ключа мы всегда получим некоторое консистентное состояние. Проверка наличия ключа в таблице выполняется максимально быстро: проверяется наличие соответствующего ключа в memcached. Любое изменение списка элементов всегда происходит одновременно и в ключе, хранящем весь список, и в отдельных ключах для каждого элемента (которые используются только для проверки). На основе приведенной схемы можно реализовать полноценный хэш, когда для каждого элемента таблицы будет храниться связанное значение, это значение необходимо будет записывать только в отдельные ключи, соответствующие элементам, а список элементов не будет содержать значений. ## Заключение Итак, приведем список "приемов" или "трюков", описанных в данной статье: * атомарность операций с помощью memcached (пара `add`/`set` и т.п.); * блокировки; * теневые ключи; * кольцевой буфер с автоматическим "отмиранием" ключей; * блокировки и модель reader-writer. В статье не рассматривались вопросы оптимизации, специфичной для memcached, например, использование multi-get запросов. Это делалось сознательно, чтобы не перегружать исходный код и рассказ. Во многих ситуациях приведенные выше примеры следует рассматривать скорее как псевдокод, чем как пример идеальной реализации на Python. Если Вы нашли ошибку, хотите предложить более ясное, более оптимальное решение поставленным задачам, хотите предложить реализацию для какой-то еще структуры данных - буду рад комментариям и критике.