Google Maglev

Google's Maglev paper describes a high-performance software-based load balancing system. Like many of the systems that Google has described in the literature, Maglev applies commodity hardware and horizontal scaling to a problem in a novel way. These are some notes on the parts most interesting to me.

Packets reaching Google's networks are destined for virtual IP addresses, which are assigned to particular services. These addresses map to several physical machines running the service application. Maglev's basic job is to look up the machines serving that virtual IP and then to evenly divide the load between these servers. Each Maglev array manages many virtual IPs and many backend servers per IP.

The main smarts in Maglev are in allowing an unintelligent frontend hardware router to distribute packets -- and packet fragments -- in any fashion it chooses to a resizeable array of Maglev instances which forward packets on to the machines handling each service and maintain connection semantics.

There were several problems that caught my attention:

  • Making something fast enough in software on commodity machines.
  • Ensuring even load balancing at the connection level.
  • Allowing a distributed load balancing tier to maintain connections between clients and backend machines.

Performance

The basics here are a combination of efficient coding and moving the networking work into user space. This speeds things up in a few ways. First, you avoid the context switches into kernel space. Second, the kernel's stack supports far more features than Maglev requires, so doing the work itself avoids a lot of possible code paths and checks. Finally, you can interact directly with the network card via shared memory buffers rather than be interrupt driven; when you're pretty sure there will always be packets waiting, polling is pretty efficient.

Balancing connections

Maglev is fortunate to be distributing the load from many different source IPs, so can achieve good balancing characteristics based on the source and destination data.

An obvious initial problem is that the router is distributing packets to multiple Maglev machines, but these packets form part of a larger connection stream, so they need to be routed to the same machine to allow complete requests to be reconstructed. The Maglev machines take care of routing packets belonging to the same connection to the same backend machine using a consistent hashing technique.

Backend selection is based on a packet's 5-tuple representation. This representation is the packet's source IP, source port, destination IP, destination port and IP version number. To avoid sharing state for ensuring consistent backend selection, a Maglev server takes the 5-tuple of an incoming packet and derives the appropriate backend for it using the hash of the 5-tuple. First, the Maglev machine checks a connection table for an existing entry. If that fails, a specialised consistent hashing technique allows each Maglev machine to choose the same backend server for a given connection. The selection is then stored in the connection table, for quicker directing of packets that are part of that connection.

Overall, the paper is a very readable solution to an interesting problem of scale.

How Money is Made

The Bank of England, I found out recently, produces a quarterly bulletin. The Bank published a couple of fascinating -- to me at least -- articles on how money is created and destroyed in the modern economy in their quarterly bulletin for Q1 2014:

  1. Money in the modern economy: an introduction
  2. Money creation in the modern economy

While other articles in the bulletin look to be fairly specialised, I found these opening two quite accessible. Mostly anyway, some paragraphs required a little more thinking than I was willing to put in for now.

At the crux of the articles is the theory, which the Bank says is the currently correct one, of how money is created. Surprisingly, money is created by commercial banks when they lend to you, me, companies and so on. Out of thin air, a higher number appears in our deposit accounts. On the bank's side, a corresponding lending account appears. As we pay back into that lending account, we are actively destroying money. So money is created from nothing and, mostly, returns to nothing.

This runs counter to the belief that banks lend out money that people have previously deposited; in fact, it runs exactly in reverse to that thought. Instead, lending comes first, banks creating money at the stoke of a pen and tap of a key.

My first thought was what, then, stops banks just creating more and more money, leading to runaway inflation? Competition and profit-motive, basically. Increasing a bank's lending typically comes at the cost of their decreasing the interest they charge on loans, which decreases the likely profit. And there is a balance between the interest paid to depositors by a bank and the interest they charge on loans, which has to be positive for the bank to have enough money to pay its employees. I did ponder whether a bank could just conjure up money for their employees, but realised that, of course, employees don't want to be paid in loans.

The interest rate set on reserves by the central bank -- that is, the money that commercial banks hold with the central bank -- also affects the price of loans on the street, to you and I. I get a bit lost at this part, so do email me if I've buggered this bit up. But so far as I can see we're broadly saying that the reserves which the commercial bank borrows from the central bank have an interest rate attached, which, given banks settle between themselves in reserve bank currency, influences the rate at which the bank is willing to loan that money further down the chain. Competition between banks drives down that rate towards the central bank rate, and the desire not to lose money keeps rates above it. By increasing the rate, the central bank can make lending more expensive, decreasing demand and therefore money creation.

