valyala / Ybc

YBC - Yet another Blob Cache library.

This library implements fast in-process blob cache with persistence support.

===============================================================================

YBC features.

• Huge amounts of data can be cached. Cache size may exceed available RAM size by multiple orders of magnitude.

  • Very large objects may be cached (up to 2^64 bytes). Think of media files such as videos, audios and images.
  • Very large cache size is supported (up to 2^64 items and up to 2^64 bytes). In practice cache size is limited by free space on backing store, not by available RAM size.

• Persistence support. Cached objects survive process restart if the cache is explicitly backed by files.

• Data file layout is optimized for HDD and SSD devices. The code prefers sequential I/O instead of random I/O. If random I/O is inevitable, the code tries hard localizing it in the smallest possible memory region.

• Automatic robust recovery from corrupted index files. Corruptions in data files may be left unnoticed due to performance reasons - it may be quite expensive validating multi-GB blobs on every access.

• Built-in handling of dogpile effect (aka 'thundering herd').

• Cached objects may be sharded among available backing store devices. Such sharding may linearly increase cache performance if frequently accessed items don't fit available physical RAM.

• The library is thread-safe out of the box.

• Concurrent atomic updates. It is safe updating an item from multiple threads while other threads are reading old value for the item under the same key.

• 'Add transaction' support allows constructing object's value on the fly without serializing it into a temporary buffer (aka 'zero-copy'). Uncommited transaction can be rolled back at any time. Think of videos streamed directly into the cache without usage of temporary buffers or complex objects requiring serialization from multiple distinct places before storing them into the cache.

• Readers and writers don't block each other while reading/writing data from/into the cache. The speed is actually limited by hardware memory bandwidth (if frequently accessed items fit RAM) or backing store random I/O bandwidth (if requently accessed items don't fit RAM).

• Instant invalidation of all items in the cache irregardless of cache size.

• Optimization for multi-tiered memory hierarchy in modern CPUs. The code avoids unnecessary random memory accesses and tightly packs frequently accessed data in order to reduce working set size and increase CPU cache hit ratio.

• The code avoids using dynamic memory allocations in frequently executed paths, so cache performance is almost independent of the efficiency of the provided malloc() implementation.

• The code avoids using expensive system calls in frequently executed paths.

• The code depends only on OS-supplied libraries.

• The code can be easily ported to new platforms. All platform-specific functions and types are hidden behind platform-independent wrappers.

• Public interface (ybc.h) is designed with future versions' compatibility in mind. It doesn't expose private structures' contents, so they can be freely modified in the future versions of the library without breaking applications dynamically linked against older versions.

• Small library size (can be packed to 22Kb with -Os).

===============================================================================

Use-cases.

• CDN cache.

• File hosting cache.

• Memcache-like shared cache.

• Per-process local cache in web-servers.

• Web-proxy or web-accelerator cache.

• Web-browser cache.

• Out-of-GC blob cache for programming languages with GC support.

================================================================================

Credits.

YBC design is inspired by Varnish's "Notes from the Architect" - https://www.varnish-cache.org/trac/wiki/ArchitectNotes .

================================================================================

FAQ.

Q: Give me performance numbers! A: Well, YBC achieves 25.8 Mops/s for get() calls and 5.8 Mops/s for set() calls on my not-so-fast laptop with 2.50GHz Intel i5 CPU when running in 4 threads.

Q: Does YBC work with /dev/shm/ ? A: Yes. Just create data and index files on /dev/shm . This will completely eliminate page swapping at the cost of potential data loss on power failure or computer reboot.

Q: Is this yet another boring cache implementation? A: No. YBC is designed for modern OSes running on modern hardware. It takes advantage of OS's and computer's hardware features, while simultaneouly avoiding their weaknesses. This results in high performance and low resource usage. Read 'Features' chapter for more details.

Q: OK, how to use it in my program? A: 1. Investigate API provided by YBC at ybc.h . See tests/ folder for examples on how to properly use the API. 2. Use this API in your program. 3. Build either object file (ybc-[32|64]-[debug|release].o) or library (libybc-[debug|release].so) using the corresponding build target in the provided Makefile. 4. Link the object file or library against your program. 5. ????? 6. PROFIT!!!

Take a look also at bindings/ folder. It contains YBC bindings for various programming languages if you don't like programming in C. Though currently only Go is supported :)

Other folders also worth investigation: * libs/ folder contains additional libraries built on top of YBC. * apps/ folder contains applications built on top of YBC. Currently there are the following apps here with self-describing names: * cdn-booster - caching HTTP proxy implementation on top of Go bindings. * cdn-booster-bench - benchmark tool for HTTP/1.1-compliant servers. * memcached - memcache server implementation on top of Go bindings for YBC. Unlike the original memcache server, it supports cache sizes exceeding available RAM by multiple orders of magnitude. It also provides cache persistence, so cached data survives server restarts or server crashes. * memcached-bench - benchmark tool for memcached servers. Makefile already contains build targets for all these apps.

Q: Why recently added items may disappear from the cache, while their ttl isn't expired yet? A: Because YBC is a cache, not a storage. They serve different pruposes:

• Storage is used for items' persistence. It guarantees that added items exist until they are explicitly deleted.
• Cache is used as a performance booster. It doesn't guarantee that added items exist until they are explicitly deleted. YBC may delete any item at any time due to various reasons, which depend on implementation details. So always expect that the added item may disappear at any time during subsequent requests.

Q: Can YBC cache small items, not large blobs? A: Yes. YBC works well with small items - it even supports zero-byte key and zero-byte value.

Q: Why YBC cannot adjust backing files' size on-demand? I.e. automatically shrink files when the number of items in the cache is small and automatically expand files when the number of items exceeds current files' capacity. A: Because this is stupid idea due to the following reasons:

• If cache size isn't bound, then backing files may eat all the available space on storage devices.
• Automatic file size adjustment may significantly increase file fragmentation, which will lead to performance degradation.
• File size adjustment may lead to arbitrary long delays in requests' serving.
• This will complicate the implementation, which may result in more bugs.

Q: What's the purpose of cache persistence? A: Cache persistence allows skipping cache warm-up step ater the application restart. This step can be very expensive and time-consuming for large caches and slow backends. You can also make a 'golden' copy of a persistent cache and start every node in the application cluster using their own copy of the 'golden' cache, thus avoiding warm-up step on all nodes in the cluster.

Q: How well YBC performance scales on multiple CPUs? A: It scales perfectly if specially designed functions are used - ybc_config_disable_overwrite_protection(), ybc_simple_set() and ybc_simple_get().

Q: Are cache files platform-neutral? A: No. Cache files are tightly tied to the platform they were created. Cache files created on one platform (for example, x86) will be completely broken when read on another platform (for example, x64). Though it is likely they will appear as empty. So copy cache files only between machines with identical platforms.