← Back to team overview

novacut-community team mailing list archive

Houston, We Have A Sorting Problem


No idea why this didn't dawn on me much earlier, but better late than never,
I guess.  There is a serious design problem with how we currently
base32-encode IDs, and this is something that we must fix before we bless the
final version one hashing protocol.

Note this email is long and technical, so no offense will taken if you decide
to stop reading here :)

Houston, We Have A Sorting Problem

Standard RFC-3548 base32 encoding has an unfortunate property in that the sort
order of the encoded data is different than the binary data, for example:

    =============  ===========
       Binary         Base32
    =============  ===========
     0 0000000000  13 3XO53XO5
     1 1111111111  14 53XO53XO
     2 2222222222  15 77777777
     3 3333333333   0 AAAAAAAA
     4 4444444444   1 CEIRCEIR
     5 5555555555   2 EIRCEIRC
     6 6666666666   3 GMZTGMZT
     7 7777777777   4 IRCEIRCE
     8 8888888888   5 KVKVKVKV
     9 9999999999   6 MZTGMZTG
    10 aaaaaaaaaa   7 O53XO53X
    11 bbbbbbbbbb   8 RCEIRCEI
    12 cccccccccc   9 TGMZTGMZ
    13 dddddddddd  10 VKVKVKVK
    14 eeeeeeeeee  11 XO53XO53
    15 ffffffffff  12 ZTGMZTGM
    =============  ===========

This is because the symbols in the RFC-3548 base32 encoding table aren't in
ASCII/UTF-8 sorted order, they are in this order::


Whereas sorted order would be this::


For space and performance reasons, a database might internally decode the
base32 doc IDs and build its indexes according to the compact, binary IDs.
This is an attractive option that we want to keep open.  But for simplicity
and compatibility, it can likewise be attractive to index according to the
base32 text.  Not to mention all the programmatic manipulation that will
happen with the docs on the application side of things, where sorting and
comparison of the doc IDs is not uncommon.

But these two approaches are going to face a giant problem as soon as one
needs to, say, request a range of documents from the other, for example a
query for all docs such that::

    start_id <= doc._id <= end_id

The binary vs base32 indexes would disagree on what the first and final
document IDs in the database are, so on the other end, this could easily
translate into a nonsense query like::

    14 <= doc_N <= 3

To be clear, I consider this a total deal-breaker for Dmedia, and so we
are *not* going to use RFC-3548 base32 encoding in the final version 1
hashing protocol.  It would be a nasty design wart that every implementation
would have to battle.  And that does not an ecosystem make.

So we're going to use *some* base32 encoding with a sorted-order alphabet,
but the question is, which one?

Simplest Solution?

Perhaps the simplest solution is to use the same set of symbols as RFC-3548,
but with an encoding table in sorted order?  We might call it Sorted-Base32,
and it indeed gives us a base32 sort order that matches the binary sort
order, as you can see:

    =============  ===========  ===========
       Binary         Base32       S-Base32
    =============  ===========  ===========
     0 0000000000  13 3XO53XO5   0 22222222
     1 1111111111  14 53XO53XO   1 46CL46CL
     2 2222222222  15 77777777   2 6CL46CL4
     3 3333333333   0 AAAAAAAA   3 AGTNAGTN
     4 4444444444   1 CEIRCEIR   4 CL46CL46
     5 5555555555   2 EIRCEIRC   5 EPEPEPEP
     6 6666666666   3 GMZTGMZT   6 GTNAGTNA
     7 7777777777   4 IRCEIRCE   7 IXVRIXVR
     8 8888888888   5 KVKVKVKV   8 L46CL46C
     9 9999999999   6 MZTGMZTG   9 NAGTNAGT
    10 aaaaaaaaaa   7 O53XO53X  10 PEPEPEPE
    11 bbbbbbbbbb   8 RCEIRCEI  11 RIXVRIXV
    12 cccccccccc   9 TGMZTGMZ  12 TNAGTNAG
    13 dddddddddd  10 VKVKVKVK  13 VRIXVRIX
    14 eeeeeeeeee  11 XO53XO53  14 XVRIXVRI
    15 ffffffffff  12 ZTGMZTGM  15 ZZZZZZZZ
    =============  ===========  ===========

