Processing Wikipedia

The other week I got it in my head that it might be fun to mess around with Wikipedia. I don't just mean the website, though - I mean their entire database of articles. I've been looking around for side projects lately, and this is a perfect opportunity/excuse to write some code that operates on Big-with-a-capital-B data, which should be exciting.

My day job is working on Microsoft Office. Now, don't get me wrong, it's interesting work... but the thing about being a junior dev on Office is that I spend most of my time writing extremely robust solutions for extremely small problems. I want a side project so that I can maintain a sense of perspective about programming, so that I don't get stuck in a rut. So, it's time for me to do something completely ridiculous. Let's datamine Wikipedia! :D

Getting started

Wikipedia posts dumps of their entire database online every once in a while. The latest one is from about two weeks ago, which is plenty fresh enough for my purposes. I'm using the pages-articles.xml.bz2 file, which is about 6.5 GB compressed, and 26 GB uncompressed. It contains just shy of nine and a half million articles. And it's a single XML file. Ouch. :(

There are probably text tools for Windows that are able to handle files that are larger than memory, but I'm not sure where they're hiding. So, I'm using Cygwin and UNIX tools for pretty much everything here; when in doubt, go old-school. "less" will get me a general sense of what the input data looks like pretty much instantly.

It looks like Wikipedia uses a consistent XML scheme for all their types of database dumps. I don't think it's documented anywhere, and the link in the XML to the schema is broken, but whatever. I can probably figure it out. >_> Anyway, it's not like their XML actually validates against any schema, as we'll see in a bit.

Splitting things up

A single XML file is not a terribly useful way to package up a database dump, but I'm sure they have their reasons. Before we can do anything with this data, we'll have to split it up into more manageable chunks. The structure I'm going for is one directory per article, with a single XML file in each directory. This makes it easy to find and read any article, and also leaves an easy way to add extra data to each article. It might be useful, for instance, to have the text of the article available without any extra formatting, or to have a list of links from the article, or things like that.

I wrote a python script to split the file into articles. It's available on the bitbucket page for this project. I decided not to use an XML parser to split up the file, and instead cobbled something together that just does substring searches to find article boundaries. This is generally a stupid thing to do, but streaming XML parsers are a pain, and this file is a hundred times bigger than I'd feel comfortable sticking in a DOM parser. (That said, I ended up using a real XML parser to get the article names out of the individual pages.)

Not using a real parser turned out to be a good move, because as it turns out, the database dump isn't actually valid XML all the way through. In the dump I happened to grab, there are six places where a page is truncated, including the closing tags. (Things may be better or worse in other dumps, but I really don't feel like grabbing another few-dozen-gigabyte dump file to find out.) If I were using a real XML parser, this is about where I'd give up, but with the script I wrote it was pretty straightforward to work around. We can figure out that we have a broken page when we see an unexpected opening page tag, dump what we have in the buffer to a special location to manually fix up later, and continue parsing from the next page.

Right now, the script is running at a bit over ten thousand articles per minute. I don't know if I can make that much faster, since it seems like the filesystem is the bottleneck at this point, but whatever. Once I've got a preprocessed copy of the database, the next steps will be to parse the articles and pull out a list of links, and to use that data to solve the "six degrees" problem. Stay tuned!

Thinking with Portals

Portal is a fun little puzzle game, wherein you can create little wormholes that connect different places and walk through them. But it's also so much more! The puzzles by themselves would qualify Portal as a pretty neat game, but it's the writing and the story and the general atmosphere that make it one of the best (and most-quoted) games of the last decade.

I'm a couple years late to be singing Portal's praises, though; it came out in 2007. So why am I writing about it now?

[Spoilers follow. If you haven't played Portal, GO DO THAT RIGHT NOW OMG. No spoilers for Portal 2, so if you haven't played that one yet you're still good to keep reading.]

Actually, I've been thinking a lot about just what made Portal so awesome ever since I played through it a few weeks ago. (In general, I think it's worthwhile to examine awesome things!) One thing that's really struck me in retrospect is that the whole game is permeated by this incredible level of cognitive dissonance. I don't think it was an accident, or some happy quirk of the way they ended up writing it. It happens on so many levels, and in so many ways, that I think they must have planned it that way, or at least made a conscious decision about it at some point.

Example: turrets. There are automatic gun turrets sprinkled through the later levels, and they are adorable. They have little singsong voices, and they say things like "Are you still there?" and "Could you come over here?", and when you 'kill' them by knocking them over, they sometimes say "I don't hate you..." in a dejected little voice. You can't help but fall in love with them, and feel guilty about taking them down, even though they will basically kill you on sight. Relevant.

Example: GLaDOS. You start the game taking orders from a friendly-if-slightly-glitchy computer, and she gradually develops over the course of the game into the lying, omnicidal GLaDOS that we all know and love. GLaDOS herself is really a fine example of cognitive dissonance, on top of the unease she induces as she becomes more and more unhinged. She guides you through the levels with friendly-if-unsettling comments, and even goes as far as trying to be nice during The Escape, but it becomes extremely clear after a certain point that she wants nothing more than to kill you and be done with it. (The light at the end of that tunnel? It's not a cake, I'll tell you that.)

"Remember when the platform was sliding into the fire pit and I said 'Goodbye' and you were like 'No way!' And then I was all 'We pretended we were going to murder you?' That was great."

Example: your Weighted Companion Cube. Here, have a cube; this one is special! It has got hearts on it. Got a puzzle that needs solving? Your cube is part of the solution. Yep, it's just you and your cube, alone against the world! What's that, you've finished this level? Time to euthanize your only friend, then! Here, use this conveniently-placed incinerator. D: (Honestly, though? The very fact that they manage to make you form an emotional bond with a box with hearts on the sides is just another example of how masterfully they are messing with your head.)

Example: Still Alive, by Jonathan Coulton. This song plays during the end credits of the game, and is generally awesome. It's later than I planned to stay up writing this, so rather than explain why, I'll just refer you to its lyrics. <_<

