When Hashing Algorithms Don't Converge

In order to take advantage of a Python patch that helps resolve issues with high-memory usage for long-lived tasks, we recently tried to upgrade some our machines to Ubuntu 14.10, which includes a distribution of Python 2.7.8 that already incorporates this fix. After upgrading, we started to notice a large amount of cache misses in our memcached cluster. We initially thought the problem was related to cache evictions, but our dashboards all seemed to indicate that there was plenty of memory available for memcached to request additional amounts.

We started doing some experiments and noticed a strange behavior between memcache clients running on Ubuntu 14.04 and 14.10 machines. Often, writing a key/value pair on one machine couldn't be read back with a different Ubuntu distribution. On the same versions, the same key/value pair could be read back consistently. For instance, we would set a test pair with the following commands against our memcache cluster:

import pylibmc
cc = pylibmc.Client(['', '',''])
cc.behaviors = {'ketama': True, 'tcp_nodelay': True}
print cc.set('test', 123)
Attempts to read the result on both sides depended on which Ubuntu version initially set the key/value pair.
print cc.get('test')

Some background context: We chose to use the ketama hashing algorithm, which is designed to reduce the number of cache misses as you add or remove servers to your memcache cluster. Since memcached nodes do not replicate between each other, a hashing algorithm that doesn't completely cause the keys to be recalculated as nodes are removed or added is important to minimize the number of cache misses. For more on how the ketama hashing algorithms work, see here.

The only major apparent change between the Ubuntu versions was that the libmemcached versions were different. By building individual libmemcached versions, we were able to confirm that the problem started happening in versions after libmemcached 1.0.9. One indication that there was a difference was that calling get_behaviors() yielded different results depending on the libmemcached version. On Ubuntu 14.04, the ketama_weighted parameter was always being set. On Ubuntu 14.10, it was not.

We traced the problem down to a bug that was fixed in libmemcached 1.0.9:

if (MEMCACHED_DISTRIBUTION_CONSISTENT_WEIGHTED) // enum, which always resolves to true

It turns out the logic for checking whether to use weighted Ketama in libmemcached 1.0.9 was always resolving to true, causing this option to be used in Ubuntu 14.04 regardless of any options that you set. Because subsequent libmemcached versions had this issue corrected (i.e. Ubuntu 14.10), different hashing algorithms are essentially being used. Because memcached clusters do not replicate their data across all machines, choosing a different hashing algorithm results in a different machine being read.

The lesson here is that if you intend to use memcached and wish to upgrade some of your Ubuntu machines, the safest option is to use weighted Ketama. Obviously if you already have a mix of older and newer Ubuntu machines in production, you should either move to use to use weighted Ketama and/or upgrade all machines to use the newer Ubuntu version.

How Facebook fixed their IE8 issues this past week

The problem at https://developers.facebook.com/bugs/791622154267956 seems to have fixed itself, but there was nothing on the bug report to indicate that it was resolved. There were enough people this week who said that things were working again, so it wasn't clear what had happened.

After tracing through Facebook's minified JS over the weekend, I came upon a tangential issue that referred a module named "quickling." It turns out that Quickling refers to Facebook's entire Ajax framework:

Many of our users saw that blank content area with the Facebook toolbar at the top. The blank area seemed to indicate that the Quickling framework was blanking the screen after successful logins. On this blank page, it was supposed to redirect back to our site -- the problem was that a lot of users were seeing "Errors on the Page" on the bottom left corner and weren't able to complete the auth flow.

I took a snapshot of the breaking JavaScript in question -- essentially the file is a shim for all the JS methods that aren't included with Internet Explorer. What I was looking for in this code was where the redirect URL would happen. I managed to confirm the section of the code is the goURI() function that usually gets executed on successful redirects. It was easier to use IE9 than IE8 to identify this function, which has the ability to debug minified JavaScript. In addition, without using an IE-based version, this file didn't seem to get loaded.

