memcache operations are mostly constant time, but their behavior is not what I would call deterministic due to the slab allocator. A long running memcached will

memcache operations are mostly constant time, but their behavior is not what I would call deterministic due to the slab allocator. A long running memcached will not behave the same as a fresh memcached because pages are not reclaimed from a particular slab class. Say you have a memcached that has been running and only storing 80 byte objects. The 80 byte slab class has all of the memory pages, and the other slab classes each have one page. Now your key size increases (for instance, because it includes the uid) and your objects fit into the 100 byte slab class. You will only be able to ever store 10,000 of these objects while the rest of your memory allocation is effectively unused. Not an obvious problem to diagnose. You can only fix it by restarting memcached (and losing everything) or (very slowly) migrating pages one at a time to the larger slab class. This anecdote is based on a true story. So your SET operation is still constant time, but the behavior is not deterministic. redis doesn't have this type of issue. I wish that I hadn't wasted so many years struggling with memcache.