Backend In the Frontend: Implementing Raft in JS

Background

Lately I’ve been studying consensus algorithms to bolster my understanding of distributed systems. Consensus algorithms achieve agreement on data that is replicated across many nodes.

Consider an online store. At any time, the store has a state that is defined by all of its transactions. The store keeps a transaction log that can be used to recreate that state. The log is replicated across multiple servers so that the store is robust against server failures. A single machine may go down at any time. But when it comes back online, it can use the log to recreate the store’s state.

Before new transactions can be added to the log, the machines must reach consensus on them. If each machine didn’t check with the others before adding something to the log, then their copies of the log would drift apart. Eventually, this would result in adverse behavior like the same widget being sold twice or a successful sale getting forgotten.

There are many consensus algorithms out there. I started with Paxos, since I knew that it powered Spanner. After reading through a whitepaper on implementing Paxos, I found it to be powerful but also relatively enigmatic for a distributed systems layperson.

As it turns out, I was not alone in my confusion. Two students at Stanford who shared my frustration with Paxos’s complexity created a simpler consensus algorithm called Raft. Raft breaks its algorithm down into more discrete steps that could be easily understood. I decided that it would be fun and helpful for my understanding to implement Raft in JavaScript using their whitepaper. Note that the Raft page has a different implementation made by the paper’s author.

This post doesn’t go into depth on how Raft works, but if you’re interested, I recommend checking out the Raft site. Instead, it displays the simulation I made and describes the underlying code.

TL;DR: The Product

Three nodes sit inside of an SVG graphic. Even though Raft would usually be implemented with five nodes, I chose three to optimize simplicity over robustness (remember folks, it’s not real). Raft can operate with just two nodes, but that assumes neither will ever go down.

At initialization, the nodes have no leader. When a leader is finally chosen via a timer-based election, it will remain in power unless manually turned down (i.e. clicked). In the absence of any new data, the leader will reaffirm its reign with the other nodes by periodically sending heartbeats to the other nodes.

Meanwhile, a client perpetually fades in and out of the edges of the graphic, periodically sending new data to the system. The client only speaks to the leader in this simulation, but Raft allows the client to speak any node and be redirected to the leader.

When the client sends new data, the leader persists and attempts to replicate it on the other nodes. Once a majority of nodes report back that they have replicated the data, the leader will commit it. At this point, the leader could report success back to the client, but that is not implemented.

Clicking a node will turn it down until it is clicked again. This allows you to interact with the simulation and explore some specific states. You can also pause to drop (click on) messages.

What I Learned

While reading the white paper can give a decent understanding of Raft, implementing the algorithm crystalizes its nuances. In addition, faking components of the networking stack also made me think a lot more about building blocks that I normally take for granted, like request-response protocols.

Observing Values Purged From a Replica’s Log

One of the most complex situations in Raft is when a replica has a set of log entries that differ from the the committed entries at those indices. This happens in the following scenario:

  1. The leader receives some new values but is not able to replica them on a majority of replicas. So, the values are uncommitted.
  2. The leader goes down.
  3. A new leader is chosen, and it commits a handful of values. Now, at some indices i through k, the old leader has bogus values.
Replica 2 recorded a few values as leader but was not able to commit them. After it was turned down, Replica 0 committed a bunch of new values.

When the old leader comes back online, it will attempt to maintain its leadership reign. Instead, it will learn about the new leader, purge all of its outdated values, and replace them with the committed values. Watching this in action is surprisingly satisfying!

Replica 2 has been corrected. It purged the outdated values and replaced them with Replica 0’s values.

Raft Is For Fault-Tolerance, Not Performance

At first glance, replacing a single machine with a Raft consensus network may seem like a way to boost an application’s performance. In fact, it is the exact opposite: Raft adds more latency, CPU, and storage in exchange for robustness. In the Raft algorithm, only the leader can serve both reads and writes. And, since leader must commit a value before returning success to the client, responses are slowed. The CPU and storage come from the extra machines at work.

Raft Only Works Because of Trust

As I was implementing the algorithm, I thought about how odd it was that the leader would step down from power as soon as it had heard about a leader with a more recent election term. The leader respects this information no matter who tells it. Raft actually guarantees that the leader with the most recent election term (i.e. highest term number) is the true leader.

