An Algorithmic Lucidity

I used to think of $ in regular expressions as matching the end of the string. I was wrong! It actually might do something more subtle than that, depending on what regex engine you're using. In my native Python's re module, $

[m]atches the end of the string or just before the newline at the end of the string, and in MULTILINE mode also matches before a newline.

Note! The end of the string, or just before the newline at the end of the string.

In [2]: my_regex = re.compile("foo$")

In [3]: my_regex.match("foo")
Out[3]: <_sre.SRE_Match object; span=(0, 3), match='foo'>

In [4]: my_regex.match("foo\n")
Out[4]: <_sre.SRE_Match object; span=(0, 3), match='foo'>

I guess I can see the motivation—we often want to use the newline character as a terminator of lines (by definition) or files (by sacred tradition), without wanting to think of \n as really part of the content of interest—but the disjunctive behavior of $ can be a source of treacherous bugs in the fingers of misinformed programmers!

It happened to me while I was doing speculative pre-development of the speculative pre-prototype for my speculative Glitteral programming language, specifically in the lexical analyzer—the part of a compiler that recognizes strings of source code as representing tokens that mean something in the language's grammar: this is a language keyword, that's an integer literal, this is an identifier, and so forth. My makeshift lexical analyzer (inspired by, but diverging significantly from, the more sophisticated thing that textbook said to do—I was in a hurry) involved deciding if a segment of source code could represent a particular token (or prefix thereof) by checking if it matched the regular expression defining each token class (or a regex describing prefixes of that token class). I had prudently (but not prudently enough, as you see) anchored each of my token class regexes with $, so that, for example, the source fragment fore could not be erroneously recognized as the language keyword for. But that just left me with a bug in which a newline immediately following a token would be recognized as part of the token: for example, you could end up lexing the string 3\n as an integer literal, even though the integer literal was supposed to be just 3. After my first crude fix later proved to be inadequate, I ended up fixing it by augmenting the $s with the negative lookahead assertion (?!\n) immediately thereafter, in effect saying, "match the end of the string or just before the newline at the end of the string, but not just before a newline," the negative lookahead assertion canceling out the interpretation of $ that I didn't want. And then later I replaced all those $(?!\n)s with \Zs (which actually match the end of the string, like I wanted in the first place), after it was brought to my attention that \Z was a thing.

But I'm not the only one who was confused! (Note: the previous sentence should be read in a tone of terror and despair at the tightness of the cruel grip of ignorance on our fragile world, not relief that other people are as dumb as me.) The famous Django web application framework recently released patch versions 1.8.3, 1.7.9, and 1.4.21 due to security concerns, one of which being validators failing to guard against possible header injection vulnerabilities owing to the use of $ instead of \Z in regular expressions.

All this that I have said about $ in regexes concerns the Python world. Apparently Perl is the same way (maybe we got it from them?). But other regex engines don't have the "or just before the newline" semantic flourish in their interpretation of $. In Java, for example (and therefore, more importantly from my point of view, Clojure),

[b]y default, the regular expressions ^ and $ ignore line terminators and only match at the beginning and the end, respectively, of the entire input sequence.

user=> (re-matches #"foo$" "foo")
"foo"
user=> (re-matches #"foo$" "foo\n")
nil

Whereas in Ruby, $ is explicitly the end of line anchor (like in Python's MULTILINE mode), \Z matches the end of the string or just before the newline if the string ends with a newline (like Python's default), and \z is for the end of the string!

I guess the moral is that if you want to write a kind of regular expression that you're not already intimately familiar with, you should think carefully and read the owner's manual of your chosen regex engine. What you find there may surprise you!

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]

Suppose we want to find the powerset of a given set, that is, the set of all its subsets. How might we go about it? Well, the powerset of the empty set is the set containing the empty set.

And the powerset of the union of a set S with a set containing one element e, is just the union of the powerset of S with the set whose elements are like the members of the powerset of S except that they also contain e.

So in Clojure we might say

(require 'clojure.set)

(defn include-element [collection element]
  (map (fn [set] (clojure.set/union set #{element}))
       collection))

(defn powerset [set]
  (if (empty? set)
    #{#{}}
    (let [subproblem (powerset (rest set))]
      (clojure.set/union subproblem
                         (include-element subproblem
                                          (first set))))))