Richard Jones, Esq.

Anti-RDBMS: A list of distributed key-value stores

Perhaps you’re considering using a dedicated key-value or document store instead of a traditional relational database. Reasons for this might include:

1. You’re suffering from Cloud-computing Mania.
2. You need an excuse to ‘get your Erlang on’
3. You heard CouchDB was cool.
4. You hate MySQL, and although PostgreSQL is much better, it still doesn’t have decent replication. There’s no chance you’re buying Oracle licenses.
5. Your data is stored and retrieved mainly by primary key, without complex joins.
6. You have a non-trivial amount of data, and the thought of managing lots of RDBMS shards and replication failure scenarios gives you the fear.

Whatever your reasons, there are a lot of options to chose from. At Last.fm we do a lot of batch computation in Hadoop, then dump it out to other machines where it’s indexed and served up over HTTP and Thrift as an internal service (stuff like ‘most popular songs in London, UK this week’ etc). Presently we’re using a home-grown index format which points into large files containing lots of data spanning many keys, similar to the Haystack approach mentioned in this article about Facebook photo storage. It works, but rather than build our own replication and partitioning system on top of this, we are looking to potentially replace it with a distributed, resilient key-value store for reasons 4, 5 and 6 above.

This article represents my notes and research to date on distributed key-value stores (and some other stuff) that might be suitable as RDBMS replacements under the right conditions. I’m expecting to try some of these out and investigate further in the coming months.

Glossary and Background Reading

• Distributed Hash Table (DHT) and algorithms such as Chord or Kadmelia
• Amazon’s Dynamo Paper, and this ReadWriteWeb article about Dynamo which explains why such a system is invaluable
• Amazon’s SimpleDB Service, and some commentary
• Google’s BigTable paper
• The Paxos Algorithm - read this page in order to appreciate that knocking up a Paxos implementation isn’t something you’d want to do whilst hungover on a Saturday morning.

The Shortlist

Here is a list of projects that could potentially replace a group of relational database shards. Some of these are much more than key-value stores, and aren’t suitable for low-latency data serving, but are interesting none-the-less.

Name	Language	Fault-tolerance	Persistence	Client Protocol	Data model	Docs	Community
Project Voldemort	Java	partitioned, replicated, read-repair	Pluggable: BerkleyDB, Mysql	Java API	Structured / blob / text	A	Linkedin, no
Ringo	Erlang	partitioned, replicated, immutable	Custom on-disk (append only log)	HTTP	blob	B	Nokia, no
Scalaris	Erlang	partitioned, replicated, paxos	In-memory only	Erlang, Java, HTTP	blob	B	OnScale, no
Kai	Erlang	partitioned, replicated?	On-disk Dets file	Memcached	blob	C	no
Dynomite	Erlang	partitioned, replicated	Pluggable: couch, dets	Custom ascii, Thrift	blob	D+	Powerset, no
MemcacheDB	C	replication	BerkleyDB	Memcached	blob	B	some
ThruDB	C++	Replication	Pluggable: BerkleyDB, Custom, Mysql, S3	Thrift	Document oriented	C+	Third rail, unsure
CouchDB	Erlang	Replication, partitioning?	Custom on-disk	HTTP, json	Document oriented (json)	A	Apache, yes
Cassandra	Java	Replication, partitioning	Custom on-disk	Thrift	Bigtable meets Dynamo	F	Facebook, no
HBase	Java	Replication, partitioning	Custom on-disk	Custom API, Thrift, Rest	Bigtable	A	Apache, yes
Hypertable	C++	Replication, partitioning	Custom on-disk	Thrift, other	Bigtable	A	Zvents, Baidu, yes

Why 5 of these aren’t suitable

What I’m really looking for is a low latency, replicated, distributed key-value store. Something that scales well as you feed it more machines, and doesn’t require much setup or maintenance - it should just work. The API should be that of a simple hashtable: set(key, val), get(key), delete(key). This would dispense with the hassle of managing a sharded / replicated database setup, and hopefully be capable of serving up data by primary key efficiently.

Five of the projects on the list are far from being simple key-value stores, and as such don’t meet the requirements - but they are definitely worth a mention.

1) We’re already heavy users of Hadoop, and have been experimenting with Hbase for a while. It’s much more than a KV store, but latency is too great to serve data to the website. We will probably use Hbase internally for other stuff though - we already have stacks of data in HDFS.

2) Hypertable provides a similar feature set to Hbase (both are inspired by Google’s Bigtable). They recently announced a new sponsor, Baidu - the biggest Chinese search engine. Definitely one to watch, but doesn’t fit the low-latency KV store bill either.

3) Cassandra sounded very promising when the source was released by Facebook last year. They use it for inbox search. It’s Bigtable-esque, but uses a DHT so doesn’t need a central server (one of the Cassandra developers previously worked at Amazon on Dynamo). Unfortunately it’s languished in relative obscurity since release, because Facebook never really seemed interested in it as an open-source project. From what I can tell there isn’t much in the way of documentation or a community around the project at present.

