Single-server Level of Memcache

Introduction to the single server level

We'll improve certain aspects of Memcached by modifying its internal mechanisms for a single server. Memcached uses four main data structures to form a key-value store:

1. A Hash table

2. A Cache item data structure

3. A Slab allocator

4. A Least Recently Used (LRU) list

Hashtable with separate chaining

The hashtable uses hash functions to look up items using the key quickly. As illustrated below, the hashtable is an array of buckets, where each bucket is a linked list.

Memcached items

A Memcached item is an object that holds data for the key-value pair. This item is what we store in a single chunk. The item stores metadata like the max key length, time till expiration and more.

Slab allocator

The slab allocator is a memory management mechanism used to decrease memory fragmentation.

Slabs

Slabs are lists of memory sections containing objects (pages) categorized by the memory size range they fall into. By default, the memory is split into 42 slabs. The first slab is for items less than 96 bytes, the second is for items from 96 to 120 bytes, and so on until the 42^nd slab. The motivation to use these slabs is to reduce memory fragmentation as items of similar sizes are in the same slab, which leads to more efficient memory usage.

Pages

Slabs contain multiple pages, where each page is the size of ...