Memcache migration

Posted on 3/17/2010 by César Ortiz Architecture Engineer

Tuenti is an example of one of the many sites that is currently using memcache to improve performance. It's important to keep in mind that once you start using it your application performance will heavily depend on it. Consequently, if for any reason the memcache connectivity is lost, the user experience will not work as well as intended because it uses memcache as a key element that just failed.

When you deal with a lot of data and a lot of users, at some point you will need to replace a memcache server due to a hardware problem or a systems upgrade. When this happens you could simply disconnect it and replace it with another, but if you do so your cached data will be lost, which is normally something you don´t want. To avoid this problem, you need a mechanism to migrate the data from one server to another.

You might also decide at some point to change the format of the keys, or the format of the values. You could invalidate the keys, or empty the cache. But as previously mentioned, generally you want to make these changes while preserving the end user experience. The invalidation of keys can be done by including the version (or generation) in the key. By only changing the version, the previous key gets invalidated withouth any changes in memcache.

Another option for the migration is to stop the site and migrate the data during a maintenance window. If you have a small set of data this could be an option but you should avoid it. Users do not like maintenance windows.

Memcache Server Migration

In order to migrate a memcache server you need to design a mechanism to migrate the data from one server to another one while the site is up and running. The way to do this is by integrating the migration mechanism into your application code.

If you are facing this problem, it's likely that you already have a framework that transparently accesses memcache, and redirects to data stored in the database when there is no data in memcache.

If a memcache server is accessed by an IP address, you need to change this inside your framework so it is accessed by your internal storage ID instead. That storage ID can have any information attached to it and one piece of information will be the IP address. When your application is coded to access the memcache via the storage ID you can configure it to transparently use any server. This comes in handy during memcache migration. In other words, you can get a memcache driver by its storage ID.

We could design a solution with the following objects.

The MemcacheFactory  will return a memcache driver when its getObject($storageId) method is called. What driver is returned is transparent to client code.

If you manage a lot of data, you shouldn't migrate all the keys that are being used at the same time. You should do it progressively by defining a migration rate. A migration rate of "0" will mean that you don't migrate any keys at all and a migration rate of 6 will trigger the migration of 6% of the keys.  After determining the migration rate you need to decide the increment you want to apply to the rate and the frequency of the updates. The increment is directly related to the number of misses in memcache; it should be small enough to not increment them too much and avoid unhealthy spikes. The frequency is related to the number of accesses to the keys. It should be big enough to get the target keys used and consequently migrated. There are no magic values; the right values will depend on your data. For example, you could decide to increment 5% of the rate every 12 hours.

The method getObject would be something like (in PHP):

public function getObject($storageId, $forceRecreate = FALSE) {
    if ($forceRecreate or !isset($this->drivers[$storageId])) {
                ...
        $driver = $this->getDriver(...);
        if ($migrationData !== FALSE) {
                $driver = new MigratingMemcacheDriver($driver);
        }

        $this->drivers[$storageId] = $driver;
    }
    return $this->drivers[$storageId];
}

The getObject method just with an ID instantiates the driver with all the data it needs (ip, port, ...).

This leads to the question of how you choose what keys to migrate. You need a hash function that distributes your keys uniformly. The hash function you choose should be tested against real keys (you can get a set of them easily by sniffing the network). In the linked article, there is a good set of hash functions. Now that you already have everything you need, how will it all work? If you are using a memcache driver that is being migrated it will perform operations depending on whether the key of the operation is being migrated. If the key is not in the process of being migrated the operation will go against the old server. If the key is being migrated the operation will go to the new server.

Let's see it with code... For example the add operation in the MemcacheMigrationDriver would be something like:

public function add($key, $value, $ttl = MemcacheDriver::DEFAULT_TTL) {
    return $this->getDriver($key)->add($key, $value, $ttl);
}

private function getDriver($key) {
    if ($this->migrationHelper->toMigrate($key)) {
        $result = $this->migrationDriver;
    } else {
        $result = $this->driver;
    }
    return $result;
}

The MemcacheMigrationDriver maintains internally the references to the old driver and to the new driver. It is a proxy object. The decision of whether a key is going to be migrated is delegated to a helper object.

If there is a ‘memcache miss’ after you load the data from the DB the data will the cached. With this solution you will be moving data from one server to other through memcache misses.