4) CouchDB is an interesting one - it’s a “distributed, fault-tolerant and schema-free document-oriented database accessible via a RESTful HTTP/JSON API”. Data is stored in ‘documents’, which are essentially key-value maps themselves, using the data types you see in JSON. Read the CouchDB Technical Overview if you are curious how the web’s trendiest document database works under the hood. This article on the Rules of Database App Aging goes some way to explaining why document-oriented databases make sense. CouchDB can do full text indexing of your documents, and lets you express views over your data in Javascript. I could imagine using CouchDB to store lots of data on users: name, age, sex, address, IM name and lots of other fields, many of which could be null, and each site update adds or changes the available fields. In situations like that it quickly gets unwieldly adding and changing columns in a database, and updating versions of your application code to match. Although many people are using CouchDB in production, their FAQ points out they may still make backwards-incompatible changes to the storage format and API before version 1.0.

5) ThruDB is a document storage and indexing system made up for four components: a document storage service, indexing service, message queue and proxy. It uses Thrift for communication, and has a pluggable storage subsystem, including an Amazon S3 option. It’s designed to scale well horizontally, and might be a better option that CouchDB if you are running on EC2. I’ve heard a lot more about CouchDB than Thrudb recently, but it’s definitely worth a look if you need a document database. It’s not suitable for our needs for the same reasons as CouchDB.

Distributed key-value stores

The rest are much closer to being ’simple’ key-value stores with low enough latency to be used for serving data used to build dynamic pages. Latency will be dependent on the environment, and whether or not the dataset fits in memory. If it does, I’d expect sub-10ms response time, and if not, it all depends on how much money you spent on spinning rust.

MemcacheDB is essentially just memcached that saves stuff to disk using a Berkeley database. As useful as this may be for some situations, it doesn’t deal with replication and partitioning (sharding), so it would still require a lot of work to make it scale horizontally and be tolerant of machine failure. Other memcached derivatives such as repcached go some way to addressing this by giving you the ability to replicate entire memcache servers (async master-slave setup), but without partitioning it’s still going to be a pain to manage.

Project Voldemort looks awesome. Go and read the rather splendid website, which explains how it works, and includes pretty diagrams and a good description of how consistent hashing is used in the Design section. (If consistent hashing butters your muffin, check out libketama - a consistent hashing library and the Erlang libketama driver). Project-Voldemort handles replication and partitioning of data, and appears to be well written and designed. It’s reassuring to read in the docs how easy it is to swap out and mock different components for testing. It’s non-trivial to add nodes to a running cluster, but according to the mailing-list this is being worked on. It sounds like this would fit the bill if we ran it with a Java load-balancer service (see their Physical Architecture Options diagram) that exposed a Thrift API so all our non-Java clients could use it.

Scalaris is probably the most face-meltingly awesome thing you could build in Erlang. CouchDB, Ejabberd and RabbitMQ are cool, but Scalaris packs by far the most impressive collection of sexy technologies. Scalaris is a key-value store - it uses a modified version of the Chord algorithm to form a DHT, and stores the keys in lexicographical order, so range queries are possible. Although I didn’t see this explicitly mentioned, this should open up all sorts of interesting options for batch processing - map-reduce for example. On top of the DHT they use an improved version of Paxos to guarantee ACID properties when dealing with multiple concurrent transactions. So it’s a key-value store, but it can guarantee the ACID properties and do proper distributed transactions over multiple keys.

Oh, and to demonstrate how you can scale a webservice based on such a system, the Scalaris folk implemented their own version of Wikipedia on Scalaris, loaded in the Wikipedia data, and benchmarked their setup to prove it can do more transactions/sec on equal hardware than the classic PHP/MySQL combo that Wikipedia use. Yikes.

From what I can tell, Scalaris is only memory-resident at the moment and doesn’t persist data to disk. This makes it entirely impractical to actually run a service like Wikipedia on Scalaris for real - but it sounds like they tackled the hard problems first, and persisting to disk should be a walk in the park after you rolled your own version of Chord and made Paxos your bitch. Take a look at this presentation about Scalaris from the Erlang Exchange conference: Scalaris presentation video.

The reminaing projects, Dynomite, Ringo and Kai are all, more or less, trying to be Dynamo. Of the three, Ringo looks to be the most specialist - it makes a distinction between small (less than 4KB) and medium-size data items (<100MB). Medium sized items are stored in individual files, whereas small items are all stored in an append-log, the index of which is read into memory at startup. From what I can tell, Ringo can be used in conjunction with the Erlang map-reduce framework Nokia are working on called Disco.

I didn’t find out much about Kai other than it’s rather new, and some mentions in Japanese. You can chose either Erlang ets or dets as the storage system (memory or disk, respectively), and it uses the memcached protocol, so it will already have client libraries in many languages.

Dynomite doesn’t have great documentation, but it seems to be more capable than Kai, and is under active development. It has pluggable backends including the storage mechanism from CouchDB, so the 2GB file limit in dets won’t be an issue. Also I heard that Powerset are using it, so that’s encouraging.

Summary

Scalaris is fascinating, and I hope I can find the time to experiment more with it, but it needs to save stuff to disk before it’d be useful for the kind of things we might use it for at Last.fm.

I’m keeping an eye on Dynomite - hopefully more information will surface about what Powerset are doing with it, and how it performs at a large scale.

