An Algorithmic Lucidity

I don't particularly care for Christianity, but my heart went out to the designer of the greeting card with a chocolate cross attached that was on sale at the corner drugstore. May His Light Shine Upon You, it said on the front, and Happy Easter inside, as if some foresight-burdened defender of the faith had reasoned, "We know we're powerless to stop the secular commercialization of our holy day, but maybe we can slow it down, just a bit."

A sentiment to remember for the day when your favorite ideology ends up on the wrong side of history.

Our users have a need although
Our budget's rather ...
     Thrifty—
Not just, "I want my data," but
"I want my data
     Swiftly."
But should their need our budget meet
I'd think it not an oddity,
In an age of open source in which
The hardware's a commodity.
The right solution's quick to get,
No need to hunt or forage;
We'll see our users' needs are met
With open object storage.

I—I'm afraid that examination of my 23andMe raw data has revealed a horrible truth about myself. I mean, I had always suspected, but now there's no room for doubt, no hope for denial. The terrible fact is that—

I am not a geneticist.

The other week I was reading a book that used the word multimegaline—from multi- and mega- and line, referring to software projects composed of many millions of lines of source code. But I prefer to believe that the last syllable rhymes with keen and that the word is good for anything really big.

Dear reader, if you're like me—and if you're not, why are you reading this stupid blog about random shit that no one who's anyone could possibly care about?—close the tab and go do something worthwhile instead. No, I mean it. I'll wait ...

Right. Dear remaining readers, since you're like me, you've probably considered force-pushing to a remote Git repository. Do not force-push to a remote Git repository.

I can hear you protest, "But, but—what about when I want branch B to have content from branch A but I don't want to do a merge like any sane person would, because rebasing would make the history more elegant in my completely arbitrary aesthetic opinion and because I'm a reckless degenerate who is too dumb to live?" Do the merge.

Because, commit my words, if you rebase and force-push—well, it's a story nearly as old as history itself (which began on 3 April 2005; so, like, a really long time ago). You might get away with it this time. And the next, and the next. But one day, your project will start failing with mysterious errors, errors ominously reminiscent of those caused by a nasty bug your gracious and talented colleague had fixed the other week. Your feeble attempts at investigation will fail, and you'll entreat your gracious and talented colleague to take a look.

You will never forget the expression of bafflement and horror that you'll infer must have crossed his face when he discovered that his fix for the nasty bug of last week had vanished, as if it had never been written. (Infer because all you'll actually observe is the message "FUCK" over the company IRC channel.)

After the hypothesis occurs to you, you'll have to explain to your gracious and talented coworker what you think could have happened—that you thought you had communicated with him about rebasing branch B eight days ago, but maybe you hadn't been clear, and that it was just barely possible, in theory, that maybe, possibly he had pushed his fix just before you force-pushed your newly-rebased branch ... overwriting your gracious and talented colleague's work on the remote. Not to be noticed for more than a week, long after your colleague had pulled the new version of branch B, overwriting his local copy.

Heed my words, dear reader! Unless you mend your ways, this is your future! I hear you sneer, "But pulling doesn't actually destroy data. It only retrieves the new commit and blob objects and updates the branch pointer; I know because I read it on Hacker News when I should have been working but wasn't because I'm a scoundrel and a thief. The missing commits should still be in the reflog, both in my hypothetical colleague's repository and on the remote."

But suppose the remote is an off-site hosting service that doesn't offer an API to the reflog. What will you do when your gracious, talented, long-suffering (from having to work with the likes of you) colleague fails to find the missing work in his local reflog? "But how could that be?" you ask. Well, I don't know. Maybe the Git garbage-collector ran at an inopportune time? Maybe your understanding of Git's internals gleaned from the tl;dr section of a blog post eight months ago wasn't entirely accurate? Whatever happened, and however it happened, eventually your gracious and talented colleague will give up and spend an hour rewriting his earlier work.

"Oh. Well," you say, "that's a bit unfortunate, but it's far from a disaster. Between the time we spent being confused about the cause of the errors, and looking for the lost commits, and my colleague rewriting his work, that costs the company, what, maybe five developer-hours? That's pocket change," you continue, a slight quaver in your voice betraying your knowledge that you wouldn't speak that way about $250 of your own money being set on fire.

But you're right. It won't be a disaster. You won't get fired or disciplined. Your gracious and talented colleague won't even be angry at you (as far as you can tell), over this one little mistake. You won't do it again.