Raft won’t work without assurance that all of the replicas can be trusted. Algorithms for networks that may include rogue nodes are discussed via the Byzantine General’s Problem. Interestingly, both Paxos (precursor to Raft) and the Byzantine General’s Problem were invented by Leslie Lamport. Consensus algorithms without trust are considerably more complex than Raft, and they power peer-to-peer systems like the famous Bitcoin blockchain. (For those interested, Bitcoin is powered more specifically by a Proof-of-Work system called Hashcash).

Difficulties in Testing Correctness

After just a few hours of work, I had an implementation of Raft that appeared to be “mostly correct”. But, I quickly realized that without extensive unit test coverage (which I was not interested in writing for a learning experience), it was nearly impossible to determine whether I had achieved real correctness. As I watched the simulation, I would sometimes observe odd behavior and note for later investigation. After checking many of the edge-cases in the system using a combination of the pause button and the turn-down features, I believe I have handled most or all of them correctly.

Avoiding Derivative State

Thankfully, the Raft paper describes the necessary state that each replica must hold to function. To avoid a messy soup of instance variables, I derived many other “states” from these variables. For example, state like isLeader can be derived from the bare bones information.

High-Level: The Architecture

The simulation uses object-oriented programming to represent the distributed system. The Replica class handles all logic related to a single node, and hence the bulk of the algorithm. Replicas are responsible for rendering themselves, handling incoming messages, and sending out messages. They also push updates to the TableUpdater class, which reflects those updates in the table.

The Message class is responsible for rendering a message, determining its component velocities, and marking itself dropped when clicked. Messages are created using factories to avoid passing repetitive parameters into each message constructor. The parameters are dynamically determined by simulation-wide constants (FPS, simulation size, etc).

Once a message is in-flight, it is handled by a singleton MessageManager. The MessageManager is responsible for moving messages, delivering messages, and removing dropped messages.

A singleton ClientManager creates and destroys Clients. The ClientManager is given an average client lifetime, a rate of client creation, and a maximum number of clients at any given time. I actually determined that one client was enough for the simulation, so some of these features are unused. Once a client is created, it periodically sends new data to the Raft replicas.

The Animation Loop

Th simulation uses a standard animation loop [1]. It is updated frame-by-frame at a specified FPS. The simulation continuously polls the browser for new animation frames and handles them at the correct rate. Code (see original):

var FPS = 60;
var interval = 1000 / FPS;

function draw() {
    window.requestAnimationFrame(draw);

    var now = new Date().getTime();
    if (now - time > interval) {
        time = now;
        // DO STUFF HERE (ex: myObj.handleFrame())
    }
};

$(document).ready(function() {
    window.requestAnimationFrame(draw);
})

The Messaging Layer

In the real world, the nodes in a distributed system would communicate over an established messaging protocol like RPC. And, they would sit on top of networking technologies that would route requests and responses to the right addresses. In the simulation, this all needs to be faked. The entities (clients or nodes) in the animation need to have unique addresses, and they need to send messages over an agreed-upon protocol.

Establishing Addresses

Each node’s “address” is its coordinates in the graphic. When an entity sends a message to another, the message determines its direction by breaking a predetermined speed (scalar) into x and y component vectors. Code (original here):

getComponentVelocities(sender, receiver) {
    var dx = receiver.x - sender.x;
    var dy = receiver.y - sender.y;
    var theta = Math.atan(Math.abs(dy / dx));

    var v = this.v + (Math.random() * this.jitter);
    var vx = v * Math.cos(theta);
    var vy = v * Math.sin(theta);
    if (dx < 0) { vx *= -1; }
    if (dy < 0) { vy *= -1; }
    return [vx, vy];
}

In order to add realistic randomness, jitter is added to each message’s velocity. This reduces the chances that messages arrive in the exact same frame.

Delivering Messages

On every frame, the MessageManager deletes dropped messages, moves in-flight messages forward, and delivers arrivals. A message has arrived when its overlaps with the recipient.

One interesting quirk here is that delivering a message can actually result in a new in-flight message. A naive message manager would iterate over its messages and remove arrivals. That will not work, since its messages can actually be altered during that process. In a real, multi-threaded backend, the messages would be a global variable protected by a mutex, and this naive implementation would result in deadlock.

