fatcache - Memcache on SSD

https://github.com/twitter/fatcache

by buttscicles • 13 years ago

175 54 13 years ago

github.com

jonemo• 13 years ago

If you find this interesting, you might also find this article in Communications of the ACM interesting:

Michael Cornwell: Anatomy of a Solid-State Drive

Communications of the ACM, Vol. 55 No. 12, Pages 59-63

http://cacm.acm.org/magazines/2012/12/157869-anatomy-of-a-so...

Alternative link in case the first is paywalled for people not on a university campus: http://queue.acm.org/detail.cfm?id=2385276

It goes into quite some detail on how SSD storage works on a system level and how it differs from hard disks.

benaiah2• 13 years ago

This is insane.

Awesome, useful, and cool, but insane.

I like it.

throwaway54-762• 13 years ago

No, it's pretty sane. I work at a well-known NAS storage-appliance vendor and we're doing something quite similar in-kernel as a caching layer for our filesystem.

benaiah2• 13 years ago

When I said "insane", I meant more "this is not something you would expect or that is immediately obvious". My phrasing wasn't the finest.

cowmix• 13 years ago

The README says that memory is 1000s of times faster than SSD.

With that, how much faster is SSD over disk and then memory over SSD?

cdvonstinkpot• 13 years ago

This whitepaper goes into some detail about how/why to use SSDs as cache in a zfs fileserver: http://info.nexenta.com/rs/nexenta/images/white_paper_nexent...

wmf2• 13 years ago

Latency Numbers Every Programmer Should Know: https://gist.github.com/jboner/2841832 discussion: http://news.ycombinator.com/item?id=4047623

DRAM (~100 ns) is very nearly 1000x better latency than SSD (~70 us) which is only 100x faster than disk (~10 ms).

rorrr• 13 years ago

Actually, modern SSDs have lower latency than 70 microseconds:

26 microseconds for OCZ Vertex 4 (reads)

http://thessdreview.com/our-reviews/ocz-vertex-4-128gb-ssd-r...

No more than 20 microseconds for Corsair Neutron GTX and Vertex 4 (writes):

http://www.storagereview.com/samsung_ssd_840_pro_review

sigil3• 13 years ago

Curious, why not just use an mmapped file for the store a la varnish? If the file lived on the SSD you'd get in-memory caching for free from the OS.

zellyn• 13 years ago

They shape their reads and writes to work well with SSD characteristics. Randomly reading and writing to an SSD (whether directly or through mmap) would be slower and wear out the SSD more quickly.

peter_l_downs• 13 years ago

Just to further illustrate your point, the relevant section from the readme file:

    There have been attempts to use an SSD as a swap layer to implement SSD-backed
    memory. This method degrades write performance and SSD lifetime with many small,
    random writes. Similar issues occur when an SSD is simply mmaped.
    
    To minimize the number of small, random writes, fatcache treats the SSD as a
    log-structured object store. All writes are aggregated in memory and written to
    the end of the circular log in batches - usually multiples of 1 MB.

parbo• 13 years ago

Shouldn't it be possible to make the linux kernel behave like this with the swap partition on SSD, to get this benefit for all programs?

hosay1234• 13 years ago

