Perspectives - Software

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

High Availability for Cloud Computing Database Systems

James Hamilton — Sun, 27 Nov 2011 20:50:18 GMT

While at Microsoft I hosted a weekly talk series called the Enterprise Computing Series (ECS) where I mostly scheduled technical talks on server and high-scale service topics. I said “mostly” because the series occasionally roamed as far afield as having an ex-member of the Ferrari Formula 1 team present. Client-side topics are also occasionally on the list either because I particularly liked the work or technology behind it or thought it was a broadly relevant topic.

The Enterprise Computing Series has an interesting history. It was started by Jim Gray at Tandem. Pat Helland picked up the mantle from Jim and ran it for years before Pat moved to Andy Heller’s Hal Computer Systems. He continued the ECS at HAL and then brought it with him when he joined Microsoft where he continued to run it for years. Pat eventually passed it to me and I hosted the ECS series for 8 or 9 years myself before moving to Amazon Web Services. Ironically when I arrived at Amazon, I found that Pat Helland had again created a series in the same vein as the ECS called the Principals of Amazon (PoA) series.

The PoA series is excellent but it doesn’t include external speakers and is hosted on a fixed day of the week so I occasionally come across a talk that I would like to host at Amazon that doesn’t fit the PoA. For those occasions, the Enterprise Computing Series lives on!

In this ECS talk Ashraf Aboulnaga of the University of Waterloo presented High Availability for Database Systems in Cloud Computing Environments. Ashraf presented two topics, 1) RemusDB: Database high availability using virtualization, and 2) DBECS: Database high availability and availability using eventually consistent cloud storage. The first topic was based upon the VLDB 2011 Best Paper Award “RemusDB: Transparent HighAvailability for Database Systems” by Umar Farooq Minha, Shriram Rajagopalan, Brendan Cully, Ashraf Aboulnaga, Ken Salem, and Andrew Warfield. The second topic is work that is not yet published nor as fully developed.

Focusing on the first paper, they built an active/standby database system using Remus. Remus implements transparent high availability for Xen VMs. It does this by reflecting all writes to memory in the active virtual machine to the non-active, backup VM. Remus keeps the backup VM ready to take over with exactly the same memory state as the primary server. On failover, it can take over with the same memory contents including an already warm cache.

Remus is a simple and easy to understand approach to getting very fast takeover from a primary VM. The challenge is that memory write latencies are a fraction of network latencies so any solution that turns memory write latencies into network write latencies simply will not perform adequately for most workloads. Remus tackles this problem using the expected solution: batching many requests in a single network transfer. By default, every 25msec Remus suspends the primary VM, copies all changed pages to a Dom0 (hypervisor) buffer and the allows the VM to continue. The Dom0 buffer is used to minimized the length of time that the guest VM needs to be suspended but comes at the expense of requiring sufficient Dom0 memory for the largest group of changed pages in 25msec.

Once the guest machine changed pages are copied to Dom0, the primary VM is released from suspend state and the changes just copied to dom0 are then transferred to the secondary system and applied to the ready to run backup VM.

The downsides to the Remus approach are 1) a potentially large dom0 buffer is required and 2) up to 25msec of forward progress can be lost on failover, 3) the checkpoint work consumes considerable resources including time. The time to copy the changed pages may be acceptable but the other overheads are sufficiently high that it is very difficult to host demanding workloads like database workloads on Remus.

The authors tackle this problem but noting that Remus actually does more than is needed for database workloads. Or, worded differently, a Remus optimized for database workloads can dramatically reduce the implementation overhead. They introduced the following optimizations:

· Asynchronous checkpoint compression: Maintain an LRU buffer of recent pages and only ship a delta of these pages. This optimization is based upon the assumption that DB systems modify some pages frequently and typically only change a small part of these pages between checkpoints.

· Disk read tracking: don’t mark pages read from disk as dirty since they are already available to the backup server via an I/O

· Memory deprotection: allows DB to declare regions of memory that don’t need to be replicated. This turned out not to be as powerful an optimization as the others and had the further downside of requiring database engine changes

· Network optimization/Commit protection: Remus buffers every outgoing network packet to ensure clients never see the results of unsafe execution but this increases latency by not allowing any response back to the client until the next Remus checkpoint. Because DBs can fail and transactions can be aborted, they DB optimization is to send all packets back to client in real time except for commit, abort, or other database transaction state changing operations. On failover, any client in an unprotected network state (changes have been sent since the last checkpoint) has the transaction failed. A correct client will re-run the transaction and proceed without issue.

What was achieved is Remus, fast-failover protection for database workloads and far lower replication overhead. The authors used the database transaction benchmark TPC-C to show that Remus with DB optimizations has all the protection of Remus but with roughly 1/10^th the overhead.

Slides: http://mvdirona.com/jrh/TalksAndPapers/AshrafAboulnaga20111114.pdf

VLDB Paper: http://www.cs.uwaterloo.ca/~ashraf/pubs/pvldb11remusdb.pdf

I'm not 100% convinced Remus is the best solution to the database high availability problem but I like the solution, learned from the proposed optimizations, and enjoyed the talk. Thanks to Pradeep Madhavarapu, who leads part of the Amazon database kernel engineering team (and is hiring :-)), for organizing this talk and to Ashraf Aboulnaga for doing it.

--jrh

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Software Define Networking Comes of Age

James Hamilton — Sun, 23 Oct 2011 15:57:07 GMT

From the Last Bastion of Mainframe Computing Perspectives post:

The networking equipment world looks just like mainframe computing ecosystem did 40 years ago. A small number of players produce vertically integrated solutions where the ASICs (the central processing unit responsible for high speed data packet switching), the hardware design, the hardware manufacture, and the entire software stack are stack are single sourced and vertically integrated. Just as you couldn’t run IBM MVS on a Burrows computer, you can’t run Cisco IOS on Juniper equipment. When networking gear is purchased, it’s packaged as a single sourced, vertically integrated stack. In contrast, in the commodity server world, starting at the most basic component, CPUs are multi-sourced. We can get CPUs from AMD and Intel. Compatible servers built from either Intel or AMD CPUs are available from HP, Dell, IBM, SGI, ZT Systems, Silicon Mechanics, and many others. Any of these servers can support both proprietary and open source operating systems. The commodity server world is open and multi-sourced at every layer in the stack.

Last week the Open Network Summit was hosted at Stanford University. This conference focused on Software Defined Networks in general and Openflow specifically. Software defined networking separates out the router control plane responsible for what is in the routing table from the data plane that makes network packet routing decisions on the basis of what is actually in the routing table. Historically, both operations have been implemented monolithically in each router. SDN, separates these functions allowing networking equipment to compete in how efficiently they route packets on the basis of instructions from a separate SDN control plane.

In the words of OpenFlow founder Nick Mckeown, Software Defined Networks (SDN), will: 1) empower network owners/operators, 2) increase the pace of network innovation, 3) diversify the supply chain, and 4) build a robust foundation for future networking innovation.

This conference was a bit of a coming of age for software defined networking for a couple of reasons. First, an excellent measure of relevance is who showed up to speak at the conference. From academia, attendees included Scott Shenker (Berkeley), Nick McKeown (Stanford), and Jennifer Rexford (Princeton). From industry most major networking companies were represented by senior attendees including Dave Ward (Juniper), Dave Meyer (Cisco), Ken Duda (Arista), Mallik Tatipamula (Ericsson), Geng Lin (Dell), Samrat Ganguly (NEC), and Charles Clark (HP). And some of the speakers from major networking user companies included: Stephen Stuart (Google), Albert Greenberg (Microsoft), Stuart Elby (Verizon), Rainer Weidmann (Deutsche Telekom), and Igor Gashinsky (Yahoo!). The full speaker list is up at: http://opennetsummit.org/speakers.html.

The second data point in support of SDN really coming of age was Dave Meyer, Cisco Distinguished Engineer, saying during his talk that Cisco was “doing Openflow”. I’ve always joked that Cisco would rather go bankrupt than support Openflow so this one definitely caught my interest. Since I wasn’t in attendance myself during Dave’s talk I checked in with him personally. He corrected that it wasn’t a product announcement. They have Openflow running on Cisco gear but “no product plans have been announced at this time”. Still exciting progress and hat’s off for Cisco for taking the first step. Good to see.

