CS 417: Distributed Systems 11/7/2012 © 2011 Paul Krzyzanowski 1 Distributed Systems 18. BigTable Paul Krzyzanowski [email protected] 1 BigTable • Highly available distributed storage for structured data • Built with structured data in mind – URLs: content, metadata, links, anchors, page rank – User data: preferences, account info, recent queries – Geography: roads, satellite images, points of interest, annotations • Large scale – Petabytes of data across thousands of servers – Billions of URLs with many versions per page – Hundreds of millions of users – Thousands of queries per second – 100TB+ satellite image data 2 Uses • At Google, used for: – Google Analytics – Google Finance – Orkut – Personalized search – Writely – Google Earth & Google Maps – Dozens of others… 3 A big table • BigTable is NOT a relational database • BigTable appears as a large table – “A BigTable is a sparse, distributed, persistent multidimensional sorted map”* *Bigtable: OSDI 2006 “language:” “contents:” com.aaa EN <!DOCTYPE html PUBLIC… com.cnn.www EN <!DOCTYPE HTML PUBLIC… com.cnn.www/TECH EN <!DOCTYPE HTML>… com.weather EN <!DOCTYPE HTML>… sorted Webtable example rows columns 4 Table Model • (row, column, timestamp) → cell contents – Contents are arbitrary strings (arrays of bytes) “language:” “contents:” com.aaa EN com.cnn.www EN com.cnn.www/TECH EN com.weather EN sorted Webtable example rows columns <!DOCTYPE html… <!DOCTYPE html… <!DOCTYPE html… <!DOCTYPE html… <!DOCTYPE html… <!DOCTYPE html… t4 t7 t15 t2 t7 t7 versions 5 Tablets: Pieces of a Table • Row operations are atomic • Table partitioned dynamically by rows into tablets • Tablet = range of contiguous rows – Unit of distribution and load balancing – Nearby rows will usually be served by the same server – Accessing nearby rows requires communication with a small # of machines – Select row keys to ensure good locality • E.g., reverse domain names: com.cnn.www instead of www.cnn.com 6CS 417: Distributed Systems 11/7/2012 © 2011 Paul Krzyzanowski 2 Table splitting • A table starts as one tablet • As it grows, it it split into multiple tablets – Approximate size: 100-200 MB per tablet by default “language:” “contents:” com.aaa EN <!DOCTYPE html PUBLIC… com.cnn.www EN <!DOCTYPE HTML PUBLIC… com.cnn.www/TECH EN <!DOCTYPE HTML>… com.weather EN <!DOCTYPE HTML>… tablet 7 Splitting a tablet “language:” “contents:” com.aaa EN <!DOCTYPE html PUBLIC… com.cnn.www EN <!DOCTYPE HTML PUBLIC… com.cnn.www/TECH EN <!DOCTYPE HTML>… com.weather EN <!DOCTYPE HTML>… com.wikipedia EN <!DOCTYPE HTML>… com.zcorp EN <!DOCTYPE HTML>… com.zoom EN <!DOCTYPE HTML>… 8 Columns and Column Families • Column Family – Group of column keys – Column family is the basic unit of data access – Data in a column family is typically of the same type – Implementaion compresses data in the same column family • Operations – (1) Create column family – (2) Store data in any key within the family • Column families will typically be small – ≤ hundreds of keys; a table may have an unlimited # • Identified by family:qualifier 9 Column Families: example • Three column families – “language:” – language for the web page – “contents:” – contents of the web page – “anchor:” – contains text of anchors that reference this page. • www.cnn.com is referenced by Sports Illustrated (cnnsi.com) and My-Look (mlook.ca) • The value of (“com.cnn.www”, “anchor:cnnsi.com”) is “CNN”, the reference text from cnnsi.com. “language:” “contents:” anchor:cnnsi.com anchor:mylook.ca com.aaa EN <!DOCTYPE html PUBLIC… com.cnn.www EN <!DOCTYPE HTML PUBLIC… “CNN” “CNN.com” com.cnn.www/TECH EN <!DOCTYPE HTML>… com.weather EN <!DOCTYPE HTML>… sorted 10 Column Families: example “language:” “contents:” anchor:cnnsi.com anchor:mylook.ca com.aaa EN <!DOCTYPE html PUBLIC… com.cnn.www EN <!DOCTYPE HTML PUBLIC… “CNN” “CNN.com” com.cnn.www/TECH EN <!DOCTYPE HTML>… com.weather EN <!DOCTYPE HTML>… Sorted rows column family column family column family row keys 11 Timestamps • Each column family may contain multiple versions • Version indexed by a 64-bit timestamp – Real time or assigned by client • Per-column-family settings for garbage collection – Keep only latest n versions – Or keep only versions written since time t • Retrieve most recent version if no version specified – If specified, return version where timestamp ≤ requested time 12CS 417: Distributed Systems 11/7/2012 © 2011 Paul Krzyzanowski 3 API: Operations on BigTable • Create/delete tables & column families • Change cluster, table, and column family metadata (e.g., access control rights) • Write or delete values • Read values from specific rows • Iterate over a subset of data in a table – All members of a column family – Multiple column families • E.g., regular expressions, such as anchor : * . cnn. com – Multiple timestamps – Multiple rows • Atomic read-modify-write row operations • Allow clients to execute scripts (written in Sawzall) for processing data on the servers 13 Implementation: Supporting Services • GFS – For storing log and data files • Cluster management system – For scheduling jobs, monitoring health, dealing with failures • Google SSTable – Internal file format – Provides a persistent, ordered, immutable map from keys to values – Memory or disk based 14 Implementation: Supporting Services • Chubby – Highly-available & persistent distributed lock (lease) service – Five active replicas; one elected as master to serve requests – Majority must be running – Paxos used to keep replicas consistent – Namespace of files & directories. Each file or directory can be used as a lock • Chubby is used to: – Ensure there is only one active master – Store bootstrap location of BigTable data – Discover tablet servers – Store BigTable schema information – Store access control lists 15 Implementation 1. Many tablet servers – Can be added or removed dynamically – Each manages a set of tablets (typically 10-1,000 tablets/server) – Handles read/write requests to tablets – Splits tablets when too large 2. One master server – Assigns tablets to tablet server – Balances tablet server load – Garbage collection
View Full Document
Unlocking...