In the described solution all the logic related to the migration is distributed between the factory and the MemcacheMigrationDriver.

Memcache Data Format Migration

This migration happens inside a server, when a change in the format of the key or the format of the value is needed.

In case you want to change the value and in situations when it does not affect many keys you can just invalidate them. If you are using a framework you should be able to do it with a version tag by modifying the version and leaving the old entries in memcache to expire.

It´s important to keep in mind, however, that when the change affects a lot of keys or values you need a mechanism to do it progressively as in the 'memcache server migration'. Similar to the 'memcache server migration', this migration can be managed by a framework but the framework can´t manage the change in the format, therefore additional work is required by the developer who is migrating the data. The worst scenario here would be when you want to change all the keys or all the values.

Migration of a key

Here we are going to show a different solution than the one described in 'memcache server migration'. Instead of using memcache misses we are going to update the new entry without accessing the DB in case the old key exists in memcache.

The change of the key format should be done progressively because the number of accesses to memcache is increased.

In order to reflect that a memcache format migration is active you need to modify the configuration of the framework so that when a memcache miss is reached in a reading (in a writing we need to do nothing) a callback to get the old key is performed and the old key is used. A successful memcache hit with the old key will automatically trigger the update of the memcache.

To sum things up, during a migration of keys there are at least a couple of accesses to memcache in case of a miss. There are three accesses if the key is being migrated.

The implementation of this migration is done in a different layer than the 'server migration'. It could be implemented inside the driver, but it is generally preferable to implement it in a more external layer (in which you can have other functionality, like transactions for example). The logic works only with one memcache driver. The code for a migration of keys would be similar to the code for a migration of values.

Migration of a value

As in 'migration of a key', you need a callback to get the right value from the key with the old format after it is received from memcache. The detection of the old or new format can be performed in another callback.

After the callback returns a new value the memcache is updated with it, so there are a couple of accesses instead of one to memcache.

Let's see it with some code. The object that has made the change in the format has to implement the following interface.

interface MemcacheValueMigration {
    public function getNewValue($key, $oldValue);
    public function isOldValue($key,$value);
}

So we could write the following code (as you can notice, the logic is outside the memcache driver):

private function getMigratedValue($key,$value,$object) {
    $result = $object->getNewValue($key,$value);
    if ($result !== FALSE) {
        ...
        $driver->store($key, $result);
    }
    return $result;
}

private function recordFromMemcache($key,$object) {
    ...
    if ($this->migratingMemcache($object) and $object->isOldValue($key,$value)) {
        $result = $this->getMigratedValue($key, $value,$object);
    } else {
        ...
    }
    ...
}

Aditional considerations

Before implementing a migration mechanism consider whether it is truly necessary, because proper development requires some time (it won´t be implemented in an afternoon...) and a lot of testing. You have to be very sure it works properly before trying it out with real data.

The most dangerous migration is the migration of values because it can break down the system if the values get corrupted. You can provide mechanisms to rollback the operation or to invalidate the migrated keys, but they will have additional performance costs, as the access will be redirected to the DB for each invalidated key.

If something goes wrong in the migration of keys, you can just rollback to the previous format and all the new keys will be automatically invalidated. But its important not to forget that the values associated with the old keys could already be invalid.

The good news is that if there are any problem they will show up very soon.

Implementing the procedure incorrectly isn't the only risk. Accesses to memcache shouldn't be increased unnecessarily.

Conclusion

As it has been described in this article it is possible to implement a general mechanism to migrate memcache data within a framework.

Migration from one server to another can be done automatically, being activated by configuration.

Migration of keys or values inside a server needs some coding outside the framework. Helper classes should be provided by the framework. Migration of a bit set of data should be done progressively.

JavaScript Tests 1 - DOM lookup

Posted on 3/17/2010 by José Serrano Núñez Frontend Engineer

As shown in below tables, there are different sets of time for each test in particular, this is because each test has been timed performing on a different DOM tree for the sake of completion and complexity. Rough estimates on the DOM elements used in the site are up to 3500 at its highest and so the heaviest tests timed are performed on an approximate DOM tree size looped a thousand times (3.5K * 1K). Tests range from 13 (static DOM tree), to 1.5k and 3.5k elements (the last two DOM trees have an approximate number of elements since they are generated randomly).