This provides the easiest migration path for Dmedia as we wouldn't have to
change the sub-directories used inside the FileStore layout (there are 1024
sub-directories, built using the first two characters of the base32-encoded
file IDs).

However, in terms of being good Internet citizens, this seems like a *really*
bad idea.  Especially if (knock on wood) our database-friendly encoding gets
widely used, we'd be doing everyone a disservice by popularizing an encoding
that on the surface looks exactly like RFC-3548, but is in fact 100% not the

So let's rule out Sorted-Base32.

With even a single character difference in the encoding alphabet, it only
takes a mere dozen or so random IDs to have an *extremely* high probably of
getting an ID containing the symbol not present in the other alphabet.  At
which point the programmer knows the encoding that looked very much like
RFC-3548 is in fact not, and they can fix their code.

The problem of picking the character set comes down to this: here are 36
symbols, and we need to remove 4 or them::


RFC-3548 excludes ``0``, ``1``, ``8``, and  ``9``, so for our set to be
different, we need to include at least one of those.  The general goal is to
remove symbols that look too much alike so that the alphabet has a good
signal-to-noise ratio for us human folk.

However, before we dive into that, I'd like to step back and look at some
engineering properties that might help us narrow the search.

Engineering Considerations

In terms of engineering aesthetic, it's attractive to chop off characters at
the ends so that the reverse-table doesn't require any unnecessary internal
"dead-spots" (as, for example, the RFC-3548 set requires for ``8`` and ``9``).

When it comes to end-chopping, there are five permutations::


The topmost offers the max possible symbol difference from RFC-3548 (d=4), the
2nd has (d=3), and the bottom three all have (d=2).  So any of them would
work, as we only need d=1.

It may seem like splitting hairs, but I think even small improvements in how
quickly one can understand a technology can have a big impact on its adoption
success.  We certainly don't want something that seems *more* complex than

We have some solid engineering problems we're solving, issues that might
effect anyone using base32-encoded IDs, especially in document oriented
databases, distributed file systems, etc.  Even so, a non-standard base32
encoding means we're going out on limb here.  It would be far better for
Dmedia and Novacut if the encoding we come up with was also adopted by others.

In addition to the above engineering advantages (for specific problems),
I'd also like to have something that's just a tiny bit simpler and more
elegant than RFC-3548. Not the same, and certainly not worse.  Better, even
if only by a smidge.

So instead of opening Pandora's box in an epic search for the best 32 letters,
which would mean a reverse table that is full of more dead spots than RFC-3548,
I think we should restrict ourselves to picking the best of the five above

Signal to Noise

I'm unconvinced that one set of 32 can be much better than another because it
depends so heavily on the font being used, and the people of the world of
course aren't all using the same font.  Opinions are all over the map, for the
most part.

The once place where there seems to be near-consensus is around::

    0O (zero and oh)
    1I (one and eye)

At least there is agreement on them being a problem, not so much on the best
way fix it (remove the number, remove the letter, or even remove both?).

Fortunately, our hands are tied and we can only remove the numbers, so lets do
that.  Now we're down to three options, with two more symbols to remove::


We can remove ``YZ``, ``2Z``, or ``23``.  My vote is to remove ``2Z``, as they
look quite similar to each other, and I feel that probably provides the best
overall signal-to-noise.  So that gives us this alphabet::



