Log in

No account? Create an account
Fun with genetic algorithms... - brad's life — LiveJournal [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Fun with genetic algorithms... [Jun. 1st, 2003|07:20 pm]
Brad Fitzpatrick
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.

[User Picture]From: toast
2003-06-01 11:25 pm (UTC)
I'm sure linear algebra could have helped me, but I thought it'd be more fun to make a genetic algorithm.

Reminds me of a quote: "Genetic algorithms are the second best solution to every problem."
(Reply) (Thread)
[User Picture]From: edm
2003-06-02 04:39 am (UTC)

Building a machine to....

Reminds me of a quote: "Genetic algorithms are the second best solution to every problem."

But they're such a cool "build a robot to tidy my room" solution. Every geek should have one.

More seriously, Brad, if you know exactly the size of the objects you're caching (and it sounds like you mostly do), why not just have a bunch of specialised allocators for those that simply work with large chunks of raw storage (obtained from malloc() or mmap(), or brk()). (If you're using C++ you can overload the allocators for most containers to get it to use your specialised per-class allocator automatically. If you're using C, you'll have to track it yourself (eg, allocate_foo_memory()).

And if you want to generalise it, why not read the info in from a config file on startup? (It wouldn't be that hard to build specialised allocators that got their marching instructions from a central table, read on startup.) Or for that matter, code generation of the specialised allocators. (Code generation is such a cool toy. Every geek should have some. :-) )

(Reply) (Parent) (Thread)
[User Picture]From: brad
2003-06-02 07:59 am (UTC)

Re: Building a machine to....

That's what we do.
(Reply) (Parent) (Thread)
From: equally_diverse
2003-06-02 01:07 am (UTC)


What has it been...about a week since you thought up memcached? And already you've got it almost perfect? Pure genius, Brad. Keep up the good work dude.

BTW, over how long a period of time is that output?
(Reply) (Thread)
[User Picture]From: brad
2003-06-02 01:24 am (UTC)

Re: Jeez.

Well, avva did a lot of the work. And I got good pointers from lots of people.
(Reply) (Parent) (Thread)
[User Picture]From: taral
2003-06-02 11:11 am (UTC)
I thought you said the malloc problems were caused by mlockall()?

You may want to look at a compacting heap allocator instead of slabs if your objects really are variable-sized.
(Reply) (Thread)
[User Picture]From: brad
2003-06-02 11:21 am (UTC)
Ironically (since I'm talking to you), the problem was an IBM ServRAID controller crashing the machine. I just thought it was mlockall since that was the first time we'd used it.

The machine hasn't crashed in a while, so I think the firmware upgrade did the trick. We'll see.

The malloc problems were caused by fragmentation, though. All our objects are variable-sized.

A compacting heap allocator might be the way to go, but slab classes works pretty well for now. It would be nice for full memory utilization, but I'll put it off for now.
(Reply) (Parent) (Thread)