Fortunately, we can get around the deadlock by storing the current messages in a temporary variable before handling them. Code (see original):

var tmpMessages = this.messages.slice(0);
this.messages = [];
tmpMessages.forEach(function(msg) {
    var receiver = this.receivers[msg.receiver];
    if (receiver.containsMessage(msg)) {
        receiver.handleMessage(msg);
        msg.cleanup();
    } else {
        inFlightMessages.push(msg);
    }
}.bind(this));

// Concatenation is essential, since this.messages may have
// been appended to since the reset above.
this.messages = this.messages.concat(inFlightMessages);

Handling Arrivals

Instead of inventing a new protocol, we can fake one with JS features. Each message has its own class that extends the base Message class (ex: AppendEntriesRequest). When an entity receives a message, it can use the message’s constructor to determine how to handle it. Code:

    handleMessage(msg) {
        switch (msg.constructor) {
            case RequestVoteRequest:
                this.handleRequestVoteRequest(msg);
                break;
             // More cases left out for brevity.
            default:
                break;
        }
    }

Correlating Responses With Their Respective Requests

Another messaging challenge I faced was that responses were totally disconnected with their respective requests. In most messaging frameworks (RPC, AJAX, etc), the caller has request information handy when processing the response. My solution was hacky but sufficient. Each node stores a map from request ID to request, and responses contain the request ID. Code:

this.pendingRequests = {};

sendRequest() {
  var msg = new Message();
  this.pendingRequests[msg.id] = msg;
  this.messageManager.schedule(msg);
}

handleResponse(msg) {
  var request = this.pendingRequests[msg.requestId];
  // Do some processing...
  delete this.pendingRequests[msg.requestId];
}

Deployment

The simplest way to share this project was via iframe. I exposed the simulation through Github Pages, and you can find the iframe’s link here.

The code uses ES6 modules for organization. I learned that many minifiers can’t operate on multiple JS files or a single file made from modules. Ultimately, I used an npm module called rollup to combine the JS files and terser to minify the result. Before pushing a new version, I update the minified JS with a small bash script:

#!/bin/bash
rollup main.js --file bundle.min.js --format iife
terser bundle.min.js -m -c -o bundle.min.js

Further Work

A number of further features could be added to the simulation:

  • Implement group membership changes (nodes leaving and entering)
  • Responding to the client when its data has been committed
  • Giving the client the ability to perform reads and not just writes
  • Implementing snapshotting

Conclusion

After spending over a year writing exclusively C++, it was fun to combine thinking about the backend with coding in the frontend. Implementing from a whitepaper was also new for me, and the work helped me understand the material on a deeper level. Hopefully this visualization will help some folks learn about consensus!

[1] I learned about the easiest way to make a JS animation loop here.

A Simple iOS App to Commemorate Mad Men

For those who aren’t fans, AMC’s Mad Men ended recently. Arguably one of the best TV series in the last decade and definitely my favorite, I wanted to do something to commemorate its finale. Fortunately, the last episode coincided with the end of my undergraduate thesis and a two-week stretch until graduation. I decided I could explore mobile programming and continue to worship Mad Men by creating an iOS app. What I ended up with was a small but surprisingly stylish application called Mad Draper. It may not be the most fleshed out application in the store, but it was a very helpful project for picking up some introductory Swift and iOS skills. Basically, Mad Draper lets you flip through some quotes from the show, backed by famous advertisements from the 1960’s. You can swipe through a series of screens like this one:

example-draper

Each image can be shared via text, email, Facebook, Twitter, etc. Quotes were curated by hand from an IMDB database, and the images come from all kinds of famous companies like Heinz, Ford, and Budweiser.

And, the application will send you quotes as notifications! This last part has really made it fun to have on my phone for the last ten days or so. Quotes can be scheduled for time intervals ranging from never to weekly.

To make this a reality, I started with Ray Wenderlich’s Swift tutorial (it comes free with signing up). I chose Swift mostly because it seemed fun and flashy, as opposed to its wordy predecessor. The tutorial is really fantastic, and it walks you through a lot of Xcode’s powerful but cryptic functionality.

