streadway/ngx_txid — pull request #3 by GUI (2014-10-25 02:02:22+00:00)
Title: Fix so the generated txids are lexically sortable over time

The description of the project and the README indicate the generated IDs should be lexically sortable in their base32 format. However, based on log files, I was consistently seeing a lot of TXIDs being generated out of order. Here's a quick example that I pulled from a log file where I had both the TXID and the timestamp of the request. I then sorted the results by the TXID. As you can see, TXIDs from across days are intermingled, and within days, the timestamps are in the reverse order:

```csv
"a8ngh01uerf1r7ig51lg","2014-09-29T04:03:50+00:00"
"a8ngjg6fl9fkdqtppokg","2014-09-28T22:49:15+00:00"
"a8ngs02onb550dei94i0","2014-09-29T04:17:03+00:00"
"a8ngv00nfu7j74gm4khg","2014-09-28T20:55:46+00:00"
"a8ngv07p83gdhd077qd0","2014-09-28T17:52:16+00:00"
```

In this example, the requests are spread over a longer period of time, but on a busier server, I was seeing similar problems for requests within a few seconds of each other (there were concentrations of requests where things were sorted properly, but then randomly requests from other hours or days would pop up).

I believe the issue boiled down to the bitwise shifts going on in this bit code:

```
const ngx_msec_t msec = ngx_txid_next_tick() << 22;
out[0] = (msec >> 56) & 0xff;
out[1] = (msec >> 48) & 0xff;
out[2] = (msec >> 32) & 0xff;
out[3] = (msec >> 16) & 0xff;
out[4] |= (msec >> 8) & 0xff; // share the 5th byte with entropy
```

The problem was that not all of the timestamp was actually being added to the output. It's missing the shifts for `40` and `24`. The last shift for the last 2 bits should have also been for `16` (since the whole thing was right shifted by 22 to begin with, there was nothing on the `8` shift, so it was always random). So basically chunks of the timestamp data were missing from the output, so that would explain why things were a bit funky (but the beginning of the timestamp was present, so that's why things were sortable on the scale of multiple days).

I believe the fix for this is pretty straightforward (just filling in the missing shifts so all the timestamp data is present on the output).

The rest of this pull request is adding tests surrounding this behavior. Testing this with `Test::Nginx` was a little trickier than I had anticipated, so let me know if any of it doesn't make sense. Basically there's three new tests to sanity check all this:

- A test that performs 50 consecutive requests, sleeping 0.1 second in between each request. It then ensures that all the TXIDs generated are sortable (on short time-frame test like this, the previous algorithm was failing to provide sortable TXIDs, so even though it's only over a short time, I think this is a decent test of the main sortable behavior).
- A test that uses [libfaketime](https://github.com/wolfcw/libfaketime) fake nginx into thinking the current time is in the past and then checks to ensure the timestamp portion of the txid is what we would expect. I basically wanted some way to make sure the algorithm was sortable over much longer durations. This might have been easier with a C-level test, but since `Test::Nginx` doesn't support this, I landed on libfaketime to achieve this.
- The same test as above, but for a time in the future. Again, just to ensure that the TXID hash continues to increment lexically as expected.

Let me know if you have any questions. Thanks!