Exponential backoff is the go-to algorithm for dealing with transient remote API errors in client applications. Indeed, all the major cloud service providers document it (AWS, Google, Microsoft) and incorporate it in their respective SDKs (e.g. AWS’s Javascript SDK). It is simple to explain (“double the retry delay after each error, limit to a max value, add some jitter” – more on the latter below), trivial to implement, and it “just works”.

The problem is it’s not very good at throttling your requests and avoiding errors – you could say it’s appallingly bad. This graph is telling:

Continue Reading

Database and storage systems with control over spatial locality and window or page-level compression (or a moral equivalent) can achieve fantastic compression rates when similar pieces of data are placed close together.

Back in 2004, Bigtable was used by Google to store crawled web page contents, obtaining 10-to-1 space reductions, despite using very fast compression. The space gains were better than the 3-to-1 or 4-to-1 ratios resulting typically from slower algorithms like GZip. This was achieved by storing (keying) all pages from the same host close to each other.

Likewise, a year later git used locality to improve delta compression in pack files.

Similarly to git, the Sync Appliance uses structures resembling Merkle trees in content-addressed storage to power the time travel (point in time recovery) functionality. Unlike git, though, this is not used for file data, and it is possible to purge files or versions without having the rewrite the history (also, there’s no separate stop-the-world packing phase or blob GC, everything is done incrementally).

git uses simple heuristics to order objects and pick candidates to perform delta compression against. Is it possible to find a more general way to improve spatial locality of arbitrary blobs in content-addressed storage? You’re probably guessing it is, and you’re right if so.

Continue Reading

Once you know how much you want to charge and which taxes apply, and have all the information you are required by law to keep, it’s finally time to perform the payment and fulfill the order. And, of course, you want both to happen at once. Fulfillment without payment is bad for obvious reasons, and because moreover you become liable for tax over something you were not paid for. Payment without fulfillment is even worse: there’s no easier way to lose a customer than charging without delivering (and you’ll get a chargeback with a penalty sometime later).

This post explains how we perform (credit/debit) card payment via Stripe and order fulfillment transactionally.

Continue Reading