• This repository has been archived on 02/Nov/2021
  • Stars
    star
    1,300
  • Rank 35,370 (Top 0.8 %)
  • Language
    C
  • License
    Apache License 2.0
  • Created over 11 years ago
  • Updated over 2 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Memcache on SSD

fatcache

status: retired Build Status

fatcache is no longer actively maintained. See twitter/pelikan for our latest caching work.

fatcache is memcache on SSD. Think of fatcache as a cache for your big data.

Overview

There are two ways to think of SSDs in system design. One is to think of SSD as an extension of disk, where it plays the role of making disks fast and the other is to think of them as an extension of memory, where it plays the role of making memory fat. The latter makes sense when persistence (non-volatility) is unnecessary and data is accessed over the network. Even though memory is thousand times faster than SSD, network connected SSD-backed memory makes sense, if we design the system in a way that network latencies dominate over the SSD latencies by a large factor.

To understand why network connected SSD makes sense, it is important to understand the role distributed memory plays in large-scale web architecture. In recent years, terabyte-scale, distributed, in-memory caches have become a fundamental building block of any web architecture. In-memory indexes, hash tables, key-value stores and caches are increasingly incorporated for scaling throughput and reducing latency of persistent storage systems. However, power consumption, operational complexity and single node DRAM cost make horizontally scaling this architecture challenging. The current cost of DRAM per server increases dramatically beyond approximately 150 GB, and power cost scales similarly as DRAM density increases.

Fatcache extends a volatile, in-memory cache by incorporating SSD-backed storage.

SSD-backed memory presents a viable alternative for applications with large workloads that need to maintain high hit rate for high performance. SSDs have higher capacity per dollar and lower power consumption per byte, without degrading random read latency beyond network latency.

Fatcache achieves performance comparable to an in-memory cache by focusing on two design criteria:

  • Minimize disk reads on cache hit
  • Eliminate small, random disk writes

The latter is important due to SSDs' unique write characteristics. Writes and in-place updates to SSDs degrade performance due to an erase-and-rewrite penalty and garbage collection of dead blocks. Fatcache batches small writes to obtain consistent performance and increased disk lifetime.

SSD reads happen at a page-size granularity, usually 4 KB. Single page read access times are approximately 50 to 70 usec and a single commodity SSD can sustain nearly 40K read IOPS at a 4 KB page size. 70 usec read latency dictates that disk latency will overtake typical network latency after a small number of reads. Fatcache reduces disk reads by maintaining an in-memory index for all on-disk data.

Batched Writes

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.

By managing an SSD as a log-structured store, no disk updates are in-place and objects won't have a fixed address on disk. To locate an object, fatcache maintains an in-memory index. An on-disk object without an index entry is a candidate for garbage collection, which occurs during capacity-triggered eviction.

In-memory index

Fatcache maintains an in-memory index for all data stored on disk. An in-memory index serves two purposes:

  • Cheap object existence checks
  • On-disk object address storage

An in-memory index is preferable to an on-disk index to minimize disk lookups to locate and read an object. Furthermore, in-place index updates become complicated by an SSD's unique write characteristics. An in-memory index avoids these shortcomings and ensures there are no disk accesses on cache miss and only a single disk access on cache hit.

Maintaining an in-memory index of all on-disk data requires a compact representation of the index. The fatcache index has the following format:

struct itemx {
  STAILQ_ENTRY(itemx) tqe;    /* link in index / free q */
  uint8_t             md[20]; /* sha1 message digest */
  uint32_t            sid;    /* owner slab id */
  uint32_t            offset; /* item offset from owner slab base */
  rel_time_t          expiry; /* expiry in secs */
  uint64_t            cas;    /* cas */
} __attribute__ ((__packed__));

Each index entry contains both object-specific information (key name, &c.) and disk-related information (disk address, &c.). The entries are stored in a chained hash table. To avoid long hash bin traversals, the number of hash bins is fixed to the expected number of index entries.

To further reduce the memory consumed by the index, we store the SHA-1 hash of the key in each index entry, instead of the key itself. The SHA-1 hash acts as the unique identifier for each object. The on-disk object format contains the complete object key and value. False positives from SHA-1 hash collisions are detected after object retrieval from the disk by comparison with the requested key. If there are collisions on the write path, new objects with the same hash key simply overwrite previous objects.

