-
Notifications
You must be signed in to change notification settings - Fork 2
Bigtable
A Bigtable is a sparse, distributed, persistent, multi-dimensional sorted map.
SSTable: a persistent, ordered immutable map from keys to values (indexed). To locate a key, two binary searches are needed. One is for locating the block. Another is for locating the key in the block.
Lock service:
- Ensure that there is at most one active master at any time
- Store the bootstrap location of Bigtable data
- Discover tablet servers and finalize tablet server deaths
- Store schema
- Store access control lists
Master
- Assigning tablets to tablet servers
- Detecting the addition and expiration of tablet servers
- Balancing the tablet-server load
- Garbage collection of files in GFS
Master keep the following data in its memory:
- All tablets
- All tablet servers
- The assignments from tablets to tablet servsers
Tablet server
- Handle reads and writes
- Tablet split
Bigtable handles table split/merge in a way similar to B-Tree.
Tablet location is a three-level hierarchy analogous to a B+tree index in a database system
row_key = table_name + end_row_key. Capacity computation: - rows_per_tablet = 128M / 1K = 2^17 - tablet_count = 2^17 * 2^ = 2^34 - byte_count = 2^34 * 128M = 2^34 * 2^27 = 2^61
Each tablet contains keys in the range of (prev-tablet-endRowKey,endRowKey].
HBase region contains keys in the range of [startKey, endKey). Refer to
61. Catalog Tables and
HRegionInfo
Javadoc
for details. Cockroach only contains endKey. Keys in a single CockroachDB range
is the range of (prev-range-endKey, endKey]. See CockroachDB
design for
details.
Tablet location caching is similar to B+tree index caching in a database.
- 3 round-trips if cache is empty
- Fetch Chubby File
- Fetch Root tablet
- Fetch METADATA tablet
- 6 round-trips if cache is stale
- Read from user tablet (miss: the user table does not contain the row)
- Read from METADATA tablet (miss: the METADATA tablet does not contain the row)
- Read from Root tablet
- If the row is can't be found in Root tablet, skip step-4 and step-5.
- If Root tablet can't found, go to step-4.
- Fetch Chubby File
- Fetch Root tablet
- Fetch METADATA tablet
METADATA tablets are prefetched.
Tablet assignment changes:
- Tablet merge
- Tablet movement for load balancing or tablet server failures
- Tablet split
Only 3 is initialized by a tablet server. A tablet server can do 1 and 2 since 1 and 2 needs involvements from more than one tablet server. The master can also do 3. But in order to minimize load on the master, 3 is initialized by a tablet server.
Why does the master periodically ask each tablet server for the status of its lock? Why not let master only monitor the server file in Chubby? The lock on the server file held by tablet server will expire if something is wrong with the tablet server. So it is enough for the master to periodically check the lock on the server file. In this way, master will only interact with tablet servers for tablet assignment changes. With tablet assignment changes, no interaction between the master and tablet servers. Maybe the approach in the paper is for reducing workloads on Chubby.
Conditions to serving data for a tablet server:
- The tablet server's server file exists
- Holding the exclusive lock on the server file
Why will a tablet server attempt to reacquire an exclusive lock on its file as long as the file exist? Let the tablet server has a chance to compete with the master to acquire the exclusive lock. If the tablet server wins the lock, it can resume its functionality. It is better not to re-assign the tablets.
The tablet server needs to storage the information of tablets on durable storage. Otherwise, how can it commit a split?
Tablet server metadata stored in METADATA table:
- A list of SSTables
- A set of redo points
Common log stores redo log records. Undo log records are unneeded since only single-row transactions are provided. For the same reason, Bigtable provides strict serializability.
- Scan Cache:
- Block Cache: If the tablet server is collocated with a GFS chunkserver, there is already a block buffer in Linux. So there is the double-caching problem.
GFS replication level is not specified in the test setup. Google Bigtable does not talk about collocating tablet servers with GFS chunkservers. But HBase does it to improve performance.
Both GFS and Bigtable perform load balancing.
- GFS: chunk level
- Bigtable: tablet level
For a good load balancing, both replication and sharding mechanisms should be provided.
- Why duplicated log entries are generated during log switching?
Duplicates is possible GFS record append even w/o log switching. The tablet server will also cause duplicated log entries.A GFS primary finishes the record append. And it is sending response to the tablet server. But the tablet server thinks that the GFS primary is responding too slow. So the tablet server switches to the other GFS server which hosts the other commit log.
There do exist some consistency problem if the tablet server performs some GFS operations concurrently:
- Concurrent writes to the commit log.
- Concurrent writes to the SSTable.
But as far as I can imagine, such kind of usages are meaningless to Bigtable. So they are not a problem.
- How does Bigtable ensure not to read stale GFS data? One tablet is owned by one tablet server. If anything GFS writes, the tablet server will be informed. w/o a write failure, even a GFS replica is partitioned. The tablet server is also guaranteed to see updated data.