Secure Random Code Generator

Long time no blog. I’d like to break the ice with a lighthearted Python code readability optimization discussion.

I need a Python function that generates short, random, numeric codes of a specified length using a secure random number generator. The codes must not start with 0, but the output should be a string. This was my first draft:

import struct, os

def make_code(digits):
    """Generate a random short code."""
    if digits > 9:
        return make_code(9) + make_code(digits - 9)
    [rand] = struct.unpack('>L', os.urandom(4))
    min_code = 10 ** (digits - 1)
    code = min_code + rand % (9 * min_code)
    return unicode(code)

Two things about this solution bothered me:

  • The math I used looks too clever. I’m not sure future maintainers will be able to understand why it works.
  • It discards a lot of the entropy provided by /dev/urandom, which could be expensive on some servers. (I confess this thought is premature optimization.)

To try to clean this up, I created a generator that produces random secure digits and based the make_code function on it:

def random_digits():
    while True:
        [n] = struct.unpack('>L', os.urandom(4))
        s = ('%d' % n)[1:]
        for c in s:
            yield c

next_random_digit = random_digits().next

def make_code(digits):
    return ''.join(next_random_digit() for _ in range(digits))

This felt better, but it has two critical problems. It can return 0 for the first digit, and due to the next_random_digit global, this solution is not thread safe! I’ve never tried to run a generator in multiple concurrent threads. I can only imagine the possible fireworks.

So I solved the problems as follows.

class RandomDigitStream(object):
    def __init__(self):
        self.streams = threading.local()

    def stream(self):
        while True:
            [n] = struct.unpack('>L', os.urandom(4))
            s = ('%d' % n)[1:]
            for c in s:
                yield c

    def make_code(self, digits):
        """Generate a random short code containing only digits."""
        try:
            next_digit = self.streams.next_digit
        except AttributeError:
            self.streams.next_digit = next_digit = self.stream().next

        while True:
            c = next_digit()
            # Don't use 0 for the first digit.
            if c != '0':
                break
        lst = [c]
        lst.extend(next_digit() for _ in range(1, digits))
        return ''.join(lst)

make_code = RandomDigitStream().make_code

Now the solution is large and I’m pretty sure it’s less readable than the original solution. Anyone want to take a shot at making this better? I’m currently thinking that the original solution was better than I thought.

Pyramid and Traversal

There has been a lot of discussion in the Pylons/Pyramid community about the concept of traversal.  Some people, when faced with traversal for the first time, get confused and want it removed from Pyramid.  They want Pyramid to support only routes, a different way of achieving a similar goal.

Personally, I think traversal is simpler and more powerful than routes.  Conceptually, traversal is simply an interpretation of path segments as item lookup: the URL path “/spam/eggs/ham” is interpreted in Python as “root[‘spam’][‘eggs’][‘ham’]”.  The root object is some object with a __getitem__ method; root.__getitem__(‘spam’) returns some object which has its own __getitem__ method, and so on.  If __getitem__ raises a KeyError, then Pyramid generates an HTTP 404 error (which you can customize).

The objects along the path are often persistent, but there is no reason they have to be.  Pyramid only requires __getitem__.  Well, actually, they should also have __parent__ and __name__ attributes if you want Pyramid to generate correct URLs for you.  WingCash, which will soon use Pyramid, uses traversal over non-persistent objects that only survive for one request.

Routes, on the other hand, requires a mini-language (similar to regular expressions) and iteration over possible path interpretations.  Expanding the model requires changing the central list of all possible routes.  Routes limits the complexity of the model, while traversal allows arbitrarily complex models.

Traversal is one of the best ideas from the Zope world.  Traversal was painful to do correctly in Zope, yet we still loved it because it allowed us to expand web applications organically.  I am very glad that Pyramid has simplified traversal and made the mechanism easily accessible.  I think traversal is a major ingredient that led to the success of Plone.

The Holy Grail server framework

… and I think I just wrote it.

For years, I have wanted a Python TCP server framework with the following features.

  • Multi-process: I want the framework to be able to use all available processors and cores with no GIL (global interpreter lock) contention.  This is important for CPU-bound applications.
  • Multi-threaded: Each process should have a fixed number of threads so it can multiplex tasks.  This is important for I/O-bound applications.
  • Graceful shutdown: when I issue the kill signal, I want the server to close its server socket immediately, but I want existing connections to have a chance to finish their work.  This is important if the connections are involved in transactions.
  • Graceful code reloading and reconfiguration: when I issue the HUP (hangup) signal, I want the server reload its configuration, spin up new processes, and tell the old processes to stop accepting new connections and shut down only when finished.  Also, the server should only load application code in child processes, so that loading new code is simply a matter of issuing a HUP signal.
  • Transaction integration, including two-phase commit: If the connection dies, I want to roll back the associated transaction automatically, unless the connection dies after the first phase of two-phase commit, in which case I want to leave the transaction in a partially committed state and sort out the issue at a higher level.
  • No proxying: I don’t want all traffic to flow through the master process, which would be bad for both reliability and performance.  Linux (and maybe any Unix system) allows multiple processes to listen on the same server socket; I want to use that feature.

