Bigtable: A Distributed Storage System for Structured DataSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Bigtable: A Distributed Storage System for Structured DataWritten By:Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber, Google, Inc. Presented By:Manoher Shatha &Naveen Kumar RatkalOverviewOverview Introduction Data Model API Building Blocks Implementation Refinements Real Applications Conclusion DiscussionIntroductionIntroductionBigtable: It is a distributed storage system for managing structured data that is designed to scale to a very large size: i.e. petabytes of data across thousands of commodity servers.Why not Commercial DB?No commercial DB is big enough to store petabytes of data, Even though such DB exists it will be very costly.Low level storage optimizations are difficult to perform on Commercial DB. With good design and implementation Bigtable achieved wide applicability, scalability and high availability.Bigtable is used by more than sixty Google products and projects.Database Vs BigtableDatabase Vs BigtableFeatures Database BigtableSupports Relational DB ? Most of the databases. NoAtomic Transactions All are atomic transactions.Limited.Data Type Supports many data types.String of characters (un-interpreted string).ACID Test Yes NOOperations Yes (insert, delete, update etc….)Yes (read, write, update, delete etc…)Data ModelData ModelFigure 1: Web Table“Contents:”“anchor:cnnsi.com”“anchor:my.look.ca”“com.cnn.www”“CNN” “CNN.com”t3t5t6t9 t8<html><html><html><html> Bigtable is a multidimensional stored map. Map is indexed by row key, column key and timestamp. i.e. (row: string , column: string , time:int64 ) String. Rows are ordered in lexicographic order by row key. Row range for a table is dynamically partitioned, Each row range is called “Tablet ”. Columns: syntax is family : qualifier. Cells can store multiple version of data with timestamps.APIAPIWriting to Bigtable// Open the tableTable *T = OpenOrDie("/bigtable/web/webtable");// Write a new anchor and delete an old anchorRowMutation r1(T, "com.cnn.www");r1.Set("anchor:www.c-span.org", "CNN");r1.Delete("anchor:www.abc.com");Operation op;Apply(&op, &r1);Taken From paperAPI Contd…API Contd…Reading from BigtableScanner scanner(T);ScanStream *stream;stream = scanner.FetchColumnFamily("anchor");stream->SetReturnAllVersions();scanner.Lookup("com.cnn.www");for (; !stream->Done(); stream->Next()) {printf("%s %s %lld %s\n",scanner.RowName(),stream->ColumnName(),stream->MicroTimestamp(),stream->Value()); }Taken From paperBuilding BlocksBuilding BlocksGFS Uses Google File system to store data.Cluster Management Google cluster management system manages Bigtable’s clusterChubby Its is a distributed lock server. Allows multi-thousand node Bigtable cluster to stay coordinated. Five replicas, one is elected as master.SSTablesSSTables This is the underlying file format used to store Bigtable data. SSTables are immutable. If new data is added, a new SSTable is created. Old SSTable is set out for garbage collection.Figure: SSTable Figure : From Erik Paulson presentation64KBlock64KBlockIndexSSTableTablet & TableTablet & Table Tablets contains some range of rowsFigure : TableFigure : From Erik Paulson presentation64KBlock64KBlockIndexSSTable64KBlock64KBlockIndexSSTableTabletStart : aardvark End : apple64KBlock64KBlockIndexSSTable64KBlock64KBlockIndexSSTable64KBlock64KBlockIndexSSTableTabletaardvark appleTabletapple_two boatFigure : Tablet Bigtable contains tables, Tables contains set of tablets and each tablet contains set of rows (100-200MB).ImplementationImplementation Bigtable components Library linked into every client. Master Server. Tablets Server. Tablet server can be added dynamically based on the workload. Master assigns tablets to tablet server. Master is lightly loaded.Tablet LocationTablet LocationChubby FileRoot tablet(1at METADATA tablet)Other METADATA tabletsUser Table 1User Table NFigure : Tablet Location HierarchyTablet AssignmentTablet Assignment Each Tablets Server is given a tablet for serving client requests. Master keeps track of the tablet server (RPC) to assign the tablet. Chubby directory is used to acquire lock by the tablet server. If Tablet server terminates, it release the lock on the file. Status is sent to Master by tablet server.How Does Master comes to know about Tablets, Tablet servers? Master acquires unique master lock in chubby. Master scans server directory in chubby to find live servers. Master communicates with each tablet server to get the details. It scans the METADATA table to find the unassigned tablets.Steps are taken from the paper “google bigtable”.Chubby DirectoryAcquires unique lockOnce scanned it will come to know about the live tablet serverCommunicates with all the tablet server to get the details about the tablet they are servingMetadata tableScans the metadata tableMasterTablet ServerTablet Assignment Contd …Tablet Assignment Contd …Tablet ServingTablet Serving Commit log stores the updates that are made to the data. Updates are stored in memtable. Recovery process. Reads/Writes that arrive at tablet server. Is the request Well-formed. Authorization. Chubby holds the permission file. If a mutation occurs it is wrote to commit log and finally a group commit is used.Figure : Tablet Representation.Figure is taken from the paper “google bigtable”.MemoryGFSTablet LogWrite OpRead OpMemtableSSTSST SSTSSTable FilesCompactionCompactionWrite OperationFigure : Minor Compaction. FrozenSSTableMemtableConverted to SSTableFigure : Merging Compaction.SSTSSTableSmall New SSTables Due to minor compaction.New Large SSTablesSSTSSTSST Merging compaction leads to major compaction.RefinementsRefinements<html><html><html><html>“CNN” “CNN.com”“Contents:”“anchor:cnnsi.com”“anchor:my.look.ca”“com.cnn.www”<html><html><html><html>“CNN” “CNN.com”“Contents:”“com.cnn.www”“anchor:cnnsi.com”“anchor:my.look.ca”Locality GroupFigure : From Jeff Dean presentation Multiple column families are grouped into locality group. Efficient reads are done by separating column families. Additional parameters can be specified.Caching for Read PerformanceTwo types
View Full Document
Unlocking...