Thursday, May 1, 2014

Writing a small application using Parse and Backbone - Part 3

The Story So Far

In the last post, I set up a Backbone view and a model, and connected the two. I also connected the view to a route so that we could see it render with the data. This time I want to figure out:
  1. How to query the Facebook Graph API
  2. How to persist data to the Parse backend

The Graph API

The first thing you will need to hit the Graph API is an access token. This token as an associated set of permissions which will determine which of your queries succeed. When you play with the Graph API Explorer, you will see a button saying "Get Access Token", which brings up a window asking you which permissions you are going to ask the Facebook user for:


When you do this through Parse, you will ask for permissions in the call to Parse.FacebookUtils.logIn. If the user grants you the permission you want, the access token will be in Parse.User.current()._serverData.authData.facebook.access_token.

To use this token to make a query, you call the FB.api function. Which works fine... except when the FB object doesn't exist yet. Or the Parse.User hasn't signed in. Or the access token has expired. All of which are possible, especially if the initialization flow is still in progress.

To handle this I wrote a little helper:

 facebookQuery = function(queryString, callback) {  
     var doer = function () {  
       if ((!!window.FB) && (!!Parse.applicationId) && (!!Parse.User.current())) {  
         window.FB.api(queryString, { 'access_token': Parse.User.current()._serverData.authData.facebook.access_token }, function(response) {  
           // token expired! this logic needs to be a)understood, and b)put everywhere  
           if(response.hasOwnProperty('error') && response.error.code === 190) {  
             Parse.User.logOut();  
             Invite.loginUser(doer);  
           }  
           else {  
             callback(response);   
           }  
         });  
       }  
       else {  
         // wait 0.1s  
         setTimeout(doer, 100);  
       }  
     };  
     doer();  
   };  

The 190 error code is what Facebook returns if the access token has expired. What I do is I log out and log back in, and this seems to work.

Persisting to Parse

They have actually made this pretty easy - the Parse.User object has a save method you can call. Here is some code which shows a Graph query for the logged-in user's profile information - you can see that I am asking for only the name, gender, and cover photo. Then I call the set method to assign to the fields, followed by save to send it to their servers.


 facebookQuery('/me?fields=name,cover,gender', function(response) {  
       
       // information to populate the model  
       var info = {  
         fbId : response.id,  
         realname : response.name,  
         gender : response.gender,  
         privacy_non_fb_see_only_name : Parse.User.current().get("privacy_non_fb_see_only_name"),  
         photoURL : response.cover && response.cover.source  
       };  
       // overwrite existing values, if any, and send to Parse  
       _.each(info, function(val, key) {  
         Parse.User.current().set(key, val);  
       });  
       Parse.User.current().save();  
       //   
       next(info);  
     });  


Next Time

In the next post I'm going to build the core functionality of this application, which is the creation of an invite. The code is on GitHub if you want to follow along!


Update (May 10 2014)

I'm not going to get to the next post for a while, some other tasks have come up at higher priority! I'll get to it when I get to it.


Wednesday, April 30, 2014

Writing a small application using Parse and Backbone - Part 2

Last time

In the previous post I created a Backbone application and integrated it with Parse. I also managed to log the user in using their Facebook account. This time I'm going to create a couple of pages, which will require some understanding of how Backbone's views work.

I managed to figure this out yesterday, so in this post I will just record what worked, along with a few of the problems I recall having encountered.

Routes

First I'm going to add a route called invites. Backbone's routing system is simple enough to get started with, you create a Router object and specify your URL patterns and their handlers. My first handler isn't going to do much; here is the code:

 Invite.Router = Backbone.Router.extend({  
      routes: {  
           "invites"          : "allInvites",  
      },  
      allInvites : function() {  
           console.log("allInvites");  
      }  
 });  

When the user navigates to /#invites, the handler allInvites is called. If you don't have the #, this won't work! The router only works on whatever comes after it, and it needs that starting point. This is not specific to Backbone, and if you Google "fragment identifier URI" you will learn more. I plan to do that one day myself.

The next route I added is to look at the details of a specific invite. This route takes a parameter, the invite's id.

 Invite.Router = Backbone.Router.extend({  
      routes: {  
           "invites"         : "allInvites",  
           "invite/:id"      : "viewInvite"  
      },  
      allInvites : function() {  
           console.log("allInvites");  
      },  
      viewInvite : function(inviteId) {  
           console.log("viewInvite, id=" + inviteId);  
     }  
 });  

You can see how the parameter is specified in the URL, and you will also notice that the parameter name in the URL doesn't need to match the parameter to the handling function.

Now let's make the handlers do something.

Views

To create a view in Backbone, you run Backbone.View.extend passing it a configuration object. This object could contain a function called initialize, which will be called without parameters when the view is created. In order for the view to do anything i.e. modify the HTML of a DOM element, you probably want to add a function which you can call when you're ready, and typically this is called render. But note that you have to call this function yourself, Backbone doesn't call it for you.