Finished with the tutorial, I hacked at a Swift application with a Parse database. Sometimes Parse gets flack for being what some consider a replacement for hardcore coding, but its cloud services were key for quickly scaffolding this project.

The quotes portion of the application was pretty straightforward. I put them all in a Parse database, and I fetch them when the app opens. When the user swipes, the next quote is selected randomly from the list held in memory.

The notifications portion was a little tricker. Notifications are usually triggered by some action, but I wanted to send scheduled notifications. At first, I scheduled a bunch of notifications in a loop. Apple doesn’t allow an application to have more than 64 scheduled notifications at once. This meant that when the user reopened the app, I’d cancel all pending notifications and scheduled 64 new ones. This obviously was not ideal, especially if the user didn’t reopen Mad Draper before the notifications finished.

The answer was Parse Cloud Code. Parse lets you write Javascript code and deploy it on their servers, essentially creating a backend really fast. And, their Background Jobs were exactly what I needed for event-less notifications. Parse can group devices into different channels. I labeled each time interval a different channel, where the interval is determined from the settings. Here’s what checking and settings a user’s channel looks like in Swift:

    // Fetch the current setting
    let defaults = NSUserDefaults.standardUserDefaults()
    var channel = defaults.stringForKey("quote_notifications")
    
    // Give users with no channel the default of daily
    if channel == nil {
      channel = "Daily"
    }
    
    // Reset the channels on parse
    var currentInstallation = PFInstallation.currentInstallation()
    currentInstallation.channels = [channel as! AnyObject]
    currentInstallation.saveInBackground()

Next, notifications could be sent to each channel through cloud code. Here’s what the code to send a quote notification to a given channel looks like:

function sendPush(timegroup) {
  var Quote = Parse.Object.extend("quote");
  var query = new Parse.Query(Quote);

  query.find({
    success: function(results) {

      // Create random alert content
      var index = getRandomInt(0, results.length);
      quote = results[index];
      text = quote.get("text");
      speaker = quote.get("speaker");
      alert = text + "\n-" + speaker;

      Parse.Push.send({
        channels: [timegroup],
        data: {
          alert: alert
        }
      }, {
        success: function() {
          response.success(timegroup + " push successful.");
        },
        error: function(error) {
          response.error(timegroup + " push failed");
       }
      });
    },
    error: function(error) {
      console.log("An error occurred fetching quotes")
      console.error(error)
    }
  });
};

Parse.Cloud.job("dailynotification", function(request, status) {
  sendPush("Daily")
});

Scheduling the job can be done from a fancy Parse interface where logs and analytics are stored. This system was a significant upgrade from scheduling the notifications in the application.

From a design perspective, I had a lot of help from my colleague Runi Goswami. With her advice, I put a dark semitransparent layer over the ’60s ads so that the white text on top could be read easily. She was also adamant about using a font called Cooper Hewitt by Chester Jenkins, which looks awesome. And of course, she churned out the “share” button and the app icon. On the coding side, I used small tricks like fading the text and hiding the “share” button from a shared image to polish things up.

After a long wait in Apple purgatory (roughly one week), I pushed my project to the App Store. It was a fun few days putting everything together, and I learned that XCode is a really amazing tool. Swift is remarkably straightforward, too, but I wish iOS had more libraries for making UI elements; building an iOS view is much tougher than building an HTML page. I also learned to appreciate Parse’s functionality. It wouldn’t be my preferred tool for a large operation, but it was great for this quick project.

If you’re interested in checking out the code, it’s hosted on Github.

Play With All of Your Google Searches

I read this article recently, where I learned that Google now lets you download your search history as JSON. After a handful of clicks around your Google account settings, you can get a zip file emailed to you containing JSON files going way back (how far back will depend on how long you’ve had a Google account). I decided to make a simple command-line tool to visualize your personal search results. I had originally planned to visualize anonymized results from a pool, but most people I spoke with said they would probably not release their search history to a web application. Instead, I threw together a small tool that uses MongoDB and PyMongo to store and display results in chronological order. You can enter query text and get back all of your results, like this:

Screen Shot 2015-05-18 at 2.38.51 PM

To download your results, go to history.google.com/history. Sign in, click the gear in the top right corner, and click download. Google will email you with a zip file of your history.

