google bigtable教学文稿.ppt

Google Bigtable
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber
Google, Inc.
OSDI 2006
Adapted by S. Sudarshan from a talk by
Erik Paulson, UW Madison
1
Google Scale
Lots of data
Copies of the web, satellite data, user data, email and , Subversion backing store
Many ing requests
mercial system big enough
Couldn’t afford it if there was one
Might not have made appropriate design choices
Firm believers in the End-to-End argument
450,000 machines (NYTimes estimate, June 14th 2006
2
Building Blocks
Scheduler (Google WorkQueue)
Google Filesystem
Chubby Lock service
Two other pieces helpful but not required
Sawzall
MapReduce (despite what the says)
BigTable: build a more application-friendly storage service using these parts
3
Google File System
Large-scale distributed “filesystem”
Master: responsible for metadata
Chunk servers: responsible for reading and writing large chunks of data
Chunks replicated on 3 machines, master responsible for ensuring replicas exist
OSDI ’04 Paper
4
Chubby
{lock/file/name} service
Coarse-grained locks, can store small amount of data in a lock
5 replicas, need a majority vote to be active
Also an OSDI ’06 Paper
5
Tablet
Contains some range of rows of the table
Built out of multiple SSTables
Index
64K block
64K block
64K block
SSTable
Index
64K block
64K block
64K block
SSTable
Tablet
Start:aardvark
End:apple
8
Table
Multiple tablets make up the table
SSTables can be shared
Tablets do not overlap, SSTables can overlap
SSTable
SSTable
SSTable
SSTable
Tablet
aardvark
apple
Tablet
apple_two_E
boat
9
Finding a tablet
Stores: Key: table id + end row, Data: location
Cached at clients, which may detect data to be incorrect
in which case, lookup on hierarchy performed
Also prefetched (for range queries)
10