After five minutes I realized that setting the HTML of a DOM element is quite easily the most painful experience in the world, and why don't they have a template mechanism, integrating with things like Handlebars? If I knew more about how Handlebars worked, I could have probably figured out how to plug it in, but as it happens, Yeoman came to my rescue again. I ran yo backbone:view AllInvites and it generated this nice file for me:

 Invite.Views = Invite.Views || {};  
 (function () {  
   'use strict';  
   Invite.Views.AllInvites = Backbone.View.extend({  
     template: JST['app/scripts/templates/all_invites.ejs'],  
     tagName: 'div',  
     id: '',  
     className: '',  
     events: {},  
     initialize: function () {  
       this.listenTo(this.model, 'change', this.render);  
     },  
     render: function () {  
       this.$el.html(this.template(this.model.toJSON()));  
     }  
   });  
 })();  

Here's what I noticed:
  • The initialize function sets up the render function to list to the change event on the model
  • (There's something called a model)
  • The render function takes the model and runs it through a templating mechanism, the output of which is HTML which is set to a DOM element called $el. According to this helpful site, the el is a div which is created automatically by Backbone if we don't specify it ourselves.
  • The template seems to be in a file with an EJS extension.
So it looks like I need a model. This model object receives (generates?) a change event, and also has a JSON serialization method. So it can't be any old object, it's probably a Backbone.Model. No problem, I can look that up, and generate one using yo backbone:model once I'm ready.

But what is EJS...oh here it is. With example usage! I love the Internet. It doesn't look at pretty as Handlebars, but I don't care, it will get my work done.

 <h2>AllInvitesView</h2>  
 <ul>  
 <%   
           _.each(this.model.models, function(invite) {  
 %>  
   <li>  
     <a href="#/invite/<%= invite.get('id') %>">Detailed View</a>   
 <%=  
   invite.get('what') + ' ' + invite.get('who') + " " + invite.get('when') + " " + invite.get('where').venueName  
 %>  
   </li>  
 <%  
   });  
 %>  
 </ul>  
 <a href="#">Home</a>  

There's really only one thing to pay attention to: if you want to run JavaScript, enclose it in <% %>, but if you actually want the results to be inserted into the HTML, you have to use <%= %>.

Notice that the data is coming from this.model.models. I actually just stumbled upon it (with a little help from the Chrome developer console), and it worked . A little more exploring led me to understand that this.model refers to a collection (if the view is set up correctly), and the collection provides access to its objects via models. More on this below.

It's time to talk about the models now.

Models and Collections

Running the Yeoman generator yo backbone:model gave me a very simple file, which I haven't needed to touch yet. I ran it to create a model called Invite.Models.Invite, and left it there. But there is a separate generator for collections - yo backbone:collection - and that's what I want right now, since I'm working on a view which displays a collection.

The backbone collection definition looks like this:

 Invite.Collections = Invite.Collections || {};  
 (function () {  
   'use strict';  
   Invite.Collections.AllInvites = Backbone.Collection.extend({  
     model: Invite.Models.Invite  
   });  
 })();  

You can see that the Invite model is referenced in the configuration object, this clearly tells the collection what it's going to hold (in addition, I inferred that that Backbone collections are homogeneous, this turned out to be incorrect).

Creating objects is easy, as is creating a collection and adding these objects to it. Here is some example code which creates some dummy data for my application:

   var invDate = new Date(2014, 04, 19, 15, 0, 0, 0);  
   var venue = {  
     venueName:'Pizza Hut',   
     venueId: 1  
   };  
   appController.allInvites = new Invite.Collections.AllInvites();  
   appController.allInvites.add(new Invite.Models.Invite({ id: 1, what: 'fun', who: 'rohit', when: invDate, where: venue }));  
   appController.allInvites.add(new Invite.Models.Invite({ id: 2, what: 'fun', who: 'abrar', when: invDate, where: venue }));  
   appController.allInvites.add(new Invite.Models.Invite({ id: 3, what: 'fun', who: 'arun', when: invDate, where: venue }));  

You can see that I have created the collection inside an object called appController (which I will get to soon), and then just called the add method on the new Invite objects. There is no schema for the Invite model, and it accepts numbers, strings, dates and sub-objects with no extra work on my part! These objects can now be found in the models property of the collection, i.e appController.allInvites.models.

Now that we know how to create models and collections, and to insert models into a collection, it's time to link them to our views. I'm going to start by linking the appController.allInvites collection to the AllInvites view created earlier.

The way to associate data to a view is just to set the view's model property to the model or collection you want. So I create my view like this:

 var invitesView = new Invite.Views.AllInvites({model:Invite.appController.allInvites});  

Now when I render the view, the template code will find the individual models and iterate over them in the loop

  _.each(this.model.models, function(invite) {  
   ....  
 });  

The App Controller

I have been referring to an object called , which I haven't talked about too much yet. I'm using it as a global state holder and data store, and as I go forward I will figure out what else I want it to do. But I wanted to mention one piece of state it holds - the current view.

I lifted this from this StackOverflow answer, it performs some cleanup on any current view before switching to the new view and calling render. Then it takes the current view's el HTML and assigns it to a div I created in the index.html.

 function AppController() {  
   this.showView = function(view) {  
     if (this.currentView){  
       this.currentView.close();  
     }  
     this.currentView = view;  
     this.currentView.render();  
     $("#targetElement").html(this.currentView.el);  
   };  
 }  
 Invite.appController = new AppController();  

The way I use this is I set up the view in each route handler, and ask the appController to show it.

Next time

That's it for this post. In my next post I'm going to figure out how to use Parse's models and collections.

Tuesday, April 29, 2014

Writing a small application using Parse and Backbone - Part 1

Motivation

A few weeks ago I discovered the Parse backend-as-a-service, and immediately loved what I saw. So now I'm going to put together a small application, called Invite. I'm going to use Backbone as my front-end framework, because that's what Parse is based on.

My usual strategy is to read one good post on the subject at hand, and then just Google everything else I need as I need it. Sometimes I find a tutorial which is so well written and suited to my immediate need that I can get by with only that one, but normally I just bounce around a bunch of different ones.

The code is on Github, you will find it here.

Yeoman

To get started, I figure I should install a Yeoman generator for Backbone. And... Yeoman craps out on me. Bunch of error messages about not being able to find files in the global node_modules etc. So instead of trying to make it work, I just removed my ENTIRE node.js installation and built it from source. Only this time, I specified a value for the --prefix flag while running configure.sh, essentially telling it to install to a folder in my home directory.

No problems - it installs, and I run npm config ls to ensure that it shows the correct prefix. It doesn't, so I update the .npmrc in my home directory, which I had completely forgotten even existed.

The upside? Now I can install Yeoman globally without using sudo. Which I shall immediately do... and it works. Next I need the generator for Backbone, so I run Yeoman and asked it to find it for me. Yeoman is smart, it shows me a list of possible generators, and I choose generator-backbone since the others looked like Backbone + other stuff. And this time it works. Yeoman even confirms that it has installed the generator as a global node module. Thank you, Yeoman!

The scaffold

Now I'm running the Backbone generator, and Yeoman is doing its thing. It looks like it's installing a million node modules, mostly grunt stuff which I will not be looking at today or anytime soon. But more interestingly, it creates  the scaffolding for my Backbone application! Let's take a look at what we've got:
  • An invite/app/index.html
  • An app/scripts/main.js - this is where the application definition is. The application object has been named Invite (which Yeoman figured out from the name of the folder), and has been placed inside the global window object.
  • Other files I'm not interested in right now
I start up the application by running grunt serve, and the page which shows up looks good. It says I should run some more Yeoman commands, for models views and controllers. Ok, why not... I run

 yo backbone:router places  
 yo backbone:collection places  
 yo backbone:model places  
 yo backbone:view places  

which create a bunch of files which I will get to soon. Ok, great. Now I can get back to actually building this application.

The Application

This would be a good point for me to pin down exactly what I want to build. So here it is:
  1. Users must sign in, and sign-in must be through their Facebook account
  2. Once signed in, they can see a list of People, initially just their Facebook friends
  3. They see a list of places they could hang out at in their city. Also from Facebook
  4. They can invite their friends to meet them at a place, after specifying when this should happen. I am going to find the absolute simplest date & time control to do this with.
  5. Their friends will see the invitation when they sign in, and will be able to accept or reject. A notification goes out. 
Ok, that's enough to get started. So here's a list of pages we will need:
  1. Sign-Up / Sign-In
  2. List of People
  3. Person Details
  4. List of Places
  5. Place Details
  6. Invite
  7. See invitations, respond, see other responses and other updates

Facebook Login

What I want to do first is integrate with Facebook. I want my users to be able to authorize my app to access their profile, and then I will create a User object using their profile information. I also want the app to detect if they already have an account with me, and retrieve that User instead of creating a new one.

Naturally, I expect Parse to be able to handle this simple workflow, so I just need to figure out how they do it. I'm going to read the documentation and just note down over here what I did.

1. Integrate the Facebook JavaScript SDK. Instructions are here. I put the fb-root div into index.html right after the opening <body> tag, and I include the Parse JavaScript SDK just before scripts/main.js is included.

2. Parse says that fbAsyncInit should contain a call to their own initialization routine rather than directly to Facebook's.

3. Hmm their init function wants a channel URL...

4. StackOverflow to the rescue. Created my local channel.html

5. I placed the Facebook code along with the Parse init in main.js 

So far, so good. Now the Parse documentation wants me to call a function called Parse.FacebookUtils.logIn. But where should I call it from...hmm.

6. Ok, I'm going to put it into fbAsyncInit right after the call to Parse.FacebookUtils.init. So now fbAsyncInit contains calls to  Parse.initialize,  Parse.FacebookUtils.init  and  Parse.FacebookUtils.logIn.

7. Chrome blocks pop-ups from localhost by default. Changed the policy.

8. Now Facebook is complaining that the URL is wrong. Changed it in my Facebook app's settings page i.e. https://developers.facebook.com/apps/<my app id>/settings/

9. Refreshed my app. The browser's console logs tell me that the user is "signed up and logged in through Facebook!".


Next

In the next installment I will figure out routes, views and models, and build one of the pages for the app.

Saturday, February 1, 2014

What modern web frameworks do for you

Motivation

If you are like I was, a former CS major whose programming experience consisted of writing command-line programs using C++, the world of web applications might seem mysterious and foreign.

You know how computers work i.e. you know processor architecture, you know the basics of operating systems, compilers, networking protocols… but this web stuff is something else. And it’s hard to get started – for one because there’s all this terminology, but even if you learn the terminology it feels like there’s all this magic going on.

This blog post is for people who were in the position I was in 6 months ago. It is not a tutorial – it is meant to be read before your tutorials so that things make sense.

Web Application – Basic Flow

First let’s break down the basic structure of a web application.

  1. An application will expose multiple endpoints, which usually correspond to different parts of the application but don’t necessarily need to. An endpoint is represented by a URL, like www.myapp.com/register or www.myapp.com/logout.
  2. Clients make requests to these endpoints. These use the HTTP protocol, which I won’t get into other than to say that a request is made up of:
    1. Headers, some of which are used during transit and delivery, but you can add your own
    2. The desired endpoint
    3. An HTTP verb, like GET or POST
    4. GET requests will often have a query string attached, like                                              /getInfo?name=Rohit&age=36
    5. POST requests will usually have a body, which could be XML, JSON or something called “form-data
  3. When the application starts up, it registers its endpoints with the web server (a separate process running on that machine). Registration means providing callbacks for these endpoints.
  4. When a request comes in, the web server matches the URL against the endpoints it has registered, to see if there is a listener available. If not, it returns an error message (following what the HTTP protocol defines, hopefully). Otherwise it passes it on to the registered handler.
  5. The handler does what it needs to, and then sends an HTML response back to the web server
  6. The web server sends this response back to the client

Ok, simple enough.

Web Frameworks

So what do web frameworks do for you? Keeping in mind the steps above, the framework should provide:

  1. A simple endpoint & handler registration mechanism
  2. Automatic parsing of the request, putting the information into some simple data structures
  3. Simple ways for handlers to redirect a request (possible modified) to other endpoints

Another useful feature is an authentication framework, so you can mark certain endpoints as "protected" i.e. requiring a logged-in user. Of course to do this you need the concept of a user, so let's not get into that.

But an even more useful feature is layout templating. Think of your final page as being data placed in a layout container. The layout defines the colors, the text areas, navigation controls, where the scroll bars are, which buttons do what etc. Some of these don't change depending on the data being presented, and some do. The template will define the data-independent portions and indicate where the data is meant to go. It might be as simple as

<div id="userName" class="userNameDisp">
    {{userNameVar}}
</div>

The framework will read this HTML template, figure out that userNameVar is a variable whose value is required, and get that variable's value from the interpolation context. You can imagine this working like this:

getPage (templateName, dataContext):
    response = loadTemplateAsString (templateName)
    for every {{varName}} in the response string
        look up varName in the dataContext
        replace {{varName}} by this value in the response string
    return response

The two web frameworks which I know of which work this way are Django, written in Python, and Ruby on Rails, which is written in Ruby.

A different strategy

Nowadays everyone loves JavaScript, supposedly because browser support is so much better than it was before (I don't know how it used to be, this is just what I hear). In fact browsers are so good at running JavaScript now that applications are being written so that a large part just sits in the browser! 

One of these frameworks is called AngularJS, and I've actually written a small application using it. But I don't fully know how it works yet. Here's what I do know/ believe at this point:
  1. Request to the web application loads a whole bunch of JavaScript code. This contains all the endpoint definitions and associated handlers.
  2. As the user interacts with the application, requests will be triggered to different endpoints. These will, as far as possible, be trapped by the client-side application and NOT be translated into fresh requests to the server (since the application logic has already been loaded into the browser)
  3. Of course certain requests do need to go to the server, like requests for data. The server will now just send back JSON or XML.
  4. Layout templates will also be sent on request, though a framework might also provide a mechanism for pre-requesting and caching them locally. One would hope that a layout template is not loaded more than once though.
Now the server sends only three types of responses: the initial application code, layout templates, and raw data. Less network traffic, but more work for the browser.

I hope this helped. If you want to learn more about these JavaScript frameworks, you can Google 
  1. AngularJS for the client side (and yes there are others)
  2. Express for the server (again, there are others) 
  3. and for solutions which combine both the client and server - Meteor and Sails! 


Thursday, January 30, 2014

App Architecture and the Basics of Scale

Motivation
Recently a friend asked me about building applications. He is a graphics designer, and doesn't want to learn how to write code. He just wants to get a "big-picture" view of some of the common themes that arise when designing applications today. This blog post is aimed at people like him - interested but non-technical.

I'm going to start off by saying that what I'm about to describe does NOT describe all the different types of software being written today. In fact I know developers who never touch these issues. But my feeling is that this will be accurate for the vast majority of developers.

What Kind of Applications are We Talking About?
Here are some examples:
  1. A blogging platform
  2. An order and procurement system
  3. A recruitment platform
  4. A corporate HR system
  5. A corporate finance system
  6. A (software) bug tracking system
  7. An email and chat platform
These are all very different, but let's see what's similar for most or all of them.
  1. There are UI elements through which users can enter data. Very often these take the shape of forms.
  2. There are UI elements which show data to users. This could be:
    1. the data which they, or other users entered into the system,
    2. data from external systems (machinery, sensors, the Internet),
    3. the results of aggregation and computation, generally shown in a report. Think of "monthly sales totals", or your bank statement.
    4. Often people want to see entire collections of similar data (your MakeMyTrip search results); these are displayed in a list.
  3. There are processes which run in the background which actually do something with this data. These processes may only involve computers (generating your bank statement), or sometimes other people (processing your loan request). For something like email, one process would be the delivery of mail, which might involve looking up email addresses from nicknames; another process would be receiving mail, and running it through a spam filter.
  4. All this data has to be stored somewhere, since it is generally not just sent from user to user. Even in the case of a chat system, users generally want a history of their chats stored for later. So there needs to be a database.
More and more applications today are being developed on the browser - whether Internet-facing or inside an organization, the browser is the portal of choice. We can book hotels, apply to university, check football scores... all through a single portal.

(I am completely ignoring stand-alone applications like Photoshop, Excel, Mathematica, StarCraft... I'm not understating their importance, but they're not relevant right now).

Another medium which is gaining in popularity is the mobile app. They don't run in browsers, but many of them provide functionality which would be natural on a browser. Many of them (LinkedIn, Facebook, Twitter) actually have browser counterparts.

How They Work
The following flow is widely applicable:
  1. A request arrives at some endpoint. For web applications, an endpoint is just a URL, like http://www.my-awesome-app.com/login 
  2. The web server decides whether or not the application can handle this request. For this to happen, the application needs to have told the web server what it can handle. Anything not on that list is a fail.
  3. If the request is valid, and the endpoint exists, the web server forwards it to the appropriate handler in the application.
  4. The handler takes the request and does what it needs to. This usually involves talking to the database. The list of tasks which needs to be performed fall into a workflow. Workflows will have portions which are straightfoward - "after checking that their ZIP code is valid, check their area code" - and portions which are conditional - "if their account balance is too low then deny their ATM request. Otherwise give them their money".
  5. If the request has arrived "bearing data", it gets written to the database. Before that, there will usually be
    1. validation e.g. the user entered their birth date. People from the future are not allowed.
    2. clean-up or sanitization e.g. the user entered their name all in lowercase, so the application capitalizes the first letter
  6. If the request is for data from the database, the application will ask the database for the data. When it comes back, maybe it gets re-formatted, or cleaned-up, before being sent back to the user
  7. Many types of requests need to be authorized, so that not just anybody can get into the system and do just anything. Sometimes this is done using usernames and passwords. Sometimes it is outsourced to another service (sign in with Facebook!).
In summary (and since I'm too lazy to draw a picture):

    User --> Web Server --> Application --> Database --> Application --> Web Server --> User

Scaling Them Up

Now suppose you have more users - more customers, more employees, whatever. It might be obvious that the system will slow down, but how exactly does this happen?

Let's consider an analogy from the real world (which is actually more than an analogy, it really works just like this). Think of a fast-food restaurant, say one which makes sandwiches. They have 4 cashiers where customers place their orders (their requests) and the cashier forwards their order to the kitchen (the application, which starts the workflow). The workflow might look like this:
  1. Get some bread
  2. Put mustard on the bread
  3. Put meat and cheese on the bread
  4. Put the bread in the oven for 3 minutes
  5. Put it on a plate with some chips and signal that its ready
Then the cashier would pick it up and give it to the user. We also assume that the restaurant hasn't figured out how to let a cashier serve more than one customer at a time - which means that until the sandwich has been made, that cashier's tied up.

Now imagine that the restaurant has a lot of customers one day. What happens?

Well, the cashiers work pretty fast, so they can handle the load. And the cooks are pretty fast too. But:

  1. The oven can only handle one sandwich at a time, so there's more waiting there
Okay, so the customers wait. But if this happens repeatedly, the restaurant owners will want to do something about it. They have a few options, all of which will have an impact, but none of which will "solve" the problem permanently.
  1. Buy a bigger oven
  2. Buy more ovens
  3. Hire more cooks
(Also, until the kitchen problem is solved, there's no point in hiring more cashiers).

Here's the analogy: The oven is the database server. A bigger oven is a more powerful server - more memory, faster CPU. More ovens means more database servers. The cooks are the application servers and the cashiers are the web servers.

The cashiers are all the same, and their job is easy. The cooks are all similar, but maybe some specialize in Reubens and some in pastrami on rye. 

The database is the real work-engine, that's where the time is spent. The performance of the application will eventually just be the performance of the database.

Terminology
Let me close with some terminology.
  • Scaling up: This means making a component more powerful, generally by throwing CPU and RAM at it
  • Scaling out: Add more components of the same type at that layer (like hiring more cashiers). Scaling out is cheaper (2 Marutis are cheaper than a Mercedes), but the application needs to have been designed to work that way.
  • High Availability: A deployment that is fault-resistant due to intentional redundancy. Like having extra cooks waiting in case a working cook gets sick or injured.
  • Disaster Recovery. How does the application react when something really bad happens e.g. the data center gets hit by a hurricane, or a virus attack. DR strategies generally involve setting up an entirely separate (and geographically separated) center, ready and waiting for such scenarios. Of course if they're ready and waiting, they cost money even while there's no disaster in-progress!
  • Replication: Keep copies of the data, to protect against drive failure. Disk drives are mechanical objects, and they are the components which fail first and fail often. Data must always be stored in multiple locations
One part I left out is the entire portion of flow between the client and the web servers i.e. the network part. I left it out because one generally has no control over the network, especially if one is using the Internet. Your control starts at the web front-end, and that's where you start optimizing.

Monday, January 27, 2014

1+2+3+... = -1/12 ... huh?

Recently a video did its rounds on social media, showing how the sum of the natural numbers was $\frac{-1}{12}$. Naturally there was some skepticism from some of my friends, so I decided to write up a short note to clarify the situation.

You can find the video here, and for the more mathematically inclined, a blog post by Terry Tao.

What I'm going to show is that there is a slightly more rigorous way of interpreting the manipulations performed in the YouTube video, while pointing out the parts which are still not fully kosher.

(Could I start by saying that the sum doesn't work "because of physics"? Thank you.)

Infinite Sums
In case your response upon watching that video was "Wait a minute! That sum is clearly infinity" - you're not wrong. The typical way to define an infinite sum is as the limit of its partial sums i.e. 

$$S = a_1 + a_2 + a_3 + \cdots = \sum _{n=1} ^ \infty a_n $$
is defined to be 
$$ lim _{N \rightarrow \infty} \sum_{n=1} ^N a_n$$
and according to this definition, the sum $1+2+3+\cdots$ is certainly $\infty$.

And it gets worse - there are sums whose partial sums don't even have a limit. Here's an example which is actually from the video; the sum
$$S_1=1-1+1-1+1-1+ \cdots$$
has partial sums alternating between 1 and 0. In the video, he says that since the partial sums alternate in this way, the sum must be the "average" of these two values i.e. 1/2. 

I'm going to show you another way of seeing this. We won't actually use this sum, but it's a good way to start.

Start with the series expansion
$$\frac{1}{1-x} = \sum _{n >= 0} x^n$$
Let's first see why the fraction $\frac{1}{1-x}$ has that series expansion (you've probably seen this before):
$$(1-x) (1+x+x^2+x^3\cdots) = (1+x+x^2+x^3\cdots) - x (1+x+x^2+x^3\cdots)$$
which becomes
$$ = (1+x+x^2+x^3\cdots) - (x+x^2+x^3\cdots) $$
just by multiplying by $x$. Now all the powers of $x$ cancel, leaving only
$$ (1-x) (1+x+x^2+x^3\cdots) = 1$$
and therefore
$$(1+x+x^2+x^3\cdots) = \frac{1}{1-x}$$

Now this is fine as far as algebra goes i.e. symbolic manipulation. But what happens when we want to plug in values for $x$, say $x=500$?

Well, you can't. The problem is that the infinite sum will just stop making sense. The values of $x$ for which the sum does make sense is called its domain of convergence. For the sum $\sum x^n$, the domain of convergence is just the interval $-1<x<1$ (take my word for it - if we get into that level of detail I'll never get done here).

Okay, so 
  1. When $x$ is between -1 and 1, the value of the fraction $\frac{1}{1-x}$ matches with the limit of partial sums i.e. the infinite sum of $\sum x^n$.
  2. When $x=1$, both the fraction and the sum clearly blow up - the fraction gets a zero in the denominator and the sum just becomes $1+1+1+1+\cdots$. 
  3. But what happens at $x=-1$?
Let's compute - I'm going to plug in some values of $x$, starting at $-0.1$ and going down to $-0.9$. You can imagine $x$ moving to the left on the number line as you go down the rows of this table: 


For each row, I've listed the first few terms of the series along with their signs so that it looks like a sum (as if I've plugged values of $x$ into $1+x+x^2+\cdots$). Then in the sixth column I have the infinite sum itself (well, not quite infinite, I did the computation with $1+x+\cdots + x^{1000}$). The final column has the value of the fraction for this value of $x$.

Here's what you're supposed to notice about this table:
  1.  The sum $\sum x^n$ matches the fraction $\frac{1}{1-x}$. Of course if I had shown more digits after the decimal points they would eventually have differed, because the sum only used 1000 terms.
  2. Both of these get closer to $1/2$ as $x$ gets closer to $-1$ (the bottom rows)
  3. The second column is getting closer to -1, the third column to +1, the fourth to -1 and the fifth to +1.
I've attempted to draw a graph which to show (3). The different colors correspond to the rows of the table. Take a look at each block of colored bars.
  1. The first one is $x^0$, which is just 1, no matter what $x$ is
  2. The second one is $x^1$, so you can see the dark blue bar is for $x=-0.5$ and the red one is for $-1$
  3. The third one is for $x^2$, etc...

Every time you move from blue to red in a colored block, it's like going down the rows of the table.

Now what I'm trying to show you here is how the individual terms of the series $1+x+x^2+\cdots$ get closer to $1-1+1-1+\cdots$ as $x \rightarrow -1$. So when you look at the series, this is a way you can picture it changing as $x \rightarrow -1$.

I would have been nice if I had also indicated the sums of these terms, but my graphing skills only go so far... anyway from the table you can see that they approach $1/2$. 

(And of course if you plug $x=-1$ into the fraction $\frac{1}{1-x}$, you get $1/2$, no magic there). 

So what have you just seen? What I just showed you was that $1+x+x^2+\cdots \rightarrow 1/2$ as $x \rightarrow -1$, i.e 
$$ 1-1+1-1+1- \cdots = 1/2$$
To summarize, I'm going to state all this in a very particular way:
  1. There is a function $f(x) = \frac{1}{1-x}$,
  2. with a series expansion $1+x+x^2+x^3\cdots$
  3. and there is also a point $x=-1$ 
  4. which allows us to view the sum $1-1+1-\cdots$ as $f(-1)$.
LET ME REITERATE: The sum $1-1+1-\cdots$ has no meaning according to the definitions of infinite sums. We are specifically interpreting it as the specialization of a series at a point on the boundary of the domain of convergence.

The sum $S_2$

The next sum in the video is 
$$ S_2 = 1 - 2 + 3 - 4 + \cdots $$
which they claim equals $1/4$.

If you believe what I said in the last section, this one is easy. Just differentiate
$$ \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots $$
with respect to $x$; you get
$$ \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots$$
and plug in $x=-1$ to get
$$ \frac{1}{4} = 1 - 2 + 3 - 4 + \cdots$$

A different kind of series
We just interpreted $1 - 2 + 3 - 4 + \cdots$ as the specialization of $$1 + 2x + 3x^2 + 4x^3 + \cdots$$ at $x=-1$. Now we're going to look at it differently, as the specialization at $x=-1$ of
$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$

Here comes the non-kosher part: I'm going to ask you to believe that since
$$1 - 2 + 3 - 4 + \cdots = 1/4$$
using the series
$$1 + 2x + 3x^2 + 4x^3 + \cdots,$$
it continues to be $1/4$ even when we use this new series
$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$

Accepting this for the moment, the final series we need is
$$ g(x) = \frac{1}{1^x} + \frac{1}{2^x} + \frac{1}{3^x} + \frac{1}{4^x} \cdots$$
Very similar, but now we have a + sign on every term.

Step 1. Make a modification of $g(x)$ which only uses even numbers.

This is easy - we just divide it by $2^x$; watch:
$$\frac{g(x)}{2^x} = \frac{1}{2^x} \left ( \frac{1}{1^x} + \frac{1}{2^x} + \frac{1}{3^x} + \frac{1}{4^x} \cdots \right )$$
$$ = \frac{1}{2^x} + \frac{1}{4^x} + \frac{1}{6^x} + \cdots$$

Cool.

Step 2. Now we subtract it from $g(x)$, first once:
$$ g(x) - \frac{g(x)}{2^x} =  \frac{1}{1^x} +  \frac{1}{3^x} +  \frac{1}{5^x} + \cdots $$
and then again:
$$ g(x) - \frac{g(x)}{2^x}- \frac{g(x)}{2^x} = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} + \frac{1}{5^x}+ \cdots $$
(Looking familiar!) Let's simplify the left-hand side by grouping the $g(x)$'s
$$g(x) (1 - \frac{1}{2^x}- \frac{1}{2^x} ) = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} + \frac{1}{5^x}+ \cdots$$
$$g(x) \left (1 - \frac{2}{2^x} \right ) = \frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x}  +  \frac{1}{5^x}+ \cdots $$
If we plug $x=-1$ into the left-hand side, we get $g(-1) (1-4)$, and if we plug it into the right-hand side we get $1 - 2 + 3 - 4 + \cdots =1/4$. 
Diving by $1-4$ gives us $$g(-1) = -1/12$$

