blog.x.com Open in urlscan Pro
2606:4700:4400::6812:230a  Public Scan

Form analysis
0 forms found in the DOM

Text Content

Engineering Back
 * Engineering
 * Insights
 * Infrastructure
 * Open source

Sign Up
Sign Up



CACHING WITH TWEMCACHE

Tuesday, 10 July 2012

Link copied successfully

Update - July 11, 2012, 9:45am

We want to correct an error regarding the slab calcification problem we
mentioned in the original post. This problem only applied to our v1.4.4 fork of
Memcached; this correction is reflected below. The recent Memcached version has
addressed some of these problems.

We built Twemcache because we needed a more robust and manageable version of
Memcached, suitable for our large-scale production environment. Today, we are
open-sourcing Twemcache under the New BSD license. As one of the largest
adopters of Memcached, a popular open source caching system, we have used
Memcached over the years to help us scale our ever-growing traffic. Today, we
have hundreds of dedicated cache servers keeping over 20TB of data from over 30
services in-memory, including crucial data such as user information and Tweets.
Collectively these servers handle almost 2 trillion queries on any given day
(that’s more than 23 million queries per second). As we continued to grow, we
needed a more robust and manageable version of Memcached suitable for our large
scale production environment.

We have been running Twemcache in production for more than a year and a half.
Twemcache is based on a fork of Memcached v1.4.4 that is heavily modified to
improve maintainability and help us monitor our cache servers better. We
improved performance, removed code that we didn’t find necessary, refactored
large source files and added observability related features. The following
sections will provide more details on why we did this and what those new
features are.

Motivation

Almost all of our cache use cases fall into two categories:



 * as an optimization for disk where cache is used as the in-memory serving
   layer to shed load from databases.
 * as an optimization for cpu where cache is used as a buffer to store items
   that are expensive to recompute.


An example of these two optimizations is “caching of Tweets”. All Tweets are
persisted to disk when they are created, but most Tweets requested by users need
to be served out of memory for performance reasons. We use Twemcache to store
recent and frequently accessed Tweets, as an optimization for disk. When a Tweet
shows up in a particular client, it takes a particular presentation - rendered
Tweet - which has other metadata like number of retweets, favorites etc. We also
use Twemcache to store the recently rendered Tweets, as an optimization for cpu.

To effectively address the use cases mentioned above, it’s extremely important
that caches are always available and have predictable performance with respect
to item hit rate even when operating at full capacity. Caches should also be
able to adapt to changing item sizes on-the-fly as application data size grows
or shrinks over time. Finally, it is critical to have observability into caches
to monitor the health and effectiveness of our cache clusters. It turns out that
all these problems are interrelated because adapting to changing item sizes
usually requires a cache reconfiguration — which impacts availability and
predictability. Twemcache tries to address these needs with the help of the
following features:

Random Eviction

The v1.4.4 implementation of Memcached, which Twemcache is based on, suffers
from a problem we call slab calcification. In Memcached, a slab can only store
items of a given maximum size and once a slab has been allocated to a slab
class, it cannot be reassigned to another slab class. In other words, slabs once
allocated are locked to their respective slab classes. This is the crux of the
slab calcification problem. When items grow or shrink in size, new slabs must be
to allocated to store them. Over time, when caches reach full memory capacity,
to store newer items we must rely on evicting existing items in the same slab
class. If the newer items are of a size with no slabs allocated, write requests
may fail completely. Meanwhile, slabs allocated to a different slab class may
sit idle. Slab calcification leads to loss of capacity and efficiency.

To solve this problem without resorting to periodically restarting the server
instances, we introduced a new eviction strategy called random eviction. In this
strategy, when a new item needs to be inserted and it cannot be accommodated by
the space occupied by an expired item or the available free memory, we’ll simply
pick a random slab from the list of all allocated slabs, evict all items within
that slab, and reallocate it to the slab class that fits the new item.

It turns out that this feature is quite powerful for two reasons:



 * Cache servers can now gracefully move on-the-fly from one slab size to
   another for a given application. This enables our cache servers to adapt to
   changing item sizes and have a predictable long term hit rate by caching an
   application’s active working set of items.
 * Application developers don’t have to worry about reconfiguring their cache
   server when they add or delete fields from their cache item structures or if
   their item size grows over time.


By providing a stable hit rate, random eviction prevents performance degradation
due to data pattern change and system instability associated with restarts. The
video below illustrates how over time Twemcache is able to adapt to a shifting
size pattern and still remain effective.






Lock-less Stats Collection

Cache observability enables us to monitor the health of our cache clusters and
ensure that applications are using them effectively. To address this need, we
redesigned the Memcached stats module. Similar to the findings in Facebook’s
attempt to scale Memcached, we found that the global statistics lock was a main
contention point.