__d("goURI", ["URISchemes"], function(a, b, c, d, e, f, g) {
    function h(i, j, k) {
        i = i.toString();
        if (/^([^.:/?#]+):/.test(i) && !g.isAllowed(RegExp.$1)) throw new Error('goURI: URI scheme rejected, URI: ' + i);
        if (!j && a.PageTransitions && a.PageTransitions.isInitialized()) {
            a.PageTransitions.go(i, k);
        } else if (window.location.href == i) {
        } else window.location.href = i;
    e.exports = h;
}, null);

Note: The function __d() is basically equivalent to their require() function used in RequireJS. The first parameter is the module name being declared, the second declares the module depedencies, and the third provides references to the declared dependencies, including 6 default ones that are always included (see http://connect.facebook.net/en_US/all/debug.js for more context.)

Comparing against what this IE-specific code is today, it looks like the code that injects itself for checking load times (called "Calvary" -- http://davidwei.org/cv/talks/FacebookFrontEnd_Velocity2009.pdf) wasn't being wrapped in a require block.

Old file: https://fbstatic-a.akamaihd.net/rsrc.php/v2/yP/r/ZUMgdMGlluT.js
New file: https://fbstatic-a.akamaihd.net/rsrc.php/v2/yD/r/ZCm6GakvyT5.js

< /*!CK:3945686364!*//*1420495125,*/
> /*!CK:2123995118!*//*1421197783,*/
< if (self.CavalryLogger) { CavalryLogger.start_js(["FwIBa"]); }
> (self.TimeSlice ? self.TimeSlice.guard : function(f) { return f; })(function() {if (self.CavalryLogger) { CavalryLogger.start_js(["lPiYN"]); }

< __d("setIntervalAcrossTransitions",[],function(a,b,c,d,e,f){function g(h,i){return setInterval(h,i,false);}e.exports=g;},null);
> __d("setIntervalAcrossTransitions",["TimeSlice"],function(a,b,c,d,e,f,g){var h=a.setInterval;e.exports=function(){for(var i=[],j=0,k=arguments.length;j<k;j++)i.push(arguments[j]);i[0]=g.guard(i[0],'setInterval');return h(i[0],i[1],i[2],i[3],i[4],i[5]);};},null);

I suspect it's the changes in this diff that helped resolve our issues this past week. At the very least, it has some connection to the 2nd bug I encountered that eventually led to these findings.

Learning Python's C Extension API through librabbitmq

Over this past weekend, I was trying to figure out how to enable some of the RabbitMQ extensions in the AMQP standard. One of these features includes the ability to receive a connection-blocked status in the event that RabbitMQ decides to start throttling connections, which can happen because of memory pressure or a large influx of incoming messages being published to a queue. I was trying to understand among other issues why performance of certain processes seemed to slow down without any obvious hint or warning.

We use the librabbitmq module, which is a highly performant AMQP client written in C for the Celery project. The issue is that librabbitmq doesn't expose the ability to enable these extensions directly from Python. I wanted to figure out a way to pass in a hash structure similar to how the Ruby AMQP client Bunny provides a dictionary of extension properties:

      :capabilities => {
        :publisher_confirms           => true,
        :consumer_cancel_notify       => true,
        :exchange_exchange_bindings   => true,
        :"basic.nack"                 => true,
        :"connection.blocked"         => true,
        # See http://www.rabbitmq.com/auth-notification.html
        :authentication_failure_close => true

How would one modify the existing librabbitmq source code to do the same except in Python? First, I had to understand how the Python C Extension API worked. Because segmentation faults and memory leaks are common when working in the C language, I realized that I needed to rebuild the Python source tree to trace down which line of code was contributing to the errors.

Since all the underlying methods for the librabbitmq library are implemented in C, the first thing I needed to do was to modify the connect() method of the Connection class to be able to accept arguments. Unless I made changes to the underlying C code, Python would not recognize this library as needing any parameters unless I changed this declaration. The change entailed modifying the METH_NOARGS to METH_VARS in connection.h:

static PyMethodDef PyRabbitMQ_ConnectionType_methods[] = {
    {"fileno", (PyCFunction)PyRabbitMQ_Connection_fileno,
        METH_NOARGS, "File descriptor number."},
    {"connect", (PyCFunction)PyRabbitMQ_Connection_connect,
        METH_VARARGS, "Establish connection to the broker."},
(If I wanted keyword arguments, I could also use the METH_KEYWORDS definition too. The declaration can be bitwise joined to accept both positional and keyword arguments.)

Once I allowed the method's signature to accept positional arguments, the next step was to be able to convert the arguments into a data type that could be used by the AMQP library. The PyArg_ParseTuple() function allowed me to specify how to extract the arguments provided and has different format options to use (i.e. converting a parameter into a native C integer). I ended up deciding to keep the argument as a Python Object data type since the AMQP library C code had a special function called PyDict_ToAMQTable that takes a PyObject type and converts it to a specific C data structure.

static PyObject*
PyRabbitMQ_Connection_connect(PyRabbitMQ_Connection *self, PyObject *args)
    PyObject *client_properties;

    if (!PyArg_ParseTuple(args, "|O", &client_properties))
        goto bail;
(Note the pipe symbol (|). It specifies that the argument can be considered optional when invoking the connect() method.)

The next step was to take this PyObject type and convert it to a data structure for the AMQP client library. Specifically, I needed to figure out how to convert this PyObject to an amqp_table_t data structure, which is what the amqp_login_with_properties() function uses to send the correct wire format to the RabbitMQ server. The challenge was to figure out how to create this data structure and set the values accordingly.

Even though the librabbitmq module had this special function to handle the conversion of Python objects, one major issue that I encountered was that the function didn't handle Python boolean types, so the wrong wire format was initially being sent to the RabbitMQ broker. I came to this conclusion only after capturing the network traffic and comparing the responses from the broker against the output from the Ruby AMQP client. The changes to support converting boolean values are listed in this pull request.

There were other minor bug fixes I had to make to the librabbitmq module, such as preventing segmentation faults when using integer values. The full set of changes in librabbitmq are located in this pull request. There is still more work to be done in terms of making the AMQP extensions fully supported, so these changes are just the start. I hope that this writeup serves as a guide to those less familiar with how Python C extension modules work and motivates others to make similar improvements too!

Posted on June 16, 2014