Paying for something, in this world, really is the action of decreasing the number in someone's deposit account and increasing the number listed against someone else's. If the parties are with the same bank, this can be instantaneous. If not, it needs to be accompanied with a transfer in central bank reserves (I think) from the buyer's bank to the seller's bank.

There is a classic computer science example of the need to have transactional protection around a purchase, to keep the addition and subtraction appearing instantaneous, and in that we tend to think about the numbers as only representing people's balance. In reality, it seems to me that the bits on disk really are that balance -- and if they accidentally change, the money really does change. If that happens, the bank has, most likely, accidentally created or destroyed money.

I haven't quite figured out what this means. It's a bit like quantum physics, where you learn that reality is far less solid than everyday experience suggests. Similarly, money appears to be a far more mailable, slippery concept than I thought. I get the feeling that if my mind comes to accept this new view of money, a bunch of my underlying feelings about how economies -- and governments -- work will come tumbling down to be replaced with quite different ones.

Just open a blank document

When I start an app like Word by typing its name into Alfred, I almost never want to do anything other than open a new, blank document. Instead, by default, tons of apps show a "New Document" dialog, offering to help me by creating a generic looking flyer, brochure or todo list.

Here's how to go back to just the blank paper, spreadsheet, or whatever, at least for the apps I find myself requiring it:

  • Office:
    • Word: PreferencesGeneralShow Word Document Gallery when opening Word.
    • Excel: PreferencesGeneralOpen Workbook Gallery when opening Excel.
    • Powerpoint: PreferencesGeneralShow the Start screen when this application starts.
  • iWork: from Preferences you need to choose a default template to skip the template gallery for every new document. Skipping the open dialog box at startup requires some defaults work, see below.
  • OmniGraffle: the key I missed here is that this is a two-step process. Go to PreferencesGeneral, then: (1) select Create a new document if nothing else is open, and (2) select a template for the new document, I chose Auto-Resizing.

The Apple Stackexchange has the answer for turning off the open dialog box at start up that many apps on the Mac show; iWork, Text Edit and Calca are the ones where I see it most. From the command line:

defaults write -g NSShowAppCentricOpenPanelInsteadOfUntitledFile -bool false

If you want to show the dialog again:

defaults write -g NSShowAppCentricOpenPanelInsteadOfUntitledFile -bool true

If nothing else, writing this note prompted me to figure out whether you can disable that stupid dialog. Given it took all of 30 seconds to find, I'm rather saddened at the immense amount of time and bother that I have cost myself by not looking previously.

Limiting concurrent execution using GCD

Soroush Khanlou recently wrote The GCD Handbook, a cookbook for common Grand Central Dispatch patterns. It's a great set of patterns, with code examples.

While a great example of semaphores, I wondered whether the code in the Limiting the number of concurrent blocks section could be improved -- I'll explain why below. Soroush and I emailed back and forth a little bit, and came up with the following.

In the example, Soroush shows how to use GCD semaphores to limit the number of blocks that are concurrently executing in a dispatch queue. The key part is the enqueueWork function:

func enqueueWork(work: () -> ()) {
    dispatch_async(concurrentQueue) {
        dispatch_semaphore_wait(semaphore, DISPATCH_TIME_FOREVER)
        work()
        dispatch_semaphore_signal(semaphore)
    }
}

The problem I saw here, which Soroush also notes, is that this approach starts a potentially unbounded number of threads, which are immediately blocked by waiting on a semaphore. Obviously GCD will limit you at some point, but that's still a lot of work and a decent chunk of memory. While this code is necessarily simplified to introduce this use of semaphores, the bunch of waiting threads needled at me.

To achieve effects like this with queue-based systems, I often find I need to combine more than one queue. Here, in the solution Soroush and I got to, we need two queues to get to a more efficient solution which only requires a single blocked thread.

