Memcached memory allocation and optimization

Database queries are fast. Extremely fast sometimes. Faster than almost anything. But – you knew it would come – they don’t stack up. More operations per second, more variation to the speed of the query. We need something that will offer a fast constant alternative. And that is a caching system.

I’m differentiating the caching system from the database caches because you can use it to store other different objects not specifically related to the database itself. When it comes to a web application, everything the user does since his arrival, every click, every mouse movement, every keystroke is a possible source of information and can be used to better improve his current and future visits. The web app gets to know you and acts accordingly. This information gets split into real-time database actions, delayed events, session and cached information, cookies and so on.

To put it simple, caching is a must. My favorite flavor (at least for now) is memcached.

How does memcached store objects?

First of all, memcached is an in-memory key-value store. Everything is stored into memory and gets accessed by a unique key. Now lets dig deeper.

Pre-allocation of memory on startup

Data is stored into memcached into slab classes. Each slab class contains pages. Each page gets filled with chunks. On startup a slab of each class is created filled with one page already divided into chunks.

Slabs, pages, chunks

A slab class is a collection of pages divided into same sized chunks. Each slab class is referenced to by its chunk size. So we’ll have Slab class 80kb, Slab class 100kb and so on. When an object needs to be stored, its size determines where it gets stored. So if the object is larger than 80kb but less than 100kb, it gets stored into Slab class 100kb.

Each slab class has one or more pages. The page is of a predefined size (default 1MB). So, depending on the chunk size each page has a certain number of chunks and some space left over wasted.

How do we control it all?

First of all, we get to set the min chunk size. That’s the first slab class. Then we set the growth factor. Lets say we have the min chunk size at 100kb. We set a growth factor of 3. The next slab class will be 100kb X 3. The following 300kb X 3. And so on.

We can also set the maximum page size. As I said earlier it defaults to 1MB and until recently it was a fixed value.

As an example, lets take the values above (I’ll round up some values to make the math easier). When memcached starts it will create 3 slab classes : A(100kb), B(300kb), C(900kb). Each slab class will have one page allocated and ready for objects.

A(100kb) : Page1 - can hold 10 objects (each having a size <= 100kb)
B(300kb) : Page1 - can hold 3 objects (each having a size >100kb and <=300kb)
C(900kb) : Page1 - can hold 1 object (each having a size >300kb)
---
Total space occupied : 3MB
Total space usable : 2,8MB

We just lost 0,2MB, without even storing an object. Every time a page from a slab is full (all chunks have objects stored inside) a new page is created. So every time a page is created into Slab B we lose 0.1MB and the same with Slab C. Also, every time an object is stored we lose space equal to the difference between the chunk size and the object size.

How do we optimize?

Lets start with a question which will decide our entire caching architecture. Will we be storing small objects or large objects?

Lets go with small. That probably means we need to start with a small min chunk size. Second we need to set a small growth factor. That will result in slab classes closer together as size. Max page size will have to be the largest object size we will permit.

The ideal situation is to have as little slab classes as possible and to determine the max page size as a multiple of your median object size.

Dealing with large objects is similar, probably your chunk size needs to be set at a higher value. But dealing with both small and large on the same configuration is not efficient.

The key to memcached optimization is to have the difference between your smallest object stored and your largest as low as possible.

You can always create different memcached clusters each storing a different group of objects (similar in size). It would be really interesting to have an automated distribution method of objects in a cluster based not only on key name but also on object size. Worth looking into it.

The value of a string

As I said earlier, memcached is a key-value store. Never underestimate the key when optimizing. I’ve used the term object when referring to the entity being stored into memcached. The object’s size is the size of the key + the size of the value.

Each character in your key = 1byte. Lets take a really common situation, sessions being stored into memcached. It’s pretty common to start sessions early, like when a user lands on your page. That session, when started and if nothing stored initially, is empty. The key used to tie that session to the application is some sort of hash. So for storing nothing you waste space.

Lets say we have 1 million objects stored. If we were to remove one character from each of those objects’ key name we would gain 1MB. Might not sound like a lot, but with a simple key renaming and prefix change I’ve seen gains of more than 10% in free space.

Memory full, LRU to the rescue

We’ve talked about how memcached stores objects. How about eviction? When memory gets full, so no pages can be created, the LRU (Least Recently Used) algorithm kicks in.

One thing to mention : memcached uses LRU per slab class, not globally. This is huge. Lets say we have one slab class with hot items : Slab A (100kb) and one class with more or less stale items : Slab X (500kb). Memory is full. A new 99kb objects comes in. The common sense thing to do is to kick an object from Slab X and free 500kb thus having more space for the hot items. Wrong. Memcached will leave the stale items as they are and kick one item from Slab A to make room for … 1 more item.

Give me tools, config files, actual settings

One great tool for monitoring your memcached cluster, seeing slabs, pages and diving into them and browsing objects is : phpmemcacheadmin. I highly recommend it for anyone playing around with memcached.

Other links (including links to the actual settings – which are just command line params for the daemon) :

man memcached
telnet commands

Happy caching!

Leave a Reply