Category: Uncategorized

Dear reader, this is a unusual day. For the first time (possibly) ever, I’m actually writing my next future the economy post while NOT airborne.

When I left you, we were talking about productivity. I claimed that productivity is the root of all wealth and nearly all improvements in the human condition. And I told you about the two ways that productivity improves:

1. Doing the same thing faster
2. Doing different things

It’s pretty obvious how computers let you do #1. Once upon a time, rocket scientists had to compute thousands of ballistic equations using slide rules. “Computer” used to be the job title of a person who simply did computations all day.

Now scientists can do the same thing, but faster. And Moore’s law tells they’ll be able to do that about 50% faster ever year. That’s pretty good, unless of course I want to do something that currently takes a million years (e.g. perform a 1 second/byte calculation on 10 terabytes of data).

For that, I’m going to have to get creative. My only option is to choose an algorithm that does substantially fewer computations or does each computation substantially faster.

Computer scientists have a fancy way of talking about how long a certain type of algorithm will take. When you see expressions like “O(n^2)” (i.e. “big O notation”) or “polynomial time”, people are talking about how much slower an algorithm will run as the amount of input data increases. For some problems, like sorting a list of n integers, a good algorithm might take (n)*(log n) nanoseconds while a bad one takes n^2 nanoseconds. For a billion item list, that’s a difference of about 30 years.

By using the better algorithm, I’ve increased my productivity by about 4,000,000,000%.

These examples are most dramatic in computer science but they apply just as much to normal life. Say I need to attend a meeting in Houston. That’s a ~20 hour travel ordeal OR a 1 hour Skype conversation. If they’re both equivalently good[1], I can 20x my productivity by choosing wisely.

Next time, we’ll get a little meta and talk about how to choose better algorithms.

[1] In real life, alternative solutions are rarely perfect substitutes. But they’re often close enough along the attributes that matter.

When building websites, you’ll often want users to be able to search for something by name. On LinerNotes, users can search for bands, albums, genres etc from a search bar that appears on the homepage and in the omnipresent nav bar. And we need a way to match those queries to entities in our Postgres database.

At first, this might seem like a simple problem with a simple solution, especially if you’re using the ORM; just jam the user input into an ORM filter and retrieve every matching string. But there’s a problem: if you do

Bands.objects.filter(name="beatles")

You’ll probably get nothing back, because the name column in your “bands” table probably says “The Beatles” and as far as Postgres is concerned if it’s not exactly the same string, it’s not a match.

Users are naturally terrible at spelling, and even if they weren’t they’d be bad at guessing exactly how the name is formatted in your database. Of course you can use the LIKE keyword in SQL (or the equivalent ’__contains’ suffix in the ORM) to give yourself a little flexibility and make sure that “Beatles” returns “The Beatles”. But 1) the LIKE keyword requires you to evaluate a regex against every row in your table, or hope that you’ve configured your indices to support LIKE (a quick Google doesn’t tell me whether Django does that by default in the ORM) and 2) what if the user types “Beetles”?

Well, then you’ve got a bit of a problem. No matter how obvious it is to human you that “beatles” is close to “beetles”[1], to the computer they’re just two non-identical byte sequences. If you want the computer to understand them as similar you’re going to have to give it a metric for similarity and a method to make the comparison.

There are a few ways to do that. You can do what I did initially and whip out the power tools, i.e. a dedicated search system like Solr or ElasticSearch. These guys have notions of fuzziness built right in (Solr more automatically than ES). But they’re designed for full-text indexing of documents (e.g. full web pages) and they’re rather complex to set up and administer. ES has been enough of a hassle to keep running smoothly that I took the time to see if I could push the search workload to Postgres, and hence this article.

Unless you need to do something real fancy, it’s probably overkill to use them for just matching names.

Instead, we’re going to follow Starr Horne’s advice and use a Postgres EXTENSION that lets us build fuzziness into our query in a fast and fairly simple way. Specifically, we’re going to use an extension called pg_trgm (i.e. “Postgres Trigram”) which gives Postgres a “similarity” function that can evaluate how many three-character subsequences (i.e. “trigrams”) two strings share. This is actually a pretty good metric for fuzzy matching short strings like names.