I'm calling our encoding D-Base32 (D is for Dmedia, and D is for Database).  It
has the desired property of preserving the sort order, as you can see:

    =============  ===========  ===========  ===========
       Binary         Base32       S-Base32     D-Base32
    =============  ===========  ===========  ===========
     0 0000000000  13 3XO53XO5   0 22222222   0 33333333
     1 1111111111  14 53XO53XO   1 46CL46CL   1 57BK57BK
     2 2222222222  15 77777777   2 6CL46CL4   2 7BK57BK5
     3 3333333333   0 AAAAAAAA   3 AGTNAGTN   3 9FSM9FSM
     4 4444444444   1 CEIRCEIR   4 CL46CL46   4 BK57BK57
     5 5555555555   2 EIRCEIRC   5 EPEPEPEP   5 DODODODO
     6 6666666666   3 GMZTGMZT   6 GTNAGTNA   6 FSM9FSM9
     7 7777777777   4 IRCEIRCE   7 IXVRIXVR   7 HWUQHWUQ
     8 8888888888   5 KVKVKVKV   8 L46CL46C   8 K57BK57B
     9 9999999999   6 MZTGMZTG   9 NAGTNAGT   9 M9FSM9FS
    10 aaaaaaaaaa   7 O53XO53X  10 PEPEPEPE  10 ODODODOD
    11 bbbbbbbbbb   8 RCEIRCEI  11 RIXVRIXV  11 QHWUQHWU
    12 cccccccccc   9 TGMZTGMZ  12 TNAGTNAG  12 SM9FSM9F
    13 dddddddddd  10 VKVKVKVK  13 VRIXVRIX  13 UQHWUQHW
    14 eeeeeeeeee  11 XO53XO53  14 XVRIXVRI  14 WUQHWUQH
    15 ffffffffff  12 ZTGMZTGM  15 ZZZZZZZZ  15 YYYYYYYY
    =============  ===========  ===========  ===========

Because D-Base32 is *not* designed to encode arbitrary data, but instead is
designed only to encode our well-formed IDs, we're only supporting IDs that are
multiples of 40-bits, and we're *not* supporting padding.

Data to be encoded must be a multiple of 5 bytes in length, and ASCII/UTF-8
text to be decoded must be a multiple of 8 bytes in length.  This strict
validation is good in terms of enforcing correctness at higher levels, and it
makes the implementation easier, eliminates a lot of potential spots for
security goofs.

In terms of implementation, I currently have both a pure-Python version and a
high-performance C extension in this new `dbase32` project on Launchpad:


The C extension currently only supports Python 3.3 and newer (because I'm using
the new PyUnicode API).  There are daily builds for Raring:


This encoding will be used both for our 120-bit random IDs, and our 240-bit
intrinsic IDs (derived from the file content-hashes).  Because of the different
encoding alphabet, it will require tweaks to our schema validation functions
and to the FileStore layout.  We'll do our best to provide a reasonable
migration tool for users with existing Dmedia libraries, but I do not plan to
support the existing version zero interim hashing protocol alongside the final
version one protocol.  This base32 encoding change just makes that too much

So this will require coordinated releases of `filestore`, `microfiber`,
`dmedia`, and `novacut` when we switch from RFC-3548 base32 to D-Base32.  It's
too late in the month for this to happen for 13.01, so we'll target this for
13.02, which also gives us time to get feedback from folks before we finalize
our D-Base32 encoding.


So what do people think?

Any compelling proposals for ways in which we could stick with standard RFC-3548
base32 encoding and not have interoperability problems with a database that
indexes according to the binary IDs?  Would it be worth it?

Anything people think we should do differently in the proposed D-Base32

PS: A Note on Lowercase

Anyone with typographic savvy will tell you that using lowercase letters will
make the IDs more readable, and I don't disagree.  This is something that folks
put a lot of thought into for the z-base-32 encoding, which you can read about


However, I personally think the overall readability of our *schema* is far more
important than the readability of our encoded IDs.  After all, there is nothing
to *read* in the IDs as they are random, meaningless values, not words.
Whereas the *words* used in rest of the schema have been careful chosen to be
both clear and concise, and are *always* lowercase.

The reason I prefer uppercase IDs in the schema is it helps differentiate the
meaningless garble from the bits you actually will *read*.  For me, it helps
push the IDs into the background, and brings out rest of the schema more clearly
in the foreground.

For example, consider this Novacut edit node with lowercase IDs::

        "_id": "jg444obnf5juunspcce5ypik",
        "type": "novacut/node",
        "time": 1234567892,
        "audio": [],
        "node": {
            "type": "video/sequence",
            "src": [

And the same with uppercase IDs::

        "_id": "JG444OBNF5JUUNSPCCE5YPIK",
        "type": "novacut/node",
        "time": 1234567892,
        "audio": [],
        "node": {
            "type": "video/sequence",
            "src": [

Of course, arguments for lowercase IDs are welcomed... but please keep in mind
the overall schema readability.