So back to the title of this post, Thinking with Portals. Usually it's used in the context of "Now you're thinking with portals!", meaning that you're learning to use some of the cleverer tricks you can do with portals to solve puzzles. But can we interpret it another way? What if you actually could use portals to navigate your headspace; jumping between disparate and occasionally contradictory ideas, connecting things that would never normally be connected, being mentally in two places at once. Sound familiar?

Something to ponder.

I am done beating this horse. It is dead.

You know what? I can handle it when mainstream media outlets call Anonymous a "hacking group". Everybody knows they don't exactly have a ready supply of technical expertise on hand; they probably couldn't tell an ethernet crimper from a can opener. We expect that from them. It's even sort of adorable sometimes, like seeing an elderly person trying to use a mouse like a foot pedal. But the point is, they don't know any better.

But when Ars Fucking Technica writes a long investigative piece about how dangerous it is to mess with Anonymous, because Anon is a Legitimate Group of Serious Hackers, that's just shameful. They, of all people, should know better. Nothing about Anonymous is secret except their names, and everybody who cares to ask knows that they're a bunch of angry teenagers with computers. But that doesn't make for a very good story, so now we have the tragic tale of Aaron Barr, who came too close to the leaders of Anonymous and got burned.

You know what I see when I read this story? A slightly deranged man, who happens to head a private security firm, decides to pick a fight with a group that's known mostly for their skill at harassment. His boss thinks he's going off the rails, his employees think he's completely deranged, but he presses on. Eventually a hacker shows up, exploits a SQL injection to get access to his company's internal network, and then passes out his passwords to Anonymous, who goes and has a field day, since that's what they do. However, his story happens to involve the major players of the Wikileaks scandal, so people pick it up as a useful proxy for real news.

So fine. I give up. If Ars Technica has decreed that Anon is a Serious Hacking Group, then that's it. Hacking is dead, nobody remembers what it means anymore. Long live Anonymous. :(

Chrome, H.264, and 2015

Google ruffled a lot of feathers a few weeks ago when it announced that it would be dropping H.264 support from Chrome. In the short term, it seems like a ridiculous move - one guaranteed to kill HTML5 video, and keep Flash dominant for the foreseeable future - but come 2015, I think this move will make a lot of sense.

Some background on video codecs: A video codec is a method of compressing video. The measure of a codec is how well it compresses, and what sort of tradeoff you have to make between file size and image quality. Any codec can give you perfect video if you give it enough space to work with, but H.264 is one of the best when it comes to giving you high quality video at reasonable bitrates. Other prominent codecs for web streaming include Theora (which is open-source and royalty-free, but doesn't compress as well as H.264), Dirac (an experimental codec developed by the BBC, which has yet to gain any traction), and VP8 (Google's codec, bought from On2, and part of WebM). H.264 is dominant right now because it gives good results, is widely implemented, and because hardware accelerated decoders are available (crucial for mobile devices).

The HTML5 video tag doesn't specify any required video codecs, so sites are responsible for using one that all their users are able to use. Last year there was a huge shootout between proponents of H.264 and Theora. H.264 is technically the better solution, but it's owned by the MPEG-LA, and they intend to start charging royalties for it in 2015. Right now, though, H.264 seems to be winning - it's backed by Microsoft and Apple, and it's actually the only way to get video to play on iOS devices.

This is a problem for Google: YouTube would be hit pretty hard by the license fees, since every video on YouTube is streamed in H.264. Google doesn't plan to take this lying down, though. If Theora isn't up to the job, then Google will buy a codec that is competitive with H.264, and release it royalty-free for anybody to use. If it looks like H.264 is still winning, then Google is willing to drop H.264 from Google Chrome (just over 10% of the browser market) to try to kill its momentum, and replace it with Google's own codec.

MPEG-LA was originally set to start charging royalties for web streaming H.264 in 2010, but they moved it back to 2015 in order to allow H.264 to become more solidly entrenched. People say that Google is being shortsighted by promoting their own codec, since they'll never make any progress when IE9 and Safari (and iPhones!) support H.264 by default. Google doesn't need to win, though - they just need a solid alternative to H.264 to exist by 2015, so that MPEG-LA is in a weaker position when it comes time to work out what YouTube has to pay for using H.264. That's their real game here, and so far it seems like they're going to make it.

Using "make" as a download manager (or: how to parallelize EVERYTHING)

I find myself in the somewhat tedious position of having to download about a hundred large files from S3. I need to only download certain files, so I can't even use S3's APIs and pull down the entire bucket. What a pain!

The first thirty or so, I did by copy/pasting the URLs onto a command line with wget, so that I could at least download them in batches. This worked, but was slower than necessary: S3 occasionally gives you a slow download, so that every once in a while I'd get a file that took ten times longer than the rest, holding everything up. You know what'd really be great? If I could download with wget, but parallelize it, so that several files were downloading at once.

There are a few different options here. I could get a download manager, which would do what I want but requires me to install some random program that I'll never use again. I could use the solution presented in this blog post (first hit for "wget parallel downloads"), but that's still too much code. Or, I could use this nifty UNIX trick for parallelizing anything. :3

The code

First, write a Makefile that looks like this:

%::
        wget -nv -c $@

Save that as "Makefile", of course. Then, in the same directory, run this:

make -j3 [URL1] [URL2] [URL3] ...

...and all the URLs you specify will be downloaded, with three downloads going at a time.

But how does it work?

Not everybody knows this, but make includes a really neat dependency-aware parallel work queue. If you give it a really long list of jobs, where some of them depend on others, make can do them in parallel, while keeping track of what depends on what and making sure that dependencies happen before things that depend on them. (In this case, though, we have no dependencies to express, so the Makefile is really simple.) The "-j" option controls the number of jobs that make will run in parallel.

Our Makefile consists of a single wildcard rule (%::), matching any input, and calls wget with whatever we pass in ($@ - clearly whoever wrote make thought Perl-style variables were a good idea :p). make works by taking its command-line parameters, finding a rule that matches each one of them, and executing that rule. So all we have to do is run make with a bunch of URLs as parameters; it will look for a file called Makefile (the default), find a rule in it that matches the URLs (the wildcard rule, in this case), and execute that rule (downloading the file).

Variant: what if I have a list of URLs