To use pg_trgm, you’ll need to install the “Postgres Contrib” package. On ubuntu:

sudo apt-get install postgres-contrib

**WARNING: THIS WILL TRY TO RESTART YOUR DATABASE**

then pop open psql and install pg_trgm (NB: this only works on Postgres 9.1+; Google for the instructions if you’re on a lower version.)

psql

CREATE EXTENSION pg_trgm;

dx # to check it's installed

Now you can do

SELECT *

FROM types_and_labels_view

WHERE label % 'Mountain Goats'

ORDER BY similarity(label, 'Mountain Goats')

DESC LIMIT 100;

And out will pop the 100 most similar names. This will still take a long time if your table is large, but we can improve that with a special type of index provided by pg_trgm:

CREATE INDEX labels_trigram_index ON types_and_labels_table USING gist (label gist_trgm_ops);

or

CREATE INDEX labels_trigram_index ON types_and_labels_table USING gin (label gin_trgm_ops);

(GIN is slower than GIST to build, but answers queries faster.

That’ll take a while to build (possibly quite a while), but once it does you should be able to fuzzy search with ease and speed. If you’re using Django, you will have to drop into writing SQL to use this (until someone, maybe you, writes a Django extension to do this in the ORM.)

And as a frustrating finishing note, my attempt to implement this on LinerNotes was not ultimately succesful. It seems that that index query performance is at least O(n) and with 50 million entities in my database queries take at least 10 seconds. I’ve read that performance is great up to about 100k records then drops off sharply from there. There are some apparently additional options for improving query performance, but I’ll be sticking with ElasticSearch for now.

[1] Sorry, Googlebot! Not sorry, Bingbot.

Edit: I’ve come to believe that one premise of this article is wrong. You definitely can send email from an EC2 instance; Django will send error emails from a production server. So instead of using SNS, it would probably be easier to trigger some kind of simple email sending Python (or whatever) script when the termination event happens.

I make pretty heavy use of EC2 spot instances, which as you know can terminate at any time with no warning.

In order to get my spots back up ASAP, I’d like be notified when they terminate.

This turned out to be much harder than I expected. I thought I’d be able to add a simple script that would send me an email when the instance shuts down (Amazon is nice enough to send a shutdown command on termination instead of just pulling the plug.)

But that approach has a couple of problems.

First, you can’t easily send email from EC2 instances (because of spammers) and have to manually get instances whitelisted by elastic IP which is a pain.

Second, it’s not the easiest thing to write a shutdown hook in Linux.

So, here’s a solution for both of those problems.

The email problem

Amazon has a service called CloudWatch that seems great for this, except that it can only monitor metrics emitted by running instances. So you can’t set it to alert you on a system shutdown, nor on a metric polling failure because it randomly misses packets all the time.

So the solution is a different Amazon service called SNS (simple notification service) that will let you trigger an event that can be configured to send you an email. So we’re going to write a script that tells SNS to send us an email.

(SNS is free for ~200k requests/month, so unless you’re planning on doing something nuts this approach should have no marginal costs.)

To do that, you first need to set up a “topic” in SNS. Go to the SNS dashboard and

1) click “create topic”.
2) Create a topic called “instance_down” or whatever you like.
3) Click the topic and click “create subscription”
4) Choose protocol “email” and enter your email address as the endpoint

To use SNS in a script, we need the AWS command line tools.

If you already have pip installed, just

pip install awscli

Then:

touch ~/.awsconfig
emacs ~/.awsconfig

Make it say:

[default]
AWS_ACCESS_KEY_ID=<< YOUR AWS ID>>
AWS_SECRET_ACCESS_KEY=<< YOUR AWS SECRET KEY>>
region=<< YOUR REGION >>

Create an init.d script:

sudo emacs /etc/init.d/ec2-shutdown

Make it say:

#! /bin/sh
### BEGIN INIT INFO
# Provides: ec2-terminate
# Required-Start: $network $syslog
# Required-Stop:
# Default-Start:
# Default-Stop:
# Short-Description: restart
# Description: send termination email
### END INIT INFO
#