We use a concurrent queue for executing the user's tasks, allowing as many concurrently executing tasks as GCD will allow us in that queue. The key piece is a second GCD queue. This second queue is a serial queue and acts as a gatekeeper to the concurrent queue. We wait on the semaphore in the serial queue, which means that we'll have at most one blocked thread when we reach maximum executing blocks on the concurrent queue. Any other tasks the user enqueues will sit inertly on the serial queue waiting to be executed, and won't cause new threads to be started.

import Cocoa

class MaxConcurrentTasksQueue: NSObject {

    private let serialq: dispatch_queue_t
    private let concurrentq: dispatch_queue_t
    private let sema: dispatch_semaphore_t

    init(withMaxConcurrency maxConcurrency: Int) {
        serialq = dispatch_queue_create("uk.co.dx13.serial", nil)
        concurrentq = dispatch_queue_create(
            "uk.co.dx13.concurrent", 
            DISPATCH_QUEUE_CONCURRENT)
        sema = dispatch_semaphore_create(maxConcurrency);
    }

    func enqueue(task: () -> ()) {
        dispatch_async(serialq) {
            dispatch_semaphore_wait(self.sema, DISPATCH_TIME_FOREVER);
            dispatch_async(self.concurrentq) {
                task();
                dispatch_semaphore_signal(self.sema);
            }
        }; 
    }

}

To test this, I created a Swift command line application with this code in main.swift:

import Foundation

let maxConcurrency = 5
let taskCount = 100
let sleepFor: NSTimeInterval = 2

print("Hello, World!")

let q = MaxConcurrentTasksQueue(withMaxConcurrency: maxConcurrency);
let group = dispatch_group_create()

for i in 1...100 {
    dispatch_group_enter(group);
    q.enqueue {
        print("Task:", i);
        if (sleepFor > 0) {
            NSThread.sleepForTimeInterval(sleepFor);
        }
        dispatch_group_leave(group);
    }
}

dispatch_group_wait(group, DISPATCH_TIME_FOREVER);

print("Goodbye, World");

Running this, Hello, World! should be printed, followed by Task: N in batches of five (or whatever you set maxConcurrency to), followed by a final Goodbye, World! before the application succumbs to the inevitability of termination.

Even here there is an interesting use of GCD. In order to stop the app terminating before the tasks have run, I needed to use dispatch groups. I hadn't really used these before, so I'll refer you to Soroush's explanation of dispatch groups at this point; the above is hopefully straightforward once you've read that.

I uploaded an example project for this code to my GitHub account. It's under Apache 2.0; hopefully it comes in handy sometime.

More can be... more

"Less is more". It's a frustrating phrase. Less is not not more; by definition, it never can be. But sometimes less is better. On the other hand, sometimes more is better. Mostly, from what I can tell, there are some things where less is better and others where less is worse. Often there's a level which is just right: more is too much, and less is too little. Salt intake falls into that bucket.

Less is more is a paraphrasing of a whole book, The Paradox of Choice, written by Barry Schwartz. It's become a bit of a mantra, one that is deployed often without thought: "this page is cluttered, we need to remove stuff; less is more, dude". This closes a conversation without exploring the alternatives.

It's looking increasingly, however, like the idea is either false or, at the very least, that the book length discussion is more appropriate than the three word version.

Iyengar and Lepper's jam study from back in 2000, where all this stuff came from, is coming under fire: a whole bunch of other studies don't find the same effect. This is all described in more detail in an article on the Atlantic.

A logical conclusion of less is more is that one is enough. For shopping, at least, one appears to be too few. This relates to the topic of framing. My reading is that if you only have one item in a given category in a store, it's easy to worry that the price of that item is too high. Introduce even one more, and the pricing is framed. Add a more expensive item and you will increase sales of your previously lonely cheaper item: a framing effect will suddenly make your original item seem better value. The implication being that, without the price framing, customers will feel the urge to look elsewhere to be sure they have a good deal.

Looking online for articles that Schwartz has written, things seem to come back to this one from the HBR in 2006:

Choice can no longer be used to justify a marketing strategy in and of itself. More isn't always better, either for the customer or for the retailer. Discovering how much assortment is warranted is a considerable empirical challenge.

That is, less can be better, but sometimes more can be better; and it's expensive, but sometimes you just have to pay the price to find out.