Best of all, the rewrite allowed the project to shed its past baggage and build on a more modern stack with a better perspective of the required features for a modern deployment (Drizzle is another recent example from the MySQL camp). Case in point, Tokyo Tyrant supports Lua scripting on the server, allowing us to add arbitrary user defined functions (UDF's in MySQL parlance) and to extend the database itself!

Lowering the Barrier With Lua Scripting

If you have played with Lego Mindstorms, or ever tried to script your phone or a gaming environment (WoW), chances are you've worked with Lua. Due to its extremely small footprint (~212kb for source, documentation, and examples), fast interpreter, portability and easy to understand syntax it has become the de-facto embedded scripting language for many applications. Explore the available tutorials, or pick up "Programming Lua" by the creator of the language for a more in depth look, it's a fun language!

So why is Lua scripting such an exciting feature for Tokyo Tyrant? Because it lowers the barrier for programming and extending the database by an order of magnitude! If you have ever worked with MySQL UDF functions, you'll definitely appreciate the ease and the speed of development. No need for mucking with internal API's, nothing to compile or link against, and execution is done within a stable and sandboxed environment.

Extending Tokyo Tyrant with Lua

Anytime you bootup a Tokyo Tyrant server you can tell it to load arbitrary Lua code alongside which will then be evaluated at runtime if the client requests it. From there, the developer of the extension has full access to the incoming request and the underlying Tokyo Cabinet database, allowing us to inject arbitrary functionality. To get a flavor for the workflow, take a look at some of the examples in the following slides:

tokyo-recipes.git (Lua Extensions for Tokyo Tyrant)

Downloads: 94 File Size: 0.0 KB

Because the Lua scripting interface is relatively new, the number of available extensions and documentation is not very large. For that reason, I've started the tokyo-recipes repo on GitHub, in which I've aggregated some of the available extensions, and added extra documentation and examples to help grease the wheels: TTL functionality (ala memcached), working with Sets (ala Redis), session timestamping and a wordcount map-reduce example just to name a few. Give it a try, it is an extremely powerful feature!

The best part about Webhooks is that most of us are already familiar with them: callbacks over HTTP. Pioneered by PayPal and Subversion as a way to send real-time notifications to the client, they have found their way into many dozens of products we all use every day. Need pre or post commit hooks for your SVN or Git repository? Both GitHub and SVN support HTTP callbacks. Need a payment alert from PayPal, or an alert when a wiki page is modified? There are webhooks for that too. This simple mechanism allows us to build web services that work together via a simple and ubiquitous protocol we can all understand: HTTP!

Working with Webhooks

A good way to think about webhooks is as Unix pipes for the web. While PubSub is a great application of the technology, Webhooks allow bidirectional communication, which opens up our possibilities to: publishing notifications, chaining web services to perform complex actions, or allowing external plugins to enter the workflow. All of this functionality is accomplished via simple HTTP queries (both POST and GET), which means no special libraries or servers to make it all happen. In fact, building your own Webhooks powered PubSub server takes less than a hundred lines with the help of Sinatra, as demonstrated by the Julio Capote and his watercoolr project on GitHub. To see it in action, we can use PostBin as our mock recipient:

[ilya@igvita ~]# ruby postbin.rb http://www.postbin.org/1987c4m
creating channel...
adding subscriber to channel sej7u7
{"status":"OK"}
Post message: Hello Webhooks PubSub!
{"status":"OK"}

In this scenario, our local watercoolr service acts as a PubSub server, accepting requests to create custom channels, maintaining a subscriber list, and pushing out notifications when an update arrives at the channel. Best of all, interacting with the server is as simple as writing a RESTful client:

> postbin.rb

require "rubygems"
require "rest_client"
require "json"
 
puts "creating channel..."
resp = RestClient.post "http://localhost:4567/channels", :data => ""
id = JSON.parse(resp)["id"]
 
puts "adding subscriber to channel #{id}"
resp = RestClient.post "http://localhost:4567/subscribers", :data => {:channel => id, :url => ARGV[0]}.to_json
 
loop do
  print "Post message: "
  msg = STDIN.gets.chomp
 
  resp = RestClient.post "http://localhost:4567/messages", :data => {:channel => id, :message => msg}.to_json
  puts resp
end
 

PubSubHubbub Spec: Auth, Discovery & Protocol Implementation

Brad Fitzpatrick of Livejournal fame and Brett Slatkin, both of whom are currently at Google drafted a PubSubHubbub spec for a "simple web-scale pubsub protocol" which preserves the spirit of HTTP webhooks but adds a much needed layer of basic security, discovery, and coherent protocol definition:

We offer this spec in hopes that it fills a need or at least advances the state of the discussion in the pubsub space. Polling sucks. We think a decentralized pubsub layer is a fundamental, missing layer in the Internet architecture today and its existence, more than just enabling the obvious lower latency feed readers, would enable many cool applications, most of which we can't even imagine. But we're looking forward to decentralized social networking.

The google code project also provides an AppEngine implementation with a public hub, which we can test via an asynchronous (EventMachine based) PubSubHubbub Ruby library:

> pubsub-gae.rb

require "rubygems"
require "pubsubhubbub"
 
EventMachine.run {
  # publish single URL
  pub = EventMachine::PubSubHubbub.new('http://pubsubhubbub.appspot.com/publish').publish "http://www.test.com/"
  pub.callback { puts "Successfully notified hub." }
  pub.errback  { puts "Uh oh, something broke: #{pub.response}" }
 
  # publish multiple URL's to hub
  feeds = ["http://www.test.com", "http://www.test.com/2"]
  pub = EventMachine::PubSubHubbub.new('http://pubsubhubbub.appspot.com/publish').publish feeds
 
  pub.callback { puts "Successfully notified hub." }
  pub.errback  { puts "Uh oh, something broke: #{pub.response}" }
}
 

PubSubHubbub.git (Asynchronous PubSubHubbub Ruby Client)

Downloads: 201 File Size: 0.0 KB

Webhooks & PubSubHubbub

Of course, neither Webhooks nor PubSubHubbub are the answer to every problem. Both XMPP and AMQP will continue to exist alongside, but chances are, will take on the brunt of high-velocity feeds while Webhooks can happily power the remaining 90% of the simpler use-cases. In fact, there is already a RabbitMQ PubSubHubbub hub server implemenation in the works! For further reading, flip through Jeff Lindsay's presentations on webhooks, and if you are interested in PubSubHubbub check out this presentation by Brad Fitzpatrick and Brett Slatkin.

Monitoring IO Performance with iostat

If IO performance is suspect, iostat is your best friend. Having said that, the man pages are cryptic so don't be surprised if you find yourself reading the source. To get started, identify the device in question and start a monitoring process:

# -k output rates in kB
# -x output extended stats
# -d monitoring single device
# sample stats every 5 seconds for device /dev/sdh
[ilya@igvita]> iostat -dxk /dev/sdi 5

Next, allocate yourself a couple of hours to understand the output or expect to find yourself down a wrong path in no time flat (been there, done that). iostat is a popular tool amongst the database crowd, so not surprisingly you'll find a lot of great discussions documenting the use. Depending on your application you will need to focus on different metrics, but as a gentle introduction let's take a look at await, svctime and avgque:

await - The average time (in milliseconds) for I/O requests issued to the device to be served. This includes the time spent by the requests in queue and the time spent servicing them.
svctime - The average service time (in milliseconds) for I/O requests that were issued to the device.
avgqu-sz - The average queue length of the requests that were issued to the device.

First off, await is a deceiving metric! Even though it claims to measure average time, it is better understood as an aggregate function, so don't be mislead by it: avgqu-sz * svctm / (%util/100). Ideally, await should be roughly equal to your svctime, which leads us to a corollary: your average queue size is ideally hovering around single digits. Understanding these variables alone can tell you volumes about the application generating the load.

Disk Latencies Refresher & EBS Performance

Disk access time is determined via the sum of several variables: spin-up, seek, rotational delay, and transfer time. Assuming your disk is not is not sleeping we can discount the spin-up time, which leaves us with seek (time for the disk arm to find the track: ~10ms), rotational delay (time to get the right sector under the head: depends on RPM), and the actual transfer time. Hence, in the worst case we will take ~10ms to seek, 60s/7200RPM ~= 8ms in rotational delay, plus the read time. On average, for a 7.2k RPM disk this translates into roughly ~5ms access time (~20ms in worst case) to read the first byte!

Armed with this knowledge we can now put Amazon's EBS performance in context: on average our EBS mounts show 10~30ms svctime, which all things considered is not outrageous for a SAN. This number also dips into low single digits at nights and on weekends, which points to the fact that as with any shared resource, the performance of EBS degrades during the day. Having said that, a 6x performance difference based on time of day is definitely not anything to sneeze at, so let's hope Amazon is on top of this!

Average queue size (avgqu-sz) is a popular metric in the DBA circles, but do be careful with it when running on a SAN or any multi-spindle device. Ideally, your queue size (avgqu-sz) for a single disk should be in single digits, which means that the underlying device is well matched to the IO load generated by the application. Conversely, if the queue size is artificially low, chances are your application code can benefit from some tuning: do less disk flushing, think about caching or buffering, or in other words, double check the assumption that IO is the bottleneck!

Disks, Filesystems and Facebook Case Study: Haystack

Average access time on our disks places some hard limits on the number of IOPs - at 5ms average, we get a very optimistic 200 req/s with no read time. Hence, if you're trying to store several hundred files a second, you might want to revisit the architecture or seriously think about switching to SSD's! Databases such as MySQL work around this constraint by minimizing the number of file handles, caching data, and using aggressive buffering techniques. Willing to potentially loose a little bit of data with InnoDB? Set flush_log_at_trx_commit to 2 to avoid flushing on every transaction in favor of a periodic one second flush. In similar fashion, you can tweak your MyISAM key buffers, or even place your index and data files on different drives.

Facebook team recently released the details of their Haystack photo storage system which serves as a great case study of working around the IO bottlenecks: over 15PB of photo storage, and ~360 new photos being uploaded every second as of April '09. To meet the requirements, they dropped the POSIX filesystem semantics and went for an append only structure with a separate in-memory index which stores the direct inode offsets for each photo. As a result, each photo access is translated into a single IO request - a huge win. Read through it, fascinating stuff and an illustrative example of optimizing for IO.

If you're working with Rails, the story is better, as within the past year companies such as FiveRuns and New Relic have built a number of great performance and monitoring applications. However, if you're working on the bowels of the framework itself, or attempting to optimize a codepath in any other Ruby application, you're out of luck. For that reason, one interesting project to explore is perftools.rb, an adaptation of Google's perftools library to the Ruby land by Aman Gupta.

Hidden Gems in Google's Perftools: CPU + Heap profilers

Google's perftools library, which recently reached 1.0 status is largely known for its fast TCMalloc which offers impressive drop in speed improvements over the regular malloc (memory allocation). However, also hidden inside is a set of heap and CPU performance analysis and visualizations tools that are all too often overlooked.

At the moment perftools.rb only supports the CPU profiler, but the heap profiler is next on the agenda and offers a lot of promise. To get started, simply download and install the gem (gem install perftools.rb), the installer will download Google's perftools library, patch it on the fly to enable Ruby instrumentation and install it on your system. From here, you have two options on how to perform the profiling: explicitly instrument your code, or include the perftools library on the fly.

> perftools-instrument.rb

## instrument your code
require 'perftools'
PerfTools::CpuProfiler.start("/tmp/add_numbers_profile") do
  5_000_000.times{ 1+2+3+4+5 }
end
 
## profile existing application
CPUPROFILE=/tmp/my_app_profile RUBYOPT="-r`gem which perftools | tail -1`" ruby my_app.rb

The actual profiling of your code is done via a sampling process where the interpreter is interrupted on a periodic interval, the state is frozen for a few milliseconds and a snapshot of the stack is taken. This does mean that your process has to run for long enough for the profiler to collect a few samples (be careful with short scripts). Once the process is complete you can extract a quick text summary. For example, here is sample output for a simple Sinatra application:

> sinatra-perf.rb

[ilya@igvita r]> CPUPROFILE=/tmp/sinatra RUBYOPT="-r`gem which perftools | tail -1`" ruby hello.rb
[ilya@igvita r]> ab -c 10 -n 2000 localhost:4567/
 
[ilya@igvita r]> pprof.rb --text --ignore=Gem /tmp/sinatra
Total: 502 samples
     180  35.9%  35.9%      412  82.1% EventMachine.run_machine
     150  29.9%  65.7%      150  29.9% Time#initialize
      38   7.6%  73.3%       38   7.6% garbage_collector
      24   4.8%  78.1%       24   4.8% Time#-
      17   3.4%  81.5%       17   3.4% String#split
      10   2.0%  83.5%       10   2.0% IO#write
       6   1.2%  84.7%        6   1.2% StringIO#size
 
# generate a visualization of the callstack
[ilya@igvita r]> pprof.rb --gif /tmp/sinatra > /tmp/sinatra.gif

perftools.rb (Google-perftools for Ruby code)

Downloads: 267 File Size: 0.0 KB

Visualizing Performance & Bottlenecks With pprof.rb

However, while the text analysis is definitely useful, the real gold nugget in Google's perftools library is its ability to visualize the profiling information. By converting our profiler output into GIF or PDF formats, we immediately find several interesting codepaths in our Sinatra application (click on preview): majority of the time is spent in EventMachine (as expected), about 8% of time is taken up by the GC, and 30% of time is spent in the logging code calling Time.new! Armed with that information we now know where the bottlenecks are, their associated codepaths, and we can now work on optimizing our application!

In similar fashion, Aman produced visualizations for rubygems, Merb, Rails, and EventMachine - tons of insights in each graph! Definitely a nice library to add to your debug and performance optimization toolkit!

Undoubtedly inspired by Google's work, the guys at NY Times recently released MRToolkit, a Ruby framework for setting up and running Apache Hadoop jobs with a heavy Sawzall flavor. Short of a great community contribution, and a great source tree to get familiar with, perhaps the most interesting part of the project is the great showcase of Hadoop Streaming at work - an interface worth getting familiar with.

Hadoop Streaming: Simple Map-Reduce

Writing a Map/Reduce job in Hadoop usually entails writing two Java functions: a map which splits the dataset into independent chunks, and a reduce which combines the results to perform some useful analysis. The framework takes care of the sorting, coordination and scheduling, and thus provides the underlying abstraction for distributed computing. However, although the framework is implemented in Java, Hadoop's Streaming interface is an important, and an often overlooked feature, which allows us to write Map/Reduce applications in any language that is capable of working with STDIN and STDOUT!

In fact, we can create a simple Map/Reduce word count application with nothing but standard *nix tools available on any machine: cat, and wc. Assuming your data is already loaded into an HDFS cluster, we can kick-off our job:

$HADOOP_HOME/bin/hadoop jar $HADOOP_HOME/hadoop-streaming.jar \
-input myInputDirs \
-output myOutputDir \
-mapper /bin/cat \
-reducer /bin/wc

As the example shows, our map and reduce scripts can be any executable that reads input from STDIN (line by line) and emit output to STDOUT. Have a Ruby/Python/Bash script that is capable of both? Congratulations, you can write a Map/Reduce job on Hadoop!

MRToolkit: Hadoop + Ruby = Sawzall

Map/Reduce Toolkit by NY Times engineers is a great example of a Ruby DSL on top of the Hadoop Streaming interface. Specifically aimed at simplifying their internal log processing jobs, it exposes just the necessary bits for handling the access log inputs and provides a number of predefined reduce steps: unique, counter, etc. For example, to get a list of all unique visitor IP's, the entire program consists of:

> mr-unique-ip.rb

require 'mrtoolkit'
 
class MainMap < MapBase
  def declare
    # declare log fields
    field :ip
    field :request
    field :status
 
    emit :ip_ua
    emit :ip
    emit :ua
  end
 
  def process(input, output)
    ua = input.ua.split(/\\s/)[0]
    output.ip_ua = "#{input.ip}|#{ua}"
    output.ip = input.ip
    output.ua = ua
    output
  end
end
 
class MainJob < JobBase
  def job
    mapper MainMap
    reducer UniqueCountReduce, 2
    indir "logs"
    outdir "ip-ua"
  end
end

Take a closer look at the execution logic, as that's where all the magic happens for spooling up Hadoop jobs and invoking the Ruby interpreter. This pattern can be easily adapted for any language and offers a very powerful way to leverage Hadoop instead of trying to build your own distributed processing layer.

In fact, we should think of other higher-order frameworks we can build on top of this pattern: data mining & machine learning, video & audio processing, etc., it's all fair game!

Unlike a function, which has a defined entry and exit point, a continuation can return (yield) many times over, which means that the execution of a Fiber can be arbitrarily suspended and then resumed from the same point. While somewhat subtle, this is actually a very practical feature: continuations implicitly preserve state without having the programmer to worry about it.

Fiber Performance in Ruby

Continuations in Ruby 1.8 (MRI) suffered from a number of serious performance problems, but the introduction of Fibers in Ruby 1.9 warrants that we revisit the concept. First of all, Fibers are now cheaper to create and perform better than threads due to their nature as a lightweight context. And even better, they give us the ability to do cooperative scheduling - instead of using the preemptive context switch model we're all used to with threading, we can manually schedule Fibers to pass control back and forth whenever we want to. Let's take a look at an admittedly contrived, but also a realistic scenario: two execution threads; one thread blocks for 40ms on an IO call and then takes 10ms to post-process the data; second thread needs 50ms of pure CPU time; vs same scenario implemented with Fibers and cooperative scheduling.

By default, Ruby MRI uses a fair scheduler, which means that each thread is given an equal time to run (10ms quantum) before it is suspended and the next thread is put in control. If one of your threads is inside a blocking call during those 10ms, think of it as time wasted - everyone is sleeping! By contrast, Fibers force the programmer to do explicit scheduling which can certainly add to the complexity of the program, but offer us the full flexibility of determining how our CPU resources are used and also help us avoid the need for locks in mutexes in our code!

Fibers and Cooperative IO Scheduling

Event-driven and asynchronous programming models are great candidates for application of Fibers. Ruby EventMachine allows us to asynchronously defer blocks of code to be executed when the resource (socket, file descriptor, etc) responds, which means that unlike a regular Net::HTTP call, we don't have to spin-wait indefinitely for the response. However, this model comes at a cost: it is often hard to retrofit code with asynchronous libraries because the callbacks have to be nested and the abstraction often breaks down (compare em-http-request to net/http API). Fibers solve this problem for us by allowing us to turn an asynchronous library into what looks like a synchronous API without losing the advantages of IO-scheduling of the asynchronous execution:

> fibered-http.rb

require 'eventmachine'
require 'em-http'
require 'fiber'
 
def async_fetch(url)
  f = Fiber.current
  http = EventMachine::HttpRequest.new(url).get :timeout => 10
  http.callback { f.resume(http) }
  http.errback { f.resume(http) }
 
  return Fiber.yield
end
 
EventMachine.run do
  Fiber.new{
    puts "Setting up HTTP request #1"
    data = async_fetch('http://www.google.com/')
    puts "Fetched page #1: #{data.response_header.status}"
 
    EventMachine.stop
  }.resume
end
 
# Setting up HTTP request #1
# Fetched page #1: 302
 

Running the following code shows in-order output, which means that we've simulated a synchronous API while using an asynchronous library! Now imagine running multiple fibers in parallel while repeating this pattern: you will have interleaved execution which will be scheduled via IO interrupts - no extra context switches, no locks! Joe Damato and Aman Gupta ported the functionality of Fibers to Ruby 1.8.(6|7), and also provide a great example of converting the asynchronous MySQL driver to work in synchronous fashion. Looking for more? Take a look at an implementation of Futures in Ruby and the Neverblock library.

Cooperative Scheduling: M Threads + N Fibers Model

While manual scheduling of Fibers may seem like a high cost, much of it can be abstracted into the underlying libraries and the potential benefits are enormous: cooperative scheduling is the optimal scheduling model and it does not incur the complexity inherent with threading. Having said that, there is still a place for threads! Fibers will not give you concurrency on multi-core systems and they can only be resumed in the thread that created them. Hence, if we were aiming for the optimal resource utilization: run M threads, where M corresponds to number of cores, and optimize the number of Fibers (N) which can run within each thread. This way we can utilize all the available cores, and also take advantage of the IO scheduling model!

Fibers in JRuby, Rubinius and Other Applications

Unlike the MRI Ruby VM, both JRuby and Rubinius implement "Poor Man's Fibers" where each Fiber is in fact, mapped to a native thread. This of course looses on the conceptual efficiency side when compared to MRI, but it still remains a viable and a more efficient option than the pure preemptive scheduling.

In fact, while Fibers are great tool for abstracting asynchronous execution, they are also great for lazy evaluation patterns (such as Generators) and can even be used to add state/session persistence to the HTTP protocol! Wee is a Ruby continuations based web framework, which is likely inspired by some of Paul Grahams work at Viaweb (great read). Get Ruby 1.9 on your system, give Fibers a try!

Listening to the frameworks panel at GoGaRuCo (Rails, Merb, Sinatra, Adhearsion, RAD, Shoes) the message was abundantly clear: distributed version control systems (DVCS - Git, Mercurial, Bazaar) are changing the game in the open source world. Every project attributed at least part of their success to the new "easy fork, branch and merge" model, which both lowers the entry barrier and encourages experimentation. Visualization of Ruby on Rails contributions is a great example of this trend (with a big explosion in new contributors after the switch to Git, circa April '08).

Social Coding & Distributed Version Control

It is hard to scientifically measure the impact of a switch to DVCS, since there are a number of hidden variables in the equation. For example, at least one reason why the number of contributors rises dramatically is due to the fixed attribution model: distributed version control allows to trace code and patches back to the original author instead of having the commit guardians merge changes under their own name. Let's face it, we all like to see our name and get recognition, there is nothing wrong with that, and in fact, it should be encouraged.

"Social coding, community, and switch to DVCS" is the new mantra in the open source world. But while definitely a step in the right direction, it also strikes me as a passive strategy: "put it in DVCS and they will come, community will grow". This approach hasn't worked for many companies in the past when it comes to product development, nor do I think it will work wonders in the open source world. After all, while building a community and contributing code are not mutually exclusive, they are very different tasks. Some developers can successfully juggle both roles, some can't, and majority doesn't even think about it. A source tree with one contributor is a personal itch, two is a project, and three is a tribe. We need to build tribes.

Fostering the Role of the Software Apprentice

Every field has a rockstar (or a few), it may be the original author of a successful project (Linus: Linux, Monty: MySQL, Rasmus: PHP, Matz: Ruby), or a core contributor who knows the source tree inside out. Their time is scarce, but I am always amazed how approachable and willing to help most of them are. Databases tickle your fancy? Did you know that Drizzle team (one of the most promising DB initiatives) is looking for people to mentor? In fact, I think it is more than a curious coincidence that any successful open source project today is also one that is actively engaging in apprenticeship programs. Master-Apprentice model is an incredible community builder.

Like most Ruby developers, I am a big fan of GitHub as it allows me to track and contribute to dozens of projects in a fraction of time I would have spent previously. However, I think some of the tooling is missing. Launchpad which uses bazaar DVCS and hosts projects such as Ubuntu and MySQL is already tapping into the master-apprentice community (ex. Drizzle mentor projects). But we can do better. Those roadmap and todo txt's in our source trees or a hijacked bug-tracker as a roadmap tool is pointing to one thing: they need to be social artifacts. If the author publishes his wishlist and offers his time to mentor and guide the contributor, everyone wins. Instead of guessing and bickering over the features, I can learn from the best, and together we can start a tribe. Let me vote on features, propose new ones, let's discuss them - hardly revolutionary concepts for the social web.

Mentors, please stand up!

Have a project? Let the community know what you want, put yourself out there, offer your time. Google Summer of Code is a fantastic initiative to pair students and mentors (Rails + GSoC '09 projects), but I don't think it's the money that ultimately motivates either side to contribute. Of course, this is no magic bullet, and make no mistake, as a mentor you'll have to invest just as much, if not more of your time to make a feature come true. Outside contributors will make 'newbie mistakes', and they will try your patience, but the endgame is worth it.

I want to help, I want to learn, I want to see roadmaps, I want to discuss wishlists, I want to build tribes.

However, nobody said that we should limit ourselves to HTTP, or that the proxy server has to be transparent to the user! After all, there is a great number of other potential use cases which we can use in our infrastructure: intercepting data, validating requests, benchmarking, logging, etc. In fact, a proxy server can be a powerful swiss-army knife in the right hands. Want to intercept SMTP traffic to detect spam? Maybe encrypt or decrypt a datastream on the fly? It’s all surprisingly simple with Ruby.

Proxy language: Transparent, Intercepting, Cut-through ...

Proxy servers can be placed in numerous places between the user and the destination, they can be chained and they can even alter the data at will. A transparent proxy will not modify the request or response and is commonly used for load balancing, authentication, or validation. On the other hand, an intercepting proxy is often used to modify the request or response to provide some added service to user or architect: transform data on the fly, encryption, extending a protocol, etc. Needless to say, intercepting proxies are a wonderful tool!

Ruby Proxy: Duplex Benchmarking

With minimal overhead, a proxy server can allow us to duplicate a request to multiple servers, for example to production and staging. Instead of the "record and replay headache" we can instrument ourselves with a real-time performance debugging and monitoring tool: a request gets forked but only the production response is forwarded back to the client. From there, we can analyze the response time in realtime, compare the response bodies, or even alter the data at will:

> em-proxy.rb

options = {
  :proxy => {:port => 9000, :host => "10.2.1.0"},
  :production => {:port => 9000, :host => "10.2.1.1"},
  :benchmark => {:post => 9000, :host => "10.2.1.2"}
}
 
EventMachine.run do
  EventMachine::ProxyServer.new(options).start
end

em-proxy (Ruby EventMachine Duplex Proxy)

Downloads: 445 File Size: 0.0 KB

EM-Proxy is a barebones proxy implemented with Ruby EventMachine which uses the reactor pattern for handling network connections. The performance overhead in the simplest proxy implementation is roughly 3-5% in the latency - a very low cost for the added functionality. Best of all, it is only ~300 lines of Ruby start to finish, and easily extensible. Take a look through the source, it's a powerful and wonderful hammer!

Updated slides from RailsConf 2009 and updated code for EM-Proxy on Github.

As an industry, we've come a long way in the past decade. Not so long ago, everyone rolled their own flat-file databases, nowadays the challenge is with storing and accessing terabytes of data. However, a lot of this innovation is often a process of reinventing the wheel. It may not seem so trendy, but looking back exactly a century ago is a good place to start: the manufacturing & assembly line revolution.

Henry Ford: Beyond Horizontal Scalability

Horizontal scalability is all the rage, that is, if you can achieve it. If you've managed to abstract your database layer, then just keep adding servers, hide them behind a collection of proxy servers, and you're in the money. It works, up to a point.

What's remarkable is how similar this pattern is to the way a car was manufactured in the early 1900's. A team of two or three men would work a car, start to finish, and would take anywhere from a day or two to finish the order. Need more capacity, hire more teams! Life is great.

Then Henry Ford came along and changed the game. The simple insight that the efficiency can be increased by an order of magnitude by creating a workflow, as opposed to optimizing the start-to-finish process, is actually quite remarkable. Ford invented the assembly line, we're calling it "Staged Event Driven Architecture (SEDA)". End result, ninety three seconds to manufacture a car vs one to two days, and over one million cars produced every year.

Event Driven Architecture: The steps

First and foremost, stop thinking about time to complete. Think workflow instead. There is no reason to hold up the front of the line if someone else can do the work later. By deferring the work you cut down your response time, which means snappy user experience, and it also means that you're able to take advantage of the latest industry buzzwords: elastic computing, and real-time web. Keywords to explore: AMQP, XMPP, cloud computing. Or, take a look at the slides from my MeshU presentation:

Cloud Computing: Assembly Line 2.0

It's tacky, but cloud computing is "assembly line 2.0". Even given all the industry hype, it is hard to underestimate the impact that cloud computing is going to have on our industry. All of the sudden, the cost of hiring / firing another server is zero, and the datacenter (factory) costs are swallowed by the provider - we can build and disassemble our factories in a matter of minutes! Toyota's "just in time" manufacturing is as close as it gets in the physical world, but it's only a fraction of the efficiency we can achieve in the virtual world.

Having said that, we still have a thing or two to learn from the physical world.

Sensing a nice opportunity, Kanwei Li and Austin Ziegler partnered up for the '08 Google Summer of Code (GSoC) to translate some of the most well known algorithms and data structures into Ruby, resulting in implementations of nine different containers and ten different search and sorting algorithms! And while I would encourage you to explore the entire project, a few aspects deserve special attention: first, there is the question of performance of sorting algorithms in Ruby, and second, Trie, Heap and Priority Queues are data structures worth keeping in mind.

Sorting Performance in Ruby

Turns out, the default sorting implementation in Ruby is very hard to beat. As part of the GSoC project, Kanwei Li implemented the naive (bubble sort) and all the way up to some of the best in the trade (quicksort), but the performance of all of them is well below the native implementation.

A pass through the MRI source code reveals that the the Array.sort! is implemented via quicksort. And while the benchmarks do show a four times performance hit when compared to the raw C++ version sorting an array of integers, you have to remember that an equivalent implementation in Ruby is operating on array of integer objects! In other words, native Array.sort! is a highly optimized piece of code: use it, embrace it, and don't worry about it!

Trie: Ordered Tree Data Structure

Trie is both an incredibly useful and an often overlooked data structure. More commonly known as a 'prefix tree', it can be an very compact way to store and pattern match on a collection of objects. A good example is working with a set of strings which are used as keys to a value, but the same pattern could also be used to match on any sequence of objects. For example, a Trie can be used to implement a route pattern matcher in Rails. Of course, an example is worth a thousand words:

> trie.rb

t = Containers::Trie.new
 
#       key     value
t.push("Hello", "World")
t.push("Hilly", "Billy")
t.push("Hello Bob", "Heya")
 
# regular lookup
t["Hilly"] # => "Billy"
 
# find longest matching prefix
t.longest_prefix("Hello stranger") # => "Hello"
 
# find all keys that start with H*llo (* is a wildcard)
t.wildcard("H*ll*") # => ["Hello", "Hilly"]
 

Heaps and Priority Queues

Heaps and Priority Queues are often a drop in performance replacement for a hand sorted hash. Unlike a simple associative container, heaps and priority queues build up an internal sorted tree, which allows you to have constant time access to the highest (or lowest) priority object without having to sort or manually groom the container. Best of all, the underlying Ruby implementation uses a Fibonacci heap, which means constant time lookup and inserts, and O(log n) removal:

> priority-queue.rb

pq = Containers::PriorityQueue.new
 
pq.push("Job A", 15)
pq.push("Job B", 12)
pq.push("Job C", 33)
 
pq.pop # => "Job C"
pq.pop # => "Job A"
pq.size # => 1

algorithms.git (Ruby Algorithms)

Downloads: 432 File Size: 0.0 KB

Exploring data structures & GSoC '09

The project also contains implementations of the KD-Tree, Deque, Stack, Suffix Array, and a few others, all of which are definitely worth exploring for educational value. For those who are curious, take a look at Red-Black Trees and Bloomfilters as well.

Kudos to Kanwei Li and Austin Ziegler for their great work and it is also worth highlighting that the student applications for the '09 projects are due the end of the end of next week! There is a great lineup of project ideas for Rails and some great mentors have recruited their time to help with the cause. If you're a student, or have a friend who is into Ruby and qualifies, do let them know! It is an amazing opportunity to learn from the best and make a great contribution at the same time.