If you want a good summary of what is Software Defined Networking, perhaps the best description were the slides that Nick presented at the conference: http://mvdirona.com/jrh/TalksAndPapers/NickMckeown_ON%20Summit%20NickM%2010%202011.pdf.

If you are interested in what Cisco’s Dave Meyer presented at the summit, I’ve posted his slides here: http://mvdirona.com/jrh/TalksAndPapers/DavidMeyer_openflow_and_sdn_for_enterprises.pdf.

Hortonworks Taking Hadoop to Next Level

James Hamilton — Wed, 17 Aug 2011 00:49:00 GMT

I got a chance to chat with Eric Baldeschwieler while he was visiting Seattle a couple of weeks back and catch up on what’s happening in the Hadoop world at Yahoo and beyond. Eric recently started Hortonworks whose tag line is “architecting the future of big data.” I’ve known Eric for years when he led the Hadoop team at Yahoo! most recently as VP of Hadoop Engineering. It was Eric’s team at Yahoo that contributed much of the code in Hadoop, Pig, and ZooKeeper.

Many of that same group form the core of Hortonworks whose mission is revolutionize and commoditize the storage and processing of big data via open source. Hortonworks continues to supply Hadoop engineering to Yahoo! And Yahoo! Is a key investor in Hortonworks along with Benchmark Capital. Hortonworks intends to continue to leverage the large Yahoo! development, test, and operations team. Yahoo! has over 1,000 Hadoop users and are running Hadoop over many clusters the largest of which was 4,000 nodes back in 2010. Hortonworks will be providing level 3 support for Yahoo! Engineering.

From Eric slides at the 2011 Hadoop summit, Hortonworks objectives:

• Make Apache Hadoop projects easier to install, manage & use

− Regular sustaining releases

− Compiled code for each project (e.g. RPMs)

− Testing at scale

• Make Apache Hadoop more robust

− Performance gains

− High availability

− Administration & monitoring

• Make Apache Hadoop easier to integrate & extend

− Open APIs for extension & experimentation

Hortonworks Technology Roadmap:

· Phase 1: Making Hadoop Accessible (2011)

o Release the most stable Hadoop version ever

o Release directly usable code via Apache (RPMs, debs,…)

o Frequent sustaining releases off of the stable branches

· Phase 2: Next Generation Apache Hadoop (2012)

o Address key product gaps (Hbase support, HA, Management, …)

o Enable community and partner innovation via modular architecture & open APIs

o Work with community to define integrated stack

Next generation Apache Hadoop:

· Core

o HDFS Federation

o Next Gen MapReduce

o New Write Pipeline (HBase support)

o HA (no SPOF) and Wire compatibility

· Data - HCatalog 0.3

o Pig, Hive, MapReduce and Streaming as clients

o HDFS and HBase as storage systems

o Performance and storage improvements

· Management & Ease of use

o All components fully tested and deployable as a stack

o Stack installation and centralized config management

o REST and GUI for user tasks

Eric’s presentation from Hadoop Summit 2011 where he gave the keynote: Hortonworks: Architecting the Future of Big Data

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

SolidFire: Cloud Operators Becomes a Market

James Hamilton — Mon, 01 Aug 2011 08:49:03 GMT

It’s a clear sign that the Cloud Computing market is growing fast and the number of cloud providers is expanding quickly when startups begin to target cloud providers as their primary market. It’s not unusual for enterprise software companies to target cloud providers as well as their conventional enterprise customers but I’m now starting to see startups building products aimed exclusively at cloud providers. Years ago when there were only a handful of cloud services, targeting this market made no sense. There just weren’t enough buyers to make it an interesting market. And, many of the larger cloud providers are heavily biased to internal development further reducing the addressable market size.

A sign of the maturing of the cloud computing market is there now many companies interested in offering a cloud computing platform not all of which have substantial systems software teams. There is now a much larger number of companies to sell to and many are eager to purchase off the shelf products. Cloud providers have actually become a viable market to target in that there are many providers of all sizes and the overall market continues to expand faster than any I have seen any I’ve seen over the last 25 years.

An excellent example of this new trend of startups aiming to sell to the Cloud Computing market is SolidFire which targets the high performance block storage market with what can be loosely described as a distributed Storage Area Network. Enterprise SANs are typically expensive, single-box, proprietary hardware. Enterprise SANs are mostly uninteresting to cloud providers due to high cost and the hard scaling limits that come from scale-up solutions. SolidFire implements a virtual SAN over a cluster of up to 100 nodes. Each node is a commodity 1RU, 10 drive storage server. They are focused on the most demanding random IOPS workloads such as database and all 10 drives in the SolidFire node are Solid State Storage devices. The nodes are interconnected by up 2x 1GigE and 2x10GigE networking ports.

In aggregate, each node can deliver a booming 50,000 IOPS and the largest supported cluster with 100 nodes can support 5m IOPS in aggregate. The 100 node cluster scaling limit may sound like a hard service scaling limit but multiple storage clusters can be used to scale to any level. Needing multiple clusters has the disadvantage of possibly fragmenting the storage but the advantage of dividing the fleet up into sub-clusters with rigid fault containment between them limiting the negative impact of software problems. Reducing the “blast radius” of a failure makes moderate sized sub-clusters a very good design point.

Offering distributed storage solution isn’t that rare – there are many out there. What caught my interest at SolidFire was 1) their exclusive use of SSDs, and 2) an unusually nice quality of service (QoS) approach. Going exclusively with SSD makes sense for block storage systems aimed exclusively at high random IOPS workload but they are not a great solution for storage bound workloads. The storage for these workloads is normally more cost-effectively hosted on hard disk drives. For more detail on where SSDs are win an where they are not:

· When SSDs Make Sense in Server Applications

· When SSDs Don’t Make Sense in Server Applications

· When SSDs make sense in Client Applications (just about always)

The usual solution to this approach is do both but SolidFire wanted a single SSD optimized solution that would be cost effective across all workloads. For many cloud providers, especially the smaller ones, a single versatile solution has significant appeal.

The SolidFire approach is pretty cool. They exploit the fact that SSDs have abundant IOPS but are capacity constrained and trade off IOPS to get capacity. Dave Wright the SolidFire CEO describes the design goal as SSD performance at a spinning media price point. The key tricks employed:

· Multi-Layer Cell Flash: They use MLC Flash Memory storage since it is far cheaper than Single Level Cell, the slightly lower IOPS rate supported by MLC is still more than all but a handful of workloads require and they can solve the accelerated wear issues with MLC in the software layers above

· Compression: Aggregate workload dependent gains estimated to be 30 to 70%

· Data Deduplication: Aggregate workload dependent gains estimated to be 30 to 70%

· Thin Provisioning: Only allocate blocks to a logical volume as they are actually written to. Many logical volumes never get close to the actual allocated size.

· Performance Virtualization: Spread all volumes over many servers. Spreading the workload at a sub-volume level allows more control of meeting the individual volume performance SLA with good utilization and without negatively impacting other users

The combination of the capacity gains of thin provisioning, duplication, and compression bring the dollars per GB of the SolidFire solution very near to some hard disk based solutions at nearly 10x the IOPS performance.

The QoS solution is elegant in that they have three settings that allow multiple classes of storage to be sold. Each logical volume has 2 QoS settings: 1) Bandwidth, and 2) IOPS. Each setting has a min, max, and burst capacity setting. The min setting sets a hard floor where capacity is reserved to ensure this resource is always available. The burst is the hard ceiling that prevents a single user for consuming excess resource. The max is the essentially the target. If you run below the max you build up credits that allow a certain time over the max. The Burst limits the potential negative impact of excursions above max on other users.

This system can support workloads that need dead reliable, never changing I/O requirements. It can also support dead reliable average case with rare excursions above (e.g. during a database checkpoint). Its also easy to support workloads that soak up resources left over after satisfying the most demanding workloads without impacting other users. Overall, a nice simple and very flexible solution to a very difficult problem.

--jrh

James Hamilton

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

SIGMOD 2011 in Athens

James Hamilton — Thu, 23 Jun 2011 23:21:11 GMT

