【免费】01-Google三大论文阅读.rar资源-CSDN文库

共5个文件

pdf：4个

docx：1个

需积分: 0 128 浏览量 2022-11-19 10:57:47 上传评论收藏 851KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

01-Google三大论文阅读.rar （5个子文件）

01-Google三大论文阅读

The Google File System.pdf 269KB

MapReduce Simplified Data Processing on Large Clusters.pdf 233KB

homework1-20-X-XX-姓名-论文阅读报告.docx 18KB

homework1-20-X-XX-姓名-论文阅读报告.pdf 162KB

Bigtable__A_Distributed_Storage_System_for_Structured_Data.pdf 294KB

Bigtable: A Distributed Storage System

for Structured Data

FAY CHANG, JEFFREY DEAN, SANJAY GHEMAWAT, WILSON C. HSIEH,

DEBORAH A. WALLACH, MIKE BURROWS, TUSHAR CHANDRA,

ANDREW FIKES, and ROBERT E. GRUBER

Google, Inc.

Bigtable is a distributed storage system for managing structured data that is designed t o scale

to a very large size: petabytes of data across thousands of commodity servers. Many projects at

Google store data in Bigtable, including web indexing, Google Earth, and Google Finance. These

applications place very different demands on Bigtab l e, both in terms of data size (from URLs to

web pages to satellite imagery) and latency requirements (from ba ckend bulk processing to real-

time data serving). Despite these varied demands, Bigtable has successfully provided a ﬂexible,

high-performance solution for all of these Google products. In this article, we describe the simple

data model provided by Bigtable, which gives clients dynamic control over data layout and format,

and we describe the design and implementation of Bigtable.

Categories and Subject Descriptors: C.2.4 [Computer Communication Networks]: Distributed

Systems—distributed databases

General Terms: Design

Additional Key Words and Phrases: Large-Scale Distributed Storage

ACM Reference Format:

Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T.,

Fikes, A., and Gruber, R. E. 2008. Bigtable: A distributed storage system for structured data. ACM

Trans. Comput. Syst. 2 6 , 2, Article 4 (June 2008), 26 pages. DOI = 10.1145/1365815.1365816.

http://doi.acm.org/10.1145/1365815.1365816.

This article was originally published as an award paper in the Proceedings of the 7

Symposium

on Operating Systems Design and Implementation [Chang et al. 2006]. It is being republished here

with minor modiﬁcations and clariﬁcations.

Authors’ address: Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA 94043; email: {fay,

jeff, sanjay, wilsonh, kerr, m3b, tush a r, ﬁkes, gruber}@google.com.

Permission to make digita l or hard copies of part or all of th i s work for personal or classroom

use is granted without fee provided that copies are not made or distributed for proﬁt or direct

commercial advantage and that copies show this notice on the ﬁrst page or initi a l screen of a

display along with the full citation. Copyright s for components of this work owned by others than

ACM must be honored. Abstracting with credits is permitted. To copy otherwise, to republish, to

post on servers, to redistribute to lists, or to use any component of this work in other works requires

prior speciﬁc permission and/or a fee. Permissions may be requested from the Publications Dept.,

ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or

permission@acm.org.

 2008 ACM 0734-2071/2008/06-ART4 $5.00 DOI: 10.1145/1365815.1365816. http://doi.acm.org/

10.1145/1365815.1365816.

ACM Transactions on Computer Systems, Vol. 26, No. 2, Art icle 4, Pub. date: June 2008.

4: 2 · F. Chang et al.

1. INTRODUCTION

Beginning in late 2003, we designed, implemented, and deployed a distrib-

uted storage system for managing structured data at Go ogle called Bigtable.

Bigtable is designed to reliably scale to petabytes of data and thousands of ma-

chines. Bigtable has achieved several go als: wide applicability, scalability, high

perform ance, and high availability. Bigtable is used by more than sixty Google

products and projects, including Goog le Analytics, Google Finance, Orkut, Per-

sonalized Search, Writely, and Google Earth. These products use Bigtable for a

variety o f demanding workloads, which range from throughput-oriented batch-

processing jobs to latency -sensitive servin g of data to end users. The Bigtable

clusters used by these products span a wide range of conﬁgurations, from a

handful to tho usands of servers, and store up to several hundred terabytes

of data.

In many ways, Bigtable resembles a database: it shares many im plemen-

tation strategies with d atabases. Parallel databases [DeWitt and Gray 1992]

and main-memory databases [DeWitt et al. 1984] have achieved scalability

and high performance, but Bigtable provid es a different interface than such