This motivated us to use an updater-aggregator model of thread synchronization,
in which worker threads always update thread-local metrics, and a background
aggregator thread asynchronously collects metrics from all threads periodically
holding only one thread-local lock at a time. Once aggregated, stats polling
comes for free. Removing a global lock reduces the time Twemcache spends in a
unresponsive state. There is a slight trade-off between how up-to-date stats are
and how much burden stats collection puts on the system. However, the difference
in total mutex wait time between aggregating once and 100 times per second is
under 20%, and the impact on performance is totally predictable and
thread-local. On top of making stats collection scalable, we also systematically
reviewed the metrics, and came up with a more comprehensive list of metrics:
Memcached provides 48 global metrics, 18 slab metrics and 10 item stats;
Twemcache, on the other hand, provides 74 global metrics and 39 slab metrics. We
merged item metrics into slab metrics to further simplify stats collection.

Asynchronous Command Logger

When using Memcached, one of the hardest problems we faced was the hit-rate and
memory-footprint trade-off - the sweet spot for achieving the desired
performance gain with reasonable resources, as it is typically not possible to
keep the entire data set in memory. To pinpoint the minimum memory requirement
for a given hit rate, we needed a way to systematically analyze an application’s
data access pattern. To address this need, we implemented a new feature called
command logger in Twemcache. When turned on, each worker thread will record a
time stamped command header as well as return status, as shown below:








Each line of the command log gives precise information on the client, the time
when a request was received, the command header including the command, key,
flags and data length, a return code, and reply message length. In fact, the
only thing missing is the item value itself, which turns out to be unimportant
for our analysis.

The command logger supports lockless read/write into ring buffers. Each worker
thread logs into a thread-local buffer as they process incoming queries, and a
background thread asynchronously dumps buffer contents to either a file or a
socket. Thus the overhead on worker threads is minimal and so would not affect
the service availability. The logger has been tested to log at about 100k
requests-per-second. To control the speed of log generation, the command logger
also supports sampling. Once we know what keys are accessed, the way they are
accessed, and their return status, we can perform offline data analysis to
estimate optimal working set size, item heat map, etc.

Future work

Twemcache is the result of our effort to turn Memcached into a reliable building
block in Twitter’s data infrastructure. We kept the simplicity of the Memcached
protocol intact, but made the service more dependable and more informative with
Twemcache, without sacrificing performance. While we initially focused on the
challenging goal of making Memcached work extremely well within the Twitter
infrastructure, we look forward to sharing our code and ideas with the Memcached
community in the long term.

In the near future, we plan to evolve Twemcache in the open, address the
hashtable lock contention issue that would further improve scalability, support
more eviction strategies, support bootstrapping the cache from disk and provide
a complete set of real-time data analysis tools. To view the source code and
share feedback, please visit the Twemcache GitHub page. You can also follow
Twemcache’s Twitter account (@Twemcache) for updates. We would love to hear any
ideas you have in improving Twemcache via pull requests or issues. Or better
yet, why not consider joining the flock (@jointheflock) if you want to help
build a world class caching system?

Other work: Twemproxy

Twemcache is one of the building blocks that comprise the caching system at
Twitter. Another fundamental building block in our caching system is Twemproxy,
a proxy for memcached protocol that we recently open sourced. Twemproxy
minimizes the connections to our backend caching servers and enables us to scale
horizontally. Furthermore, we are also actively developing the client side of
our caching system on top of the Twitter Finagle stack.

Acknowledgements

Twemcache was primarily engineered by Manju Rajashekhar (@manju) and Yao Yue
(@thinkingfish). In addition, we’d like to acknowledge the following folks who
contributed to the project either directly or indirectly and its deployment and
maintenance in our datacenters: Anirudh Srinivas (@asrin), David Lam (@kkdlam),
Krishna Gade (@krishnagade), Joshua Coats (@shu), Owen Vallis (@o_e_bert), Rob
Benson (@rgbenson), Brandon Mitchell (@bitbckt) and Xin Xiang (@xiangxin72).

- Chris Aniszczyk, Manager of Open Source (@cra)


Share:

Link copied successfully



X platform
 * X.com
 * Status
 * Accessibility
 * Embed a post
 * Privacy Center
 * Transparency Center
 * Download the X app

X Corp.
 * About the company
 * Company news
 * Brand toolkit
 * Jobs and internships
 * Investors

Help
 * Help Center
 * Using X
 * X for creators
 * Ads Help Center
 * Managing your account
 * Email Preference Center
 * Rules and policies
 * Contact us

Developer resources
 * Developer home
 * Documentation
 * Forums
 * Communities
 * Developer blog
 * Engineering blog
 * Developer terms

Business resources
 * Advertise
 * X for business
 * Resources and guides
 * X for marketers
 * Marketing insights
 * Brand inspiration
 * X Ads Academy

‎© 2024 X Corp.‎

Cookies
Privacy
Terms and conditions