And... what is $g(-1)$? Go ahead, look at the definition, you will get
$$1+2+3+4+\cdots = -1/12$$

The Non-Kosher Step

Why am I uncomfortable with saying that 
$$\frac{1}{1^x} - \frac{1}{2^x} + \frac{1}{3^x} - \frac{1}{4^x} \cdots$$
approaches $1/4$ as $x \rightarrow -1$?

Remember that whole bit above where I drew the graphs of those series and said "well, the series approaches 1/4 as $x$ approaches -1"? I showed you a table and hopefully convinced you that what I was doing wasn't complete nonsense. (Okay, I drew the graphs for $S_1$, but it works for $S_2$ as well. Try it in Excel or something).

We can't do that here.

Not only can we not approach $x = -1$, we can't even cross $x=+1$! The series converges when $x>1$, and blows up at $x=1$, but even if you try to evaluate it at $x=0.99$ it won't work. It just blows up.

So how did I jump from $x=1$, across 0 all the way to $x=-1$?

Well, that's why this is the non-kosher step. And I don't have an explanation which doesn't involve more machinery.

But it's not "because of the physics".

Sunday, December 29, 2013

Playing with roots of unity


This post doesn't have a goal, I'm just recording some behavior I came across. Sometimes people approach me at parties and tell me how interested their children are into math; now I can point them here.

 Let $p$ be prime, and let $\zeta$ be a $p$-th root of unity. This means that $\zeta^p=1$ (but $\zeta \neq 1$). For every integer $k$, defined $\epsilon_k$ to be $\zeta^k + \zeta^{-k}$.

 Note that $\epsilon_0 = 2$, and $\epsilon_k = \epsilon _{-k}$. Let's see how these multiply:
