Communications of the ACM

118 COMMUNICATIONS OF THE ACM | JULY 2016 | VOL. 59 | NO. 7 of ads metrics, Mesa is a generic data warehousing solution that satisfies all of the above requirements.

Mesa leverages common Google infrastructure and services, such as Colossus (Google’s distributed file system), 7 BigTable, 3 and MapReduce. 6 To achieve storage scalability and availability, data is horizontally partitioned and replicated. Updates may be applied at the granularity of a single table or across many tables. To achieve consistent and repeatable queries during updates, the underlying data is multi-versioned. To achieve update scalability, data updates are batched, assigned a new version number, and periodically (e.g., every few minutes) incorporated into Mesa. To achieve update consistency across multiple data centers, Mesa uses a distributed synchronization protocol based on Paxos. 11

In contrast, commercial DBMS vendors4, 14, 17 often address the scalability challenge through specialized hardware and sophisticated parallelization techniques. Internet services companies1, 12, 16 address this challenge using a combination of new technologies: key-value stores, 3, 8, 13 columnar storage, and the MapReduce programming paradigm. However, many of these systems are designed to support bulk load interfaces to import data and can require hours to run. From that perspective, Mesa is very similar to an OLAP system. Mesa’s update cycle is minutes and it continuously processes hundreds of millions of rows. Mesa uses multi-versioning to support transactional updates and queries across tables. A system that is close to Mesa in terms of supporting both dynamic updates and real-time querying of transactional data is Vertica. 10 However, to the best of our knowledge, none of these commercial products or production systems has been designed to manage replicated data across multiple datacenters. Also, none of Google’s other in-house data solutions2, 3, 5, 15 support the data size and update volume required to serve as a data warehousing platform supporting Google’s advertising business.

Mesa achieves the required update scale by processing updates in batches. Mesa is, therefore, unique in that application data is redundantly (and independently) processed at all datacenters, while the metadata is maintained using synchronous replication. This approach minimizes the synchronization overhead across multiple datacenters in addition to providing additional robustness in face of data corruption.

2. MESA STORAGE SUBSYSTEM

Data in Mesa is continuously generated and is one of the
largest and most valuable data sets at Google. Analysis que-
ries on this data can range from simple queries such as,
“How many ad clicks were there for a particular advertiser
on a specific day?” to a more involved query scenario such
as, “How many ad clicks were there for a particular adver-
tiser matching the keyword ‘decaf’ during the first week of
October between 8:00 am and 11:00 am that were displayed
on google.com for users in a specific geographic location
using a mobile device?”
Data in Mesa is inherently multi-dimensional, capturing
all the microscopic facts about the overall performance of
Google’s advertising platform in terms of different dimen-
sions. These facts typically consist of two types of attributes:
dimensional attributes (which we call keys) and measure
attributes (which we call values). Since many dimension
attributes are hierarchical (and may even have multiple hier-
archies, e.g., the date dimension can organize data at the day/
month/year level or fiscal week/quarter/year level), a single
fact may be aggregated in multiple materialized views based
on these dimensional hierarchies to enable data analysis
using drill-downs and roll-ups. A careful warehouse design
requires that the existence of a single fact is consistent across
all possible ways the fact is materialized and aggregated.

2. 1. The data model

In Mesa, data is maintained using tables. Each table has a table schema that specifies its structure. Specifically, a table schema specifies the key space K for the table and the corresponding value space V, where both K and V are sets. The table schema also specifies the aggregation function F : V × V → V which is used to aggregate the values corresponding to the same key. The aggregation function must be associative (i.e., F(F(u0, u1), u2) = F(u0, F(u1, u2) ) for any values u0, u1, u2 ∈ V). In practice, it is usually also commutative (i.e., F(u0, u1) = F(u1, u0)), although Mesa does have tables with non-commutative aggregation functions (e.g., F(u0, u1) = u1 to replace a value). The schema also specifies one or more indexes for a table, which are total orderings of K.

The key space K and value space V are represented as tuples of columns, each of which has a fixed type (e.g., int32, int64, string, etc.). The schema specifies an associative aggregation function for each individual value column, and F is implicitly defined as the coordinate-wise aggregation of the value columns, that is:

F ((x1, . . . , xk), ( y1, . . . , yk)) = ( f1(x1, y1) , . . . , fk (xk, yk)), where (x1, . . . , xk), ( y1, . . . , yk) ∈ V are any two tuples of column values, and f1, . . . , fk are explicitly defined by the schema for each value column.