Earlier this week, I was in Athens Greece attending annual conference of the ACM Machinery Special Interest Group on Management of Data. SIGMOD is one of the top two database events held each year attracting academic researchers and leading practitioners from industry.

I kicked off the conference with the Plenary keynote. In this talk I started with a short retrospection on the industry over the last 20 years. In my early days as a database developer, things were moving incredibly quickly. Customers were loving our products, the industry was growing fast and yet the products really weren’t all that good. You know you are working on important technology when customers are buying like crazy and the products aren’t anywhere close to where they should be.

In my first release as lead architect on DB2 20 years ago, we completely rewrote the DB2 database engine process model moving from a process-per-connected-user model to a single process where each connection only consumes a single thread supporting many more concurrent connections. It was a fairly fundamental architectural change completed in a single release. And in that same release, we improved TPC-A performance a booming factor of 10 and then did 4x more in the next release. It was a fun time and things were moving quickly.

From the mid-90s through to around 2005, the database world went through what I refer to as the dark ages. DBMS code bases had grown to the point where the smallest was more than 4 million lines of code, the commercial system engineering teams would no longer fit in a single building, and the number of database companies shrunk throughout the entire period down to only 3 major players. The pace of innovation was glacial and much of the research during the period was, in the words of Bruce Lindsay, “polishing the round ball”. The problem was that the products were actually passably good, customers didn’t have a lot of alternatives, and nothing slows innovation like large teams with huge code bases.

In the last 5 years, the database world has become exciting again. I’m seeing more opportunity in the database world now than any other time in the last 20 years. It’s now easy to get venture funding to do database products and the number of and diversity of viable products is exploding. My talk focused on what changed, why it happened, and some of the technical backdrop influencing.

A background thesis of the talk is that cloud computing solves two of the primary reasons why customers used to be stuck standardizing on a single database engine even though some of their workloads may have run poorly. The first is cost. Cloud computing reduces costs dramatically (some of the cloud economics argument: http://perspectives.mvdirona.com/2009/04/21/McKinseySpeculatesThatCloudComputingMayBeMoreExpensiveThanInternalIT.aspx) and charges by usage rather than via annual enterprise license. One of the favorite lock-ins of the enterprise software world is the enterprise license. Once you’ve signed one, you are completely owned and it’s hard to afford to run another product. My fundamental rule of enterprise software is that any company that can afford to give you 50% to 80% reduction from “list price” is pretty clearly not a low margin operator. That is the way much of the enterprise computing world continues to work: start with a crazy price, negotiate down to a ½ crazy price, and then feel like a hero while you contribute to incredibly high profit margins.

Cloud computing charges by the use in small increments and any of the major database or open source offerings can be used at low cost. That is certainly a relevant reason but the really significant factor is the offloading of administrative complexity to the cloud provider. One of the primary reasons to standardize on a single database is that each is so complex to administer, that it’s hard to have sufficient skill on staff to manage more than one. Cloud offerings like AWS Relational Database Service transfer much of the administrative work to the cloud provider making it easy to chose the database that best fits the application and to have many specialized engines in use across a given company.

As costs fall, more workloads become practical and existing workloads get larger. For example, If analyzing three months of customer usage data has value to the business and it becomes affordable to analyze two years instead, customers correctly want to do it. The plunging cost of computing is fueling database size growth at a super-Moore pace requiring either partitioned (sharded) or parallel DB engines.

Customers now have larger and more complex data problems, they need the products always online, and they are now willing to use a wide variety of specialized solutions if needed. Data intensive workloads are growing quickly and never have there been so many opportunities and so many unsolved or incompletely solved problems. It’s a great time to be working on database systems.

· The slides from the talk: http://mvdirona.com/jrh/TalksAndPapers/JamesHamilton_Sigmod2011Keynote.pdf

· Proceedings extended abstract: http://www.sigmod2011.org/keynote_1.shtml

· Video of talk: https://services.choruscall.eu/links/sigmod1106.html# (select June 14^th to get to the video)

The talk video is available but, unfortunately, only to ACM digital library subscribers (thanks to Simon Leinen for pointing out the availability of the video link above).

--jrh

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Guido van Rossum: 21 Years of Python

James Hamilton — Mon, 23 May 2011 17:42:12 GMT

Guido van Rossum was at Amazon a week back doing a talk. Guido presented 21 Years of Python: From Pet Project to Programming Language of the Year.

The slides are linked below and my rough notes follow:

· Significant Python influencers:

o Algol 60, Pascal, C

o ABC

o Modula0-2+ and 3

o Lisp and Icon

· ABC was the strongest language influencer of this set

· ABC design goals:

o Professionals but not professional programmers (lab personal, scientists, etc.)

o Easy to teach, easy to learn, easy to use

· Parts of ABC most liked by Guido:

o Design iterations based on user testing

§ E.g. colon before indented blocks

o Simple design: IF, WHILE, FOR, …

o Indentation for grouping (Knuth, occam)

o Tuples, lists, dictionaries (though changed)

o Immutable data types

o No limits

o The >>> prompt

· Parts of ABC that most needed improvement:

o Monolithic design – not extensible

§ E.g. no graphics, not easily added

o Invented non-standard terminology

§ E.g. “how-to” instead of “procedure”

o ALL'CAPS keywords

o No integration with rest of system

§ No file-based I/O (persistent variables instead)

· The beginnings of Python:

o Amoeba project at CWI

§ Writing apps in C and sh and wanting something in between

· Python design philosophy:

o Borrow ideas whenever it makes sense

o As simple as possible, no simpler (Einstein)

o Do one thing well (UNIX)

o Don’t fret about performance (fix it later)

o Go with the flow (don’t fight environment)

o Perfection is the enemy of the good

o Cutting corners is okay (get back to it later)

· User Centric Design Philosophy:

o Avoid platform ties, but not religiously

o Don’t bother the user with details

o Discourage but allow coding to the platform

o Offer multiple levels of extensibility

o Errors should not be fatal, if possible

o Errors should never pass silently

o Don’t blame the user for bugs in Python

· Core language stabilized quickly in the 1990 to 1991 timeframe

· Early days of active Python community:

o 1990 – internal at CWI

§ More internal use than ABC ever had

§ Internal contributors

o 1991 – first release; python-list@cwi.nl

o 1994 – USENET group comp.lang.python

o 1994 – first workshop (NIST)

o 1995-1999 – from workshops to conferences

o 1995 – Python Software Association

o 1997 – www.python.org goes online

o 1999 – Python Consortium

§ Modeled after X Consortium

o 2001 – Python Software Foundation

§ Modeled after Apache Software Foundation

· Present day Python community:

o PSF runs largest annual Python conference

§ PyCon Atlanta in 2011: 1500 attendees

§ 2012-2013: Toronto; 2014-2015: Bay area

§ Also sponsors regional PyCons world-wide

o EuroPython since 2002

o Many local events, user groups

o python.org

o docs.python.org, mail.python.org, bugs.python.org, hg.python.org,
planet.python.org, wiki.python.org

o Stackoverflow etc.

· Python 2 vs Python 3

o Fixing deep bugs intrinsic in the design

o Avoid two extremes:

§ perpetual backwards compatibility (C++)

§ rewrite from scratch (Perl 6)

o Our approach:

§ evolve the implementation gradually

§ some backwards incompatibilities

§ separate tools to help users cope

Thanks to Guido for doing the well received Python presentation.

Guido’s slides and blog URLS:

· Slides: http://mvdirona.com/jrh/TalksAndPapers/GuidoVanRossum_21_years_of_python.pdf

· Blog: http://python-history.blogspot.com

--jrh

James Hamilton

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Challenges and Trade-offs in Building a Web-scale Real-time Analytics System

James Hamilton — Fri, 11 Feb 2011 13:41:36 GMT

Ben Black always has interesting things on the go. He’s now down in San Francisco working on his startup Fastip which he describes as “an incredible platform for operating, exploring, and optimizing data networks.” A couple of days ago Deepak Singh sent me to a recent presentation of Ben’s I found interesting: Challenges and Trade-offs in Building a Web-scale Real-time Analytics System.

The problem described in this talk was “Collect, index, and query trillions of high dimensionality

records with seconds of latency for ingestion and response.” What Ben is doing is collecting per flow networking data with tcp/ip 11-tuples (src_mac, dst_mac, src_IP, dest_IP, …) as the dimension data and, as metrics, he is tracking start usecs, end usecs, packets, octets, and UID. This data is interesting for two reasons: 1) networks are huge, massively shared resources and most companies haven’t really a clue on the details of what traffic is clogging it and have only weak tools to understand what traffic is flowing – the data sets are so huge, the only hope is to sample it with solutions like Cisco's NetFlow. The second reason I find this data interesting is closely related: 2) it is simply vast and I love big data problems. Even on small networks, this form of flow tracking produces a monstrous data set very quickly. So, it’s an interesting problem in that it’s both hard and very useful to solve.

Ben presented 3 possible solutions and why they don’t work before offering a solution. The failed approaches that couldn’t cope with high dimensionality and the sheer volume of the dataset:

1. HBase: Insert into HBase then retrieve all records in a time range and filter, aggregate, and sort

2. Cassandra: Insert all records into Cassandra partitioned over a large cluster with each dimension indexed independently. Select qualifying records on each dimension, aggregate, and sort.

3. Statistical Cassandra: Run a statistical sample over the data stored in Cassandra in the previous attempt.

The end solution proposed by the presenter is to treat it as an Online Analytic Processing (OLAP) problem. He describes OLAP as “A business intelligence (BI) approach to swiftly answer multi-dimensional analytics queries by structuring the data specifically eliminate expensive processing at query time, even at a cost of enormous storage consumption.” OLAP is essentially a mechanism to support fast query over high-dimensional data by pre-computing all interesting aggregations and storing the pre-computed results in a highly compressed form that is often kept memory resident. However, in this case, the data set is far too large to be practical for an in-memory approach.

Ben draws from two papers to implement an OLAP based solution at this scale:

· High-Dimensional OLAP: A Minimal Cubing Approach by Li, Han, and Gonzalez

>>>>· Sorting improves word-aligned bitmap indexes by Lemire, Kaser, and Aouiche

The end solution is:

· Insert records into Cassandra.

· Materialize lower-dimensional cuboids using bitsets and then join as needed.

· Perform all query steps directly in the database

Ben’s concluding advice:

· Read the literature

· Generic software is 90% wrong at scale, you just don’t know which 90%.

· Iterate to discover and be prepared to start over

If you want to read more, the presentation is at: Challenges and Trade-offs in Building a Web-scale Real-time Analytics System.

--jrh

James Hamilton

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Speeding Up Cloud/Server Applications With Flash Memory

James Hamilton — Sun, 06 Feb 2011 21:48:10 GMT

Last week, Sudipta Sengupta of Microsoft Research dropped by the Amazon Lake Union campus to give a talk on the flash memory work that he and the team at Microsoft Research have been doing over the past year. Its super interesting work. You may recall Sudipta as one of the co-authors on the VL2 Paper (VL2: A Scalable and Flexible Data Center Network) I mentioned last October.

Sudipta’s slides for the flash memory talk are posted at Speeding Up Cloud/Server Applications With Flash Memory and my rough notes follow:

· Technology has been used in client devices for more than a decade

· Server side usage more recent and the difference between hard disk drive and flash characterizes brings some challenges that need to be managed in the on-device Flash Translation Layer (FTL) or in the operating systems or Application layers.

· Server requirements are more aggressive across several dimensions including required random I/O rates and higher reliability and durability (data life) requirements.

· Key flash characteristics:

· 10x more expensive than HDD

· 10x cheaper than RAM

· Multi Level Cell (MLC): ~$1/GB

· Single Level Cell (SLC): ~$3/GB

· Laid out as an linear array of flash blocks where a block is often 128k and a page is 2k

· Unfortunately the unit of erasure is a full block but the unit of read or write is 2k and this makes the write in place technique used in disk drives not workable.

· Block erase is a fairly slow operation at 1500 usec whereas read or write is 10 to 100 usec.

· Wear is an issue with SLC supporting O(100k) erases and MLC O(10k)

· The FTL is responsible for managing the mapping between logical pages and physical pages such that logical pages can be overwritten and hot page wear is spread relatively evenly over the device.

· Roughly 1/3 the power consumption of a commodity disk and 1/6 the power of an enterprise disk

· 100x the ruggedness over disk drives when active

· Research Project: FlashStore

· Use flash memory as a cache between RAM and HDD

· Essentially a flash aware store where they implement a log structured block store (this is essentially what the FTLs do in the device implemented at the application layer.

· Changed pages are written through to flash sequentially and an in-memory index of pages is maintained so that pages can be found quickly on the flash device.

· On failure the index structure can be recovered by reading the flash device

· Recently unused pages are destaged asynchronously to disk

· A key contribution of this work is a very compact form for the index into the flash cache

· Performance results excellent and you can find them in the slides and the papers referenced below

· Research Project: ChunkStash

· A very high performance, high throughput key-value store

· Tested on two production workloads:

· Xbox Live Primetime online gaming

· Storage deduplication

· The storage dedeuplication test is a good one in that dedupe is most effective with a large universe of objects to run deduplication over. But a large universe requires a large index. The most interesting challenge of deduplication is to keep the index size small through aggressive compaction

· The slides include a summary of dedupe works and shows the performance and compression ratios they have achieved with ChunkStash

For those interested in digging deeper, the VLDB and USENIX papers are the right next stops:

· http://research.microsoft.com/apps/pubs/default.aspx?id=141508 (FlashStore paper, VLDB 2010)

· http://research.microsoft.com/apps/pubs/default.aspx?id=131571 (ChunkStash paper, USENIX ATC 2010)

· Slides: http://mvdirona.com/jrh/talksandpapers/flash-amazon-sudipta-sengupta.pdf

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Interested in Core Database Engine Development?

James Hamilton — Thu, 13 Jan 2011 16:12:54 GMT

If you have experience in database core engine development either professionally, on open source, or at university send me your resume. When I joined the DB world 20 years ago, the industry was young and the improvements were coming ridiculously fast. In a single release we improved DB2 TPC-A performance by a factor of 10x. Things were changing quickly industry-wide. These days single-server DBs are respectably good. It’s a fairly well understood space. Each year more features are added and a few percent performance improvement may happen but the code bases are monumentally large, many of the development teams are over 1,000 engineers, and things are happening anything but quickly.

If you are an excellent engineer, have done systems or DB work in the past, and are interested in working on the next decade’s problems in database, drop me a note (james@amazon.com).

--jrh

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Clustrix Database Appliance

James Hamilton — Thu, 06 May 2010 17:49:22 GMT

Earlier this week Clustrix announced a MySQL compatible, scalable database appliance that caught my interest. Key features supported by Clustrix:

· MySQL protocol emulation (MySQL protocol supported so MySQL apps written to the MySQL client libraries just work)

· Hardware appliance delivery package in a 1U package including both NVRAM and disk

· Infiniband interconnect

· Shared nothing, distributed database

· Online operations including alter table add column

I like the idea of adopting a MySQL programming model. But, it’s incredibly hard to be really MySQL compatible unless each node is actually based upon the MySQL execution engine. And it’s usually the case that a shared nothing, clustered DB will bring some programming model constraints. For example, if global secondary indexes aren’t implemented, it’s hard to support uniqueness constraints on non-partition key columns and it’s hard to enforce referential integrity. Global secondary indexes maintenance implies a single insert, update, or delete that would normally only require a single node change would require atomic updates across many nodes in the cluster making updates more expensive and susceptible to more failure modes. Essentially, making a cluster look exactly the same as a single very large machine with all the same characteristics isn’t possible. But, many jobs that can’t be done perfectly are still well worth doing. If Clustrix delivers all they are describing, it should be successful.

I also like the idea of delivering the product as a hardware appliance. It keep the support model simple, reduces install and initial setup complexity, and enables application specific hardware optimizations.

Using Infiniband as a cluster interconnect is a nice choice as well. I believe that 10GigE with RDMA support will provide better price performance than Infiniband but commodity 10GigE volumes and quality RDMA support is still 18 to 24 months away so Inifiband is a good choice for today.

Going with a shared nothing architecture avoids dependence on expensive shared storage area networks and the scaling bottleneck of distributed lock managers. Each node in the cluster is an independent database engine with its own physical (local) metadata, storage engine, lock manager, buffer manager, etc. Each node has full control of the table partitions that reside on that node. Any access to those partitions must go through that node. Essentially, bringing the query to the data rather than the data to the query. This is almost always the right answer and it scales beautifully.

In operation, a client connects to one of the nodes in the cluster and submits a SQL statement. The statement is parsed and compiled. During compilation, the cluster-wide (logical) metadata is accessed as needed and an execution plan is produced. The cluster-wide (logical) metadata is either replicated to all nodes or stored centrally with local caching. The execution plan produced by the query compilation will be run on as many nodes as needed with the constraint that table or index access be on the nodes that house those table or index partitions. Operators higher in the execution plan can run on any node in the cluster. Rows flow between operators that span node boundaries over the infiniband network. The root of the query plan runs on the node where the query was started and the results are returned to client program using the MySQL client protocol

As described, this is a very big engineering project. I’ve worked on teams that have taken exactly this approach and they took several years to get to the first release and even subsequent releases had programming model constraints. I don’t know how far along Clustrix is a this point but I like the approach and I’m looking forward to learning more about their offering.

White paper: Clustrix: A New Approach

Press Release: Clustrix Emerges from Stealth Mode with Industry’s First Clustered DB

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

MapReduce in CACM

Sat, 02 Jan 2010 16:15:19 GMT

In this month’s Communications of the Association of Computing Machinery, a rematch of the MapReduce debate was staged. In the original debate, Dave Dewitt and Michael Stonebraker, both giants of the database community, complained that:

1. MapReduce is a step backwards in database access

2. MapReduce is a poor implementation

3. MapReduce is not novel

4. MapReduce is missing features

5. MapReduce is incompatible with the DBMS tools

Unfortunately, the original article appear to be no longer available but you will find the debate branching out from that original article by searching on the title Map Reduce: A Major Step Backwards. The debate was huge, occasionally entertaining, but not always factual. My contribution was MapReduce a Minor Step forward.

Update: In comments, csliu offered updated URLs for the original blog post and a follow-on article:

· MapReduce: A Major Step Backwards

· MapReduce II

I like MapReduce for a variety of reasons the most significant of which is that it allows non-systems programmers to write very high-scale, parallel programs with comparative ease. There have been many attempts to allow mortals to write parallel programs but there really have only been two widely adopted solutions that allow modestly skilled programmers to write highly concurrent executions: SQL and MapReduce. Ironically the two communities participating in the debate, Systems and Database, have each produced a great success by this measure.

More than 15 years ago, back when I worked on IBM DB2, we had DB2 Parallel Edition running well over a 512 server cluster. Even back then you could write a SQL Statement that would run over a ½ thousand servers. Similarly, programmers without special skills can run MapReduce programs that run over thousands of serves. The last I checked Yahoo, was running MapReduce jobs over a 4,000 node cluster: Scaling Hadoop to 4,000 nodes at Yahoo!.

The update on the MapReduce debate is worth reading but, unfortunately, the ACM has marked the first article as “premium content” so you can only read it if you are a CACM subscriber:

· MapReduce and Parallel DBMSs: Friend or Foe

· MapReduce: A Flexible Data Processing Tool

Update: Moshe Vardi, Editor in Chief of the Communications of the Association of Computing Machinery has kindly decided to make both the of the above articles freely available for all whether or not CACM member. Thank you Moshe.
>

Even more important to me than the MapReduce debate is seeing this sort of content made widely available. I hate seeing it classified as premium content restricted to members only. You really all should be members but, with the plunging cost of web publishing, why can’t the above content be made freely available? But, while complaining about the ACM publishing policies, I should hasten to point out that the CACM has returned to greatness. When I started in this industry, the CACM was an important read each month. Well, good news, the long boring hiatus is over. It’s now important reading again and has been for the last couple of years. I just wish the CACM would follow the lead of ACM Queue and make the content more broadly available outside of the membership community.

Returning to the MapReduce discussion, in the second CACM article above, MapReduce: A Flexible Data Processing Tool, Jeff Dean and Sanjay Ghemawat, do a thoughtful job of working through some of the recent criticism of MapReduce.

If you are interested in MapReduce, I recommend reading the original Operating Systems Design and Implementation MapReduce paper: MapReduce: Simplied Data Processing on Large Clusters and the detailed MapReduce vs database comparison paper: A Comparison of Approaches to Large-Scale Data Analysis.

--jrh

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Randy Shoup & John Ousterhout at HPTS 2009

Sat, 14 Nov 2009 16:24:25 GMT

HPTS has always been one of my favorite workshops over the years. Margo Seltzer was the program chair this year and she and the program committee brought together one of the best programs ever. Earlier I posted my notes from Andy Bectolsheim’s session Andy Bechtolsheim at HPTS 2009 and his slides Technologies for Data Intensive Computing.

Two other sessions were particularly interesting and worth summarizing here. The first is a great talk on high-scale services lessons learned from Randy Shoup and a talk by John Ousterhout on RAMCloud a research project to completely eliminate the storage hierarchy and store everything in DRAM.

Randy Shoup

My notes from Randy’s talk follow and his slides are at: eBay’s Challenges and Lessons from Growing an eCommerce Platform to Planet Scale.

· eBay Manages

1. Over 89 million active users worldwide

2. 190 million items for sale in 50,000 categories

3. Over 8 billion URL requests per day

4. Roughly 10% of the items are listed or ended each day

5. 70B read/write operations/day

· Architectural Lessons

1. Partition Everything

2. Asynchrony Everywhere

3. Automate Everything

4. Remember Everything Fails

5. Embrace Inconsistency

6. Expect Service Evolution

7. Dependencies Matter

8. Know which databases are Authoritativeand which are caches

9. Never enough data (save everything)

10. Invest in custom infrastructure

John Ousterhout

My notes from John’s talk follow and his slides are at: RAMCloud: Scalable Data Center Storage Entirely in DRAM. I really enjoyed this talk despite the fact that I saw the same talk presented at the Stanford Clean Slate CTO Summit. This talk is sufficiently thought provoking to be just as interesting the second time through. My notes from John’s talk:

· Storage entirely in DRAM spread over 10s to 10s of thousands of servers

· Focus of project:

o Low latency and very large scale

· ~64GB server each supporting:

o 1M ops/second

o 5 to 10 us RPC

· Today commodity servers can stretch easily to 64GB. Expect to see 1TB in commodity servers out 5 to 10 years

· Current cost is roughly $60/GB. Expect this to fall to $4/GB in 5 to 10 years

· Motivation for RAMCloud project:

o Databases don’t scale

· Disk access rates not keeping up with capacity so disks must become archival:

o See Jim Gray’s excellent Disk is Tape

· Aggressive goal of achieving 5 to 10 u sec RPC

· Points out that very low latency applications are not built upon relational databases and argues that very low data access latency removes the need for optimization of access plans and concludes the relational model will disappear.

o I see value in low latency but don’t agree that the relational model will disappear. See One Size Does Not Fit All.

· John makes an interesting observation “the cost of consistency increases with transaction over-lap”

o Let:

§ 0 = # overlapping transactions

§ R = arrival rate for new transactions

§ D = duration of each transaction

o Then:

§ 0 is proportional to R * D

§ R increases with system scale and, eventually, strong consistency becomes unaffordable

§ But, D decreases with lower latency

o The interesting question: can we afford higher levels of consistency with lower latency?

· John argues perhaps with very low latency, one size might fit all (a single data storage system could handle all workloads).

o The counter argument to this one is that capital cost and power cost of an all memory solution appears prohibitively expensive for cold sequential workloads. Its perfect for OLTP but I don’t yet see the “one size can fit again” prediction.

If you are interested in digging deeper, the slides for all sessions are posted at: http://www.hpts.ws/agenda.html.

--jrh

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Conversation with Butler Lampson at SOSP 2009

Sat, 07 Nov 2009 18:45:57 GMT

Just about exactly one year ago, I posted a summary and the slides from an excellent Butler Lampson talk: The Uses of Computers: What’s Past is Merely Prologue. Its time for another installment. Butler was at SOSP 2009 a few weeks back and Marvin Theimer caught up with him for a wide ranging discussion on distributed systems.

With Butler's permission, what follows are Marvin’s notes from the discussion.

Contrast cars with airplanes: when the fancy electronic systems fail you (most-of-the-time) can pull a car over to the side of the road and safely get out whereas an airplane will crash-and-burn.

Systems that behave like cars vs. airplanes:

· It’s like a car if you can reboot it

· What’s the scope of the damage if you reboot it

Ensuring that critical sub-systems keep functioning:

· Layered approach with lower layers being simpler and able to cut off the higher layers and still keep functioning

· Bottom layers need to be simple enough to reason about or perhaps even formally verify

· Be skeptical about designing systems that gracefully degrade/approach their “melting points”. Nice in theory, but not likely to be feasible in practice in most cases.

· Have “firewalls” that partition your system into independent modules so that damage is contained.

· Firewalls have “blast doors” that automatically come down in case of alarms going off. Under normal circumstances the blast doors are up and you have efficient, optimized interaction between modules. When alarms go off the blast doors go down. The system must be able to work in degraded mode with the blast doors down.

· You need to continually test your system for how it behaves with the blast doors down to ensure that “critical functioning” is still achievable despite system evolution and environment evolution. Problem is that testing is expensive, so there is a trade-off between extensive testing and cost. Essentially you can’t test everything. This is part of the reason why the lowest levels of the system need to be simple enough to formally reason about their behavior.

o Dave Gifford’s story about bank that had diesel backup generators for when power utility failed. They religiously tested firing up the backup generators. However, when a prolonged power actually occurred they discovered that the generators failed after half an hour because their lubricating oil failed. No one had thought to test running on backup power for more than a few minutes.

Low-level multicast is bad because you can’t reason about the consequences of its use. Better to have application-level multicast where you can explicitly control what’s going on.

RPC conundrum:

· People have moved back from RPC to async messages because of the performance issues of sync RPC.

· By doing so they are reintroducing concurrency issues into their programs.

A possible solution:

· Constrain your system (if you can) to enable the definition of a small number of interaction patterns that hide the concurrency and asynchrony.

· Your experts employ async messages to implement those higher-level interaction patterns.

· The app developers only use the simper, higher-level abstractions.

· Be happy with 80% solution – which you might achieve – and don’t expect to be able to handle all interactions this way.

Partitioned, primary-key scale-out approach is essentially mimicking the OLTP model of transactional DBs. You are giving up certain kinds of join operators in exchange for scale-out and the app developer is essentially still programming the simple ACID DB model.

· Need appropriate patterns/framework for updating multiple objects in a non-transactional manner.

· Standard approach: update one object and transactionally write a message in a message queue for the other object. Transactional update to other object is done asynchronously to the first object update. Need compensation code for when things go wrong.

· An interesting approach for simplifying the compensation problem: try to turn it into a garbage collection problem. Background tasks look for to-do messages that haven’t been executed and figure out how to bring the system back into “compliance”. You need this code for your fsck case anyway.

WARNING: don’t over-engineer your system. Lots of interesting ideas here; you’ll be tempted to over-generalize and make things too complicated. “Ordinary designers get it wrong 99% of the time; really smart designers get it wrong 50% of the time.”

Thanks to Butler Lampson and Marvin Theimer for making this summary available.

--jrh

e: jrh@mvdriona.com

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Here's Another Innovative Application of Commodity Hardware

Mon, 21 Sep 2009 14:41:49 GMT

Here’s another innovative application of commodity hardware and innovative software to the high-scale storage problem. MaxiScale focuses on 1) scalable storage, 2) distributed namespace, and 3) commodity hardware.

Today's announcement: http://www.maxiscale.com/news/newsrelease/092109.

They sell software designed to run on commodity servers with direct attached storage. They run N-way redundancy with a default of 3-way across storage servers to be able to survive disk and server failure. The storage can be accessed via HTTP or via Linux or Windows (2003 and XP) file system calls. The later approach requires a kernel installed device driver and uses a proprietary protocol to communicate back with the filer cluster but has the advantage of directly support local O/S read/write operations. MaxiScale architectural block diagram:

Overall I like the approach of using commodity systems with direct attached storage as the building block for very high scale storage clusters but that is hardly unique. Many companies have head down this path and, generally, it’s the right approach. What caught my interest when I spoke to the MaxiScale team last week was: 1) distributed metadata, 2) MapReduce support, and 3) small file support. Let’s look at each of these major features:

Distributed Metadata

File systems need to maintain a namespace. We need to maintain the directory hierarchy and we need to know where to find the storage blocks that make up the file. In addition, other attributes and security may need to be stored depending upon the implemented file system semantics. This metadata is often stored in large key/value store. The metadata requires at least some synchronization since, for example, you don’t want to create two different objects of the same name at roughly the same time. At high scale, storage servers will be joining and leaving the cluster all the time, so having a central metadata service is a easy approach to the problem. But, as easy as it is to implement a central metadata systems, they bring scaling limits. Eventually the metadata gets too hot and needs to be partitioned. In fairness, it’s amazing how far central metadata can be scaled but eventually hot spots develop and it needs to be partitioned. For example, Google GFS just went down this path: GFS: Evolution on Fast-forward. Partitioning metadata is a fairly well understood problem. What makes it a bit of a challenge is making the metadata system adaptive and able to re-partition when hot spots develop.

MaxiScale took an interesting approach to scaling the metadata. They distributed the metadata servers over the same servers that store the data rather than implement a cluster of dedicated metadata servers. They do this by hashing on the parent directory to find what they call a Peer Set and then, in that particular Peer Set, they look up the object name in the metadata store, find the file block location, and then apply the operation to the blocks in that same Peer Set.

Distributing the metadata over the same Peer Set as the stored data means that each peer set is independent and self-describing. The downside of having a fixed hash over the peer sets is that it’s difficult to cool down an excessively hot peer set by moving objects since the hash is known by all clients.

MapReduce Support

I love the MaxiScale approach to multi-server administration. They need to provide customers the ability to easily maintain multi-server clusters. They could have implemented a separate control plane to manage the all the servers that make up the cluster but, instead, they just use Hadoop and run MapReduce jobs.

All administrative operations are written as simple MapReduce jobs which certainly made the implementation task easier but it’s also a nice, extensible interface to allow customers to write custom administrative operations. And, since MapReduce is available over the cluster, its super easy to write data mining and data analysis jobs. Supporting MapReduce over the storage system is a nice extension of normal filer semantics.

Small File Support

The standard file system access model is to probe the metadata to get the block list and then access the blocks to perform the file operation. In the common case, this will require two I/Os which is fine for large files but the two I/Os can be expensive for small file access. And, since most filers use fixed size blocks and, for efficiency these block size tend to be larger than the average small file, some space is wasted. The common approach to this two problems is to pull small files “up” and rather than store the list of storage blocks in the file metadata, just store the small file. This works fine for small files and avoids both the block fragmentation and the multiple I/O problem on small files. This is what MaxiScale has done as well and they claim single I/O for any small file stored in the system.

More data on the MaxiScale filer: Small Files, Big Headaches: Ensuring Peak Performance

I love solutions based upon low-cost, commodity H/W and application maintained redundancy and what MaxiScale is doing has many of the features I would like to see in a remote filer.

--jrh

James Hamilton

e: jrh@mvdriona.com

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

Code Splitting for Fast Javascript Application Startup

Sun, 13 Sep 2009 17:03:46 GMT

AJAX applications are wonderful because they allow richer web applications with much of the data being brought down asynchronously. The rich and responsive user interfaces of applications like Google Maps and Google Docs are excellent but JavaScript developers need to walk a fine line. The more code they download, the richer the UI they can support and the less synchronous server interactions they need. But, the more code they download, the slower the application can be to start. This is particularly noticeable when the client cache is cold and in mobile applications with restricted bandwidth back to the server.