systems. Bigtable does no t support a f ull relational data model; instead, it pro-

vides clients with a simple data model that supports dynamic control ov er d ata

layout and format, and allows clients to reason about the locality properties of

the data represented in the under lying storag e. Data is indexed using row and

column n ames that can be arbitrary strings. Big table also treats data as unin-

terpreted strings, although clients often serialize various forms of structured

and semi-structured data into these strings. Clients can control the locality of

their d ata through careful choices in their schemas. Finally, Bigtable schema

parameters let clients dynamically control whether to serve data out of mem-

ory or from disk.

Section 2 describes the d ata model in more detail, and Section 3 provide s an

overview of the client API. Se ction 4 brieﬂy describes the underlying Google

infrastructure on which B igtable depends. Section 5 describes the fun damen-

tals of the Bigtable implementation, and Section 6 describes some of the re-

ﬁnements that we made to improv e Bigtable’s performance. Section 7 provides

measurements of Bigtable’s performance. We describe several examples of how

Bigtable is used at Google in Section 8, and discuss some lessons we learned in

designing and supporting Bigtable in Section 9. Finally, Section 10 describes

related work, and Section 11 presents our conclusions.

2. DATA MODEL

A Bigtable cluster is a set of processes that run the Bigtable software. Each

cluster serves a set of tables. A table in Big table is a sparse, distributed, per-

sistent m ultidimensional sorted map. Data is organized into three dimensions:

rows, columns, and timestamps.

(row:string, column:string, time:int64) → string

We refer to the storage referenced by a particular row key, column key, and

timestamp as a c e ll. Rows are grouped together to form the unit o f load

ACM Transactions on Computer Systems, Vol. 26, No. 2, Article 4, Pub. date: June 2008.

Bigtable: A Distributed Storage System for Structured Data · 4: 3

Fig. 1. A slice of an exa mple table that stores Web pages. The row name is a reversed URL. The

contents column family contains the page contents, and the anchor column family contains the

text of any anchors that reference the page. CNN’s home page is referenced by both t he Sports

Illustrated and the MY-look home pages, so the row contains columns named anchor:cnnsi.com

and anchor:my.look.ca. Each anchor cell has one version; the contents column has three versions,

at timestamps t

, t

, and t

balancing, and column s are grouped together to form the unit of access control

and resource accounting.

We settled on this data model after examining a variety of potential uses of

a Bigtable-like system. Consider on e concrete example that drove many of our

design decisions: a copy of a large collection of web pages and related in forma-

tion that could be used by many different projects. Let us call this p articular

table the Webtable. In Webtable, we wou ld use URLs as row keys, various as-

pects o f web pages as column names, and store the contents of the web pages

in the contents: column under the timestamps when they were fetched, as

illustrated in Figure 1.

Rows. Bigtable maintains data in lexicographic order by row key. The row

keys in a table are arbitrary strings (currently up to 64KB in size, although

10-100 bytes is a typical size fo r most of o ur users). Every read or write of

data und er a single row key is serializable (regardless of the number of dif fer-

ent columns being read or written in the row), a design decision that makes

it easier for clients to reason about the system’s behavior in the presence of

concurrent updates to the same row. In other words, the row is the unit of

transactional consistency in Bigtable, which does not currently support trans-

actions across rows.

Rows with consecutive keys are grouped into tablets, which form the unit

of distribution and load balancing. As a result, reads o f short row ranges

are efﬁcient and typically require communication with only a small number

of machines. Clients can exploit this property by selecting their row keys so

that they get good locality for their data accesses. For example, in Webtable,

pages in the same domain are grouped together into contiguous rows by

reversing the hostname components of the URLs. We would store data for

maps.google.com/index.html under the key com.google.maps/index.html. Stor-

ing pages from the same domain near each other makes some host and domain

analyses more efﬁcient.

Columns. Column keys are grouped into sets called column families, w hich

form the unit of access control. All d ata stored in a column family is usually

of the same type (we compress d ata in the same column family together). A

column family must be created explicitly before data can be store d under any

ACM Transactions on Computer Systems, Vol. 26, No. 2, Art icle 4, Pub. date: June 2008.

4: 4 · F. Chang et al.

column key in that family. After a family has been cre ated, any column key

within the family can be used: data can be stored under such a column key

without affecting a table’s schema. It is our intent that the number of distinct

column families in a table be small (in the hundreds at most), and that families

rarely change during operation; this limitation keeps widely shared metadata

from being too large. In contrast, a table may have an unbounded number

of columns.

Entire column families may be deleted by changing a table’s schema, in

which case the data stored under any colu mn key s in that family is deleted.