The index entry (struct itemx) on a 64-bit system is 48 bytes in size. It is possible to further reduce index entry size to 32 bytes, if CAS is unsupported, MD5 hashing is used, and the next pointer is reduced to 4 bytes.

At this point, it is instructive to consider the relative size of fatcache's index and the on-disk data. With a 44 byte index entry, an index consuming 48 MB of memory can address 1M objects. If the average object size is 1 KB, then a 48 MB index can address 1 GB of on-disk storage - a 23x memory overcommit. If the average object size is 500 bytes, then a 48 MB index can address 500 MB of SSD - a 11x memory overcommit. Index size and object size relate in this way to determine the addressable capacity of the SSD.

Build

To build fatcache from a distribution tarball:

$ ./configure
$ make
$ sudo make install

To build fatcache from a distribution tarball in debug mode:

$ CFLAGS="-ggdb3 -O0" ./configure --enable-debug=full
$ make
$ sudo make install

To build fatcache from source with debug logs enabled and assertions disabled:

$ git clone [email protected]:twitter/fatcache.git
$ cd fatcache
$ autoreconf -fvi
$ ./configure --enable-debug=log
$ make
$ src/fatcache -h

Help

Usage: fatcache [-?hVdS] [-o output file] [-v verbosity level]
           [-p port] [-a addr] [-e hash power]
           [-f factor] [-n min item chunk size] [-I slab size]
           [-i max index memory[ [-m max slab memory]
           [-z slab profile] [-D ssd device] [-s server id]

Options:
  -h, --help                  : this help
  -V, --version               : show version and exit
  -d, --daemonize             : run as a daemon
  -S, --show-sizes            : print slab, item and index sizes and exit
  -o, --output=S              : set the logging file (default: stderr)
  -v, --verbosity=N           : set the logging level (default: 6, min: 0, max: 11)
  -p, --port=N                : set the port to listen on (default: 11211)
  -a, --addr=S                : set the address to listen on (default: 0.0.0.0)
  -e, --hash-power=N          : set the item index hash table size as a power of two (default: 20)
  -f, --factor=D              : set the growth factor of slab item sizes (default: 1.25)
  -n, --min-item-chunk-size=N : set the minimum item chunk size in bytes (default: 84 bytes)
  -I, --slab-size=N           : set slab size in bytes (default: 1048576 bytes)
  -i, --max-index-memory=N    : set the maximum memory to use for item indexes in MB (default: 64 MB)
  -m, --max-slab-memory=N     : set the maximum memory to use for slabs in MB (default: 64 MB)
  -z, --slab-profile=S        : set the profile of slab item chunk sizes (default: n/a)
  -D, --ssd-device=S          : set the path to the ssd device file (default: n/a)
  -s, --server-id=I/N         : set fatcache instance to be I out of total N instances (default: 0/1)

Performance

  • Initial performance results are available here.

Future Work

  • fatcache deals with two kinds of IOs - disk IO and network IO. Network IO in fatcache is async, but disk IO is sync. It is recommended to run multiple instances of fatcache on a single machine to exploit CPU and SSD parallelism. However, by making disk IO async (using libaio, perhaps), it would be possible for a single instance to completely exploit all available SSD device parallelism.
  • observability in fatcache through stats

Issues and Support

Have a bug or question? Please create an issue here on GitHub!

https://github.com/twitter/fatcache/issues

Contributors

License

Copyright 2013 Twitter, Inc.

Licensed under the Apache License, Version 2.0: http://www.apache.org/licenses/LICENSE-2.0

More Repositories

1

the-algorithm

Source code for Twitter's Recommendation Algorithm
Scala
61,569
star
2

twemoji

Emoji for everyone. https://twemoji.twitter.com/
HTML
16,673
star
3

typeahead.js

typeahead.js is a fast and fully-featured autocomplete library
JavaScript
16,522
star
4

twemproxy

A fast, light-weight proxy for memcached and redis
C
12,072
star
5

the-algorithm-ml

Source code for Twitter's Recommendation Algorithm
Python
9,938
star
6

finagle

A fault tolerant, protocol-agnostic RPC system
Scala
8,752
star
7

hogan.js

A compiler for the Mustache templating language
JavaScript
5,141
star
8

labella.js

Placing labels on a timeline without overlap.
JavaScript
3,875
star
9

scala_school

Lessons in the Fundamentals of Scala
HTML
3,700
star
10

AnomalyDetection

Anomaly Detection with R
R
3,534
star
11

scalding

A Scala API for Cascading
Scala
3,479
star
12

twitter-text

Twitter Text Libraries. This code is used at Twitter to tokenize and parse text to meet the expectations for what can be used on the platform.
HTML
3,060
star
13

TwitterTextEditor

A standalone, flexible API that provides a full-featured rich text editor for iOS applications.
Swift
2,966
star
14

opensource-website

Twitter's open source website, identifying projects we've released, organizations we support, and the work we do to support open source.
SCSS
2,957
star
15

util

Wonderful reusable code from Twitter
Scala
2,679
star
16

algebird

Abstract Algebra for Scala
Scala
2,284
star
17

finatra

Fast, testable, Scala services built on TwitterServer and Finagle
Scala
2,273
star
18

effectivescala

Twitter's Effective Scala Guide
HTML
2,242
star
19

summingbird

Streaming MapReduce with Scalding and Storm
Scala
2,139
star
20

pelikan

Pelikan is Twitter's unified cache backend
C
1,933
star
21

ios-twitter-image-pipeline

Twitter Image Pipeline is a robust and performant image loading and caching framework for iOS clients
C
1,852
star
22

twurl

OAuth-enabled curl for the Twitter API
Ruby
1,790
star
23

twitter-server

Twitter-Server defines a template from which services at Twitter are built
Scala
1,559
star
24

rezolus

Systems performance telemetry
Rust
1,545
star
25

communitynotes

Documentation and source code powering Twitter's Community Notes
Python
1,373
star
26

activerecord-reputation-system

An Active Record Reputation System for Rails
Ruby
1,335
star
27

compose-rules

Static checks to aid with a healthy adoption of Compose
Kotlin
1,335
star
28

rsc

Experimental Scala compiler focused on compilation speed
Scala
1,243
star
29

elephant-bird

Twitter's collection of LZO and Protocol Buffer-related Hadoop, Pig, Hive, and HBase code.
Java
1,138
star
30

cassovary

Cassovary is a simple big graph processing library for the JVM
Scala
1,042
star
31

Serial

Light-weight, fast framework for object serialization in Java, with Android support.
Java
991
star
32

hbc

A Java HTTP client for consuming Twitter's realtime Streaming API
Java
961
star
33

twemcache

Twemcache is the Twitter Memcached
C
926
star
34

vireo

Vireo is a lightweight and versatile video processing library written in C++11
C++
924
star
35

innovators-patent-agreement

Innovators Patent Agreement (IPA)
921
star
36

twitter-korean-text

Korean tokenizer
Scala
856
star
37

scrooge

A Thrift parser/generator
Scala
787
star
38

BreakoutDetection

Breakout Detection via Robust E-Statistics
C++
753
star
39

GraphJet

GraphJet is a real-time graph processing library.
Java
699
star
40

twitter-cldr-rb

Ruby implementation of the ICU (International Components for Unicode) that uses the Common Locale Data Repository to format dates, plurals, and more.
Ruby
669
star
41

bijection

Reversible conversions between types
Scala
656
star
42

chill

Scala extensions for the Kryo serialization library
Scala
608
star
43

ios-twitter-network-layer

Twitter Network Layer is a scalable and feature rich network layer built on top of NSURLSession for Apple platforms
Objective-C
573
star
44

hadoop-lzo

Refactored version of code.google.com/hadoop-gpl-compression for hadoop 0.20
Shell
545
star
45

storehaus

Storehaus is a library that makes it easy to work with asynchronous key value stores
Scala
465
star
46

rpc-perf

A tool for benchmarking RPC services
Rust
458
star
47

d3kit

D3Kit is a set tools to speed D3 related project development
JavaScript
427
star
48

scoot

Scoot is a distributed task runner, supporting both a proprietary API and Bazel's Remote Execution.
Go
347
star
49

twitter-cldr-js

JavaScript implementation of the ICU (International Components for Unicode) that uses the Common Locale Data Repository to format dates, plurals, and more. Based on twitter-cldr-rb.
JavaScript
347
star
50

rustcommon

Common Twitter Rust lib
Rust
341
star
51

scala_school2

Scala School 2
Scala
340
star
52

wordpress

The official Twitter plugin for WordPress. Embed Twitter content and grow your audience on Twitter.
PHP
315
star
53

ios-twitter-logging-service

Twitter Logging Service is a robust and performant logging framework for iOS clients
Objective-C
299
star
54

nodes

A library to implement asynchronous dependency graphs for services in Java
Java
248
star
55

SentenTree

A novel text visualization technique
JavaScript
227
star
56

interactive

Twitter interactive visualization
HTML
214
star
57

joauth

A Java library for authenticating HTTP Requests using OAuth
Java
213
star
58

thrift_client

A Thrift client wrapper that encapsulates some common failover behavior
Ruby
196
star
59

hpack

Header Compression for HTTP/2
Java
193
star
60

cache-trace

A collection of Twitter's anonymized production cache traces.
Shell
166
star
61

zktraffic

ZooKeeper protocol analyzer and stats gathering daemon
Python
166
star
62

twemoji-parser

A simple library for identifying emoji entities within a string in order to render them as Twemoji.
Scala
163
star
63

sbf

Java
161
star
64

tormenta

Scala extensions for Storm
Scala
132
star
65

whiskey

HTTP library for Android (beta)
Java
131
star
66

hraven

hRaven collects run time data and statistics from MapReduce jobs in an easily queryable format
Java
126
star
67

netty-http2

HTTP/2 for Netty
Java
120
star
68

sqrl

A Safe, Stateful Rules Language for Event Streams
TypeScript
100
star
69

ccommon

Cache Commons
C
99
star
70

focus

Focus aligns Git worktree content based on outlines of a repository's Bazel build graph. Focused repos are sparse, shallow, and thin and unlock markedly better performance in large repos.
Rust
91
star
71

metrics

78
star
72

dict_minimize

Access scipy optimizers from your favorite deep learning framework.
Python
77
star
73

twitter.github.io

HTML
74
star
74

diffusion-rl

Python
68
star
75

go-bindata

Go
68
star
76

birdwatch

67
star
77

cloudhopper-commons

Cloudhopper Commons
Java
57
star
78

.github

Twitter GitHub Organization-wide files
49
star
79

twitter-cldr-npm

TwitterCldr npm package
JavaScript
49
star
80

bazel-multiversion

Bazel rules to resolve, fetch and manage 3rdparty JVM dependencies with support for multiple parallel versions of the same dependency. Powered by Coursier.
Scala
47
star
81

libwatchman

A C interface to watchman
C
45
star
82

sslconfig

Twitter's OpenSSL Configuration
43
star
83

ios-twitter-apache-thrift

A thrift encoding and decoding library for Swift
Swift
42
star
84

gatekeeper-service

GateKeeper is a service built to automate the manual steps involved in onboarding, offboarding, and lost asset scenarios.
Python
36
star
85

dodo

The Twitter OSS Project Builder
Shell
35
star
86

repo-scaffolding

Tools for creating repos based on open source standards and best practices
34
star
87

iago2

A load generator, built for engineers
Scala
25
star
88

caladrius

Performance modelling system for Distributed Stream Processing Systems (DSPS) such as Apache Heron and Apache Storm
Python
22
star
89

ossdecks

Repository for Twitter Open Source Decks
10
star
90

curation-style-guide

Document Repository for Twitter's Curation Style Guide
10
star
91

analytics-infra-governance

Description of the process for how to commit, review, and release code to the Scalding OSS family (Scalding, Summingbird, Algebird, Bijection, Storehaus, etc)
9
star
92

gpl-commitment

Twitter's GPL Cooperation Commitment
5
star
93

second-control-probability-distributions

4
star
94

google-tag-manager-event-tag

Smarty
3
star
95

google-tag-manager-base-tag

Smarty
2
star