What I have described is well beyond what the Python standard library provides.  In theory, it will let me have all the joys of transactions and zero-downtime updates in a high performance environment.  I have been searching for an implementation of this design for years.  This week, I have been reworking some WingCash code to make better use of transactions and I realized I really need this design.

So, on Monday, I wrote my dream server framework and tried it out… and to my surprise, it actually worked!  I was surprised because I thought that some Python hacker, somewhere, must have tried this experiment by now, and must have failed; otherwise the experiment results would surely be published or mentioned somewhere.  Perhaps my requirements are not very common, the design is not obvious, or I did not type the right search terms.

I am now writing tests for the new server framework, which I am tentatively calling fdtserver (forking distributed transaction server).  I won’t put it into production until it has 100% statement coverage like the rest of WingCash.  I wonder whether fdtserver should be open source.  Doesn’t the need for all those features, particularly graceful code reloading, exist elsewhere?

WingCash is Open!

I’ve been working on a cool project for the past year.  I haven’t been able to share much about it, but now that it’s open to the public, I intend to talk about it and explore it in the open.  It’s built on Python, Repoze.BFG (to be replaced with Pyramid soon), PostgreSQL, Buildout, and a big pile of other great software.

WingCash is a system for sending cash on the Internet between people and businesses.  It is Brad Wilkes’s idea and dream.  He had the idea while working at FamilySearch.  FamilySearch is trying to help genealogical archives remain financially solvent so that the records they hold can be accessible to the world.  WingCash is completely independent of FamilySearch, but one of the intents is to solve a major financial issue for genealogical archives.

To that end, a foundational principle of WingCash is to charge no fees for direct exchanges of cash between WingCash users.  On WingCash, sending a penny is sensible and economical.  It is also sensible for millions to send a penny apiece to a single recipient.

WingCash does have to charge fees for other kinds of transfers, such as transfers to a bank, since banks charge WingCash for the service.  WingCash will also offer premium services.  But the core service of holding cash and sending it to anyone for no charge will remain free for good.

WingCash currently has limited resources, so please don’t hammer the newborn server, but WingCash does have a design that should allow it to expand into many servers over time.  Check it out and say what you think.  Please add your ideas to the feedback forum.

Here are some topics I expect to cover in future posts about WingCash:

  • I heart pythonsecurity.org
  • Bank notes are back
  • Integration with web stores and donation pages
  • Plans for the API

Python JSON Performance

This test compares the speed of various object serializers available for Python. I should have run it long ago. It opened my eyes a bit!

import time
import json
import simplejson
import marshal
import pickle
import cPickle
import cerealizer

def time_module(module):
    d = {}
    for k in range(100000):
        d[str(k)] = -k

    start = time.time()
    enc = module.dumps(d)
    stop = time.time()
    enc_time = stop - start

    start = time.time()
    got = module.loads(enc)
    stop = time.time()
    dec_time = stop - start

    if got != d:
        raise AssertionError("Module %s failed encoding" % module.__name__)

    print '%s: %.3f encode, %.3f decode' % (
        module.__name__, enc_time, dec_time)

if __name__ == '__main__':
    time_module(marshal)
    time_module(simplejson)
    time_module(cPickle)
    time_module(pickle)
    time_module(cerealizer)

    class EnhancedCPickle:
        __name__ = 'EnhancedCPickle'
        def dumps(self, obj):
            return cPickle.dumps(obj, cPickle.HIGHEST_PROTOCOL)
        def loads(self, data):
            return cPickle.loads(data)

    time_module(EnhancedCPickle())

    time_module(json)

Here are the results I got.

marshal: 0.010 encode, 0.016 decode
simplejson: 0.056 encode, 0.035 decode
cPickle: 0.136 encode, 0.051 decode
pickle: 0.570 encode, 0.553 decode
cerealizer: 0.268 encode, 0.249 decode
EnhancedCPickle: 0.115 encode, 0.030 decode
json: 0.214 encode, 1.195 decode

According to the Python documentation, the built-in json module is based on simplejson. What the documentation fails to mention is that simplejson is at least an order of magnitude faster than the built-in module. It’s even faster than cPickle, according to this microbenchmark. I would use the marshal module if I could, but that would introduce security issues in my application (as would the pickle modules).

PyCon 2010: I Want to Present Something

I’ve been racking my brains to find something to present at PyCon 2010. I have been trying to find something good to present since PyCon 2003, when I last presented at PyCon.  (I talked about Ape, the Adaptable Persistence Engine for Zope.)  I really liked the experience of presenting and it led to a lot of interesting conversations. Since then, however, nothing has really struck me as a good idea for a presentation. The right idea has to fit at least these criteria:

  • It’s something I’m good at.
  • At least a handful of PyCon attendees would like to learn more about it in a presentation.
  • I can’t spend weeks to prepare for the presentation.