Modern SSDs simply don't work like this, they all internally use some variant of log-structured storage, such that regardless of the user's write pattern a single continuous stream is generated and only one method is needed to distribute modified pages across available flash. This means an infinite loop that rewrites the first 128kb of the device with random data will eventually fill (most of) the underlying flash with random data (128kb because that's a common erase block size).

juiceandjuice• 13 years ago

They actually use mmap internally.

sigil3• 13 years ago

They use MAP_ANONYMOUS, not a file-backed mmap.

https://github.com/twitter/fatcache/blob/master/src/fc_util....

thelarry• 13 years ago

Cool idea, I believe aeorspike uses ssd's for key value store like this. Check out http://www.aerospike.com/performance/architecture/ .

23david• 13 years ago

yep. Aerospike definitely had the first implementation of this kind of ssd-based architecture I'd heard of. Use ram only for hot caching and metadata. Use ssd's with custom filesystems for persistent storage. It's a good idea.

It's too bad most cloud providers consider SSD disks to be a 'premium' feature. I guess this would work fine on custom-configured hardware at places like softlayer and serverbeach.

wazoox2• 13 years ago

So apparently inventing your own SSD caching system is all the rage? We already had flashcache from Facebook : https://github.com/facebook/flashcache/ And bcache : http://bcache.evilpiepirate.org/

However this one isn't kernel-based, so it won't help your NFS server or your postgresql engine. On the other hand it's much easier to build.

wmf2• 13 years ago

Block devices and memcached are totally different; of course you're going to need different implementations for different APIs.

wazoox2• 13 years ago

However a block layer cache can enhance any kind of IO.

nwmcsween• 13 years ago

All these level caching systems work mostly on different layers, bcache deals with the block layer, flashcache deals with device mapper et al and so does enhanceio.

arielweisberg• 13 years ago

If you are willing to give up range scans and constrain yourself to fitting all keys in memory there is a lot you can do. See SILT (www.cs.cmu.edu/~dga/papers/silt-sosp2011.pdf) and Bitcask (downloads.basho.com/papers/bitcask-intro.pdf).

Since this is a cache I really dig skipping any kind of cleanup/compaction step for deleted/expired keys.

I played around with a similar thing except as a K/V store and the performance and density is pretty amazing. With a 64 byte key and 1.5k value (compressed from 2k) I was getting 85k inserts/sec and several hundred thousands reads/sec with a quad-core Sandy Bridge i5 and a 128 gigabyte Crucial M4 on SATAII.

silasb• 13 years ago

Wonder how much of the SATAII was the bottleneck, my guess is quite a lot. You should give your test another go with SATAIII.

justincormack2• 13 years ago

Fitting all keys in memory is a pretty harsh constraint though. With your 64byte to 1.5k you are talking about a factor of 20, so for a 1TB SSD you need 64GB RAM, which costs about as much as the SSD.

efuquen• 13 years ago

"so for a 1TB SSD you need 64GB RAM, which costs about as much as the SSD."

In my experience this is not true. A 1 TB SSD, even commodity hardware, is pretty expensive. And that's not even talking about high performance SSD's like Fusion IO, where you're now talking about 10K+. Where do you see 64 GB of RAM costing that much?

pornel• 13 years ago

> False positives from SHA-1 hash collisions are detected after object retrieval from the disk by comparison with the requested key

Is that check really necessary?

To have 1 in a trillion chance of having accidental SHA-1 collision they'd have to store 1.7*10^18 keys, and mere key index of that would require 54000 petabytes of RAM.

gcr• 13 years ago

Oversights now will ensure that we can't use this system when we have the capability of storing that many petabytes in RAM.

By then, maybe the founders of this system won't even be alive.

politician• 13 years ago

What are the odds of creating an intentional SHA-1 collision in a chosen plaintext situation?

Tuna-Fish• 13 years ago

Still hasn't been done.

gus_massa• 13 years ago

Comparing the sha-1 is much faster than reading the ssd, so it's almost free.

Accidental sha-1 collision is probably not a problem, but in a few years [1] it will be possible to crate sha-1 collisions and use that as an attack. It looks difficult, but supposes that with the correct string an attacker can retrieve the cached information of another user, for example sha1("joedoe:creditcard")=sha1("atacker:hc!?!=u?ee&f%g#jo").

I don't know if they are using randomization, because the collision can be used (in a few years) as a DOS atack [2]

[1] http://www.schneier.com/blog/archives/2012/10/when_will_we_s...

[2] http://www.gossamer-threads.com/lists/python/dev/959026

speakr• 13 years ago

Your example describes a preimage attack on SHA-1, not a collision attack. Even with a working collision attack you are probably still far away from taking "some.other.input" and creating a sha1("some.other.input") = sha1("johndoe:creditcard").

For instance MD5 collisions are really easy to create but for preimage attacks on MD5 there is still no better approach than just doing brute force.

shin_lao• 13 years ago

Smells like a bad idea, I agree. You have more chances to have a hardware error or system error that will cause your branch to be incorrectly executed than having an accidental SHA-1 collision. And if you're worried about SHA-1 collisions, use SHA-2 or even SHA-3.

tveita• 13 years ago

> False positives from SHA-1 hash collisions are detected after object retrieval from the disk by comparison with the requested key.

I was curious why they would bother, but it seems this isn't quite accurate.

What happens is they first use 32 bits from the SHA-1 hash to find the hash bucket, then they scan for the full SHA-1 of the key. They do not check for actual SHA-1 collisions.

edit: Also on the subject of hashes, the readme suggests switching to MD5 as a possible way to reduce entry size. That is unnecessary; SHA-1 can be truncated to whatever size you're comfortable with.

stcredzero• 13 years ago

Cool, but what I was envisioning when I came up with the term "fat cache" over a year ago was client-side. This seems to be server side, unless I've misunderstood.

http://news.ycombinator.com/item?id=3544522

prodigal_erik• 13 years ago

"Slab item chunk sizes" suggests they retained memcache's external fragmentation problem (if you mostly have big objects expiring, those slabs of memory won't ever be reused for storing small objects, or vice versa). On memcached with no persistence, you could recover from this by restarting (if you could withstand the availability hit), but what do you do once you're relying on long-lived state?

thinkingfish• 13 years ago

This is not an issue for fatcache. slab item chunk size introduces internal fragmentation (because items sizes usually don't match "chunk" sizes unless you use slab profile, -z option, to match them up). The kind of external fragmentation you described is due to the eviction strategy memcached uses, which can be avoided by using slab level eviction strategies (Twemcache and latest Memcached both have this support). fatcache does slab level eviction based on write timestamps, which is the equivalent of LRC eviction in Twemcache, and you can read about the mechanism here: https://github.com/twitter/twemcache/wiki/Eviction-Strategie...

valyala• 13 years ago

I believe go-memcached is faster than fatcache - https://github.com/valyala/ybc/tree/master/apps/go/memcached . Will return with performance numbers soon :)

fatcache - Memcache on SSD

Related Stories