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.
As an example, Figure 1 illustrates three Mesa tables. All
three tables contain ad click and cost metrics (value columns)
Date PublisherId Country Clicks Cost
2013/12/31 100 US
2014/01/01 100 US
2014/01/01 200 UK
10 32
205 103
100 50
(a) Mesa table A
Date AdvertiserId Country Clicks Cost
2013/12/31 1 US
2014/01/01 1 US
2014/01/01 2 UK
2014/01/01 2 US
10 32
53
100 50
200 100
(b) Mesa table B
AdvertiserId Country Clicks Cost
1 US
2 UK
2 US
15 35
100 50
200 100
(c) Mesa table C
Figure 1. Three related Mesa tables.