Years ago profile directed code reorganization (a sub-class of Basic Block Transforms) were implemented to solve what might appear to be an unrelated problem. The problem tackled by these profile directed basic block reorganizations is decreasing the number of last level cache misses in a server. They do this by organizing frequently accessed code segments together and moving rarely executed code segments. The biggest gain is that seldom executed error handling code can be moved away from frequently executed application code. I’ve seen reports of error handling code making up more than 40% of an application. Moving this code away from the commonly executed mainline code allows fewer processor cache lines to support program execution which demands fewer memory faults. Error handling code will execute more slowly but that is seldom an issue. Profile directed basic block transforms need to be trained on “typical” applications workloads and code that typically executes together will be placed together. Unfortunately, “typical” is often an important, industry standard benchmark like TPC-C so sometimes “typical” is replaced by “important” :-). Nonetheless, the tools are effective and greater than 20% improvement is common and we often see much more. All commercial database servers use or misuse profile directed basic block reorganizations.

The JavaScript download problem is actually very similar to the problem addressed by basic block transforms. Getting code from the server takes relatively long time just as getting code from memory takes a long time relative to executing code already in the processor cache. Much of the application doesn’t execute in the common case so it makes little sense to download it all unless needed in this execution. Most of the code isn’t needed to start the application so it’s a big win to download the code, start the application, and then download what is needed in the background.

Last week Ben Livshits and Emre Kiciman of the Microsoft Research team released an interesting tool that does exactly this for JavaScript applications. Doloto analyses client JavaScript systems and breaks them up into a series of independent modules. The primary module is downloaded first and includes just stubs for the other modules. This primary module is smaller, downloads faster, and dramatically improves time to live application. In the Doloto team measurements, the size of the initial download was only between 20% and 60% of the size of the standard download. In the case of Google docs, the initial download was less than 20% of the original size.

Once the initial module is downloaded, the application is live and running and the rest of the modules are brought down asynchronously or faulted in as needed. Many applications due these optimizations manually but this is a nice automated approach to the problem

I’ve seen 80,000 line JavaScript programs and there are many out there far larger. Getting the application running fast dramatically improves the user experience and this is a nice approach to achieving that goal. Doloto is available for download at: http://msdn.microsoft.com/en-us/devlabs/ee423534.aspx. And there is a more detailed Doloto paper at: http://research.microsoft.com/en-us/um/people/livshits/papers/pdf/fse08.pdf and summary information at: http://research.microsoft.com/en-us/projects/doloto/.

e: jrh@mvdriona.com

b: http://blog.mvdirona.com / http://perspectives.mvdirona.com

From Perspectives.

HadoopDB: MapReduce over Relational Data

Sat, 25 Jul 2009 17:59:47 GMT

MapReduce has created some excitement in the relational database community. Dave Dewitt and Michael Stonebraker’s MapReduce: A Major Step Backwards is perhaps the best example. In that posting they argued that map reduce is a poor structured storage technology, the execution engine doesn’t include many of the advances found in modern, parallel RDBMS execution engines, it’s not novel, and its missing features.

In Mapreduce: A Minor Step Forward I argued that MapReduce is an execution model rather than storage engine. It is true that it is typically run over a file system like GFS or HDFS or simple structured storage system like BigTable or Hbase. But, it could be run over a full relational database.

Why would we want to run Hadoop over a full relational database? Hadoop scales: Hadoop has been scaled to 4,000 nodes at Yahoo! Scaling Hadoop to 4000 nodes at Yahoo!. Scaling a clustered RDBMS too 4k nodes is certainly possible but the high scale single system image cluster I’ve seen was 512 nodes (what was then called DB2 Parallel Edition). Getting to 4k is big. Hadoop is simple: automatic parallelism has been an industry goal for decades but progress has been limited. There really hasn’t been success in allowing programmers of average skill to write massively parallel programs except for SQL and Hadoop. Programmers of bounded skill can easily write SQL that will be run in parallel over high scale clusters. Hadoop is the only other example I know where this is possible and happening regularily.

Hadoop makes the application of 100s or even 1000s of nodes of commodity computers easy so why not Hadoop over full RDBMS nodes? Daniel Abadi and team from Yale and Brown have done exactly that. In this case, Hadoop over PostgresSQL. From Daniel’s blog:

HadoopDB is:

1. A hybrid of DBMS and MapReduce technologies targeting analytical query workloads

2. Designed to run on a shared-nothing cluster of commodity machines, or in the cloud

3. An attempt to fill the gap in the market for a free and open source parallel DBMS

4. Much more scalable than currently available parallel database systems and DBMS/MapReduce hybrid systems (see longer blog post).

5. As scalable as Hadoop, while achieving superior performance on structured data analysis workloads

See: http://dbmsmusings.blogspot.com/2009/07/announcing-release-of-hadoopdb-longer.html for more detail and http://sourceforge.net/projects/hadoopdb/ for source code for HadoopDB.

A more detailed paper has been accepted for publication at VLDB: http://db.cs.yale.edu/hadoopdb/hadoopdb.pdf.

The development work for HadoopDB was done using AWS Elastic Compute Cluster. Nice work Daniel.

--jrh

1200, 12^th Ave. S., Seattle, WA, 98144
W:+1(425)703-9972 | C:+1(206)910-4692 | H:+1(206)201-1859 | james@amazon.com

H:mvdirona.com | W:mvdirona.com/jrh/work | blog:http://perspectives.mvdirona.com

From Perspectives.

Erasure Coding and Cold Storage

Sat, 13 Jun 2009 17:42:58 GMT

Erasure coding provides redundancy for greater than single disk failure without 3x or higher redundancy. I still like full mirroring for hot data but the vast majority of the worlds data is cold and much of it never gets referenced after writing it: Measurement and Analysis of Large-Scale Network File System Workloads. For less-than-hot workloads, erasure coding is an excellent solution. Companies such as EMC, Data Domain, Maidsafe, Allmydata, Cleversafe, and Panasas are all building products based upon erasure coding.

At FAST 2009 in late February, A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries For Storage will be presented. This paper looks at 5 open source erasure coding systems and compares there relative performance. The open source erasure coding packages implement Read-Solomon, Cauchy Read-Solomon, Even-Odd, Row-Diagonal Parity (RDP), and Minimal Density RAID-6 codes.

The authors found:

· The special-purpose RAID-6 codes vastly outperform their general-purpose counterparts. RDP performs the best of these by a narrow margin.

· Cauchy Reed-Solomon coding outperforms classic Reed-Solomon coding significantly, as long as attention is paid to generating good encoding matrices.

· An optimization called Code-Specific Hybrid Reconstruction is necessary to achieve good decoding speeds in many of the codes.

· Parameter selection can have a huge impact on how well an implementation performs. Not only must the number of computational operations be considered, but also how the code interacts with the memory hierarchy, especially the caches.

· There is a need to achieve the levels of improvement that the RAID-6 codes show for higher numbers of failures.

The paper also provides a good introduction of how erasure coding works. Recommended. I expect erasure codes to spring up in many more application in the near future.

--jrh

1200, 12^th Ave. S., Seattle, WA, 98144
W:+1(425)703-9972 | C:+1(206)910-4692 | H:+1(206)201-1859 | james@amazon.com

H:mvdirona.com | W:mvdirona.com/jrh/work | blog:http://perspectives.mvdirona.com

From Perspectives.

Erlang Productivity and Performance

Thu, 26 Mar 2009 14:42:25 GMT

Over the last couple of years, I’ve been getting more interested in Erlang as an high-scale services implementation language originally designed at Ericcson. Back in May of last year I posted: Erlang and High-Scale System Software.

The Erlang model of spawning many lightweight threads that communicate via message passing is typically less efficient than the more common shared memory and locks approach but the lightweight processes with message passing model but it is much easier to get a correct implementation using this model. Erlang also encourages a “fail fast” programming model. Years ago I became convinced that this design pattern is one of the best ways to get high scale systems software correct (Designing and Deploying Internet-Scale Services).

Chris Newcombe of Amazon recently presented an excellent talk on Erlang at the Berkeley RAD Lab. The first part of Chris’ Berkeley talk on Erlang is posted here: Erlang: Productivity and Performance (ChrisNewcombe_ErlangProductivityPerformance.pdf (298.21 KB)). The second half of Chris’ talk is posted at: http://ulf.wiger.net/weblog/wp-content/uploads/2009/01/damp09-erlang-multicore.pdf (unfortunately this link is down at the time of this posting). Update: Ulf Wiger offers a live URL for his excellent slides: http://www.cse.unsw.edu.au/~pls/damp09/damp09-wiger-keynote.pdf. >