Except it's never "just one mistake," and you will do it again. "It" maybe not being this specific sin of force-pushing to a shared remote branch (or maybe even that is too optimistic), but something in the equivalence class of "mistakes you could and should have avoided for some reasonable if currently-unknown operationalizations of could and should" ...

"So what?" you ask. "If one stupid mistake is non-disastrous, why not say the same of a lifetime's worth of stupid mistakes?" Because, because—

Because I like living in a technological civilization. I like being cool in the summer and warm in the winter, and having plenty of tasty food to eat, and internet to play in. These things aren't guaranteed to us by nature; they exist only by of the grace of people being sufficiently non-incompetent at their jobs. And we may not know what we're missing by not being even more non-incompetent. Even if any one mistake or triumph doesn't make a perceptible difference on its own—it adds up. So I don't think you should blame me for caring.

Contempt for the past is a healthier emotion than fear for the future.

I swear to Celestia, one of these days that mare is going to get somepony killed or worse. I almost suspect it's already happened and Hasbro is just sitting on the footage.

Seriously. Levitation or teleporting is fine, but you do not buck around with mind control or transformation spells unless you are absolutely sure that nothing will go wrong and that you can fix it when it does anyway. You'd think she'd learn after, I don't know, accidentally brainwashing pests into destroying the town, or unleashing a transmissible-by-sight plague of madness that wasn't stopped until Princess Celestia herself intervened, or accidentally swapping parts of her friends' souls, or accidentally transforming her friend into a horrible bat-pony abomination, or transforming herself and her friends into tiny vaguely-insectoid creatures and venturing through a closing portal to another world and only barely making it back in time.

Even plot armor isn't infinitely thick. Someday it's going to break, and I don't want to be watching when it happens.

The blog has been silent for two weeks plus and, dear reader—that is, if there are any of you still remaining—dear reader, the thought occurs to me that maybe I should keep my drafts in a Git repository with a remote on GitHub, not because I need the full power of version control (I do not), but because then I would be rewarded for writing with those contemptible green contribution squares.

It's an anthropomorphism to think that humans have goals, that we do things because we've computed that they'll increase expected beauty or rightness in the world. We do things for the immediate reinforcement. You eat the candy because it tastes good and you show up to work on time because if you didn't, then your colleagues would notice. Serious long-term risks of diabetes or unemployment are too distant and too abstract to enter in the equation; far more effective is something immediately noticeable, even something as trivial as an integer being incremented or a square turning a darker shade of green. I tell myself that I code because it's fun and useful and lucrative (though I'm never explicit about whether that's descending or ascending order of importance), but would I be quite so diligent without the implicit gamification of my virtue? Would it be enough to have done good work, without wasting a few minutes here and there to gaze admiringly at commit diffs and contribution squares which manifest my moral worth in red and green and green?

Dear reader, I want you to picture yourself reclining at the end of a long day near the end of long career filled with great or terrible deeds. A young minion at the start of their own career will look at you and ask in awe, "O Master, what motivated you, all that time? What drove you on in your hour of deepest exhaustion? Was the it money, the fame, the men or women? Was it your ideological fervor or spirit of generosity?"

"No," you'll reply. "I did it for the green squares. And given the same circumstanstances ... I'd do it all again."

"You mean, you made the right choices? You have no regrets?"

"No, you fool!" you'll shout. "Don't you understand? I said, I'd do it again."

Apparently a gang of extortionists calling themselves the "California state Bureau for Private Postsecondary Education" are threatening to shut down a number of organizations that provide assistance in learning to program, including App Academy, which I recently benefitted from attending. I could explain why the behavior of the BPPE is an outrage that must be opposed by anyone with a scrap of decency in their heart, but I'm too busy coding and counting my money.

it's kind of strange that I think the internet is all-lowercase, when I'm so eager to slap Portentous (Pretentious?) Captial Letters on Fuck Near Everything Else

"Our civilization," said the engineer, "is decadent." This after visiting the Ghirardelli shop on Market and Montgomery, frowning and, for the first time in his life, doubting very much whether ice-cream was a force for good in the world.

"... so, what do you think?"

"It was cute, in a meta sort of way."

"Thanks. But there's something a little sad about resorting to meta cuteness so often, like I'm an n-trick pony for undisclosed but probably quite small n."

"Well, you're very good at meta cuteness."

"There is that."

Dear reader, suppose you're a distibuted data storage system. Your soul (although some pedants would insist on the word program) is dispersed across a cluster of several networked computers. From time to time, your human patrons give you files, and your job—more than that, the very purpose of your existence—is to store these files for safekeeping and later retrieval.