The coolest thing about the command line is the ease with which you can combine programs. In this case, let's combine the above hack with the "xargs" program, which translates streams of lines to command-line arguments. If you replace the command line above with this:

xargs make -j4 < list-of-urls.txt

...then you can download every URL in a list, in parallel. (As an aside, xargs has all the necessary logic to work around the maximum number of command line arguments you can use at a time, so this should work with an unlimited number of URLs.)

But how do I parallelize EVERYTHING?

Up to you! This technique works in a surprisingly wide array of situations, if you're using the command line. The last time I used it, it was batch-converting a lot of images - imagemagick doesn't use multiple CPUs, but using make let me run multiple instances of it at once, so that I finished twice as fast. (My downloads have all finished, though, so the necessary changes to the Makefile are left as an exercise to the reader. :3)

Adventures in UNIX: Pipe buffer edge cases, half-open sockets

So yesterday I had a really neat idea: exposing pipe-based programs as network services. You could open a connection to a program, send it data, and the remote computer would put it through some predefined command and send it back. Then I realized that with IPv6, you could give each program its own IP address, and give them all names in the DNS, so that you'd have a perfectly usable system without using any higher-level protocols than DNS and TCP. Then I realized that this would be simple enough that you wouldn't even need to write any code to make this work - it's all doable with simple shell commands! (I was wrong about this last one, and that's the topic of this post.)