$$ \begin{align} \epsilon_k \epsilon_l &= (\zeta^k + \zeta^{-k})(\zeta^l + \zeta^{-l}) \\ &= (\zeta ^ {k+l} + \zeta ^ {k-l} + \zeta ^ {-k+l} + \zeta ^ {-k-l}) \\ &= \epsilon_{k+l} + \epsilon _ {k-l} \end{align} $$
Now I will show that all the $\epsilon_k$'s can actually be expressed as polynomials in $\epsilon_1$. First let's expand powers of $\epsilon_1$ using the binomial expansion: $$ \begin{align} \epsilon_1^n &= (\zeta + \zeta^{-1})^n \\ &= \sum_{l=0}^n \binom{n}{l} \zeta^l \zeta^{-(n-l)} \\ &= \sum_{l=0}^n \binom{n}{l} \zeta^{2l-n} \end{align} $$

Let's add the terms in pairs, starting with the first and last: $$ \binom{n}{0} \zeta^{-n} + \binom {n}{n} \zeta^n. $$ This is just $\epsilon_n$.

Now add the second and second-to-last terms: $$ \begin{align} \binom{n}{1} \zeta^{2-n} &+ \binom {n}{n-1} \zeta^{2(n-1)-n} \\ \binom{n}{1} \zeta^{2-n} &+ \binom {n}{n-1} \zeta^{n-2} \end{align} $$ which is $n \epsilon_{n-2}$.

In this way, every term pairs up with another term, giving an integer times an $\epsilon_k$ (remember that binomial coefficients are always integers!). When $n$ is even, there is also the middle term $\binom{2l}{l}$, coming from $l=n/2$. This term is actually even making it an integral multiple of $\epsilon_0$.

To summarize: every $\epsilon_1 ^n$ is an integral sum of $\epsilon_k$'s for $k$ <= $n$. Even better, it is $\epsilon_n$ + an integral sum of $\epsilon_k$'s for $k$ < $n$! Which means we can turn it around to say that $\epsilon_n$ is $\epsilon_1^n$ minus an integral sum of $\epsilon_k$'s for $k$ < $n$.

Why is this good? Because continuing in this way, we can replace each $\epsilon_k$ with an $\epsilon_1^k$ plus/minus some other stuff, which we can then replace in the next step. And each time our coefficients stay integers.

So we get that $\epsilon_n$ is an integral polynomial in $\epsilon_1$. Here are the first few for $n$ <= $4$, I'm just going to write $\epsilon$ for $\epsilon_1$ now: $$ \begin{align} \epsilon_1 &= \epsilon \\ \epsilon_2 &= \epsilon^2 - 2 \\ \epsilon_3 &= \epsilon^3 - 3 \epsilon \\ \epsilon_4 &= \epsilon^4 - 4 \epsilon^2 + 2 \end{align} $$

As I find time I will study these polynomials and record my results here. Feel free to make contributions in the comments!