In this talk Chris gives an overview of Erlang, talks about some of the advantages of the language, and then goes through some of the performance strengths and weaknesses of Erlang.

--jrh

1200, 12^th Ave. S., Seattle, WA, 98144
W:+1(425)703-9972 | C:+1(206)910-4692 | H:+1(206)201-1859 | james@amazon.com

H:mvdirona.com | W:mvdirona.com/jrh/work | blog:http://perspectives.mvdirona.com

From Perspectives.

Key Value Stores

Sun, 22 Feb 2009 15:43:13 GMT

Richard Jones of Last.fm has compiled an excellent list of key-value stores in Anti-RDBMS: A list of key-value stores.

In this post, Richard looks at Project Voldemort, Ringo, Scalaris, Kai, Dynomite, MemcacheDB, ThruDB, CouchDB, Cassandra, HBase and Hypertable. His conclusion for Last.fm use is that Project Voldemort has the most promise with Scalaris being a close second and Dynomite is also interesting.

--jrh

1200, 12^th Ave. S., Seattle, WA, 98144
W:+1(425)703-9972 | C:+1(206)910-4692 | H:+1(206)201-1859 | james@amazon.com

H:mvdirona.com | W:mvdirona.com/jrh/work | blog:http://perspectives.mvdirona.com

From Perspectives.

Facebook Cassandra Architecture and Design

Sat, 07 Feb 2009 19:16:20 GMT

Last July, Facebook released Cassandra to open source under the Apache license: Facebook Releases Cassandra as Open Source. Facebook uses Cassandra as email search system where, as of last summer, they had 25TB and over 100m mailboxes. This video gets into more detail on the architecture and design: http://www.new.facebook.com/video/video.php?v=540974400803#/video/video.php?v=540974400803. My notes are below if you don’t feel like watching the video.

· Authors:

o Prashant Malik

o Karthnik Ranganathan

o Avinash Lakshman

· Structured storage system over P2p (keys are consistent hashed over servers)

· Initially aimed at email inbox search problem

· Design goals:

o Cost Effective

o Highly Available

o Incrementally Scalable

o Efficient data layout

o Minimal administration

· Why Cassandra

o MySQL drives too many random I/Os

o File-based solutions require far too many locks

· What is Cassandra

o Structured storage over a distributed cluster

o Redundancy via replication

o Supports append/insert without reads

o Supports a caching layer

o Supports Hadoop operations

· Cassandra Architecture

o Core Cassandra Services:

§ Messaging (async, non-blocking)

§ Failure detector

§ Cluster membership

§ Partitioning scheme

§ Replication strategy

o Cassandra Middle Layer

§ Commit log

§ Mem-table

§ Compactions

§ Hinted handoff

§ Read repair

§ Bootstrap

o Cassandra Top Layer

§ Key, block, & column indexes

§ Read consistency

§ Touch cache

§ Cassandra API

§ Admin API

§ Read Consistency

o Above the top layer:

§ Tools

§ Hadoop integration

§ Search API and Routing

· Cassandra Data Model

o Key (uniquely specifies a “row”)

§ Any arbitrary string

o Column families are declared or deleted in advance by administrative action

§ Columns can be added or deleted dynamically

§ Column families have attribute:

· Name: arbitrary string

· Type: simple,

o Key can “contain” multiple column families

§ No requirement that two keys have any overlap in columns

o Columns can be added or removed arbitrarily from column families

o Columns:

§ Name: arbitrary string

§ Value: non-indexed blob

§ Timestamp (client provided)

o Column families have sort orders

§ Time-based sort or name-based sort

o Super-column families:

§ Big tables calls them locality groups

§ Super-column families have a sort order

§ Essentially a multi-column index

o System column families

§ For internal use by Cassandra

o Example from email application

§ Mail-list (sorted by name)

· All mail that includes a given word

§ Thread-list (sorted by time)

· All threads that include a given word

§ User-list (sorted by time)

· All mail that includes a given word user

· Cassandra API

o Simple get/put model

· Write model:

o Quorum write or aysnc mode (used by email application)

o Async: send request to any node

§ That node will push the data to appropriate nodes but return to client immediately

o Quorum write:

§ Blocks until quorum is reached

o If node down, then write to another node with a hint saying where it should be written two

§ Harvester every 15 min goes through and find hints and moves the data to the appropriate node

o At write time, you first write to a commit log (sequential)

§ After write to log it is sent to the appropriate nodes

§ Each node receiving write first records it in a local log

· Then makes update to appropriate memtables (1 for each column family)

§ Memtables are flushed to disk when:

· Out of space

· Too many keys (128 is default)

· Time duration (client provided – no cluster clock)

§ When memtables written out two files go out:

· Data File

· Index File

o Key, offset pairs (points into data file)

o Bloom filter (all keys in data file)

§ When a commit log has had all its column families pushed to disk, it is deleted

· Data files accumulate over time. Periodically data files are merged sorted into a new file (and creates new index)

· Write properties:

o No locks in critical path

o Sequential disk access only

o Behaves like a write through cache

§ If you read from the same node, you see your own writes. Doesn’t appear to provide any guarantee on read seeing latest change in failure case

o Atomicity guaranteed for a key

o Always writable

· Read Path:

o Connect to any node

o That node will route to the closes data copy which services immediately

o If high consistency required, don’t return from local immediately

§ First send digest request to all replicas

§ If delta is found, the updates are sent to the nodes that don’t have current data (read repair)

· Replication supported via multiple consistent hash rings:

o Servers are hashed over ring

o Keys are hashed over ring

o Redundancy via walking around the ring and placing on the next node (rack position unaware) or on the next node on a different rack (rack aware) or on a next system in a different data center (implication being that the ring can span data centers)

· Cluster membership

o Cluster membership and failure detection via gossip protocol

· Accrual failure detector

o Default sets PHI to 5 in Cassandra

o Detection is 10 to 15 seconds with PHI=5

· UDP control messages and TCP for data messages

· Complies with Staged Event Driven Architecture (SEDA)

· Email system:

o 100m users

o 4B threads

o 25TB with 3x replication

o Uses and joins across 4 tables:

§ Mailbox (user_id to thread_id mapping)

§ Msg_threads (thread to subject mapping)

§ Msg_store (thread to message mapping)

§ Info (user_id to user name mapping)

· Able to load using Hadoop at 1.5TB/hour

o Can load 25TB at network bandwidth over Cassandra Cluster

1200, 12^th Ave. S., Seattle, WA, 98144
W:+1(425)703-9972 | C:+1(206)910-4692 | H:+1(206)201-1859 | james@amazon.com

H:mvdirona.com | W:mvdirona.com/jrh/work | blog:http://perspectives.mvdirona.com

From Perspectives.

Recardo Hermann's Snippets on Software

Mon, 19 Jan 2009 17:55:01 GMT

I recently stumbled across: Snippets on Software. It’s a collection of mini-notes on software with links to more if you are interested in more detail. Some snippets are wonderful, some clearly aren’t exclusive to software and some I would argue are just plain wrong. Nonetheless, it’s a great list.

It’s too long to read from end-to-end in one sitting but it’s well worth skimming. Below a few snippets that I enjoyed to whet your appetite:

"there is only one consensus protocol, and that's Paxos" - all other approaches are just broken versions of Paxos. – Mike Burrows

Conway’s Law: Any organization that designs a system (defined broadly) will produce a design whose structure is a copy of the organization's communication structure.

"Reading, after a certain age, diverts the mind too much from its creative pursuits. Any man who reads too much and uses his own brain too little falls into lazy habits of thinking." -- Albert Einstein

A human being should be able to change a diaper, plan an invasion, butcher a hog, conn a ship, design a building, write a sonnet, balance accounts, build a wall, set a bone, comfort the dying, take orders, give orders, cooperate, act alone, solve equations, analyze a new problem, pitch manure, program a computer, cook a tasty meal, fight efficiently, die gallantly. Specialization is for insects. -Robert A. Heinlein

"You can try to control people, or you can try to have a system that represents reality. I find that knowing what's really happening is more important than trying to control people." -- Larry Page

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it? --Brian Kernighan

--jrh