export AWS_CONFIG_FILE={{ YOUR CONFIG FILE }}
export AWS_DEFAULT_REGION={{ YOUR REGION }} # config file not picking up region for some reason
sudo -E aws sns publish –topic-arn {{ YOUR SNS ARN }} –message “ec2 ser
ver {{ YOUR IDENTIFIER }} went down at $(date)”
sleep 3 # make sure the message has time to send

exit 0

That script will tell SNS to send you a email saying your server is down and giving the time. You can customize the message however you like.

The Shutdown Script Problem

So how do we make this run on shutdown?

We’re going to use init.d scripts. It’s taken me a little while to get my head around how this works, but in a nutshell…

Linux has a concept of “runstates”, which include things like “shutdown” and “logged in”. You can tell Ubuntu to run shell scripts when it changes into a runstate by placing scripts in certain folders in side of /etc. The two states that concern us are rc0 and rc6, i.e. “shutdown” and “reboot”, which correspond to folders /etc/rc0.d and /etc/rc6.d respectively.

Ubuntu has a command line tool, update-rc.d that will automatically symlink scripts into the appropriate folders depending on the CL paramaters you pass it. It’s all a bit complicated, but all you need to do here is:

sudo update-rc.d ec2-shutdown start 10 0 6 .

(This says run the script on entering run states 0 and 6, shutdown and reboot. And put it 10th in the list of things to do)

And that should do it! Now your instance should send you an email whenever it shuts down, terminates or reboots. I’m not sure how limit to just EC2 termination, but please comment if you know!

If you have any problems, leave a comment.

And if you find this useful, consider following me on Twitter.

Back linking has gotten unwieldy, so I’m going to just update links on this page to all the parts from now on:

Intro: The future of the economy, in bite-sized chunks.

Part 1: What is An Economy?

Part 2(a): Rich Hypothetical Society, Poor Hypothetical Society

Part 2(b): Productivity is Prosperity

Part 3: How Productivity Grows

Part 4: Computers and Productivity

Part 5: Lateral Productivity Growth

A couple of weeks ago, I left a comment on Albert Wenger’s excellent blog “Continuations” about Free Will. The comment was rather long, so I reposed it here on my blog. Somewhat amazingly, Albert read my comment and left a thoughtful reply.

I’m not sure of the etiquette of reposting Albert’s comment, but to summarize he said that my argument was off-base because the “information layer” I described is just an abstraction and doesn’t interact with the physical world. No interaction means no influence, and that means that the stimulus->thought->action sequence remains a deterministically closed loop.

I, logorrheic that I am, responded with another rather long comment. This is that comment.

Well, actually this is:

If it’s true that the “information layer is entirely abstract” (i.e. completely non-interacting with the tangible world) then your whole argument is clearly right.

But I’m not sure that premise is true. It seems that the informational world is constantly interacting with the physical world in the form of “physical laws being followed.”

Metaphorically, particles in the world are “data” and the laws of physics (i.e. the information layer) are “source code.” Every particle interaction is (metaphorically) a computation. Now all of our observation to date suggests that the “source code” of the universe is stable and fixed. But any honest physicist will tell you that our (extremely elegant) mathematically descriptions of how objects have behaved in the past tell us nothing about why they behaved that way.

I raised GEB to show that “laws” aren’t necessarily well-behaved in edge cases.[1] And so similarly, the fact that we’ve observed that some parts of the “Ur-program” work one way does NOT demonstrate conclusively that there aren’t other parts of the program that introspectively alter the Ur-program’s source code and lead to measurable, experimentally verifiable physical effects.

You raise one potential “point of strangeness” in your PS – quantum waveform collapse. My knowledge of quantum mechanics and neuroanatomy is limited, but my best understanding is that neural interactions are sensitive enough that quantum effects can make the difference between whether a neuron fires or not. And we know from computers (cf. my Caesar’s cipher example above) that changing one bit in a computation chain can radically alter the downstream result, so any slight (non-random!) bias in the quantum coin-flip could be enough to completely alter behavior. (And as far as I know would not violate the conservation of energy or any other physical laws except our observation that quantum collapse is usually random.)