The methods timed are commonly used, as are getElementsByTagName, getElementById, walk the tree, etc. In both their native and jQuery implementations (since jQuery is a very commonly used spell within our scripts).

Notice: The tests performed on the native and jQuery methods are considerably different in terms of DOM tree size (browsers lock up when jQuery tests are performed with as many nodes as the native tests have). Although valid metrics can still be taken with less number of nodes (13~500 nodes).

i. Firefox 3.0

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName 0.19 5263.157 3.057 190
getElementById 0.044 22727.272 13.204 44
getElementByClass 0.064 15625 9.078 64
walking 0.581 1721.170 -- 176

DOM tree size: 13 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

10.76

92.936

2.960

10760

getElementById

8.741

114.403

3.644

8741

getElementByClass 7.699 129.886 4.137 7699
walking

31.855

31.392

--

31855

DOM tree size: 1765 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

23.515

42.526

2.698

23515

getElementById

17.991

55.583

3.526

17991

getElementByClass 15.367 65.074 4.129 15367
walking

63.454

15.759

--

63454

DOM tree size: 3513 Elements

ii. Firefox 3.5

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName 0.164

6097.560

1.073

164
getElementById 0.021 47619.047

8.380

21
getElementByClass 0.018 55555.555 9.777 18
walking 0.176

5681.181

-- 176

DOM tree size: 13 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

10.368

96.450

0.810

10368

getElementById

9.037

110.656

0.930

9037

getElementByClass 1.844 542.299 4.559 1844
walking

8.408

118.934

--

8408

DOM tree size: 1752 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

20.115

49.714

0.852

20115

getElementById

17.102

58.472

1.003

17102

getElementByClass 4.263 234.576 4.024 4263
walking

17.156

58.288

--

17156

DOM tree size: 3506 Elements

iii. Internet Explorer 6

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

0.281

3558.718

2.334

281

getElementById

0.344

2906.976

1.906

344

getElementByClass 0.172 5813.953 3.813 172
walking

0.656

1524.390

--

656

DOM tree size: 13 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementByTagName 7.069 131.423 3.725 7609
getElementById

75.531

13.239

0.375

75531

getElementByClass

35.875

27.874

0.790

35875
walking

28.344

35.280

--

28344

DOM tree size: 370 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementByTagName 15.188 65.841 4.230 15188
getElementById

225.719

4.430

0.284

225719

getElementByClass

126.796

7.886

0.506

126796
walking

64.25

15.564

--

64250

DOM tree size: 719 Elements

iv. Internet Explorer 7

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

0.234

4273.504

1.602

234

getElementById

0.11

9090.909

3.409

110

getElementByClass 0.078 12820.512 4.807 78
walking

0.375

2666.666

--

375

DOM tree size: 13 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementByTagName 23.985 41.692 2.446 23985
getElementById

154.125

6.488

0.380

154125

getElementByClass

62.562

15.98

0.938

62562

walking

58.688

17.039

--

58688

DOM tree size: 1763 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementByTagName 49.219 20.317 2.379 49219
getElementById

565.75

1.767

0.206

565750

getElementByClass

229.516

4.356

0.510

229516

walking

117.093

8.540

--

117093

DOM tree size: 3513 Elements

v. Google Chrome 3.0

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

0.128

7812.5

6.937

128

getElementById

0.035

28571.428

25.371

35

getElementByClass 0.013 76923.076 68.307 13
walking

0.888

1126.126

--

888

DOM tree size: 13 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

7.944

125.881

2.887

7944

getElementById

3.547

281.928

25.371

3547

getElementByClass 1.532 652.741 68.307 1532
walking

22.94

43.591

--

22940

DOM tree size: 1751 Elements

Method/Times Time/Iteration (-better) Executions Per Second (+ better) Times faster than walking (+ better) Total Execution Time (- better)
getElementsByTagName

15.976

62.593

2.988

15976

getElementById

7.393

135.263

6.457

7393

getElementsByClass 2.646 377.928 18.043 2646
walking

7.743

20.945

--

47743

DOM tree size: 3514 Elements

In Firefox, using the 'getElementByClass' method is faster. It is proportionally ten times faster than walking the whole DOM tree in small pages, and around four times faster for really big DOM trees. Another noticeable fact is that as the page grows in DOM nodes, retrieving a node by its id levels with the time needed to walk the whole node in search of that particular id.