This year, I was planning to do a really fun presentation by writing some Python scripts for controlling a RepRap, then I was going to present the hardware and software.  That didn’t work out, however, because the warping issues with ABS (a type of plastic) are just too severe to print useful parts, so my RepRap has sat idle.  (I’m now considering PLA, but it’s a newish and expensive material.)

Here are a few other ideas for a presentation topic.  What do you think?  Any other ideas?

  • RelStorage.  I could talk about future plans, why I think it is an improvement over ZEO, and why you should use it.  There seem to be a lot of people with questions about RelStorage, so it would be nice to have some time to answer the questions in a big room so others can hear the answers.
  • KARL and BFG.  This would probably be a team presentation.  KARL is some fairly interesting software that I got to help develop this year.  I could talk about the software, along with the development experience and style.  In KARL we made a conscious choice to ignore certain apparent DRY violations, leading to significant productivity gains.
  • A friendly introduction to Buildout.  Buildout is a tool that a lot of developers need, but don’t know it yet.  The function that Buildout performs is as important as version control and automated testing.  Come find out why Buildout is far better than a pile of Makefiles.
  • An introduction to Buildout (zc.buildout) for people familiar with Apache Maven.  Buildout and Maven fill approximately the same niche, but for different audiences.  (Buildout for Python, Maven for Java.)  Maybe there are Mavenites at the conference who would like to switch to a more Python centric system.
  • A discussion of text indexing in Plone and BFG.  This might be a narrow topic, but I find it interesting and important.  I have found ways to reduce complex 90 second text searches to 1 second.  The solution is not pure Python, unfortunately. 😉  I have also thought about how to expand into areas like faceted search/browse functionality.

Feedback encouraged!

The Fastest WSGI Server for Zope

I have been planning to compare mod_wsgi with paste.httpserver, which Zope 3 uses by default.  I guessed the improvement would be small since parsing HTTP isn’t exactly computationally intensive.  Today I finally had a good chance to perform the test on a new linode virtual host.

The difference blew me away.  I couldn’t believe it at first, so I double-checked everything.  The results came out about the same every time, though:

wsgi-zope1

I used the ab command to run this test, like so:

ab -n 1000 -c 8 http://localhost/

The requests are directed at a simple Zope page template with no dynamic content (yet), but the Zope publisher, security, and component architecture are all deeply involved.  The Paste HTTP server handles up to 276 requests per second, while a simple configuration of mod_wsgi handles up to 1476 per second.  Apparently, Graham‘s beautiful Apache module is over 5 times as fast for this workload.  Amazing!

Well, admittedly, no… it’s not actually amazing. I ran this test on a Xen guest that has access to 4 cores.  I configured mod_wsgi to run 4 processes, each with 1 thread. This mod_wsgi configuration has no lock contention.  The Paste HTTP server lets you run multiple threads, but not multiple processes, leading to enormous contention for Python’s global interpreter lock.  The Paste HTTP server is easier to get running, but it’s clearly not intended to compete with the likes of mod_wsgi for production use.

I confirmed this explanation by running “ab -n 1000 -c 1 http://localhost/”; in this case, both servers handled just under 400 requests per second.  Clearly, running multiple processes is a much better idea than running multiple threads, and with mod_wsgi, running multiple processes is now easy.  My instance of Zope 3 is running RelStorage 1.1.3 on MySQL.  (This also confirms that the MySQL connector in RelStorage can poll the database at least 1476 times per second.  That’s good to know, although even higher speeds should be attainable by enabling the memcached integration.)

I mostly followed the repoze.grok on mod_wsgi tutorial, except that I used zopeproject instead of Repoze or Grok.  The key ingredient is the WSGI script that hits my Zope application to handle requests.  Here is my WSGI script (sanitized):

# set up sys.path.
code = open('/opt/myapp/bin/myapp-ctl').read()
exec code

# load the app
from paste.deploy import loadapp
zope_app = loadapp('config:/opt/myapp/deploy.ini')

def application(environ, start_response):
    # translate the path
    path = environ['PATH_INFO']
    host = environ['SERVER_NAME']
    port = environ['SERVER_PORT']
    scheme = environ['wsgi.url_scheme']
    environ['PATH_INFO'] = (
        '/myapp/++vh++%s:%s:%s/++%s' % (scheme, host, port, path))
    # call Zope
    return zope_app(environ, start_response)

This script is mostly trivial, except that it modifies the PATH_INFO variable to map the root URL to a folder inside Zope. I’m sure the same path translation is possible with Apache rewrite rules, but this way is easier, I think.

Anecdotal Evidence

I like to believe that I am a competent software developer in both Python and Java.  As a competent developer, I find that certain things are generally much easier than other things.

For instance, I just spent a frustrating week working out how to install a Shibboleth identity provider, yet I never got it working quite satisfactorily.  Then, after spending 30 minutes with Python-openid, I had an identity provider server running and I already felt quite confident with it.

It’s as if Java and Python are not really in the same league.  There is no way to prove that, though.  Sometimes Java wins anyway.