Based on my research so far, Project-Voldemort looks like the most suitable for our needs. I’d love to hear more about how it’s used at LinkedIn, and how many nodes they are running it on.

What else is there?

Here are some other related projects:

• Hazelcast - Java DHT/clustering library
• nmdb - a network database (dbm-style)
• Open Chord - Java DHT

If you know of anything I’ve missed off the list, or have any feedback/suggestions, please post a comment. I’m especially interested in hearing about people who’ve tested or are using KV-stores in lieu of relational databases.

UPDATE 1: Corrected table: memcachedb does replication, as per BerkeleyDB.

Tags: databases, dht, erlang, hashing, java

How we use IRC at Last.fm

Everyone that works at Last.fm is typically connected to our IRC server. We have different channels per team, as well as a company-wide channel, and a few channels dedicated to automated monitoring.

Sometimes it makes much more sense to discuss / ask questions on IRC instead of email, and it’s useful to be able to raise people who are not in the office. That said, the main reason I’m writing this post is to mention the dev-support bot we use: irccat.

IRCCat - Development support bot

The irccat bot joins all your channels, and waits for messages on a specified ip:port on your internal network. Anything you send to that port will be sent to IRC by the bot. IRCCat - as in, `cat` to IRC.

Using netcat, you can easily send events to irc from shell scripts:

$ echo “Something just happened” | nc -q0 somemachine 12345