(By way of comparison: This is sort of an inversion of the Plan9 model of network computation. Instead of mounting a remote filesystem and piping it through a local program, you're piping local data through a remote program.)

Pipes are usually a one-way structure, but for this to work properly, I needed something a little more exotic. I need to be able to take output from a command, and pipe it back around to the beginning of the pipe, so that the pipe has a loop in it. If I could do that, I could combine netcat with any command, and that'd be a one-liner that implements a server. :D

So here's the first thing I tried.

Server:

mkfifo t
while true; do nc -l 127.0.0.1 9999 < t | tr a-z A-Z >> t; done

Client:

nc 127.0.0.1 9999 < testdata

In a perfect world, this would work! But here's where we get into the details of pipe buffers.

The first problem with this is in the server. When you use a pipe, data's actually buffered along the way, in the commands that are being piped. Normally, this is transparent, because the buffers are flushed out when the previous command exits. This doesn't work when you have a loop through a fifo, though! The data that's buffered in the tr command doesn't get flushed to the fifo until netcat exits, and so netcat never actually has the chance to send the tail end of the data. The only way I could think of to solve this was to write some code for the server - pretty disappointing, but probably necessary. (I'm not going to post that code here, because it's even messier than being a prototype should justify. >_>)

But that's not all - it turns out the client part is broken, for a completely different reason. When you give netcat an EOF (Ctrl-D), it doesn't know how to tell the remote side of the connection that there was an EOF. The server then doesn't have any way to know when to flush the buffers out and end the command, so the whole thing deadlocks waiting for more input that's never coming.

It turns out that TCP solves this problem; the bug is in netcat. With a TCP socket, you can close one direction of traffic, but keep using the other - for example, when you're done writing data to a socket, you can shut down the socket for writes, which signals to the remote side that you're done writing, and then read whatever the server sends back. This, unfortunately, required more code.

netpipe.py:

import sys
addr = sys.argv[1]

import select
def attempt_read(s, BUF_SIZE):
    if select.select([s], [], [], 0)[0]:
        return s.recv(BUF_SIZE)
    return ''

import socket
s = socket.create_connection((addr, 9999))

BUF_SIZE = 4096
buf = sys.stdin.read(BUF_SIZE)
while buf:
    s.sendall(buf)
    
    sys.stdout.write(attempt_read(s, BUF_SIZE))
    sys.stdout.flush()
    
    buf = sys.stdin.read(BUF_SIZE)

s.shutdown(socket.SHUT_WR)

buf = s.recv(BUF_SIZE)
while buf:
    sys.stdout.write(buf)
    sys.stdout.flush()
    buf = s.recv(BUF_SIZE)

(This is trivial enough that I'm planning to port it to C soon.)

Finally, some good news: this works perfectly! :D With this, you can open a connection and use it as a component in a pipe.

p2p DNS

Now that the US is considering forcing pirate domain names out of the DNS, one of the founders of The Pirate Bay is floating the idea of a p2p DNS alternative.

Okay, wow. This is an incredibly terrible idea.

I'll start with the obvious objections:

• The DNS is meant to be authoritative
In a p2p system, you don't know who you can trust, because everybody else is just a peer. The DNS is completely useless if the results you get back aren't authoritative. Some people are proposing web-of-trust type solutions, or other idiocy. NO. Web-of-trust doesn't scale, and requires too much human maintenance to ever work. Even being able to compute some kind of transitive trust metric is an open research question, and then there's the so-far-intractable problem of picking a trust metric. Any answer you get from a p2p DNS system will be unreliable.
• The DNS is meant to be reliable
DNS is meant to be a transparent layer, when you're using the Internet. It's something that you just sort of expect to work, and bad stuff happens when it doesn't. And the thing about p2p systems is, it's actually pretty near impossible to make any guarantees at all about their behavior. I've actually read a lot of papers about building distributed storage systems. And you know what? Nobody's ever actually managed to get anything better than a relatively weak statistical guarantee about any property of a p2p storage system. For the DNS, that's simply not good enough.
• Performance
The DNS has pretty tight performance constraints, and p2p systems (for all their advantages) are extremely vulnerable to DoS attacks. It's pretty much inherent in their design - any p2p system will require a peer to have fairly complex communications with a lot of other untrusted peers. And, as many people have shown over the years, when you manage to take down the DNS with a (D)DoS attack, people tend to flip out.
• Secure decentralized systems are HARD
Look, it's not like it's impossible for random people on the Internet to band together and write a program. It's not even that difficult; open source has proven that. What is hard is getting random people together to solve a fundamentally hard problem in computer science. Let me put it this way. If a well-respected professor of computer science were to propose a p2p DNS system, I would treat it with heavy skepticism. If Peter Sunde proposes it, and expects the Internet hivemind to just sort of blast through all the hard problems by sheer virtue of wanting torrents, then I just laugh. (And then, if it looks like people are taking him seriously, I write a blog post like this.)

There are some people whose first reaction to any data management problem is to try to stick it in a magic DHT and forget about it. In many cases it works - see BitTorrent, for example. A DHT will work in any application where you don't especially need data to be reliable or trustworthy; it's a perfect fit for BitTorrent peer exchange, where reliability is optional because the DHT is only a backup for the real tracker, and trustworthiness doesn't matter because the peers aren't trusted in the first place. For the DNS, though, a DHT is exactly the wrong solution.

It may be possible, someday, to fully decentralize the DNS. To do it will take some fundamental advances in computer science, though, and Peter Sunde isn't going to be able to make that happen by rallying the pirates to his cause.

Julian Assange is a Terrorist (and I mean that in a good way)

Politicians want to classify Julian Assange as a terrorist. Insane? Only at first glance.

I've been reading about something that Assange wrote a few years ago, which basically lays out his plans for Wikileaks. It's actually a pretty neat read. Summary: Assange sees today's American government as some kind of corporate conspiracy (can't argue there), and he wants to throw sand in the works of the conspiracy by increasing the cost of secret communication (without which any conspiracy dies). He intends to do this through random attacks on government secrecy, with the goal of forcing an expensive overreaction, which will end with governments being less secretive.

My first reaction: This dovetails perfectly with a blog post that I've been meaning to write (but will probably never get around to) about the tradeoff between trust and robustness in a networked system. It's actually a really cool tradeoff - trusting another entity in a decentralized system can be viewed as a dodgy optimization, which will usually work but occasionally crashes dramatically. (Bonus: the tradeoff even has a mathematical basis, in the FLP result!) Julian Assange is giving us a real-world demonstration of this principle, by poking at the relatively cosy relationships between governments and forcing them to shift into a less useful but more secure configuration.

My second reaction: You know how the .gov has been making a lot of noise about info-terrorists, even though they have no idea what that even means? DDoS kiddies are usually held up as an example of what to watch out for, but that stuff is so trivial that I'm surprised we waste our time talking about it. Julian Assange, on the other hand, is the real deal, and he's not even terribly sophisticated. He is using the power of the Internet, and the power of the (relatively) unrestricted flow of information, to do something radical to the state.

My third reaction: Oh, man. The government doesn't know how bad this could have been. If Wikileaks had wanted to publish this stuff anonymously, it wouldn't have been terribly difficult for them to do so. The technology already exists, and has for years; it's just a matter of using it effectively. They don't like their diplomatic cables being made public as it is; imagine how much it would suck for them to have a few thousand cables appearing every month, and to be completely unable to track where they were coming from. You know how I said that Assange wasn't terribly sophisticated? If he were, he'd be doing exactly what he's doing now - we'd just have no idea who he was.

Last reaction: I can't help but worry that Julian Assange is gearing up for a dramatic exit from this world. He is simultaneously making himself extremely visible, and making a lot of very powerful enemies. Wikileaks has already published an insurance file; that's not the sort of thing you do unless you expect to have a reason to use it. If Assange does end up assassinated, that may be all the proof we need that something like Wikileaks is desperately needed in today's world.

Rewind

So I read the Void Trilogy by Peter Hamilton a few weeks ago, and one of the subplots went like this: in a world of psychics, one young man has exceptionally powerful abilities. Throughout the books, he learns of increasingly incredible things he can do, until he realizes that he can turn back time itself. Specifically, he can think about any moment in his past that he can remember clearly, and rewind the universe back to that moment (but with all his memories intact). This is where things get a little bit nuts.

For the rest of the book, he tries to make everything right with the world, because he's that sort of character. It takes a terrible toll on his mind at times, but in the end, he lives a life such that there's nothing he wants to go back and fix, and he has reached fulfillment. Happy ending, right? And then he goes and, on his deathbed, gives the secret of turning back time to everybody else in his city - and this is where my brain implodes in dismay.

If zero people know how to turn back time, then things make sense, and history proceeds in a boring linear fashion. If one person knows how to turn back time, then things are still simple enough to wrap your head around, because you can trace a single thread of narrative throughout whatever they do - by designating them the "main character" in the story, the story makes sense. But if two or more people know the secret, then things get Terribly Complicated.

Here's one trivial example of how screwed up the universe would become: imagine a game of Rock-Paper-Scissors between two especially competitive people that know how to turn back time (Rewinders?). The entire universe would be locked in a loop until one of them got bored.

There are weird issues surrounding seniority. If two Rewinders are going back and forth on something, the winner is going to be the one that can go the farthest back - back to before the other one existed, perhaps. If we follow this train of thought, then the winner in any conflict is going to be whoever is the oldest.

On the flip side, there are weird edge cases around death. If I sneak up on someone and kill them before they can react, then that's it for them, I've won, no second chances. This is the only way I can see to break out of a loop without first going through the infinite regression tango, and giving the victory to the older person. A world full of Rewinders would have a lot of immortals trying to kill each other, really - sort of like The Highlander but with more mindfuck.

I'm not really going anywhere with this post. Honestly, I just thought it'd be fun to actually think through some of the consequences of a world with Rewinders. :D

Diaspora!

So at the beginning of this summer, a group of NYU CS students started on a project to build a decentralized social network, and then made waves when they raised over $200,000 on kickstarter, a crowdsourced funding website. They then proceeded to disappear into a cave for the entire summer, which killed the buzz around Diaspora pretty effectively. Then they put the project up on Github, and people immediately jumped all over them for security flaws. (Personally, I would expect to find security holes about that magnitude for a project this young. You fix them, and you move on.)

If I had to give my opinion of the project, it's somewhere around "cautious optimism". I'm not a Ruby or a Rails fan, but there are worse languages/frameworks they could have used. I think they're striking a reasonable balance between developing in secret and developing in public. On the one hand, they promised to make everything 100% open source, but on the other hand, the open source development model is pathologically incapable of making design decisions, and for the initial stage of a project you're making nothing but. I definitely like that they're piggybacking on existing protocols.

Apparently, they were inspired by Eben Moglen's idea of a "freedom box", which makes me sort of nervous, actually. Nervous, because the idea is good in principle, but completely unworkable and sort of silly in practice. Yes, it would be useful if we all had physical control of our own social media profile, but this has tremendous implications for the reliability of the network as a whole - if my Internet connection goes down, to what extent do I disappear from the web? And, of course, I'm glossing over all the real difficulties with hosting a website on a residential Internet connection. Quite simply, our infrastructure isn't up to the job, and I don't expect that to ever change. So, I kind of hope that the Diaspora devs aren't going to waste too much time on this particular use case.

There are also a ton of fundamentally hard problems that they are going to run into, and while I remain optimistic that they're thinking about them, we won't really know how they handle them until the software is in a more complete state. For example: how do you handle security updates in a worldwide distributed system? There are already a ton of insecure Diaspora instances running around in the wild, that people brought up as soon as the code landed on Github, and the problem is going to get worse unless they do something about it.

Overall, I have high hopes for Diaspora, but it's simply too early to make a call about the project. I'm expecting it to advance rapidly, though, and we may be looking at a 1.0 release within a year. Whether or not it's a "Facebook-killer", like people want it to be, it has a lot of potential to be a useful tool.

Wallet

I seem to have lost my wallet! It is fucking with my head like you wouldn't believe.

I have looked everywhere. I have looked everywhere at least twice. I've crawled on the ground looking underneath maybe half the furniture in this house. I've torn my room apart - I don't think there's a square inch in there that I haven't looked at today, except for maybe spots that you have to disassemble furniture to get to. I have taken all the cushions off of all the couches, I think. I've called the last place I saw the wallet, and since I came home straightaway after that and haven't really gone anywhere since, there are no leads there. I am this close to trying to figure out a tactful way to call up everybody that was here for Thanksgiving and asking if they walked off with my wallet. Like I said, fucking with my head.

Why am I freaking out so much? This is my first time losing my wallet, and I suppose my first time finding out just how much of a pain it is. If I can't find it before my flight on Sunday, I'm going to have to cancel my credit card and debit card, replace my insurance card, replace my Social Security card, replace my ORCA card (free bus rides, one of many Microsoft perks) so I can ride the bus to work. (By a sheer stroke of luck, I still have my driver's license; don't even ask. XD)

And then, I have to figure out how to keep this from ever happening again. Because, see, I can't just leave a problem like this alone, and deal with it when it comes up. I'm a pathological overthinker. My reaction when a hard drive fails is to create increasingly elaborate system of redundant storage, culminating in what I built earlier this month. My reaction to almost losing my cell phone is to keep multiple backups of all the data on it, just in case. Now that I've lost my wallet once, I'm not sure that I'll be able to ignore the possibility of it happening again - my brain just doesn't work that way. I don't know how I'll solve the problem of randomly losing things that I need to carry around everywhere I go, but I know that I'll be kind of agitated and jittery until I do - it's just how I'm wired.

My mom, bless her heart, tried to help - not by helping me look, but by trying to make me feel better about losing my wallet. Frankly, it just made things worse. She asked me to imagine the worst-case scenario; thanks for the completely generic advice! I definitely feel inclined to sit and listen to you, when I know that you're taking this far less seriously than I am! Plus, I know on an almost subconscious level that she's just trying to make me feel better, and that's not what I want. I don't want to feel better about it, and I don't want to sit down and think about "how bad could it really be". I want to find my goddamn wallet. If all your help means to me is that I have to act calmer while I'm searching frantically, then please, just stop trying.

Anyway, I haven't given up yet. I still have another day to try and figure out where it went. I am convinced that it's still in this house somewhere, and that's the most incredibly frustrating thing - it's so close, but I may not have enough time to find it! Still, I've got until my flight on Sunday. Once I get on the plane, then I'll give up, and start figuring out what all I need to replace. Until then, there's still hope.

The Science of Code

Found this blog post today via reddit. It has a really cool insight: The way people work with code is evolving into the same patterns that exist in the sciences today. At the one end you have the "physicists" - people that work with code on the lowest levels (either machine code, or algorithms, depending on your interpretation), and that can expect mathematical certainty. At the other end, you have code "biologists", that mostly work with whole organisms/programs, which are messy things, but which mostly work in mostly predictable ways.

There are a few neat consequences that you can pull out of the analogy. First, while wizards slinging machine code and novices putting scripts together are both "programmers", we probably need new designations for them, in the same way that you can't always lump physicists, chemists, and biologists together as scientists. Second, even though scripting is perceived as easier than low-level programming today, that could be because of the relative immaturity of the field, and not because it's inherently easier. See this comic, for example: physicists can look down on biologists, but biology is hard! Physics can be seen as the ultimate reductionism, and other sciences are simpler in terms of the physics they use, but harder precisely because they can't afford to reduce everything to that degree.

Higher-level programming languages, then, aren't just about simplification - they're also about specialization. (Maybe this is why domain specific languages (DSLs) are a big deal today? By creating a new language, you're jumping ahead of the existing languages in terms of specialization, which is akin to opening up a new field of study in our analogy.) By leaving some of the complexity of the lower levels behind, you're able to create new abstractions and concepts, which are interesting in and of themselves.

I think the analogy actually outstrips modern programming practices by a bit. If you want to write "organic" code, for instance, you need a specialized language like Erlang, since as far as I know it's the only language designed to handle failures of different parts of the program, and keep on running smoothly. Current languages mostly have the assumption that any fault is reason to terminate the program, because the whole thing should be 100% correct. From a physicists perspective, this is fine - if it's not 100% correct, you can't count on it doing anything right! I'm coming around to the "sloppy code" view the more I think about it, though.

The assumption that all code should be 100% correct is unreasonable in this day and age. It pains me to say it, because it goes against everything I've been taught (and quite a bit of what I've said in the past). All code is going to be a bit sloppy, simply because it's written by humans, and not by the faultless code-writing machines that those humans fancy themselves to be. What we need in the next generation of languages is more robust mechanisms for handling incorrect code; if we don't do that, we're not really designing languages to be used by human beings.

Layers of Fail

So here's an annoying multi-layered fail, notable because it affects three adjacent layers of the network stack! As any programmer will tell you, the most interesting bugs to diagnose are the ones that result from the interaction of other bugs. This particular one results in me losing messages on AIM.

First fail: U-Verse and my Mac

I don't know if anybody else has seen this problem, but my Macbook Pro cannot keep up a reliable connection to any U-Verse modem. I've seen this problem with multiple U-Verse modems, and only my Mac, so the possibilities are (in order of likeliness):

1. Buggy AT&T software in the modem
2. Buggy firmware for my wireless card
3. Random hardware fault in my Mac (unlikely, because it only happens with U-Verse modems)

This is pretty annoying, because WiFi is supposed to be standardized! All implementations are supposed to be interoperable with all others. Either AT&T or Apple could have caught this (isn't it standard practice to test with other widely-used hardware?), so the fault could lie with either company. Luckily, I don't have U-Verse at home, so I don't have the need to diagnose this properly - it's only an issue when I'm visiting people that do, like my parents.

Second fail: Automatically dropping connections on interface down

This is such a widespread thing that I think it must be intentional, but I can't figure out any reason that it's not a terrible idea. On any OS that I've used, when a network interface goes down, all connections are severed automatically. The thing is, the IP protocol is explicitly designed to allow lost packets, and the TCP protocol on top of it is designed to handle it, so the dropping of connections is unnecessary. If operating systems just ignored the loss of the interface on the assumption that it'll come back up soon, everything will still work as designed, and a lot of situations involving intermittent connections will work much better!

In other words, effort went in to a feature which makes things worse, which definitely counts as a failure in my book.

Third fail: AIM protocol doesn't handle dropped connections cleanly

This one's pretty simple: if a connection drops, and a message is sent during the timeout before the server decides that the connection is dead, that message seems to be lost. Seems like a simple bug to fix on the server, but it's been going on for a while now, so apparently that's not going to happen. What's more irritating about this one is, AIM already seems to save messages that are sent to somebody that's offline - it just can't detect that you're offline during the timeout period.

The end result of these three (or two, if you don't want to count the middle one) bugs is that AIM is nearly unusable for me when I'm using the WiFi at my parents' house. (Yet another reason to switch to GTalk? :D No idea if it has the same problem, though.)

"Content" and "Consumers"

So am I the only person that gets annoyed when people talk about "content"?

The phrase is aggressively bland and intolerably reductive. "Content" can be anything. "Content" is a book, an article, a song, a cool video, a funny joke, a clever program, a picture worth a thousand words - all glommed together into a single nondescript concept. Nobody who has created something worth creating, something that they're proud of, will refer to it as "content". "Content" is anonymous. "Content" is undifferentiated. "Content" is everything, and nothing in particular. "Content" is what you call it when you don't care what it is.

"Content" is what you feed to "consumers" - nothing more.

And there's another word that bugs the hell out of me: "consumers". A "consumer" isn't a person - it's a thing, a mindless black hole, which consumes whatever you put in front of it. People are complex and individual, but we know how to market to "consumers". A "consumer" isn't something you would ever have a conversation with. A "consumer" never produces anything of value. "Consumers" are all the same, and when they're not, they're amenable to market segmentation. "Consumers" exist because they're easier to deal with than people.

I think that the mindset embodied by these two words is a sickness. When you see the world in terms of "content", and "consumers" that want it, you're hiding away all the incredible richness of the world. "Content" is culture, viewed from the outside, with the intent to put it in boxes and sell it to people - sorry, "consumers" - and it honestly freaks me out a little that there are people out there that are willing to think in those terms.

So please. Can we all stop using these words? I think we'll all be happier in the long run.

The Shallows

So like I mentioned yesterday, I've just finished reading The Shallows, by Nicholas Carr. It's about the effect that the Internet is having on our thought processes, on a fundamental level, and it's a pretty amazing book.

We see the Internet as an incredibly powerful tool for organizing and retrieving information, and we're right - as a multiplier for our own abilities, it's an unprecedented achievement. What some people are realizing, however, is that it is not without its downsides. Ask yourself this: how many books do you read for fun these days, and how many did you read before you discovered the Internet? Carr contends that this is not just because our reading has shifted online; instead, our brains have been rewired by the constant cheap stimulus of the web, so that we find it more difficult to read extended prose than we used to.

Historical precedent

Believe it or not, this isn't the first time that a new technology has fundamentally changed how we think. Carr looks all the way back to the invention of written language, which represented the beginning of the shift from an oral culture to a written one. There's some interesting stuff here that I didn't know about. For example, written languages were originally written using only letters, with no punctuation, or even spacing between words. See, written language was originally just a transcription of what people said out loud, and only intended to be read out loud. It wasn't until hundreds of years later that these things were added to language, to make reading easier.

The revolution brought on by written language reached a fever pitch with Gutenberg's invention in the mid-1600s. All of a sudden, books (previously reserved for the wealthy) were cheap enough that everybody could have them. Simultaneously, the automation of printing meant that the cost of introducing a new book decreased dramatically, so that authors were free to experiment with radical new styles of writing. (Critics of the time decried the new styles, a product of new technology, as a massive dumbing down of literature - sound familiar?)

The introduction of reading to the population as a whole caused a fundamental change in the way we thought. Carr starts the book by just asserting this, but when he really gets into the meat of his argument, he backs it up with a lot of neurological evidence - mostly the dramatic changes that occur in our brains when we learn to read, as seen through an MRI.

Shallows

So how is the Internet changing things? Carr cites study after study that all point in the same direction - the Internet diminishes our ability to read deeply, by encouraging skimming and by allowing us to skip around to other pages easily. Furthermore, it does so on a fundamental neurological level. This is the core argument of the book, and Carr backs it up well, going all the way down to what we know about the mechanisms of human memory.

There are lots of counterarguments to be made here, of course. Even if the Internet makes it harder for us to absorb a book of information, doesn't it make up for it by giving us easy access to anything we might want to know? Doesn't the fact that looking up information is now instantaneous make it more efficient for us to know a wide variety of subjects shallowly, rather than learning a few subjects more deeply? (Personally, I'd say that it depends - some questions are harder to answer than others using a tool like Google, and it's an effect that's difficult to take into account when deciding what to learn.)

What should we do about this? It's hard to say. Really, it's hard to even say what we could do - people aren't even convinced that this is a problem today, and that would be a necessary prerequisite before we could even talk about steering the tech industry based on the effects that technology would have on us.

The technocrat in me thinks that we should just let technology happen, and deal with the consequences after the fact. Technology can solve technology's problems, and everything will work itself out, right? I used to believe that, anyway, but now I'm not so sure. (Maybe I don't have as much faith in humanity as I used to?)

In any case, though, everybody should read this book! Even if you don't agree with this author's premise, you'll probably find it an interesting read.

Nook!

I've so far neglected to mention it here, but I got a Nook!



Compared to the Sony Reader that I've had for a few years now, this is a huge improvement. I'll start with the most visible difference - while the Reader has buttons numbered 1-10 plus a few more for navigation, the Nook has a color touchscreen. They use it with the main E-Ink screen fairly effectively, too - the interface is generally divided between them sanely, with stuff being displayed on the big screen, and all the controls on the touchscreen.

The E-Ink screen on the Nook is noticeably better than the one on the Sony Reader. The contrast is much higher, and the resolution seems a bit better too (though that could also be the font, I guess). The Nook is also much smarter about updating the screen; where the Reader would have to refresh the whole screen with an annoying invert-everything action, the Nook can update individual pixels without disturbing the rest of the display.

The other most important difference is the inclusion of a wireless connection, like the Kindle. I'm pretty impressed by how well this feature works - I can browse the bookstore, buy a book, and download it to the device within a span of a few minutes. (Browsing over a cellular internet connection is a bit sluggish, though. If you can, it's much easier to buy the books through the B&N website.) There's also a WiFi-only version, but I think that's not as much fun. WiFi can be hard to find, and it's nice to be able to get new books from a moving vehicle. As far as ebook pricing goes, I don't have any complaints about the B&N store.

Battery life is a different story. While reading, the battery lasts pretty much forever (and by forever, I mean it should last through any one book, at least that I've found), as expected of an E-Ink device. When you put the device to sleep, though, it only lasts for a few days before needing to be charged. This is pretty disappointing, honestly, and I hope they fix it in a future software update.

Today on my flight to Houston, I brought the Nook and finished The Shallows, which is about how technology is changing our reading habits. (Wooo, irony!) I think I'll be talking more about that in tomorrow's post, but as far as the reading experience goes, it was at least as comfortable as reading a real book. Probably more so, in fact, because the Nook is easier to fit in my bag than the paperback (The Prefect, by Alistair Reynolds; somebody lent it to me and now I need to read it!) I brought along as a backup.

Summary: The Nook is kind of awesome, and I need to finish this post within the next minute or I'm not going to finish in time.

The Man-in-the-Middle Defense

I'm not sure why this is, and it's probably a really bad idea, but for some reason as BitTorrent gets harder to use (with all the major trackers being targeted), I become more and more motivated to come up with a p2p protocol that doesn't have BitTorrent's weaknesses. So in that vein, here's something I've been thinking about.

One of BitTorrent's biggest problems is that every user knows about all the other users, and so sending nasty letters to everybody downloading a given file is as simple as grabbing a list of IP addresses and contacting a bunch of ISPs. What we need, then, is a way to anonymize connections, and transfer data between two computers without either of them knowing the identity of the other. There are already a few protocols that get us partway there: using a traditional proxy, you can mask the address of one party, but not both; using something like Tor, you can prevent any one proxy server from knowing both the client and server address, but the client still has to know the server address. So what can we do instead?

Repeaters

The golden rule of system design: When in doubt, go for the simplest thing that could possibly work!

So in this hypothetical protocol, two peers (Alice and Bob, why not) have been communicating pseudonymously. At some point, Alice wants to send Bob a file which is too big for the channel they've been using, so they both agree on an anonymous repeater. At some predetermined time (in most protocols, the time would just be "now"), they both connect to a server, and the server just repeats everything it sees on one connection to the other.

(Once you've got the simplest thing, you may need to fix up a bunch of other problems.)

First, we need a way for a single server to distinguish between a lot of people connecting to it at once - which of them actually want to talk to each other? One solution is to have Alice and Bob agree on a shared secret ahead of time. When they both contact the repeater, they send the shared secret, and the repeater knows to establish a connection between them.

That's weak against eavesdroppers, though, and in today's world of relatively widespread DPI gear, you just can't trust the network. This can be solved with SSL, but only if Alice and Bob can agree on the repeater's public key ahead of time. (If not, then SSL certs are easy enough to fake - it's a little extra effort to do so, but if we were only defending against unmotivated eavesdroppers, then this would be pretty easy!) Solving this problem properly will take a little more thought than I'm willing to put into this problem tonight, unfortunately. (Maybe passing the SSL layer through the proxy?)

How do we keep the repeaters from learning about Alice and Bob's identities? For that, we can use proxies - we only need to keep their identities safe from the repeater, not the other way around, so existing proxy mechanisms will work for this.

How will we handle the performance cost of going through so many layers? Alice and Bob can agree on some protocol ahead of time for dividing the data across several paths, or something like that. I'm explicitly not designing that layer here - proxies and repeaters are general enough mechanisms that more complex protocols can be implemented on top of them pretty easily. (That's one of the biggest advantages of using the simplest thing!)

As a completely unintended bonus, if anonymous repeaters like I've described here become widespread, that could be a solution to the problem of establishing a connection between two computers that are both stuck behind NAT.

Digital Dead Drops

A completely different solution to the original problem would be establishing "dead drops" - locations where you can drop a file for a certain amount of time, and somebody else can pick it up later. (I've already seen pastebin used like this, come to think of it!) If both parties use proxy chains, and the data is encrypted, then this is even more secure than using repeaters because you avoid the simultaneous connection problem - an eavesdropper has a hint about who you're talking to because you're connected (however indirectly) to the other user.

The Next Problem

The other major problem with p2p networks is that search is public - by making a file available for others to download, I'm also announcing to the world that I have that file, and some people might be upset about that.

I have some ideas about how to solve that, but I've probably spent too much time blogging about this topic already. Instead, I think it's time for me to start coding these things up, and see what works. Should be fun!

Chaos Theory

The point is, ladies and gentleman, that chaos, for lack of a better word, is good. Chaos is right, chaos works. Chaos clarifies, cuts through, and captures the essence of the evolutionary spirit. Chaos, in all of its forms; chaos in life, in money, in love, knowledge has marked the upward surge of mankind. And chaos, you mark my words, will not only save Android, but that other malfunctioning entity called the US cellular industry.

This completely unnecessary riff on Gordon Gekko was inspired by this article, which asserts that Windows Phone will have an advantage over Android because it's less "chaotic". How horrid! That kind of platform lockdown moves Windows Phone onto the iPhone's turf,

The iPhone model (one OS running on one device, all controlled by one company) works for Apple, but I personally think it's a fluke. By launching the first smartphone platform in the multitouch paradigm, Apple snatched up enough of the market to become entrenched, and by the time competitors showed up, Apple was on the second or third revision of the iPhone, giving them a lead that could take a decade to wear off. I would argue that they succeed today in spite of (and certainly not because of!) their locked-down ecosystem. The iPhone hasn't changed significantly since the first revision, and at the rate things are going right now, it might not be premature to label the iPhone a legacy platform.

Android, on the other hand, is chaos. Google all but throws the software out there, yells "Come and get it!", and lets the carriers and manufacturers do whatever they want with it. It's sometimes inconvenient, but it also leads to some really cool stuff. Can you imagine something like the Nook (which secretly runs Android) being built on top of the iPhone OS?

I sometimes joke about Windows Phone copying the iPhone to an astonishing degree, but it still worries me. The iPhone model is something that will work once, for the first company to come up with a revolutionary new paradigm, but after that a single entity can't keep up with the rest of the industry for very long. Microsoft does seem to be doing a lot of things better than Apple (C# doesn't make me want to kill myself the same way Objective-C does, for instance), so Windows Phone is still a compelling platform, but if Microsoft wants long-term viability it's going to have to look beyond what Apple is succeeding at today.

We must remember that Windows - and, hell, the entire concept of an operating system - came into being to manage chaos, not eliminate it. Back in the Bad Old Days, hardware platforms were fairly standardized, and introducing any changes was likely to break existing software. This is where turbo buttons originally came from, and it's not a model we should be aspiring to. Having a number of different hardware profiles may make Android harder for developers to test their apps on, but it also means that the platform is much more flexible, and by forcing developers to account for different hardware profiles, Google is creating a better platform for the long term.

Any Windows program will (with very few exceptions) run on any Windows computer. Microsoft's past success with that model wasn't a fluke - it was a testament to the fundamental power of a model that allows for a wide variety of future hardware improvements. It's interesting to see how closely the development of mobile phones is mimicking the development of PCs 25 years ago; some of the players (like Apple) are even moving into the same positions. Microsoft has already managed to invent the PC once, and I hope that some people at the company remember enough to be able to invent it again.

In the end, it comes down to how mature you think the smartphone market is. If you think most of the innovation has already happened, then bet on the vertically integrated platform (like the iPhone). If you think most of the innovation has yet to happen, then bet on the open, flexible platform (like Android). It's still early enough in Windows Phone's development for Microsoft to make a choice, and I really hope they choose the latter.

Ken Robinson on Education

Today: lazy. Videos!

New phone!

So I've started thinking about getting a new phone!

Windows Phone

On the one hand, there's Windows Phone. I haven't had great experiences with Windows Mobile in the past, but Windows Phone is a totally new platform, and it actually seems pretty nice. I get one for "free", as a Microsoft employee - free with a two-year contract, though, so really it's closer to half price. Everybody else around the office is pretty stoked about them, and the enthusiasm is a bit infectious. The development tools look pretty awesome, too.

On the other hand, it's a totally new and somewhat unproven platform, with a radical new user interface to boot, and hardly any apps written for it yet. There's also the Microsoft factor, as much as I hate to admit it - I just don't have a ton of confidence in Microsoft's ability to execute in this space. (Here's an example: I use Microsoft My Phone to sync my phone to the web right now. It's a really useful service, but Microsoft is killing it in favor of Windows Live, and I have yet to see any official solution for migrating my data to Windows Phone. No other company in the world could get away with this kind of lack of focus.)

Pros: Employee price, easy to code on, supporting my employer, shiny.
Cons: New; unproven; Microsoft

Android

In the other corner, we have Android. It's proven to be a solid competitor in the mobile space, and is usually mentioned in the same breath as iOS these days. It's also Linux-based and relatively hackable (in the good way), and I have to confess to a certain amount of nerdy glee at the thought of being able to ssh in to my cell phone and poke around. >_> The open source factor is also a plus, even if Android isn't going along with the spirit of open source at all.

There are also problems with Android, foremost among them being that manufacturers usually don't release updates to phones that aren't ridiculously popular. The Nexus One gets updates, the Droid family gets updates, and so do other phones of similar notoriety, but most aren't so lucky. I'd also be the only guy at Microsoft without a Windows Phone, which could get awkward.

Pros: Solid platform, open source(-ish), hackable, has momentum
Cons: Carriers have too much control, Google is slightly evil
Bonus: Microsoft's strategy against Android is pretty much the sketchiest thing possible (future blog topic), and actually inclines me to support Google. <_<

iPhone

The thought of carrying millions of lines of Objective-C code in my pocket just makes me shudder. No iPhone for me.

MeeGo

MeeGo is kind of the dark horse in this race. It's a joint thing between Intel and Nokia (and a few others?) to put together a proper open source Linux-based phone OS. (None of this Android-style "code drop" crap.) This would be a really compelling option for me if they'd gotten around to releasing any phones yet, but... well.

There is the Nokia N900, which you can run MeeGo on, but I don't get the impression that it's especially well supported, and the N900 is already a year old. Overall, it seems like MeeGo is at too early a stage in its development to consider, but if Nokia or Intel announced a phone tomorrow that had high-end specs and ran MeeGo natively, well, that'd certainly throw a wrench into my decision.

So. Anybody got opinions? :D