baijia - papers and notes

Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., and Gruber, R. E. Bigtable: a distributed storage system for structured data. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (Seattle, Washington, November 06 - 08, 2006). 205-218.

* * *

Bigtable, a key component in Google's software hierarchy, constructs an abstraction similar to tables above the underlying file system (GFS).

To handle large data sets, Bigtable partitions data into shards managed by tablets. The data shards are stored as SSTables (String to String tables) on GFS. Chubby (http://baijia.info/showthread.php?tid=59) manages some metadata (schemas) and arbitrates a few crucial concurrent operations. A "cluster management system for scheduling jobs" controls the computation tasks in Bigtable operations. This cluster management system should have a similar purpose to the Workqueue mentioned in Sawzall (http://baijia.info/showthread.php?tid=60).

Bigtable supports atomicity on a single row, but not complex multirow operations, as discussed in Section 3.

Table 2 lists a few Bigtable instances, with the largest being a 800TB table for Crawl.

PDF from USENIX: http://www.usenix.org/events/osdi06/tech...http://www.usenix.org/events/osdi06/tech/chang

@inproceedings{chang06bigtable,
author = {Chang, Fay and Dean, Jeffrey and Ghemawat, Sanjay and Hsieh, Wilson C. and Wallach, Deborah A. and Burrows, Mike and Chandra, Tushar and Fikes, Andrew and Gruber, Robert E.},
title = {Bigtable: a distributed storage system for structured data},
booktitle = {OSDI '06: Proceedings of the 7th symposium on Operating systems design and implementation},
year = {2006},
isbn = {1-931971-47-1},
pages = {205--218},
location = {Seattle, Washington},
publisher = {USENIX Association},
address = {Berkeley, CA, USA},
}

Victor ZXF will present this paper.

The idea is simple and built on GFS management. (which maintained data by few chunks and depend one master to get the location information, though in GFS master work as mapping) It is key-value store. Every data record is indexed by "row", "column" and "timestamp". And in the global view, Bigtable maintains data in lexicographic order by row key. Each row range is called a tablet. Then the row range can be adjusted by load balancing. In practical implementation, they use a three-level hierarchy B+ tree to store tablet location information. Chubby file -> root tablet -> other metadata tablets -> user tablets. One great point for Bigtable is its scalability. As we can see, when data records increased in certain row range, Bigtable can adjust the range dynamically, so that the size grows when loads increase, and go down when loads decrease. Personally, I think google docs is a good example that use Bigtable as storage. one file in Google docs correspond to one row, one column, and each repository with timestamp, corresponds to different records with t(i) in that row. So when we want to achieve the previous docs, it is very convenient and fast.

(10-31-2009 01:18 AM)laxab Wrote: [ -> ]... google docs is a good example that use Bigtable as storage. one file in Google docs correspond to one row, one column, and each repository with timestamp, corresponds to different records with t(i) in that row. So when we want to achieve the previous docs, it is very convenient and fast.

There might be cases when we need multiple-row semantics even if we store each file in one row. For example, if we send multiple files to a folder (or give them a common tag), it would be confusing if only part of the files' properties are changed.

I'm Jiangchuan Zheng(10824179), I would like to present this paper for comp6111A.