Since Bigtable d oes not support transactions across multiple rows, however,

the data stored under a particular c olumn key cannot be deleted atomically if

it resides in multiple rows.

A column key is named using the fo llowing syntax: family:qualiﬁer. C olumn

family names must be pr in table, but qualiﬁers may be arbitrary strings. An

example column family for Webtable is language, w hich stores the language in

which a we b page was written. We use only one column key with an empty

qualiﬁer in the language family to store e ach web page ’s language ID. Another

useful column family for this table is anchor; each column key in this family

represents a single anchor, as shown in Figure 1. The qualiﬁer is the n ame of

the referring site; the cell contains the text associated with the link.

Access control an d both disk and mem ory accounting are performed at the

column-family level. In our Webtable example, the se controls allow us to man -

age several different types of app lications: some that add new base data, some

that read the base data and create derived column families, and some that

are only allowed to view existing d ata (and possibly not even to view all of the

existing families for privacy re asons).

Timestamps. Different cells in a table can con tain multiple versions of the

same data, where the versions are indexed by timestamp. Bigtable timestamps

are 64-bit integers. They can be assigned implicitly by Bigtable, in which case

they represent “real time” in microseconds, or they can be assigned explicitly

by client applications. Applications that need to avoid collisions must gener-

ate unique timestamps themselves. Different versions of a cell are stored in

decreasing timestamp order, so that the most recent versions can be read ﬁrst.

To make the manag ement of versioned data less onerous, we support two

per-column-family settings that tell Bigtable to garbage-collect v ersioned data

automatically. The client can spec ify either that only the last n versions of data

be kept, or that only new-enough versions be kept (e.g., only keep values that

were written in the last seven days).

In our Webtable example, we can set the timestamps of the crawled pages

stored in the contents: column to the times at w hich these page versions were

actually crawled. The garbage-collection mechanism described above en ables

us to tell Bigtable to keep only the most rece nt three versions of every page.

ACM Transactions on Computer Systems, Vol. 26, No. 2, Article 4, Pub. date: June 2008.

Bigtable: A Distributed Storage System for Structured Data · 4: 5

Fig. 2. Writing to Bigtable.

Fig. 3. Reading from Bigtable.

3. API

The Bigtable API provides functions for creating and deleting tables and col-

umn families. It also provides functions for changing cluster, table, and column

family metadata, such as acc ess control rights.

Client applications can write or delete v alues in Bigtable, look up values

from individual rows, or iterate over a subset of the data in a table. Figure 2

shows C++ c ode that uses a RowMutation abstraction to perform a series of

updates. (Irrelevant details were elided to keep the example sho r t.) The call

to Apply performs an atomic mutation to the Webtable: it adds one anchor to

www.cnn.com and deletes a different anchor.

Figure 3 shows C++ code that uses a Scanner abstraction to iterate over

all anchors in a particular row. Clients can iterate over multiple colu mn fam-

ilies, and there are several mechanisms for limiting the rows, columns, and

timestamps traversed by a scan. For example, we could restrict the scan

above to only produce anchors whose columns match the regular expression

anchor:*.cnn.com, or to only produce anchors whose timestamps fall within ten

days of the current time.

Bigtable supports several other features that allow the user to manipulate

data in more complex ways. First, Bigtable supports single-ro w transactions,

ACM Transactions on Computer Systems, Vol. 26, No. 2, Art icle 4, Pub. date: June 2008.

评论收藏

内容反馈

m0_64606798

粉丝: 0
资源: 1

01-Google三大论文阅读.rar

谷歌三大论文.rar

Google三大论文

Google 三大论文中文版

毕设-高校毕业论文管理系统小程序-源码-LW-PPT.rar

GoogLeNet论文资料共3个文档 1-原版论文pdf-2-中文翻译pdf-3-中英文翻译对照pdf.rar

spanner-Pregel-Dremel-Caffeine.rar

NLP-Word2Vec.rar

Google_三大论文中文版

谷歌三篇论文.rar

HBase-2.2.0.rar

SCI-HUB EVA.rar

281-毕设-ssm家庭食谱管理系统-论文-源码-视频讲解-LW-PPT.rar

277-毕设-jspSSM的药品销售配送网站系统-论文-源码-视频讲解-LW-PPT.rar

Google三大论文中文版

谷歌：一篇论文，让研究者吃我三份安利.rar

ExpressionRecognition-master.rar

021jspm网上电子书店.rar

022jspm物业管理系统.rar

基于QT_c++的google地图实现源码论文ppt毕业设计.rar

最新资源