Brad Fitzpatrick (brad) wrote,
Brad Fitzpatrick
brad

Fun with genetic algorithms...

I was going to finish the memcached website today, and I probably will later, but first I wanted to play with optimizing the slab sizes for LJ's usage.

The first version of memcached used malloc for everything. Once the virtual address space was totally full and unfrequently accessed items started being removed, the address space got extremely fragmented and glibc's malloc eventually fell over and died, eating 99% CPU looking for space that wasn't contiguously there.

The solution, as suggested by ff, was to move to using a set of slab caches, each a different size. The most obvious set of sizes were the powers of two.

Unfortunately, that set (while flexible for any random input) resulted in a 30% waste of memory for LJ's usage pattern. If you're storing a 94 byte item and the only slab size available is of 128 byte items, you're wasting 34 bytes. If there are 232530 of them, you've lost 7.5 of memory in your cache. Why not have a slab size of 96 bytes?

So basically the problem is: given the item size distribution from a live cache, which set of, say, 15 slab class sizes produces the least waste for that distribution?

I'm sure linear algebra could have helped me, but I thought it'd be more fun to make a genetic algorithm.

Starting with the 5 copies of the powers-of-two set, I took each candidate in the list, randomly mutated one element (moving it somewhere between its neighbors, on a 4 byte alignment), and put it on the list. Then, I ran the waste() heuristic on each candidate, both old and new, and threw away the bad ones.

Then the algorithm starts anew, always mutating, calculating, and discarding.

While the memory utilization started out at 70%, it doesn't take long for it to climb to over 80%:

(70.51%) -- [64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576]
(70.62%) -- [120,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576]
(70.64%) -- [120,128,256,512,936,2048,4096,8192,15524,32768,65536,131072,262144,524288,1048576]
(70.74%) -- [64,128,256,544,1024,2048,4096,7328,16384,32768,65536,131072,262144,524288,1048576]
(71.41%) -- [64,128,256,764,1024,2048,4096,7328,16384,32768,65536,131072,262144,524288,1048576]
(71.74%) -- [64,128,256,724,1024,2048,4096,7328,16384,32768,65536,131072,262144,524288,1048576]
(71.75%) -- [44,128,256,724,1024,2048,4096,7492,16384,32768,65536,131072,262144,524288,1048576]
...
(78.48%) -- [96,104,256,704,1220,1988,3200,4800,7016,10068,17784,27820,40668,85740,1048576]
(78.50%) -- [96,104,256,704,1220,1988,3200,4800,7016,10440,17632,28568,42236,85740,1048576]
(78.50%) -- [96,104,256,704,1220,1988,3200,4800,7016,10640,17632,28568,42236,85740,1048576]
(78.58%) -- [96,100,256,704,1220,1988,3200,4800,7016,10640,17632,28568,42236,85740,1048576]
(78.59%) -- [96,100,256,704,1220,1988,3200,4800,7016,10640,17436,28568,42236,85740,1048576]
...
(79.13%) -- [96,100,256,704,1216,1956,2912,4448,6596,10152,15468,20684,34540,72048,1048576]
(79.17%) -- [96,100,256,704,1216,1956,2912,4448,6596,10152,15468,22288,34540,72048,1048576]
(79.19%) -- [96,100,256,704,1216,1956,2912,4448,6596,10116,13820,20684,34696,72048,1048576]
(79.21%) -- [96,100,256,704,1220,1824,2912,4448,6568,9644,13520,20860,32228,72048,1048576]
(79.26%) -- [96,100,256,704,1216,1928,2912,4448,6596,9536,13820,20684,33676,72048,1048576]
...
(80.08%) -- [96,100,256,736,1152,1764,2436,3400,5036,7260,11044,18696,33164,65876,1048576]
(80.10%) -- [96,100,256,736,1152,1632,2436,3400,5036,7260,11044,18696,33164,65876,1048576]
(80.11%) -- [96,100,256,736,1152,1700,2436,3400,5036,7260,11044,18696,33164,65876,1048576]
(80.15%) -- [96,100,256,736,1152,1700,2436,3400,4740,7260,11044,18696,33164,65876,1048576]
...
(80.30%) -- [96,160,288,736,1216,1760,2496,3504,4932,6944,11184,17260,32112,66640,1048576]
(80.31%) -- [96,160,288,736,1216,1760,2496,3504,4932,6944,11184,17260,31848,66640,1048576]
(80.32%) -- [96,160,288,736,1184,1760,2496,3504,4932,6944,11184,17260,32112,66640,1048576]
(80.32%) -- [96,160,288,736,1216,1760,2496,3392,4932,6944,11184,17260,31848,66640,1048576]
(80.34%) -- [96,160,288,736,1216,1760,2496,3504,4932,6944,10636,17260,31848,66640,1048576]
(80.36%) -- [96,160,288,736,1216,1760,2496,3392,4932,6944,10404,17260,31848,66640,1048576]
(80.46%) -- [96,160,288,736,1152,1696,2432,3456,4868,6944,10404,16772,30668,66640,1048576]
(80.47%) -- [96,160,288,736,1152,1696,2432,3456,4868,6944,10404,16772,30496,66640,1048576]
(80.48%) -- [96,160,288,736,1152,1696,2432,3456,4768,6944,10404,17260,31116,65776,1048576]

I'm still not totally happy with the breeding behavior. I see it get stuck in places for periods of time. I think I want to have it do multiple breeding lines that merge every so often.

Also, know that I know the maxium size of an object in the LJ memcache is just over 64k, I think I'll remove the 1MB max object constraint from the algorithm so it can use more buckets and see if that helps.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments