More of A Blog

Some Data Analysis of Nike Night Run Tel Aviv 2011

noreply@blogger.com (habeanf) — Wed, 02 Nov 2011 21:07:00 +0000

I was playing around with google fusion tables and came across the publicized database of the nike night run tel aviv 2011 results. Playing with data is a nice way to spend an evening while my leg muscles recover from last night's run so I figured I might as well blog it.
We'll start with a visualization of the two starting groups on a timeline:
x axis - finish timey axis - place in starting group
You'll notice an area where the graph bounces between the two data sets - I think this is due to a constraint in the visualization itself requiring a single data point on the y axis for each point on the timeline / x axis. The visualization emphasizes the bulk of the runners clocking in at 50 to 60 minutes, with some late sprinters in the second group and a handful of runners that overestimated their times from the first group.

We can also see visualize fun facts about the demographics of the runners:

Sex Distribution of Runners in the first group
Sex Distribution of Runners in the second group

Sex Distribution of All Runners

Since we have the names of our runners, we can do some name analysis.
Popular male names are: גיא, שי, טל, אורי ואבי ,
While popular female names are מיכל, יעל, עדי, קרן וענת
An interesting use of this table is a view of gender-specific vs gender neutral names. Names like טל, שרון, עדי ורותם seem to be gender neutral whereas others are very gender specific. Makes you wonder if you can build a gender classifier based on just the first name? Perhaps further analysis of birth year will provide more accuracy.

Looking at age vs starting group distribution, we can see that starting at age 16 most runners sign up for the first starting group, up to around the ages 26-27 where the majority shifts to the second group. I'll leave it to the reader to find out if their finish times correlate accordingly.

However, one thing really strikes me when looking at the first graph of runner times - there appears to be a constraint on the gradient. When I got the to the finish area there were a bunch of people blocking the actual finish line.. I suspect a substantial set of runners have skewed results due to the traffic jam that ensued at the time. I was actually there so I know for a fact there was a traffic jam, but I'll try to convince readers who weren't using just the data.

First, we'll need to make a few assumptions:

The runners did not start at exactly the same time but the difference is limited to about 5 minutes. I observed that the launch lane was mostly empty after just 3-4 minutes from the start of the race.
Also, we will only run calculations within a starting group, since the first group took off a full 15 minutes before the second group.
The traffic jam occurred over a timespan of around 15 minutes.

Using these these assumptions we will use the aggregate of runners per finish time as a basis for rate of entry to the finish area. Since the finish time resolution is one second, the number of runners per finish time will be considered the rate of runners entering the finish area. The resulting table can be found here.
You'll notice I've added two fields, measuring the moving average of the previous 10 seconds. This is because the data is too noisy when looking at per-second rates. Graphing this data, we can see some evidence of the traffic jam:

Now remember, the x-axis is a 10-second moving average. So when we look at the mass of runners in group 2 between 0:52:00 and 1:17 we can see huge variations in the rate of runners crossing the finish line. Compare these rates with before and after periods, where the variation seems to be more tame. Also, notice how the variation grows as the rate itself grows, both in group 1 and group 2. If Google Docs charts would support Bollinger Bands I suspect it would be a bit more obvious.
It seems that right in the range of 1:00:03 to 1:04:09 you can really see the waves of progression that characterize traffic jams.

In conclusion, I think that for 2012 Nike Israel should build a wider, rather than longer, finish area after the finish line. The rate of people leaving the finish area was far lower than the rate entering the area, which lead to the buffer zone in the finish area overflowing and crowding the finish line. The correct solution to this problem would be a very wide finish line with plenty of room for people to dispense in every direction possible. That's it for today, see you again after next year's run!

A suggestion for Google App Engine - a state service

noreply@blogger.com (habeanf) — Fri, 08 Oct 2010 15:18:00 +0000

Background

A few months ago I met a googler at the Google I/O 2010 conference during office hours at the App Engine booth. We discussed App Engine at length, including my own development of an App Engine app.

As part of our discussion I had brought up the possibility of an ACID-compliant, fast read/write storage service (i.e in-memory database - fast [low latency] read/write relative to disk-based storage). While discussing this, a main argument he had brought up against such a service was that essentially this is an irrelevant option for a technical reason. If I remember correctly, he had stated:

If a storage service is durable (can withstand data center/system failures), it must write to two geographically distinct locations. However, if an application requests a write at one datacenter, then the latency of the two-way communication for each write to a second data center would be long enough to marginalize the gains of a memory-based database. Our "back of the envelope" calculation was that it would take at least 10-20 ms for the full round-trip of a write with it's acknowledgment to travel between data centers - even if they are performed in-memory only and are not bound by the inherent latencies of mechanical storage.

Therefore, we would be back to where we are now regarding data storage - either use memcached for non-dependable but fast storage or use the datastore for durable and dependable but comparably slower storage (even if using eventual consistency - datastore writes are noticeably slower than memcached writes, regardless of the datastore's recent performance issues).

Since our discussion back then I had thought and rethought this argument, and I would like to present an idea for a new type of storage service: a state service.

Before I describe this service I would like to get back to the previous debate. I think I had made a mistake by not giving a reason/use-case for such a service and had excluded a part of ACID that can be relaxed (specifically, Durability).

The best reason I could find for such a service is applications that have a temporary state which changes often. Putting myself in Google's AppEngine team shoes (big as they are, i'm putting myself in the position of an evangelist) - I would want any application to be written in AppEngine. The googler I talked to had pretty much said the same thing. Moreover, I would want AppEngine to be the foundation of a new class of applications, applications where the foundation itself is key to applications' features and capabilities.

An Example

A good example of such an application is a browser-based multiplayer game.

A fundamental capability of such an application is the game's state, constantly updated by players and at the same time constantly updating gamers (and likely passive viewers) of this state. Given App Engine's current array of services, it would be impossible to build such an application. At first glance, one is tempted to view this as a simple publish/subscribe scenario - players send events to a queue and both active and passive players subscribe to it to get the updates. However, a new player introduced would need more than just changes to the game - the current state would need to be sent too. To this end, this is an important difference when compared to google's pubsubhubbub or solutions like it.

Practically speaking, there are many other examples where state cannot depend on one single memcached key to store a critical part of the state, but on the other hand cannot consider using the datastore since it would be very costly and would be functionally inefficient - there's no reason to persist the state to disk for every change.

The State Service

The proposed state service, while not being ACID compliant, would be a RAIDed version of a memcached service (like an in-memory GFS, but with a smaller block size). The key feature of this service would be that a key-value pair stored in the state service would be guaranteed to have multiple in-memory copies, written to simultaneously. If any one memcached node fails (the probability of which is not negligible), no harm is done.. as is with GFS a new redundant copy would be created automatically. However, if an entire data center fails then that state is accepted to be lost and reset. In other words, I'm banking on the probability of an unexpected complete data center failure happening to be significantly less than the probability of a single computer failing.

A number of useful API features for a state service could be:

- A "timeout" API: removes a state when no changes have been made to it for longer than the timeout.

- A notification API: for changes to the state, possibly with or without the state itself. The notification could be specific, such as changed, removed, timed-out etc.

- A quiesce API: An API for an application initiated snapshot/backup of a state, either to a different data center for in-memory storage or to the datastore/persisted to disk. During this time the state is read-only.

Similar to the quiesce API, an acquiesce API - In order to meet maintenance needs of whole data centers, yet another part of the API could be a required implementation of a "transport" mechanism, which would allow data center maintainers to initiate the freeze of a state and transfer it to another data center. The API could notify the app of an immediate delay in the responsiveness in the serving of state queries while it is being transferred.

I assume Google would need a way to make sure users of app engine won't rely on the state service for anything other than a proper use of state (i.e. as persistent storage or cache). While I can't guarantee that won't happen, you can mitigate the risk of it happening using quota economics - make it an order of magnitude more expensive to store data in than the data store, but an order of magnitude less expensive to make changes in. In addition, make sure the state service is more expensive for read-only operations than the memcached service. As google probably does with the other services available, the actual prices and free quotas would be based on google's marginal cost for operating the service on a per block size basis (say, 32 K with three copies on computers at one data center with low latencies between themselves).

I think this would especially be a huge advantage to google app engine when compared to Amazon EC2 (I don't have anything against EC2, i'm just looking at it from a marketing perspective). Having a state service would be a key differentiator because the cost of building one on EC2 is quite high. While most of the GAE services are perceived to be relatively easy to implement (datastore, memcached, blobstore, image serving, static file serving, web app serving, mail and task queue), for most of the aforementioned examples there probably is a major difference between the perceived simplicity of a do-it-yourself service and the true complexity of google's implementation. However, a state service is usually not conceived in the first place - it is mimicked by implementations of in-memory storage on souped-up redundancy-laden servers. Since these solutions simply rely on the stability of a single server (redundant as it may be), they are marginally inefficient because available memory on one server cannot serve application in need on a different server - which leads to complex infrastructure software that tries to move processes around with their memory in order to fix inbalances. On EC2 these models fall apart because servers can and do fail. There are fixes (what I call architectural patches) such as multiple processes executing the same job in parallel but IMHO they are inefficient because of unnecessary redundant execution.

Conclusion and TL;DR

I propose a state service which is a hybrid memcached and datastore - data is only stored in memory, on multiple computers local to a data center. The state service is not fully ACID compliant in that a full data center outage would mean loss of data (not durable) - which is considered acceptable because full data center outages are rare. By letting go of durability, it would support highly frequent changes and would be resilient in the face of single computer failure. Financial incentives would make sure the state service is not misused.

Although I have been thinking about this idea since Google I/O 2010, notice that Google Instant is a hint that Google itself needs to store and change state efficiently. I believe that in the near future whatever infrastructure Google built to enable state for Google Instant will find itself useful in other Google products - hopefully Google App Engine will be one of them.

------------------------------------

I had contacted the aforementioned googler with an email similar to above part of this post (in fact, it served as the basis for the post). I won't name the googler, if he likes he will identify himself. As you might conclude from the background section, the googler is a member of the Google App Engine team.

The googler's response was that he thought I had redesigned Cassandra/MongoDB. However, I don't think I did. Cassandra and MongoDB are designed for durability, a feature the state service would not require:

1. MongoDB - Uses memory-mapped files so any changes in memory to the data would soon be performed on disk.

2. Cassandra - Persists changes to disk using a common mechanism found in most RDBMSs - frequent fsync()s of a change/commit log, while writes to the actual data files representing data objects are fsync()ed infrequently and are (supposedly) optimized for I/O performance.

Both methods introduce a mechanical burden which is unnecessary for a service that does not require durability, since the disks have a random seek throughput rate much smaller than that of a cpu talking only to memory.

Enthroned: Part 1 - Installation

noreply@blogger.com (habeanf) — Wed, 03 Jun 2009 18:55:00 +0000

There's a good chance that there's a difference between you (as you're reading this), and I (as I wrote this).

You are probably in one of the following positions:

- Sitting in a chair, hunched forward over an inadequately sized screen.

- Sitting in a chair, neck protruding forward. Optionally your feet might be up on a makeshift footstool.

- On a couch/bed/beanbag; laptop sitting where it's name suggests.

However, I was sitting upon a throne. A nethrone that is. So I thought I'd blog about my experience, but I'm not alone:

Step 1: Delivery

The box

Classic ninja tactics - disinformation meant to thwart evil fiends
Do not be mislead, this box contains more than your standard office chair

You can see the rest of the pictures here.

Step 2: ...

Oh hai! Nethrone can haz cheezeburger?

Connecting the main structures

As you can see from the pictures, most of the structure comes connected. The technician only had to connect two main structures and a few appendages to the seat.

A word of warning - Although it looks easy to set up, I strongly recommend paying for the technician installation service - there's just too many ways to get it wrong (more on that in a later post).

Mechanically and functionally everything works out of the box; however beware that this is not an IKEA closet. Some stuff was done crudely on the spot - for example: the mousepad wrist pad had to be glued with silicone to the circular raw metal plate that was attached to the armrest.

Step 3: Profit!

C'est magnifique!

All in all, I'm quite happy with my shiny new toy :)

To be continued...

App Engine: Google's Faster Horses

noreply@blogger.com (habeanf) — Mon, 25 May 2009 18:55:00 +0000

In case you hadn't noticed, Google unleashed App Engine to the masses.

One can prescribe a plethora of hi-tech buzzword/dashed-phrase adjectives to App Engine, for example: super-cool, cutting-edge, evolutionary, revolutionary, and the all-mighty disruptive technology. Sarcasm aside, App Engine really is a disruptive technology. I will be dedicating a number of posts to sharing my thoughts on the disruptive-ness of App Engine.

With respect to Google's future directions, there is more than meets the eye to App Engine. I'll be sharing my humble opinions on what's going on at higher levels: the economical and technological disruptions, Google's reasons for launching App Engine and it's relation to MapReduce.

In this post, I'll be talking about the data storage back end that contributes significantly to making all this disruption possible.

The Horses

It is usually the case that the workhorse of a web application is the database. One can imagine web/app servers as efficient gateways of incoming requests that are translated into action items for the database (a.k.a. SQL DML). For this (and other esoteric) reasons, it is quite simple to scale web servers linearly. All too often it is evident that the Achilles heel of web application scaling is the database. I will cover the underlying scaling issue of traditional RDBMSs in a later post.

Currently, consider the problem a DBA faces when scaling the RDBMS layer of a web application after he's maxed out the performance he can get from his current hardware.

Faster Horses

At this point, the DBA and dev team want a faster (work) horse. They want a solution that will continue to work with their existing code and architecture, only "faster". There are a few solutions that appear to be available:

1. Scale-up (i.e. more cpus, new cpus, more ram, more disks/controllers in the storage device, etc.)

2. RDBMS based solutions: Clusters of computers with shared storage (i.e. Oracle RAC)

3. Software infrastructure solutions: sharding or similar types of indirection - db proxy (i.e. MySQL Proxy),

Not so fast:

The first solution is extremely limited in range - cpus only double in speed every 18 months (Moore's law) and the marginal cost of doubling the amount of cpus on a motherboard could eclipse the cost of rewriting the web app from scratch (look up the marginal cost difference between 32, 64 and 128 cpu machines). One could say that scaling-up is a form of procrastination: "I don't want to solve this problem right now, let's get a bigger/faster computer."

The second solution delegates the problem to network and storage subsystems: Since traditional RDBMSs need redo/undo logs and serial commit numbers to support ACID requirements, these must be synchronized between the computers accessing the shared storage. This inhibits scalability because synchronization tasks will eventually choke the system by starving shared network and I/O resources. Also, the performance of I/O bound tasks is not improved, since the amount of disk read/write heads has not been increased (in fact, the performance might be degraded due to contention). Additionally, scalability costs are compounded by the combination of software and hardware costs (as opposed to software-only or hardware-only costs, as in option #1 or option #3). Worst of all, when adding a computer to the shared-cluster, one must add additional I/O channels to the shared disks (and this is quite expensive).

It appears that the whole shared-storage solution was an effort to support hot fail over servers without a doubling of the storage subsystem. Somewhere along the line someone thought to themselves "this must mean we can scale".

The third solution is interesting. The same "interesting" you might apply to a home-cooked dish gone wrong (not cooked by you, and you better like it or else). The intention is honorable, but the solution is a patch to a fundamental flaw. Sharding shifts the burden of scalability up the technology stack to the programmer, where at best a sharding configuration can be centrally managed. Sharding introduces another conscientious dimension to the dev team - shard management. Since the abstract data storage layer (usually a standard database) is managed by a library/server (i.e. hibernate, MySQL Proxy), the parameters for data storage are now a part of the dev process. For example, in dev and qa environments, custom sharding parameters must be configured for the small environments mimicking production. Worst of all, in-flight scaling becomes a cumbersome task (due to the configuration nightmare of resharding) eating up human resources.

Google's Faster Horses - BigTable

It appears that at some point in recent history, someone (or a bunch of someones) at Google sat back and started asking: "What if?".

What if we could store objects directly?

Can we change the data storage layer paradigm?

Can we spare the object-relation mapping (ORM) and literally GET/PUT objects from/to storage?

What if we dealt away with connection strings and cursors?

What if a modification to the definition of stored-object attributes won't require a DBA and down time?

Can we do all this, and still support transactional modification of data?

In short, the answer to all the questions above is: yes.

This day and age, a link is worth a thousand words. So instead of writing about Google's faster horses, I'll point you in the right direction:

The App Engine blog - Google App Engine Blog: Back to the Future for Data Storage.

Google's research paper on Bigtable.

I have mentioned an Achilles heel and fundamental flaw earlier in this post, and I will blog about it in my own words another time. For those who want a more in-depth and academic take on the issue, I suggest reading:

Prof. Mike Stonebraker et al on The End of One-Size-Fits-All for databases.

From the same group - The End of an Architectural Era.

Please note that in terms of object-oriented databases, Google did not invent the wheel. Minute differences aside, they are the first to use it on a massive scale, and the first to use it for effortless scaling of web applications.

Conclusion

In this post, I focused on the back end tool that makes App Engine (and most of Google) feasible.

In this sense, the disruption is in the public world-wide availability of this technology.

App Engine is a factory for web-based applications/services/products, now available to anyone with reasonable means. This is the modern-day disruption akin to the technology that enabled entrepreneurs to establish factories in the late 18th century. The same entrepreneurs that stood behind the industrial revolution that was eventually the driving force behind consumerism. In my very humble opinion, App Engine is the beginning of a new revolution (yet to be named). I'll be talking about this concept (and my name for it) in-depth in a later, off-subject post, which leans on the availability of technologies like App Engine.

Whats Next

In my next posts, I'll be talking about other aspects of the disruptions caused by App Engine:

- The economics behind App Engine. Barriers of entry, marginal cost of production

- Google's reasoning for App Engine

- A fundamental concept of the cloud development paradigm: I call this: code once, run copies (as many as you like)

- The revolution marked by the general availability of App Engine

- Likely directions in the future of App Engine

What's all this got to do with horses?

"If I had asked people what they wanted, they would have said: 'faster horses'."

-Henry Ford

Initiation

noreply@blogger.com (habeanf) — Sat, 02 May 2009 19:54:00 +0000

Welcome to my blog. I've been planning on blogging my musings for quite a while now but never really found the time. Recent changes in my schedule lead to an open time slot, so I thought I'd give it a go.

I will be blogging on a number of subjects, mainly focusing on my infatuation with Google products and services such as:

App Engine (Python)
Chrome (which I evangelize endlessly to friends, family, associates and customers)
Experiences with unladen sallow
General thoughts on Google

I'll also be blogging about stuff from my work as a freelance BI consultant. Specifically I'll give my humble opinion on:

Hadoop/MapReduce
Column-based storage (i.e. Vertica)
Python
Experiences with ubuntu (linux)

Cheers,

habeans