Многие знают что такое memcache и используют его в своих проектах. Но мало кто знает как он работает. Будут затронуты следующие особенности:
- Big-O
- LRU
- Memory allocation

Big-O

Большинство функций memcache (например, add, get, set, flush…) являются статическими по времени. Не важно сколько элементов в кэше, метод будет выполнятся столько времени, сколько бы он выполнялся если бы внутри кэша был только один элемент.  Использование такого подхода имеет свои преимущества (memcache остается быстрым) и недостатки — например, вы не можете перебрать все элементы в кэше. Для того, что бы это выполнить вам необходимо использовать некую функцию O(N), которая зависит от количества элементов. То есть, количество времени затраченного на данную операцию возрастет вдвое, если удвоить количество элементов кэша. Именно по этой причине memcache не поддерживает функциональность такого рода.

LRU алгоритм

Перед запуском memcached вы должны указать сколько памяти он будет использовать. ОС выделит необходимый объем памяти сразу после запуска, например, если вы хотите использовать 1GB памяти для хранилища, то ОС выделит 1GB только для memcached и эта память не сможет быть использована другими приложениями (apache, php…) Но из-за того, что мы ограничиваем количество памяти используемое приложением, рано или поздно наступит момент, когда все данные просто не будут помещаться в память. Что же делать в таком случае?

Как вы догадались — memcahce будет удалять старые данные, что бы освободить место для новых. Но ему нужно знать какие же объекты можно удалить. Можно удалить наибольший объект, таким образом мы сразу получим много места. Или можно удалять элементы по порядку их добавления в кэш и получить FIFO (First In, First Out) схему кэширования. Но, memcached использует гораздо более продвинутый метод, называемый LRU: Least Recently Used (наименее часто используемый). Иными словами, он вытесняет из памяти элементы которые не использовались наибольшее количество времени. А это не обязательно наибольший или первый сохраненный элемент.

Внутри все объекты имеют «счетчик». Этот счетчик хранит timestamp. Каждый раз, когда объект создается или запрашивается, в счетчик помещается текущее время. И как только memcached нужно вытеснить какой-то объект — он ищет объект с наименьшим показателем счетчика. Это может оказаться объект который вообще не запрашивался или который не запрашивался наибольший промежуток времени.

В результате получается простая система с очень эффективным использованием кэша.

Memory allocation

В прошлой статье была затронута эта тема. Вкратце все происходит таким образом: при запуске приложения с помощью метода malloc() ОС выделяет для приложения необходимый объем памяти, который демон заполняет по своему усмотрению. Для избежания фрагментации в memcached используется свой метод для хранения данных — Slab и Chunk.

Вся выделяемая память разбивается на блоки фиксированного размена (Slab), которые содержат в себе другие под-блоки (Chunk). Каждый Slab содержит в себе 1МБ / (Chunk size) Chunk’oв. По умолчанию, размер Chunk’ов начинается с 96 байт и дальше увеличивается с коэффициентом 1.25. Например, следующий размер будет 120 байт, далее — 152, 192…. и так до размера в 1МБ (размера всего Slab’а). Убедится в этом вы можете выполнив команду «memcached -vv -u nobody»:

slab class   1: chunk size        96 perslab   10922

slab class   2: chunk size       120 perslab    8738

slab class   3: chunk size       152 perslab    6898

slab class   4: chunk size       192 perslab    5461

slab class   5: chunk size       240 perslab    4369

slab class   6: chunk size       304 perslab    3449

…

Каждый Chunk в себе несет 48 байт которые используются для хранения ключей и флагов. То есть, Chunk размером 96 байт, будет содержать в себе максимум 48 байт пользовательских данных, 120 байт — 72 байта, и т.д. Это значение можно изменить, просто запустив memcache с параметром -n и указав количество байт выделяемое для ключей, флагов. Например, выполнив «memcached -vv -unobody -n 8″ получим:

slab class   1: chunk size        56 perslab   18724

slab class   2: chunk size        72 perslab   14563

slab class   3: chunk size        96 perslab   10922

slab class   4: chunk size       120 perslab    8738

slab class   5: chunk size       152 perslab    6898

slab class   6: chunk size       192 perslab    5461

….

После запуска, memcached инициирует создание по одной копии каждого класса Chunk’ов. Дальнейшее создание Slab’ов происходит только по требованию.

При помещении данных в кэш, демон будет выделять Slab со Chunk’ами наиболее подходящего размера. Для данных размеров в 96 байт будет выделен Chunk соответствующего размера, а для 100 байт будет выделена ячейка размером в 120 байт. Как видно мы получаем 20 байт не используемой памяти. Это не страшно, когда размер данных стремится к верхней границе, но что же делать если наоборот? В таком случае вы можете изменить коэффициент роста размера Slab во время запуска приложения с помощью опции -f. Например, при запуске такой командой «memcached -vv -unobody -f 2″ мы получим 14 классов Slab’ов, размер Chunk’ов в которых увеличивается в двое:

slab class   1: chunk size        96 perslab   10922

slab class   2: chunk size       192 perslab    5461

slab class   3: chunk size       384 perslab    2730

slab class   4: chunk size       768 perslab    1365

slab class   5: chunk size      1536 perslab     682

slab class   6: chunk size      3072 perslab     341

slab class   7: chunk size      6144 perslab     170

slab class   8: chunk size     12288 perslab      85

slab class   9: chunk size     24576 perslab      42

slab class  10: chunk size     49152 perslab      21

slab class  11: chunk size     98304 perslab      10

slab class  12: chunk size    196608 perslab       5

slab class  13: chunk size    393216 perslab       2

slab class  14: chunk size   1048576 perslab       1

Благодаря этой небольшой и нехитрой оптимизации мы можем более рационально использовать выделенную память.

Итог

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