Clearspring - Your Content. Everywhere.

This is part two of a four part series on Clearspring’s approach to big data analytics. (See part 1.)  This post will focus on building tree-based data structures to store the massive quantity of information that Clearspring receives each day. Trees have several useful characteristics that make them the ideal data structure for our needs. For example, trees provide a compressed representation, an index, of our data where a path through a tree represents a row of data. Trees can also be sharded and distributed throughout our clusters which allows us to create massive trees composed of hundreds of different shards. At query time we can easily gather and merge information from each shard.

Tree Building Process

The foundation of our distributed analytics framework is the tree building process. We selected a tree-based storage structure for our processed data because we feel that it fills a useful middle ground between the datamodel-centric view of row oriented databases and the query-centric view more common with column-oriented databases.

The TreeBuilder consumes data from one or more data sources (typically a set of Stream Servers) and then builds a tree based on the input data and a job configuration that defines the desired tree structure. An example tree might look like:

One of the more interesting aspects of our tree data structure is the concept of data attachments. We often run into situations where we’d like to store certain bits of information in a way that is easily retrievable. Some nodes in a tree may have many millions of children so questions like “which URLs were clicked the most times?”, can be very expensive. This is where the data attachment comes into play. We can use operations from our recently open sourced stream-lib project to find and store the “top” URLs as a data attachment on the parent node. This top element is dynamically updated anytime new data is added to the tree. As each new record is processed the data attachment is updated to reflect the current list of n top elements. Tops may be lossy but if the top is large enough the results are generally accurate enough for our needs. Stream-lib is a very powerful library that makes it possible to count a huge number of elements in a distributed system, find the top-k elements from massive lists of data, and perform membership detection using bloom filters. You can read more about stream-lib here or checkout the source code on github.

Let’s take a look at an example JSON configuration used to create a tree:

In the example above we create a simple tree with the root “urltree”. Underneath “urltree” we have two branches,“ymd” and “ym”, representing data broken down by day and by month. Each of those branches have two levels of children. The first level contains a list of dates and the second level has a list of URLs. The first level of both branches has one data attachment called “topurls”. This data attachment will contain a list of the URLs with the highest cardinality. So if we want to know which URL was seen the most times in the month of May or on a specific day in May that data can be retrieved quickly without requiring iteration over all of the children of the date node. The resulting tree with sample data may look like:

We use Berkely DB JE as our underlying database for each job. Berkley DB JE is a powerful database and provides a nice abstraction layer to the data structure we wanted to use. It is very common for us to have jobs that store more data than we can practically fit into memory. We created a library called PageDB that provides an abstraction layer between Berkley DB JE and the rest of our system. PageDB tracks and estimates memory consumption for each database that is paged into memory. It groups keys and their values together for efficient block level compression which reduces the disk IO required to store and retrieve data. Rather than storing first class Java objects in memory, PageDB keeps the data in compressed byte format which is significantly more efficient than storing the first class Java objects in the heap.

Whats Next?

Parts one and two of this series introduced Hydra, Stream Servers, and the tree-building process. These components provide the foundation necessary to discuss the distributed query engine we use to retrieve information from our clusters and that will be the topic of the next post in this series. If you’d like to work on problems like these we are always hiring.

Last night Clearspring hosted a Big Data DC meeting at our offices in Tysons Corner, VA. Matt Abrams, Director of Data Analytics, presented to a crowd of around 40 people about how the data processing team breaks down 4-5 terabytes a day, including philosophies about design, speed and simplicity.

In case you missed out on the fun (that included pizza and beer!), here is the presentation:

We’re excited to announce that we’ve just closed an investment round led by Institutional Venture Partners (IVP). IVP has backed some of the best data-driven companies on the web, including Twitter and Zynga. 86 out of the 300 companies they last invested in have gone public.

In the last couple of years, we’ve grown tremendously across the board. AddThis is now used by over 9MM domains, reaching over 1B unique users monthly. It’s so popular that we’re now one of a handful of sites to have a Google PageRank of 10. We’re processing 10TB of data/day – every week, we process as much data as the entire digital Library of Congress.

AddThis has in turn fueled the growth of our Audience Platform, enabling hundreds of advertisers to deliver more relevant advertising. All the while we’ve been hiring as fast as we can to continue to support the needs of all the great companies that use our products.

We want to thank all of you for working with us over the years. We hope to show you just how thankful we are by putting this money to work on great new products. As always, if you have any ideas about how we can better serve publishers and advertisers, hit us up.

Look forward to continuing to rock (and roll) with all of you!

Cheers,

Hooman

Clearspring is honored to be listed as one of Lead411′s Hottest DC Companies in 2011 for the tech industry. The list recognizes fast growing companies which also includes LivingSocial, SBNation and OPower.

It’s great to be recognized among such a talented and hardworking group of companies. Clearspring is very proud to be a part of the DC tech community and cheers for the success of our neighbors.

Clearspring’s CS Motor Club crew was featured in today’s Washington Post in an article about unconventional recruitment techniques. A handful of Clearspring team members with a love of cars started the Motor Club as a side hobby. They have since purchased a $500 car, or hooptie, and plan to compete in the 24 Hours of LeMons race this summer.

There has been talk of other CS clubs starting up but so far nothing has materialized to rival the so-far impressive results of the motor gang.

Of course, we are hiring and it may take some fresh team members to grab the reigns and get something going. So make sure to check out our job openings and send in your application. You could be the next founder of CS Knitting Club or CS Bowling Club!

This is the first post in a four part series that will describe the data analytics architecture Clearspring has created to process large amounts of semi-structured data.

On a daily basis, the Clearspring network yields tens of billions of new, unique data points. In storage terms, we ingest 4 to 5 TB of new data each day; that could easily double in 12-18 months. That data must be processed as live streams, re-processed from the archive as new algorithms are developed and able to be queried in flexible ways. An interesting mix of batch, live and hybrid jobs are employed. To keep pace with a rapidly expanding network, the architecture must not only efficiently handle the current set of tasks, but it must also enable significant growth while guarding against hardware and software faults. To satisfy these needs, we built an entire software suite that leverages open source technologies and many in-house software components.

Desired System Characteristics and Challenges

Stream Server

Stream Servers provide access to the files stored on one node to any other node in the cluster. The Stream Server transmits raw bytes to clients because they may be in a compressed format. This limits the the number of times the data in the file is decoded and  reduces the total amount of data transmitted over the network. This approach does prevent the Stream Server from applying fine grained filters to the individual log lines. However we think that this limitation is acceptable given CPU cycles saved by only decoding the file once on the client side and the massive reduction in network IO.

Requests for data come into the Stream Server in the form of regular expressions which describe which files the client would like to receive.  Here is an example of what a request might look like:

The snippet above would tell the Stream Server to find all files in any directory under ‘job/1/*/live/split/us’ that has a file that matches the regular expression defined in the match field.  The date format will be replaced at run-time with the set of dates the client is interested in and the mod variable will be replaced with the modulus for the client.  This approach enables a client to stream data for a specific partition and time range without requiring complex filtering on the server side.

Conclusion