That will send to the default channel only (first in the config file). You can direct messages to specific combinations of channels (#) or users (@) like so:

$ echo “#syschan Starting backup job” | nc -q0 somemachine 12345

$ echo “#musicteam,#legal,@alice New album uploaded: …” | nc -q0 somemachine 12345

Some of the things we automatically send to appropriate IRC channels:

• SVN commits
• JIRA issue tracker updates
• Nagios alerts for monitored hosts and services
• Deployment notices to testing/staging/production
• Results of automated tests if something bad happens
• Links to pics from security camfeed when someone opens the office door out of hours

We also post messages from automated backup jobs etc, which helps correlate such events with any unusual load spikes or glitches in usually-smooth graphs.

In addition to providing a cat-to-irc conduit, irccat will also hand off commands to a script you can provide. We use this to expose lookup tools and some admin functions to our support staff and developers. The handler script we use is PHP, and has access to our core website libs. Typing “?pokereleasenode”, “?lookup user RJ” or “?uncache artist Radiohead” is faster than writing a throw-away script, more accessible to non-developers, less hassle than a web interface and creates a public log so people can see what’s going on.

The bot is written in Java, it’s easy to build and configure, all the deps are included:

http://github.com/RJ/irccat/tree/master

Tags: irc, java, last.fm

Getting to know ejabberd and writing modules

I started poking around in the ejabberd source code to see what I could learn. I couldn’t find much in the way of high level documentation that talks about how the various bits of ejabberd talk to each other, so I’m starting to piece it together myself.

After compiling ejabberd I made a php script I could use with the external authentication system. Here’s a version that supports just two hardcoded users:

ejabberd.cfg:
{auth_method, external}.
{extauth_program, "/tmp/auth.php"}.

auth.php:

I stripped down the ejabberd config to just load what I considered the bare essentials. Here is the modules section I’m testing with:

From ejabberd.cfg:
{modules,
[
{mod_caps, []},
{mod_disco, []},
{mod_roster, []},
{mod_pubsub, [ % requires mod_caps
{access_createnode, pubsub_createnode},
{plugins, ["default", "pep"]}
]},
{mod_mnesiaweb, []},
{mod_thriftctl, []}
]}.

mod_disco deals with discovery, so clients can find out what the server supports. mod_roster deals with rosters (buddy lists etc) using mnesia. mod_pubsub is enabled because I want to use User Tune, an extension that lets you broadcast the name of the song you are playing to all everyone in your roster. mod_caps provides XEP-115 - an extension for broadcasting and dynamically discovering client, device, or generic entity capabilities. mod_caps is a requirement of mod_pubsub.

I’ve removed the module that allows users to register, although I made a few accounts first whilst testing. The last two modules, mod_mnesiaweb and mod_thriftctl are modules I wrote.

mod_mnesiaweb

To help figure out what’s going on inside of ejabberd, it’s useful to be able to easily browse the mnesia database. Yaws comes with an appmod that does this, called ymnesia. This ejabberd module will start yaws in embedded mode and run this appmod, enabling you to explore the mnesia database from a web browser.

Yaws observation: yaws didn’t appear to build ymnesia by default, I edited the Makefile in src and added “ymnesia” to the module list. Also, if ./configure fails, the package you are probably missing is libpam0g-dev

mod_mnesiaweb:

To compile it:
erlc -pa ${EJAB_SRC} -I ${EJAB_SRC} mod_mnesiaweb.erl
where EJAB_SRC is the ejabberd-2.X.X/src directory, after you’ve compiled from source (so the beams are there too).

Copy the resulting mod_mnesiaweb.beam to /var/lib/ejabberd/ebin so ejabberd finds it, and it should work. Hit up http://localhost:8001/showdb/ in your browser and you can explore the mnesia database.

Use the match syntax to filter tables. For example to find everyone in my roster, I use this in the input box next to roster:
{roster,{"RJ",'_', {'_','_',[]}}, ‘_’,'_’,'_’,'_’,'_’,'_’,'_’,'_’}

Not pretty, but it gets the job done. You can just view the entire table, copy a record then replace fields with ‘_’ to build queries.

mod_thriftctl

Next up I wanted to try the Erlang Thrift bindings (written by the folks at Amie St.), and expose some useful functionality for controlling the server.

If you aren’t familiar with Thrift, I recommend reading about it first. In a nutshell, you write your API using an IDL (a .thrift file) and the thrift compiler creates client libraries, and server code in various different languages. It’s an RPC mechanism, and useful in a mixed environment.

mod_thriftctl.thrift:
#!/usr/local/bin/thrift -php -erl

struct JabberUser {
1: string name,
2: string server
}

service Ejabthrift {
/* add ruser to roster of luser, and visa-versa. also routes presence to users if online */
void add_friend( 1: JabberUser luser,
2: JabberUser ruser
),

/* remove ruser from luser's roster */
void remove_friend( 1: JabberUser luser, 2: JabberUser ruser ),

/* make it look like fromuser sent a message to touser */
void spoof_message( 1: JabberUser fromuser, 2: JabberUser touser, 3: string message, 4: string subject ),
/* .. or a chat message */
void spoof_chat( 1: JabberUser fromuser, 2: JabberUser touser, 3: string message, 4: string thread ),

/* sends PEP usertune message, see http://xmpp.org/extensions/xep-0118.html */
void publish_np ( 1: JabberUser fromuser, 2: string artist, 3: string album, 4: string track, 5: i32 tracklength, 6: i32 tracknum )
}

Run that .thrift file, and you get gen-php and gen-erl directories, with php client code, and erlang files needed to build a server.

Here’s the ejabberd module, which starts a thrift server:

mod_thriftctl:

To build, first build the gen-erl code:

erlc -pa ${EJAB_SRC} -I ${EJAB_SRC} -I ${ERL_THRIFT}/include -I ./gen-erl -o ./gen-erl ./gen-erl/*.erl

Where ERL_THRIFT is the lib/erl directory from the amiethrift code, git://repo.or.cz/amiethrift.git

Then compile the module:

erlc -pa ${EJAB_SRC} -I ${EJAB_SRC} -I ${ERL_THRIFT}/include -I ./gen-erl *.erl

To install, copy all the beam files to the ejabberd ebin dir:

sudo cp *.beam gen-erl/*.beam /var/lib/ejabberd/ebin/

This is inspired by mod_xmlrpc, which is in ejabberd-modules. As you can see from the start function, that’s what it takes to start a thrift server. It’s now trivial to call into ejabberd from other languages. For example, if you started listening to a song using a flash player on the website, a php webservice could make a user tune announcement on your behalf, or spoof messages from you boasting how much you love listening to Paris Hilton.

If anyone knows where I can read about the ejabberd architecture / design, so I don’t have to piece it all together myself, please let me know.

Tags: ejabberd, erlang, mnesia, thrift, xmpp, yaws

ssh hack: connect directly to machine via a firewall box

UPDATED 23/03/2009: added “-q0″ option to clean up netcat after session terminates, and left another useful ssh tip in the comments.

It’s common to have to ssh to firewall / gateway machine, then ssh to the machine you want to work on within a server network.
Typically you’d do this from your local machine:
$ ssh firewall.example.com
Password:
$ ssh my-private-host

I finally got bored of doing this, and created the following file, /usr/bin/sssh

#!/bin/bash
ssh -oproxycommand="ssh -q firewall.example.com nc -q0 %h %p" $*

Now I can use the sssh command to connect to hosts using the firewall machine as a proxy. Like most good hacks, this uses netcat.

Eg:
$ sssh 10.1.2.3
Will connect me directly to a machine on the server network, via the firewall box. Seeing as it passes all parameters to ssh (the $* bit) you can do port forwards and X-forwarding as usual too:

$ sssh -L 5432:localhost:5432 my-vm

This lets me tunnel the port for a PostgreSQL running on my development vm (my-vm) in a single command. I have all my keys installed, so no passwords needed - I estimate this will save me about 60 seconds every day.

Tags: hack, ssh

A Million-user Comet Application with Mochiweb, Part 3

Part 1 and Part 2 in this series showed how to build a comet application using mochiweb, and how to route messages to connected users. We managed to squeeze application memory down to 8KB per connection. We did ye olde c10k test, and observed what happened with 10,000 connected users. We made graphs. It was fun, but now it’s time to make good on the claims made in the title, and turn it up to 1 million connections.

This post covers the following:

• Add a pubsub-like subscription database using Mnesia
• Generate a realistic friends dataset for a million users
• Tune mnesia and bulk load in our friends data
• Opening a million connections from one machine
• Benchmark with 1 Million connected users
• Libevent + C for connection handling
• Final thoughts

One of the challenging parts of this test was actually being able to open 1M connections from a single test machine. Writing a server to accept 1M connections is easier than actually creating 1M connections to test it with, so a fair amount of this article is about the techniques used to open 1M connections from a single machine.

Getting our pubsub on

In Part 2 we used the router to send messages to specific users. This is fine for a chat/IM system, but that there are sexier things we could do instead. Before we launch into a large-scale test, let’s add one more module - a subscription database. We want the application store who your friends are, so it can push you all events generated by people on your friends list.

My intention is to use this for Last.fm so I can get a realtime feed of songs my friends are currently listening to. It could equally apply to other events generated on social networks. Flickr photo uploads, Facebook newsfeed items, Twitter messages etc. FriendFeed even have a realtime API in beta, so this kind of thing is definitely topical. (Although I’ve not heard of anyone except Facebook using Erlang for this kind of thing).

Implementing the subscription-manager

We’re implementing a general subscription manager, but we’ll be subscribing people to everyone on their friends list automatically - so you could also think of this as a friends database for now.

The subsmanager API:

• add_subscriptions([{Subscriber, Subscribee},...])
• remove_subscriptions([{Subscriber, Subscribee},...])
• get_subscribers(User)

subsmanager.erl

Noteworthy points:

• I’ve included qlc.hrl, needed for mnesia queries using list comprehension, using an absolute path. That can’t be best practice, it wasn’t finding it otherwise though.
• get_subscribers spawns another process and delegates the job of replying to that process, using gen_server:reply. This means the gen_server loop won’t block on that call if we throw lots of lookups at it and mnesia slows down.
• rr(”subsmanager.erl”). in the example below allows you to use record definitions in the erl shell. Putting your record definitions into a records.hrl file and including that in your modules is considered better style. I inlined it for brevity.

Now to test it. first_run() creates the mnesia schema, so it’s important to run that first. Another potential gotcha with mnesia is that (by default) the database can only be accessed by the node that created it, so give the erl shell a name, and stick with it.

$ mkdir /var/mnesia
$ erl -boot start_sasl -mnesia dir '"/var/mnesia_data"' -sname subsman
(subsman@localhost)1> c(subsmanager).
{ok,subsmanager}
(subsman@localhost)2> subsmanager:first_run().
...
{atomic,ok}
(subsman@localhost)3> subsmanager:start_link().
Waiting on mnesia tables..
OK. Subscription table info:
[{access_mode,read_write},{active_replicas,[subsman@localhost]},{arity,3},{attributes,[subscriber,subscribee]},{checkpoints,[]},{commit_work,[{index,bag,[{3,{ram,57378}}]}]},{cookie,{{1224,800064,900003},subsman@localhost}},{cstruct,{cstruct,subscription,bag,[],[subsman@localhost],[],0,read_write,[3],[],false,subscription,[subscriber,subscribee],[],[],{{1224,863164,904753},subsman@localhost},{{2,0},[]}}},{disc_copies,[subsman@localhost]},{disc_only_copies,[]},{frag_properties,[]},{index,[3]},{load_by_force,false},{load_node,subsman@localhost},{load_order,0},{load_reason,{dumper,create_table}},{local_content,false},{master_nodes,[]},{memory,288},{ram_copies,[]},{record_name,subscription},{record_validation,{subscription,3,bag}},{type,bag},{size,0},{snmp,[]},{storage_type,disc_copies},{subscribers,[]},{user_properties,[]},{version,{{2,0},[]}},{where_to_commit,[{subsman@localhost,disc_copies}]},{where_to_read,subsman@localhost},{where_to_write,[subsman@localhost]},{wild_pattern,{subscription,’_',’_'}},{{index,3},57378}]

{ok,<0.105.0>}
(subsman@localhost)4> rr("subsmanager.erl").
[state,subscription]
(subsman@localhost)5> subsmanager:add_subscriptions([ #subscription{subscriber=alice, subscribee=rj} ]).
ok
(subsman@localhost)6> subsmanager:add_subscriptions([ #subscription{subscriber=bob, subscribee=rj} ]).
ok
(subsman@localhost)7> subsmanager:get_subscribers(rj).
[bob,alice]
(subsman@localhost)8> subsmanager:remove_subscriptions([ #subscription{subscriber=bob, subscribee=rj} ]).
ok
(subsman@localhost)8> subsmanager:get_subscribers(rj).
[alice]
(subsman@localhost)10> subsmanager:get_subscribers(charlie).
[]

We’ll use integer Ids to represent users for the benchmark - but for this test I used atoms (rj, alice, bob) and assumed that alice and bob are both on rj’s friends list. It’s nice that mnesia (and ets/dets) doesn’t care what values you use - any Erlang term is valid. This means it’s a simple upgrade to support multiple types of resource. You could start using {user, 123} or {photo, 789} to represent different things people might subscribe to, without changing anything in the subsmanager module.

Modifying the router to use subscriptions

Instead of addressing messages to specific users, ie router:send(123, "Hello user 123"), we’ll mark messages with a subject - that is, the person who generated the message (who played the song, who uploaded the photo etc) - and have the router deliver the message to every user who has subscribed to the subject user. In other words, the API will work like this: router:send(123, "Hello everyone subscribed to user 123")

Updated router.erl:

And here’s a quick test that doesn’t require mochiweb - I’ve used atoms instead of user ids, and omitted some output for clarity:

(subsman@localhost)1> c(subsmanager), c(router), rr("subsmanager.erl").
(subsman@localhost)2> subsmanager:start_link().
(subsman@localhost)3> router:start_link().
(subsman@localhost)4> Subs = [#subscription{subscriber=alice, subscribee=rj}, #subscription{subscriber=bob, subscribee=rj}].
[#subscription{subscriber = alice,subscribee = rj},
#subscription{subscriber = bob,subscribee = rj}]
(subsman@localhost)5> subsmanager:add_subscriptions(Subs).
ok
(subsman@localhost)6> router:send(rj, “RJ did something”).
Subscribers of rj = [bob,alice]
Pids: []
{ok,0}
(subsman@localhost)7> router:login(alice, self()).
ok
(subsman@localhost)8> router:send(rj, “RJ did something”).
Subscribers of rj = [bob,alice]
Pids: [<0.46.0>]
{ok,1}
(subsman@localhost)9> receive {router_msg, M} -> io:format(”~s\n”,[M]) end.
RJ did something
ok

This shows how alice can a receive a message when the subject is someone she is subscribed to (rj), even though the message wasn’t sent directly to alice. The output shows that the router identified possible targets as [alice,bob] but only delivered the message to one person, alice, because bob was not logged in.

Generating a typical social-network friends dataset

We could generate lots of friend relationships at random, but that’s not particularly realistic. Social networks tend to exhibit a power law distribution. Social networks usually have a few super-popular users (some Twitter users have over 100,000 followers) and plenty of people with just a handful of friends. The Last.fm friends data is typical - it fits a Barabási–Albert graph model, so that’s what I’ll use.

To generate the dataset I’m using the python module from the excellent igraph library:

fakefriends.py:

This will generate with 2 user ids per line, space separated. These are the friend relationships we’ll load into our subsmanager. User ids range from 1 to a million.

Bulk loading friends data into mnesia

This small module will read the fakefriends.txt file and create a list of subscription records.

readfriends.erl - to read the fakefriends.txt and create subscription records:

Now in the subsmanager shell, you can read from the text file and add the subscriptions:

$ erl -name router@minifeeds4.gs2 +K true +A 128 -setcookie secretcookie -mnesia dump_log_write_threshold 50000 -mnesia dc_dump_limit 40
erl> c(readfriends), c(subsmanager).
erl> subsmanager:first_run().
erl> subsmanager:start_link().
erl> subsmanager:add_subscriptions( readfriends:load("fakefriends.txt") ).

Note the additional mnesia parameters - these are to avoid the ** WARNING ** Mnesia is overloaded messages you would (probably) otherwise see. Refer to my previous post: On bulk loading data into Mnesia for alternative ways to load in lots of data. The best solution seems to be (as pointed out in the comments, thanks Jacob!) to set those options. The Mnesia reference manual contains many other settings under Configuration Parameters, and is worth a look.

Turning it up to 1 Million

Creating a million tcp connections from one host is non-trivial. I’ve a feeling that people who do this regularly have small clusters dedicated to simulating lots of client connections, probably running a real tool like Tsung. Even with the tuning from Part 1 to increase kernel tcp memory, increase the file descriptor ulimits and set the local port range to the maximum, we will still hit a hard limit on ephemeral ports. When making a tcp connection, the client end is allocated (or you can specify) a port from the range in /proc/sys/net/ipv4/ip_local_port_range. It doesn’t matter if you specify it manually, or use an ephemeral port, you’re still going to run out. In Part 1, we set the range to “1024 65535″ - meaning there are 65535-1024 = 64511 unprivileged ports available. Some of them will be used by other processes, but we’ll never get over 64511 client connections, because we’ll run out of ports.

The local port range is assigned per-IP, so if we make our outgoing connections specifically from a range of different local IP addresses, we’ll be able to open more than 64511 outgoing connections in total.

So let’s bring up 17 new IP addresses, with the intention of making 62,000 connections from each - giving us a total of 1,054,000 connections. Safely over the 2^32 mark:

$ for i in `seq 1 17`; do echo sudo ifconfig eth0:$i 10.0.0.$i up ; done

If you run ifconfig now you should see your virtual interfaces: eth0:1, eth0:2 … eth0:17, each with a different IP address. Obviously you should chose a sensible part of whatever address space you are using.

All that remains now is to modify the floodtest tool from Part 1 to specify the local IP it should connect from… Unfortunately the erlang http client doesn’t let you specify the source IP. Neither does ibrowse, the alternative http client library. Damn.

<crazy idea>
At this point I considered another option: bringing up 17 pairs of IPs - one on the server and one on the client - each pair in their own isolated /30 subnet. I think that if I then made the client connect to any given server IP, it would force the local address to be other half of the pair on that subnet, because only one of the local IPs would actually be able to reach the server IP. In theory, this would mean declaring the local source IP on the client machine would not be necessary (although the range of server IPs would need to be specified). I don’t know if this would really work - it sounded plausible at the time. In the end I decided it was too perverted and didn’t try it.
</crazy idea>

I also poked around in OTP’s http_transport code and considered adding support for specifying the local IP. It’s not really a feature you usually need in an HTTP client though, and it would certainly have been more work.

gen_tcp lets you specify the source address, so I ended up writing a rather crude client using gen_tcp specifically for this test:

floodtest2.erl

As an initial test I was connecting to the mochiweb app from Part 1 - it simply sends one message to every client every 10 seconds.

erl> c(floodtest2), floodtest2:run(20).

This quickly ate all my memory.

Turns out opening lots of connections with gen_tcp like that eats a lot of ram. I think it’d need ~36GB to make it work without any additional tuning. I’m not interested in trying to optimise my quick-hack erlang http client (in the real world, this would be 1M actual web browsers), and the only machine I could get my hands on that has more than 32GB of RAM is one of our production databases, and I can’t find a good excuse to take Last.fm offline whilst I test this :) Additionally, it seems like it still only managed to open around 64,500 ports. Hmm.

At this point I decided to break out the trusty libevent, which I was pleased to discover has an HTTP API. Newer versions also have a evhttp_connection_set_local_address function in the http API. This sounds promising.

Here’s the http client in C using libevent:

Most parameters are hardcoded as #define’s so you configure it by editing the source and recompiling.

Compile and run:
$ gcc -o httpclient httpclient.c -levent
$ ./httpclient

This still failed to open more than 64,500 ports. Although it used less RAM doing it.

It turns out that although I was specifying the local addresses, the ephemeral port allocation somewhere in the kernel or tcp stack didn’t care, and still ran out after 2^16. So in order to open more than 64,500 connections, you need to specify the local address and local port yourself, and manage them accordingly.

Unfortunately the libevent HTTP API doesn’t have an option to specify the local port. I patched libevent to add a suitable function:
void evhttp_connection_set_local_port(struct evhttp_connection *evcon, u_short port);.

This was a surprisingly pleasant experience; libevent seems well written, and the documentation is pretty decent too.

With my modified libevent installed, I was able to add the following under the set_local_address line in the above code:
evhttp_connection_set_local_port(evhttp_connection, 1024+i);

With that in place, multiple connections from different addresses were able to use the same local port number, specific to the the local address. I recompiled the client and let it run for a bit to confirm it would break the 2^16 barrier.

Netstat confirms it:
# netstat -n | awk '/^tcp/ {t[$NF]++}END{for(state in t){print state, t[state]}}’
TIME_WAIT 8
ESTABLISHED 118222

This shows how many ports are open in various states. We’re finally able to open more than 2^16 connections, phew.

Now we have a tool capable of opening a million http connections from a single box. It seems to consume around 2KB per connection, plus whatever the kernel needs. It’s time to use it for the “million connected user” test against our mochiweb comet server.

C1024K Test - 1 million comet connections

For this test I used 4 different servers of varying specs. These specs may be overpowered for the experiment, but they were available and waiting to go into production, and this made a good burn-in test. All four servers are on the same gigabit LAN, with up to 3 switches and a router in the middle somewhere.

The 1 million test I ran is similar to the 10k test from parts 1 and 2, the main difference being the modified client, now written in C using libevent, and that I’m running in a proper distributed-erlang setup with more than one machine.

On server 1 - Quad-core 2GHz CPU, 16GB of RAM

• Start subsmanager
• Load in the friends data
• Start the router

On server 2 - Dual Quad-core 2.8GHz CPU, 32GB of RAM

• Start mochiweb app

On server 3 - Quad-core 2GHz CPU, 16GB of RAM

• Create 17 virtual IPs as above
• Install patched libevent
• Run client: ./httpclient to create 100 connections per second, up to 1M

On server 4 - Dual-core 2GHz, 2GB RAM

• Run msggen program, to send lots of messages to the router

I measured the memory usage of mochiweb during the ramp-up to a million connections, and for the rest of the day:

The httpclient has a built in delay of 10ms between connections, so it took nearly 3 hours to open a million connections. The resident memory used by the mochiweb process with 1M open connections was around 25GB. Here’s the server this was running on as seen by Ganglia, which measures CPU, network and memory usage and produces nice graphs:

You can see it needs around 38GB and has started to swap. I suspect the difference is mostly consumed by the kernel to keep those connections open. The uplift at the end is when I started sending messages.

Messages were generated using 1,000 processes, with an average time between messages of 60ms per process, giving around 16,666 messages per second overall:

erl> [ spawn( fun()->msggen:start(1000000, 10+random:uniform(100), 1000000) end) || I <- lists:seq(1,1000) ].

The machine (server-4) generating messages looked like this on Ganglia:

That’s 10 MB per second of messages it’s pumping out - 16,666 messages a second. Typically these messages would come from a message bus, app servers, or part of an existing infrastructure.

When I started sending messages, the load on server 1 (hosting subsmanager and router) stayed below 1, and CPU utilization increased from 0 to 5%.

CPU on server 2 (hosting mochiweb app, with 1M connections) increased more dramatically:

Naturally as processes have to leave their hibernate state to handle messages, memory usage will increase slightly. Having all connections open with no messages is a best-case for memory usage - unsurprisingly, actually doing stuff requires more memory.

So where does this leave us? To be on the safe side, the mochiweb machine would need 40GB of RAM to hold open 1M active comet connections. Under load, up to 30GB of the memory would be used by the mochiweb app, and the remaining 10GB by the kernel. In other words, you need to allow 40KB per connection.

During various test with lots of connections, I ended up making some additional changes to my sysctl.conf. This was part trial-and-error, I don’t really know enough about the internals to make especially informed decisions about which values to change. My policy was to wait for things to break, check /var/log/kern.log and see what mysterious error was reported, then increase stuff that sounded sensible after a spot of googling. Here are the settings in place during the above test:

net.core.rmem_max = 33554432
net.core.wmem_max = 33554432
net.ipv4.tcp_rmem = 4096 16384 33554432
net.ipv4.tcp_wmem = 4096 16384 33554432
net.ipv4.tcp_mem = 786432 1048576 26777216
net.ipv4.tcp_max_tw_buckets = 360000
net.core.netdev_max_backlog = 2500
vm.min_free_kbytes = 65536
vm.swappiness = 0
net.ipv4.ip_local_port_range = 1024 65535

I would like to learn more about Linux tcp tuning so I can make a more informed decision about these settings. These are almost certainly not optimal, but at least they were enough to get to 1M connections. These changes, along with the fact this is running on a 64bit Erlang VM, and thus has a wordsize of 8bytes instead of 4, might explain why the memory usage is much higher than I observed during the C10k test of part 2.

An Erlang C-Node using Libevent

After dabbling with the HTTP api for libevent, it seemed entirely sensible to try the 1M connection test against a libevent HTTPd written in C so we have a basis for comparison.

I’m guessing that enabling kernel poll means the erlang VM is able to use epoll (or similar), but even so there’s clearly some overhead involved which we might be able to mitigate by delegating the connection handling to a C program using libevent. I want to reuse most of the Erlang code so far, so let’s do the bare minimum in C - just the connection handling and HTTP stuff.

Libevent has an asynchronous HTTP API, which makes implementing http servers trivial - well, trivial for C, but still less trivial than mochiweb IMO ;) I’d also been looking for an excuse to try the Erlang C interface, so the following program combines the two. It’s a comet http server in C using libevent which identifies users using an integer Id (like our mochiweb app), and also acts as an Erlang C-Node.

It connects to a designated erlang node, listens for messages like {123, <<"Hello user 123">>} then dispatches “Hello user 123″ to user 123, if connected. Messages for users that are not connected are discarded, just like previous examples.

httpdcnode.c

The maximum number of users is #defined, and similarly to the mochiweb server, it listens on port 8000 and expects users to connect with a path like so: /test/<userid>. Also hardcoded is the name of the erlang node it will connect to in order to receive messages, httpdmaster@localhost, and the erlang cookie, “secretcookie”. Change these accordingly.

Run the erlang node it will connect to first:
$ erl -setcookie secretcookie -sname httpdmaster@localhost

Compile and run like so:
$ gcc -o httpdcnode httpdcnode.c -lerl_interface -lei -levent
$ ./httpdcnode

In the erlang shell, check you can see the hidden c-node:
erl> nodes(hidden).
[c1@localhost]

Now connect in your browser to http://localhost:8000/test/123. You should see the welcome message.

Now back to the erlang shell - send a message to the C node:

erl> {any, c1@localhost} ! {123, <<"Hello Libevent World">>}.

Note that we don’t have a Pid to use, so we use the alternate representation of {procname, node}. We use ‘any’ as the process name, which is ignored by the C-node.

Now you’re able to deliver comet messages via Erlang, but all the http connections are managed by a libevent C program which acts as an Erlang node.

After removing the debug print statements, I connected 1M clients to the httpdcnode server using the same client as above, the machine showed a total of just under 10GB or memory used. The resident memory of the server process was stable at under 2GB:

So big savings compared to mochiweb when handling lots of connections - the resident memory per connection for the server process with libevent is just under 2KB. With everything connected, the server machine claims:
Mem: 32968672k total, 9636488k used, 23332184k free, 180k buffers
So the kernel/tcp stack is consuming an additional 8KB per connection, which seems a little high, but I have no basis for comparison.

This libevent-cnode server needs a bit more work. It doesn’t sensibly handle multiple connections from the same user yet, and there’s no locking so a race condition exists if you disconnect at just when a message was going to be dispatched.

Even so, I think this could be generalized in such a way that would allow you to use Erlang for all the interesting stuff, and have a C+libevent process act as a dumb connection-pool. With a bit more wrapper code and callbacks into Erlang, you’d hardly need to know this was going on - the C program could be run as a driver or a C-node, and an Erlang wrapper could give you a decent api built on top of libevent. (see this post for an example Erlang C driver). I would like to experiment further with this.

Final Thoughts

I have enough data now to judge how much hardware would be needed if we deploy a large scale comet system for Last.fm. Even a worst case of 40KB per connection isn’t unreasonable - memory is pretty cheap at the moment, and 40GB to support a million users is not unreasonable. 10GB is even better. I will finish up the app I’m building and deploy it somewhere people can try it out. Along the way I’ll tidy up the erlang memcached client I’m using and release that (from jungerl, with modifications for consistent hashing and some bug fixes), and some other things. Stay tuned :)

Tags: c, cnode, comet, erlang, libevent, mochiweb