To play with your results, first clone the Github:
git clone https://github.com/ritmatter/search-results

Unzip the file and move the Searches directory (the one with all the JSON files inside) into the project directory.

Run python searches.py

Check out the Github for this project here.

Is Pop Music Getting Less Intelligent?

Lately I’ve been thinking a lot about changes in pop music over time. In particular, I wanted to get a feel for whether or not pop music in the United States is getting less intelligent (a common criticism from older folks). To prove or deny this claim, I defined “less intelligent” as having vocabulary that is less eloquent and less varied. There’s a lot to be learned from pop’s vocabulary, since it reflects the culture of a large group of Americans. Calling pop music unintelligent is a stone’s throw from calling the American population unintelligent.

After rummaging through the web, I found this Huffington Post article, which displays common words in pop lyrics over time. I think the data says a lot about how American rhetoric has changed over time. In particular, pop lyrics have seen a rise in words relating to sex, violence, and drugs. I wanted to contribute to the conversation with a more general study focused on lyrical intelligence, rather than rhetoric. I found this article by William Briggs, which boldly states that music has gotten much stupider. He looks at the ratio of unique words to total words in pop music and uses that as evidence of pop’s growing stupidity.

Eager to procrastinate my undergraduate thesis work, check Briggs’s results, and write some Python, I set out to perform a similar study using Top 40 hits since 1950. Briggs doesn’t say explicitly where his data comes from, but it appears to be roughly the same sample. Top40 Charts lists all of the top 40 hits from 1950 on, and each year lists all of the top 40 in a simple table. I could easily grab all of them with a quick loop and some help from Beautiful Soup. From there, I threw the artists and titles into MongoDB with PyMongo as my driver.

So I had roughly all of the top 40 hits, with the exception of some noise, since a handful of the entries I scraped had typos or other fuzz. Now I had to get the lyrics. This one was tougher: I couldn’t find an accessible and free API for song lyrics, and I wasn’t looking forward to building a smart scraper that could traverse Google searches. It turns out lyrics.wikia.com has a lot of lyrics, and the page layout is consistent across lots of songs. The only issue here was that the URLs for each song were very specific, and any small discrepancy would lead to a 404. For eras like the 1950’s, when big band standards were covered repeatedly by artists that could be named “So-and-So”, “So-and-So & The Orchestra”, “So-and-So And His Orchestra”, etc, this made scraping difficult. I helped the process along by curating titles and artists with different regular expressions like removing featured names and removing phrases in parenthesis. In the end, this is the breakdown I got for successfully scraped lyrics. I figured it would be enough for a reliable analysis.

From here, it wasn’t so hard to sanitize the lyrics and compare across years. First, I explored the number of unique words per song, the total words per song, and the ratio between the two. My results confirmed what Briggs had described: unique words and total words have risen over time, but the ratio has gone down significantly. This would suggest that pop lyrics have in fact gotten less eloquent.

The rise in total lyrics can probably be attributed to a shift in genre: big band music and disco likely have less words per song than rap or rock and roll. And, earlier big band music might not have had a lyrical chorus, which would significantly reduce the number of repeated words. Interestingly, total and unique words experience a peak in 2003, which could be due to the large number of rap and R&B hits at the time. The year’s top 40 are smattered with 50 Cent, Eminem, Jay Z, and others. The dip since then could be a product of the popularity of electronic music and dance hits.

I wanted to dig a little deeper, so I explored the average word length in lyrics over time. The average word length was extremely close to four characters every year. I also found the average number of words of various lengths over time. Likewise, the ratio of four, five, six, seven, and eight character words has stayed pretty consistent over time. So, while there might be a lower ratio of unique to total words in today’s music, the words that were being used way back when were not necessarily “more intelligent” words. That being said, word length alone doesn’t say a whole lot about the quality of those words.

As a sanity check, I finished by making sure that the data was relatively consistent. It would be a shame if my results were being thrown off by a few outliers with tons of large words or tons of unique words. I examined this possibility by calculating the coefficient of variation for word length per song and unique words per song. As a rule of thumb, when the coefficient of variation is less than 1, the data is considered to be fairly consistent. You can read more about determining CV from this StackExchange post, which leads to other helpful sources. It turns out that the lyrics are pretty consistent within each year, so outliers are not skewing results.