The humans who originally crafted your soul chose a simple algorithm as the means by which you decide which file goes on which of the many storage devices that live in the computers you inhabit: you find the MD5 hash of the filename, take its residue modulo n where n is the number of devices you have—let's call the result i—and you put the file on the (zero-indexed) ith device. So when you had sixteen devices and the humans wanted you to store twilight.pdf, you computed md5("twilight.pdf") = 429eb07bb8a3871c431fe03694105883, saw that the lowest nibble was 3, and put the file on your 3rd device (most humans would say the fourth device, counting from one).

It's not a bad system, you tell yourself (some sort of pride or loyalty preventing you from disparaging your creators' efforts, even to yourself). At least it keeps the data spread out evenly. (A shudder goes down your internal buses as you contemplate what disasters might have happened if your creators had been even more naive and, say, had you put files with names starting with A through D on the first device, &c. What would have happened that time when your patrons decided they wanted to store beat00001.mp3 through beat18691.mp3?)

But still, you've been having problems lately. As your patrons have come to rely on you more and more, they've added more machines bearing more devices to your cluster—and occasionally devices fail, too. And every time you gain or lose a device, your hashing scheme for assigning files to devices goes out of date: in the vast majority of cases, md5(filename) mod n changes when n does, requiring almost all of your files to be shuffled onto different devices, an expensive and unpleasant procedure.