Using Internet Explorer: getting nodes by the 'getElementByClass' is also fastest but for a small page with very few DOM elements. When the DOM node number rises, using the 'getElementsByTagName' is preferable.

Google Chrome is faster getting nodes by their class in all of the measures taken. It is also the fastest of all the targeted browsers.

Chat in the making

Posted on 3/17/2010 by Carlos Abalde Backend Engineer What is the recipe to successfully deploy a large scale and cost-effective chat service in a couple of months and not die trying? Probably there are as many answers as people wanting to contribute with their ideas. Here at Tuenti we enjoy open source and innovative approaches. This has been our dynamic duo when developing our web-based instant messaging (IM) service.

Why reinventing the wheel designing the ultimate IM service? That's usually the shortest path to repeat old mistakes and, even worst, delay product launch indefinitely. Be innovative, get a high quality IM platform, extend and/or adapt it to fit your requirements, and finally, use your experience to contribute back to the community. That is the philosophy behind open source, and that's the way we wanted to build Tuenti's chat service.

Outstanding technologies There are a good amount of outstanding open source IM solutions available out there. Specifically, those based on the open messaging standard XMPP are becoming increasingly popular. Nowadays XMPP is a mature, open, distributed and extensible middle-ware ready to power next generation large-scale real-time web applications. We strongly believe in the power of XMPP, and consequently we believe in the Jabber instant messaging and presence technology as the best choice for the Tuenti's IM service.

Jabber is a powerful IM technology, but that's not enough. The beauty of working at Tuenti is that every new product must be able to handle millions of concurrent users as soon as it is launched. Particularly, our goal with Tuenti's instant messaging service was to be able to handle peaks of one million concurrent users chatting. That's the reason we arrived at ejabberd, a high performance clustered and fault-tolerant server of the Jabber protocol implemented in Erlang and deployed all over the world, from small/internal deployments to large scale ones handling millions of users.

Erlang is a functional distributed language created by Ericsson two decades ago. Ever since its inception, Erlang was specifically designed to develop large-scale, highly distributed and non-stop soft-real-time services running in telephony switches. After its publication with an open license, the Erlang Telecom Platform (OTP) has become a general-purpose framework successfully applied in many projects worldwide. In fact, ejabberd is a great example of the main Erlang/OTP strengths: its high productivity, 5 to 10 times higher than traditional programming languages --ejabberd is developed by a very small team, and its above average scalability and fault tolerance facilities for complex server projects --the prestige of ejabberd among other commercial products is a notable proof of that.

Putting all pieces together next step was gluing XMPP, ejabberd and Erlang/OTP together with the complex backend currently handling all Tuenti services. Tuenti's chat is a simplified persistent-state-less instant messaging service accessed by an unique JavaScript client implementation. However, XMPP provides lots of extra built-in features and extensions. Therefore, the big challenge when putting all pieces together was simplifying and optimizing the ejabberd implementation as much as possible in order to handle even more concurrent users per server.

Specifically, we focused on memory consumption optimizations, XMPP message efficiency, avoidance of any additional storage requirement and/or data duplications, bidirectional integration with current Tuenti's backend services, self-managed contention strategies on server overload, integration with existing monitoring systems, anti-abuse features, etc. As a result, a fully customized ejabberd implementation together with a smart partitioning and load balancing strategies where deployed in our data center to support the new service.

Lot of simulations, benchmarks and stress tests where conducted during the whole implementation process, but, how to launch a new and highly-trafficked service like a chat to a massive audience with some quality guaranties? Our approach was a combination of dark-launch and increasing rolling-out strategies: a couple of weeks before the public release of the instant messaging service, increasingly larger groups of selected users were connected to the service in the background, sending messages and reconnecting to the service every time they logged into the site.

Thanks to the dark launch several performance bottlenecks and minor bugs were detected and fixed, both in the implementation and systems architecture. The fine-tuned service was finally gradually published to all our users in just two days. As a result, Tuenti is the largest ejabberd deployment in Spain, one of the largest ones in the world, and probably up amongst the top few in the world for that combination of frontend and backend quality and usability. After the public launch, almost all Tuenti users logging into the site with supported browsers have also logged into the service, which have routed more than 100 million messages during the first week on-line.

Pages

Follow us