Fast storage engine for millions of small files
Ultimately fast storage for billions of files with http interface. This is not a database, this is an append-only mostly-reads storage. This is a good photo storage if you want to build your own facebook, imgur or tumblr.
This project is inspired by Haystack from Facebook that is not currently an open-source project. You may read whitepaper about their implementation and some history in this document: Finding a needle in Haystack: Facebook’s photo storage
When you need to save billions of small files on fs and access them fast, you will need to make many seeks on physical disk to get files. If you don't care about permissions for files and other metadata you'll have a huge overhead.
Backpack stores all metadata in memory and only need one read per file. It groups small files into big ones and always keeps them open to return data much faster than usual fs. You also get much better space utilisation for free, because there's no need to store useless metadata. Note that backpack does not overwrite files, it's not a replacement for file system. Store only data that won't change if you don't want to waste disk space.
Backpack also have metadata for every data file so you can restore your data if redis failed and lost some parts of data. However, disks can fail so we recommend to save every piece of you data on different machines or even in different data centers.
Let's take 1 750 000 real photos from Topface and compare backpack and nginx. We'll use
two identical servers with 1Tb SATA disks (WDC WD1003FBYX-01Y7B1). Nginx is high-performance
web server so it should be fair competition. We'll save files in nginx with scheme
xx/yy/u123_abc.jpg to keep directory size relatively small.
Backpack: 175 240 megabytes on disk, 1h41m to write.
Nginx: 177 483 megabytes on disk, 2h13m to write.
Result: 23% faster, just a bit smaller size on disk. But that's not the case, actually.
In real world you cannot read files sequentially. People do random things on internet and
request random files. We cannot put files in order people will read them, so we'll just
pick 100 000 random files to read (same for nginx and backpack). To be fair, we'll drop
all page cache on linux with
echo 3 > /proc/sys/vm/drop_caches.
It's better to see on graphs how it looks like (backpack is red, nginx is green).
- Requests per second.
Backpack finished after 792 seconds, nginx after 1200 seconds. 33% faster! Here you may see that nginx is getting faster but it has it's limits.
- Reads per second (from
iostat -x -d 10).
Here you may see the reason why nginx is slower: there are too many seeks. Nginx needs to open directories and fetch file metadata that isn't in cache. Note that you can't cache everything you need if you store more data that in this test. Real servers hold way more data.
Backpack only read the data and does not seek too much.
- Disk io utilization (from
iostat -x -d 10).
Both disks are used by 100% while reads are active.
Now imagine that you have not 1 750 000 files, but 22 000 000 files on single server. Extra seek for no reason will choke your system under load. That is the main reason why we came up with backpack.
- redis - redis to save meta information about stored files
Install and run redis server. Let's assume that it's bound to
Decide where you want to save your files. Let's assume that you want to store files in
Add some storage capacity to your backpack:# each run of this command will add you# approximately 3.5Gb of storage capacity./bin/backpack-add /var/backpack 127.0.0.1 6379
Run you server. Let's assume that you want to listen for
127.0.0.1:8080./bin/backpack /var/backpack 127.0.0.1 8080 127.0.0.1 6379
Now you may try to upload file to your storage:
./bin/backpack-upload 127.0.0.1 8080 /etc/hosts my/hosts
And download file you just uploaded:
Api is very straightforward:
PUT request to save file at specified url (query string is taken into account).
GET request to retrieve saved file.
GET /stats to get some stats about what is happening.
You may ask backpack for stats by hitting
This is what you'll get (real example from production server at Topface):
"gets":"count" : 273852 // count of GET requests"bytes" : 66603359793 // total size of responses in bytes"avg" : 17.317889781518243 // average response time in ms for latest 1000 GET requests"puts":"count" : 5604 // count of PUT requests"bytes" : 1616002993 // size of written data in bytes"avg" : 4.842664467849093 // average response time in ms for latest 1000 PUT requests
./bin/backpack-add- Add data files to storage to extend capacity.
./bin/backpack-upload- Upload file to storage.
./bin/backpack-dump-log- Dump files with lengths and offsets of specified storage file.
./bin/backpack-list- List data files with their sizes and read-only flags.
./bin/backpack-get-file-info- Get data file number, offset and length by file name.
./bin/backpack-restore-from-log- Restore redis index from data file log.