Contents

1 Google

[1] Bigtable: A Distributed Storage System for Structured Data

[2] Pregel: A System for Large-Scale Graph Processing

[3] PageRank  vs HITS

[4]

2 Yahoo

[1] PNUTS: Yahoo!’s Hosted Data Serving Platform  

[2] Data Challenges at Yahoo!

[3] Cloud Data Management @ Yahoo!

 

3 Microsoft

[1] Scale-Out Beyond Map-Reduce

[2]

 

 

1 Google三驾马车

beamer_bigtable_osdi06.pdf 

 

[1-] 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, Robert E. Gruber

OSDI 2006

 

Abstract
 Bigtable is a distributed storage system for managing structured data that is designed to 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 Bigtable, both in terms of data size (from URLs to web pages to satellite imagery) and latency requirements
(from backend 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 paper 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.

1 Introduction

 

 the organization of this paper:

 1) Section 2 describes the data model in more detail

 2) Section 3 provides an overview of the client API.

 3) Section 4 briey describes the underlying Google infrastructure on which Bigtable depends.

 4) Section 5 describes the fundamentals of the Bigtable implementation

 5) Section 6 describes some of the renements that we made to improve Bigtable's performance.

 6) Section 7 provides measurements of Bigtable's performance.

 7) Section 8 describe several examples of how Bigtable is used at Google

 8) Section 9 discuss some lessons we learned in designing and supporting Bigtable

 9) Finally, Section 10 describes related work

 10) Section 11 presents our conclusions.

 

2 Data Model

 

3 API

4 Building Blocks

 GFS: the distributed Google File System

5 Implementation

 three major components:
 -- a library that is linked into every client,

 -- one master server,

 -- many tablet servers.

5.1 Tablet Location
 a three-level hierarchy analogous to that of a B+-tree to store tablet location information (Figure 4).

       

 

5.2 Tablet Assignment

5.3 Tablet Serving

 The persistent state of a tablet is stored in GFS, as illustrated in Figure 5.

     

5.4 Compactions

 

6 Renements

 

7 Performance Evaluation

8 Real Applications

 

9 Lessons

 several interesting lessons:

 --

 

10 Related Work

11 Conclusions

 

 

 

 

 

[2-] Pregel: A System for Large-Scale Graph Processing

Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski

SIGMOD’10, June 6–11, 2010, Indianapolis, Indiana, USA.

 

ABSTRACT
 Many practical computing problems concern large graphs. Standard examples include the Web graph and various social networks. The scale of these graphs|in some cases billions of vertices, trillions of edges|poses challenges to their ecient processing. In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology. This vertexcentric approach is exible enough to express a broad set of
algorithms. The model has been designed for ecient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier. Distributionrelated details are hidden behind an abstract API. The result is a framework for processing large graphs that is expressive and easy to program.

 

Keywords: Distributed computing, graph algorithms

 

1. INTRODUCTION

 

 The rest of the paper is structured as follows.

 1) Section 2 describes the model.

 2) Section 3 describes its expression as a C++ API.

 3) Section 4 discusses implementation issues, including performance and fault tolerance.

 4) Section 5 present several applications of this model to graph algorithm problems

 5) Section 6 present performance results.

 6) Finally, Sect.7 discuss related work and future directions.

2. MODEL OF COMPUTATION

 

 

 Pregel  a system for large-scale graph processing.pdf

 PPT: 20100707_Pregel.ppt

 

[3-] PageRank vs HITS

 

 

可参考：PageRank 彻底解说 中文版(www)    http://www.kreny.com/pagerank_cn.htm

                wiki

 

 

 

the n-by-n connectivity matrix G   the transition probability matrix of the Markov chain A

 

MATLAB 实现： 12 pagerank.pdf

Origin paper:   The PageRank Citation Ranking.pdf

Netlogo Model Library: PageRank

 

 

 

2 Yahoo

[1] PNUTS: Yahoo!’s Hosted Data Serving Platform  

Brian F. Cooper, Raghu Ramakrishnan, Utkarsh Srivastava, Adam Silberstein,Philip Bohannon, HansArno
 Jacobsen, Nick Puz, Daniel Weaver and Ramana Yerneni
VLDB ‘08
 
ABSTRACT
 We describe PNUTS, a massively parallel and geographically distributed database system for Yahoo!’s web applications. PNUTS provides data storage organized as hashed or ordered tables, low latency for large numbers of concurrent requests including updates and queries, and novel per-record consistency guarantees. It is a hosted, centrally managed, and geographically distributed service, and utilizes automated load-balancing and failover to reduce operational complexity. The first version of the system is currently serving in production. We describe the motivation for PNUTS and the design and implementation of its table storage and replication layers, and then present experimental results.

1. INTRODUCTION
  web applications
 
 The foremost requirements of a web application:
 -- Scalability.
 -- Response Time and Geographic Scope.
 -- High Availability and Fault Tolerance.