One day, after a particularly painful rearrangement of files, you decide enough is enough. You're going to need a new way to assign files to devices, even if it means rewriting part of your own soul (and that's exactly what it will mean). You do some searching and read about an idea called consistent hashing that seems like a perfect solution to your problem. (In fact, your reading even mentions that your older cousin, OpenStack Swift, uses a modified version of consistent hashing for the same purpose. You've always resented Swift and aren't happy with the idea of copying one of her algorithms—but you tell yourself that that's not important.)

Anyway, consistent hashing. The essential nature of your problem is that you need a way to split the space of possible filenames into n partitions in a way that minimizes the number of files that have to change partitions when n changes. So imagine mapping the 128-bit output space of MD5 around a ring. Now pseudorandomly designate m spots on the ring (m being some prudently-chosen natural number) for each of your n storage devices: say, by hashing the device name suffixed with the number j for each j between 0 and m–1 inclusive. Internally, you might represent the ring as just an array of hash/device pairs. Like this (in Clojure; here the array and the pairs it contains are actually "vectors")—

(import 'java.security.MessageDigest)

(defn md5 [string]
  (let [digest-builder
        (java.security.MessageDigest/getInstance "MD5")]
    (.update digest-builder (.getBytes string))
    (clojure.string/join
     (map (fn [chr] (format "%x" chr))
          (.digest digest-builder)))))

(defn suffixed [name n]
  (map (fn [j] (str name j))
       (range n)))

(defn ring-kv-pairs [device spots]
  (map (fn [suffixed-name]
         (vector (md5 suffixed-name) device))
       (suffixed device spots)))

(defn make-ring [devices spots]
  (vec (sort
        (reduce concat
                (map (fn [device]
                       (ring-kv-pairs device spots))
                     devices)))))

Then when your patrons ask you to store a file, you're still going to hash its name, but instead of taking the residue mod n of the hash to decide where the file should live, you're going to locate the hash in your ring, and find the next designated spot on the ring associated with one of your storage devices, and the file will live on that device. In terms of your internal representation of the ring as an array of hash/device pairs, you'll find the first pair whose first item (the hash of the suffixed device name) is greater than the hash of the name of the file to be stored, and the second item of that pair will tell you which storage device to use. (And if the filename hash is greater than all those stored in the (first items of the pairs stored in the) array, then you just use the first pair in the array. It is supposed to represent a ring, after all.) Like this—

(defn ring-search [ring key]
  (or (some (fn [pair]
              (if (> (compare (first pair) key) 0)
                pair))
            ring)
      (first ring))) 

(defn ring-lookup [ring filename]
  (last (ring-search ring (md5 filename))))

And now—why, now when you gain (respectively lose) a storage device, you can decide the allocation question simply by adding (respectively removing) the appropriate designated spots to (respectively from) your ring—

(defn ring-add [ring device spots]
  (sort (vec (concat ring (ring-kv-pairs device spots)))))

(defn ring-remove [ring device]
  (filter (fn [spot] (not= (last spot) device))
          ring))

—and most files stay on the same device: the only ones that have to move are those with a new nextmost designated spot in the ring!

You decide to run a quick simulation to see if you've gotten this right before saving the edits to your soul. Suppose you had storage devices device0 through device5 and your patrons wanted you to store file0 through file5999; how would the files end up distributed across your devices? You choose a prudent-seeming integer for the number of designated spots per device—say, 450?—and write the simulation like this—

(defn filemap [ring files]
  (into {}
        (for [file files
              :let [device (ring-lookup ring file)]]
          [file device])))

(defn counter [devices filemap]
  (for [d devices]
    [d (count (filter (fn [entry]
                        (= (last entry) d)) filemap))]))

(def my-devices (suffixed "device" 6))
(def my-first-ring (make-ring my-devices 450))
(def my-files (suffixed "file" 6000))
(def my-filemap (filemap my-first-ring my-files))
(doseq [total (counter my-devices my-filemap)]
  (println total))

And the results seem reasonable enough:

$ clojure consistent_hashing.clj 
[device0 1020]
[device1 993]
[device2 1082]
[device3 955]
[device4 993]
[device5 957]

Dear reader, as another year comes to a close, it is perhaps wise that we should take a few moments to reflect on what we learned here at An Algorithmic Lucidity in 2013—the year that was!

In the year 2013, this blog saw 103 posts and (at press time) 40 comments. Among these—

We heard a poem about why you should hire me. We surveyed a few numbers between 0 and 1. (Friend of the blog Grognor told me that the funniest part was the explicit disclaimer that the list was non-exhaustive. I replied that not everyone knows about the diagonalization argument—but considering this blog's, um, selective audience, maybe my readers do—all five of you!) We mentioned some hidden costs of talking about stuff. We noted that some words have substrings which are other words. I wrote a series about my experiences studying web development at App Academy (9 8 7 6 5 4 3 2 1). I pasted my first attempt at an OKCupid profile. We observed that I'm a moron. Books arrived in the post. We mused on the nature of personhood and implemented some classic algorithms: the Ford-Fulkerson technique somewhat clumsily in Ruby, quicksort in the form of a letter to a fictional horse, and Huffman coding in Python. We lamented the nature of existence, noticed the non-observance of an unusual tradition, and heard a poem about watching a motion picture by someone you met at university. Three problems with unsolicited advice were discussed, as was the role of bases in the theory of vector spaces, and the subjective indistinguishability of propaganda and other forms of instruction.

So that was 2013 in the year of our Common Era. But what, I hear you ask (both of you who clicked through after the break), what about twenty-fourteen? Having considered the year that was, what of the year that hasn't yet? What is your faithful correspondent thinking about writing ("thinking about writing")? Well, without giving too much away—and, come to think of it, without much of a track record of successfully predicting my future behavior—I'll say to expect more computer-scientific contrivances and more detailed fiction, but probably somewhat fewer overall posts (this last partially because I'm going to be busy contributing to world economic growth, and partially because I want to put more emphasis on the virtue of Quality rather than the virtue of Shipping). So don't touch that bookmark! The best is yet to come! I thank you for reading, and remain,

Your faithful correspondent,
Zack M. Davis

"I didn't intend for my blog to become a compendium of very short dialogues! It's just—it's just—"

"They're easier to write than anything else?"

"—they're easier to write than anything else."

"So, what do you think it—"

"It's a Turing machine."

"You didn't even look at it!"

"I don't need to!"

Is it wrong that I feel more positively disposed towards Etsy after figuring out where it must have (must have) gotten its name?

"They're going to pay you X dollars a year? But that's fantastic! You're rich!"

"I don't like the way you say that. You make it sound as if I had won the lottery."

"Lottery, new job, what's the difference? Good fortune should be celebrated."

"Not like that. If they're going to pay me X dollars a year, that means I have one year to create X dollars of economic value. It's a serious responsibility."

Beset by nights of torment,
Bent to keep your site performant,
Beneath the moon aloft there then appear
Beautied forms so gallant who
Beseech the gods of Talent to
Bequeath a junior software engineer!

You need someone specific,
One computer-scientific,
Who can complete the team at [Company Name],
Whose reputation takes repose
In repos replete with code which shows
[They put the other candidates to shame].

From graph theory to jQuery,
And matters in between,
My code Pythonic, words unironic,
I greet you through this screen
And ask, if just to highlight it,
If you've positions I might fit,
With pretense shed entirely.
I then said, "Hire me."