Could patterns of thought directly alter the wave-form collapse? Well, we already know that the quantum world is altered by observation per se. And conscious introspection is fundamentally self-observation. So it is possible that when the wetware finds itself in physical states that mirror certain “information patterns” (e.g. “contemplating two choices”), the presence of those patterns triggers an alteration in the source code that directly influences the way quantum collapse happens in connected synapses, leading a neuron to fire that otherwise wouldn’t. And from the GEB problem, we might expect the “meta program” to be especially poorly behaved (perhaps even fundamentally indeterminate, i.e. “free”) in this circumstance.

So is this explanation likely? That’s hard to say. It’s neither confirmed nor contradicted by existing data. It’s counter-intuitive, but so is every other part of quantum mechanics.

But best of all, this theory is testable. We just need to carefully measure the statistical in vivo quantum behavior of synapses during decision-making and I can be proven wrong once and for all. 🙂

[1] I admit I’m not sufficiently demonstrating that “logic laws” work the same ways as physical laws but there is certainly a remarkable symmetry. It doesn’t seem at all fundamentally necessary that physical laws should be mathematically expressible and elegant. I’m happy to write more on this point if anyone is curious.

[Once again, I’ve been inspired by a post on Albert Wenger’s blog, this time about whether or not free will exists.]

I’ve spent a long time thinking about this one as well. I think you’re probably right, but here’s the best alternative I’ve been able to come up with. These ideas are heavily inspired by having finally finished Gödel, Escher, Bach.

Basically, it’s clearly true that determinism holds over the space of physical objects if you assume that a continuous set of physical laws governs all physical interactions. If my brain is just a physical object, then the arrangement of its atoms at present is exclusively a function of their arrangement in the past.

But how justified are we in making that assumption about the continuity and coverage of physical laws?

Let’s start with coverage: it’s actually not hard to think of something that doesn’t interact with the physical world in quite the same way as an apple – a computer program.

Yes, a program is represented by marks on a disk, and yes it is executed by a set of magnets that write and erase those marks using electricity routed through a CPU. But ultimately those purely physical components produce an informational state projected through my screen. And as I write I am interacting not only with the keys of my keyboard but also but with the abstract state of the system. And the state per se has causal power: perform a Caesar cipher on your blog post and it becomes virtually meaningless to me despite having extremely similar statistical properties and on-disk representation.

So then where does the meaningfulness of the program state reside? Can we point to a memory address that distinguishes “meaningful” from not meaningful (even in principle)? Can we point to an atom in my brain that makes the text meaningful to me, even though it would remain meaningful to you even if my brain we destroyed (and vice versa) but become meaningless if all brains were destroyed?

The point here is that even in closed physical systems, there is an information “layer” that has both its own rules (i.e. “logic”) and yet tangibly influences the physical world. This is the layer where the program-ness of a program resides, or the law-ness of physical laws, or the meaningful-ness of a sentence.

Normally this layer is well behaved – I encode my experiences into words that you understand; when fundamental particles interact they “check” which laws to follow and then they follow them.

But the layer has known flaws, specifically when self-reference enters the picture. Gödel’s incompleteness theorem establishes that there are questions which can be precisely formulated but not decided, e.g whether the statement “this statement is a lie” is true or not (or the somewhat related question of whether an arbitrary computer program will ever terminate.) These questions aren’t undecidable because of a deficit in our ability to measure (a la Heisenberg uncertainty) but rather because of an irresolvable quirk in the laws of the information layer.

The interesting thing about consciousness (the domain within which free will would presumably operate) is that it is deeply and inherently self-referential. The very exercise of writing this comment is an example of an information state reflecting on its own statefulness.

Now let’s circle back to the question of consistency in physical laws. Usually it seems like the surest bet: no one has ever been fired for predicting that an apple will obey gravity.

But when we start talking about the way that particles in our brain interact with the information layer (in ways we understand only loosely, at best) and we focus in on an area (self-reference) where the information layer is already know to misbehave, how confident can we be that the rules we’ve observed elsewhere operate the same way here?

Or more colorfully, how certain can we free will isn’t some sort of buffer overflow in the operating system of the universe?

[Edit: if you like this post, please upvote on Hacker News! Look for the post titled “Is Free Will a Buffer Overflow?”]