A more comprehensive analysis of pop eloquence would require a better understanding of the meaning of the lyrics, but this 10,000 foot view suggests that pop lyrics have gotten less creative over time. Lyrics certainly seem to be repeating themselves more often. The general rise in both number of words and unique words per song can possibly be attributed to more lyrically dense music like rap or indie rock, as compared to big band music from the 1950’s and disco from the 1970’s. Since the average word length has hardly changed over time, I think it’s difficult to definitively call today’s music “stupider”, ask Briggs suggests. A safer and more substantial claim would be that music has gotten wordier and takes advantage of repeated choruses more frequently.

All of the code for this experiment is hosted on Github. The database is even dumped there if you want access to the lyrics.

Unit Testing Express Routes with Mongoose and Jasmine

I’ve been working for a while on a project called Repcoin. It’s a web application that uses Express, NodeJS, Mongoose, and MongoDB on the backend. As the Repcoin codebase has grown, we’ve become increasingly dependent on unit tests for sanity’s sake. One way to reassure that the code paths in our routes work is by unit testing with Jasmine.

Every request that hits our backend goes to the appropriate router. Consider a simplified version of the UserRouter, which handles queries related to the User Schema:

var UserHandler = require('../handlers/user.js');

module.exports = function(router) {
  router.get('/users/:user_id', UserHandler.users.userId.get);
};

From here, the request is sent to the UserHandler, which takes care of the real logic. This route might look like this:

var User = require('../models/User.js');

var UserHandler = {
  ........
    userId: {
      get: function(req, res) {
        User.findById(userId).exec().then(function(user) {
          return res.status(200).send(user);
        }, function(err) {
          return res.status(500).send(err);
        });
      },
    },
  ........
};

module.exports = UserHandler;

It would be nice if we could unit test the paths here and make sure that a response will certainly be returned. But, there’s some gritty code to mock up.

First is the Mongoose promise returned by findById(). The promise returned by calling exec() is executed by calling then(), which takes a callback for success and a callback for failure.

The other issue comes from the request and response objects. Express packs these variables with functionality, but we just need some simple mocks. Here’s how we can solve this:

Jasmine provides beforeEach() and afterEach(), which will run before and after a given test or set of tests. By declaring our req and res at the top of the file, we can mock the functionality we want like this:

var req, res;
beforeEach(function() {
  req = {
    query: {},
    params: {},
    body: {},
  };

  res = {
    status: jasmine.createSpy().andCallFake(function(msg) {
      return this;
    }),
    send: jasmine.createSpy().andCallFake(function(msg) {
      return this;
    })
  };
});

afterEach(function() {
  expect(res.status.callCount).toEqual(1);
  expect(res.send.callCount).toEqual(1);
});

Now, we have simple req and res objects that will perform the functionality we need. We can confirm that the calls to send() and status() happen with the proper arguments on a per-test basis, which I will show in a moment.

The other issue was the Mongoose promise. We can create a mock promise that looks like this:

var userPromise = {
  exec: function() {
    return {
      then: function(cbS, cbF) { return cbS({ username: 'Matt', _id: '123' }); };
    };
  },
};

This userPromise will execute successfully. If we wanted to have the promise fail, we could do that like this:

var userPromise = {
  exec: function() {
    return {
      then: function(cbS, cbF) { return cbF('Error!!'); };
    };
  },
};

Now we finally have our mocked up variables. We can include these in any of our tests to make sure errors are handled properly. A success test might look like so:

describe('get: ', function() {
  it('successfully gets the user', function() {
    spyOn(User, 'findById').andReturn(userPromise);
    req.params = { user_id: '123' };
    UserHandler.users.userId.get(req, res);
    expect(User.findByIdPublic.callCount).toEqual(1);
    expect(res.status).toHaveBeenCalledWith(200);
    expect(res.send).toHaveBeenCalledWith({ username: 'Matt', _id: '123' });
  });
});

And that’s all there is to it. A more full-stack test that takes advantage of the Express middleware could be done with a tool like supertest, but this is a good way to unit test a single function.

If you’re interested in digging deeper into the Repcoin code, check out the Github.