Does my failure on Leetcode 150 easy level algorithms has a name?

Oct. 13, 2018

Introduction

It is time for me to spend 10 to 30 minutes to go over those failed submissions on 150 easy level algorithms. I like to identify what I should be careful, the growth pain of the algorithm and data structure problem solving. Like a baby growing up in the first year, there are numerous stages an infant can continuously develop. This is the first time I intensely work with the online judge, and work with those problem statements and problem setters, and also work with those hidden test cases which may never be released but may explode any time.

Common mistakes 

I make common mistakes very often. I just could not believe that I learn so much and so quickly through those easy level algorithms.

Sometimes the algorithms are labelled by the mistake as an easy level, but then I just fell in love with the algorithms and continue to learn from my experience. I choose the algorithm to be my mock interview algorithms more than five times.

Most surprisingly I learn a few solution with such elegant solution. I just could not believe that I need to refine my thinking process, and then rework the problem after my first submission by working independently.

I will list over 5 mistakes and lessons I learn in the following later.

687. Longest univalue path with design flaw, pass 43 out of 68 test cases
687. Longest univalue path copy the idea from most popular post

Array easy level algorithms (solved 44, shared 24)

867. Transpose matrix - pass 29/36 test cases

Math easy level algorithms (solved 27/ 32, shared 12)

415. Add Strings recursive version - memory limit exceeded
415. Add Strings Iterative solution - learn to use for loop creatively

String easy level algorithms (solved 32, shared 15) 

680. Valid Palindrome II 418/460 test cases passed Time limit exceeded
686. Repeated String Match memory limit exceeded for last test case
686. Repeated String Match memory limit exceeded for last test case

Hashtable easy level algorithm (solved 25, shared 21)

204. Count Primes verbose code
204. Count Primes elegant version

242. Valid Anagram One more mistake to remind me to work on easy level

500. Keyboard Row do it myself
500. Keyboard Row use HashSet API IsSubsetOf

645. Set Mismatch first submission - XOR
645. Set Mismatch elegant one using XOR two places
645. Set Mismatch use bit manipulation trick

720. Longest Word in Dictionary use hashset
720. Longest Word in Dictionary use Trie data structure
720. Longest Word in Dictionary use Trie data structure
720. Longest Word in Dictionary use Queue data structure
720. Longest Word in Dictionary use recursive function

Medium level (solved 53, shared 4)


915. Partition Array into Disjoint Intervals use three iterations
915. Partition Array into Disjoint Intervals one pass idea discuss
916. Word Subsets using counting sort
916. Word Subsets discuss
918. Maximum Sum Circular Subarray pass 98/108, in the contest
918. Maximum Sum Circular Subarray after the contest, working code
919. Complete Binary Tree Inserter O(1) insert
919. Complete Binary Tree Inserter Using Queue
919. Complete Binary Tree Inserter Using Queue
923. 3Sum With Multiplicity
923. 3Sum With Multiplicity dynamic programming solution 

Medium level tree algorithms (solved 14, total 39, shared 12)

102. Binary Tree Level Order Traversal submitted in 2015
102. Binary Tree Level Order Traversal submitted in 2018

Hard level (solved 33, shared 5)

37. Sudoku Solver
76. Minimum Window Substring One thing a time
85. Maximal Rectangle
239. Sliding Window Maximum optimal solution using LinkedList
239. Sliding Window Maximum All submissions, SortedSet, timeout

301. Remove Invalid Parentheses 1 upvotes!
301. Remove Invalid Parentheses 3 upvotes
301. Remove Invalid Parentheses

A name

I like to give those mistakes a name to encourage myself to work hard, work on more algorithm problem solving.

The name is called in Chinese, "这需要托大家的福，托大家的福就要吃百家饭、穿百家衣". The custom is to help raise a healthy child to eat and wear in so many families. The link is here.

Leetcode discuss: 465. Optimal Account Balancing

July 5, 2022

Here is the link. 

C# | Quick learner | DFS, backtracking | GraceMeng top voted

July 4, 2022
Introduction
It is ad hoc to learn one algorithm from top voted discuss posts from graceMeng. I chose to study this hard level algorithm. I just quickly read the analysis and then studied one of C# discuss post.

GraceMeng -> top voted discuss algorithms
Leetcode newly release product feature: Leetcode profile -> discuss -> Most voites -> top 15 algorithms (https://leetcode.com/GraceMeng/). I choose to study those algorithms and figure out what is the secret in the analysis to win so many up-votes.

Ideas | Analysis from graceMeng | Top-voted one
I like to learn how to write a good analysis from graceMeng - https://leetcode.com/problems/optimal-account-balancing/discuss/130895/Recursion-Logical-Thinking.

? what does it mean to settle the debt
nobody owes others

? how do we represent how much money a person owes others
We build current debt situation debt[], e.g. debt[i] = 10 means a person owes others 10

? how do we settle one's debt
assuming [0, curId - 1] has been settled,
for debt[curId],
any curId + 1 <= i <debt.length such that debt[i] * debt[curId] < 0 can settle it

state
The next account to balance, curId, can uniquely identify a state
state function
state(debt[], curId) is the minimum transactions to balance debts[curId...debtLength - 1] such that debts[0...curId-1] are balanced.
goal state
state(initial debt[], 0)
state transition
now: state(debt[], curId)
next: state (debt[] after balance curId, curId + 1)

state(debt[], curId) = 1 + min(state (debt[] after balance curId, curId + 1))

Note

• How do we decide who can balance the account of curId?
  There are many people who can balance curId's account -- person i behind curId with debt[i] * debt[curId] < 0.

C# code implmentation -> backward -> Analysis
I think that it is easy for me to understand the algorithm by reading the following C# code. The DFS search and also brute force comparison among all options in order to get the minimum transaction.

I like to talk about a test case, and then discuss my concerns. Through the discussion, I can learn how to prototype the algorithm to this classical approach.

Example 1:
Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

By going through transactions, there are three people, [0, 1, 2].
Next it is to calculate debt[] for each person.
First transaction: [0, 1, 10], we have the following facts:
debt[0] = -10,
debt[1] = 10

Second transaction: [2, 0, 5], and then we have updates:
debt[2] = -5
debt[0] = -10 + 5 = 5.

So debt[] = int[]{5, 10, -5}

Next is the exercise how to apply DFS search and get minimum transaction.
It is easy to figure out one of minimum count (minimum count is 2) of transactions is to let person 1 to pay person 0 with 5 dollars, and then person 1 to pay person 2 5 dollars.

Now my suggestion is to go back to the above analysis, and then combine the test case I just warm up, and then try to figure out what is truth in the above analysis.

Leave for my practice privately if I have time.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _465_optimal_account_balancing
{
    class Program
    {
        static void Main(string[] args)
        {
            var transactions = new int[2][];
            transactions[0] = new int[] { 0, 1, 10 };
            transactions[1] = new int[] { 2, 0, 5 };

            var result = MinTransfers(transactions);
            Debug.Assert(result == 2);
        }

        /// <summary>
        /// code study
        /// https://leetcode.com/problems/optimal-account-balancing/discuss/130895/recursion-logical-thinking
        /// One of replies - C# solution shared by pantigalt
        /// </summary>
        /// <param name="transactions"></param>
        /// <returns></returns>
        public static int MinTransfers(int[][] transactions)
        {
            var debt = CreateDebtTable(transactions);
            return CalculateMinTransfers(0, debt);
        }

        /// <summary>
        /// It is hard for me to figure out, so I just learn quickly by studying GraceMeng's one
        /// </summary>
        /// <param name="curId"></param>
        /// <param name="debt"></param>
        /// <returns></returns>
        private static int CalculateMinTransfers(int curId, int[] debt)
        {
            // skip all account with zero balance
            while (curId < debt.Length && debt[curId] == 0)
            {
                curId++;
            }

            // Everyone has zero balance
            if (curId == debt.Length)
            {
                return 0;
            }

            // Everyone before current person has zero balance
            // current person has non-zero balance
            int minTransactions = int.MaxValue;
            for (int i = curId + 1; i < debt.Length; i++)
            {
                // check for opposite signs
                if ((debt[i] ^ debt[curId]) < 0)
                {
                    // modify debt for current person
                    debt[i] += debt[curId];

                    // recursive think -> DFS -> minimum transactions -> ?
                    minTransactions = Math.Min(minTransactions, CalculateMinTransfers(curId + 1, debt) + 1);

                    // restore debt for current person
                    debt[i] -= debt[curId];
                }
            }

            return minTransactions;
        }

        /// <summary>
        /// Lynq expression: 
        /// Dictionary<int, int> -> debts.Select(x => x.Value).ToArray();
        /// </summary>
        /// <param name="items"></param>
        /// <returns></returns>
        private static int[] CreateDebtTable(int[][] items)
        {
            // accumulate debts with original person ids
            var debts = new Dictionary<int, int>();

            foreach (int[] item in items)
            {
                if (!debts.ContainsKey(item[0]))
                {
                    debts.Add(item[0], 0);
                }

                if (!debts.ContainsKey(item[1]))
                {
                    debts.Add(item[1], 0);
                }

                debts[item[0]] += item[2];
                debts[item[1]] -= item[2];
            }

            // we need to return an array with sequential person ids
            return debts.Select(x => x.Value).ToArray();
        }
    }
}

Leetcode discuss: 212. Word Search II

Here is the link. 

C# Trie design challenge and DFS algorithm practice in June 2018

June 16, 2020
It is challenge task to write the depth first search algorithm using Trie data structure. It took me several hours to make it work. I failed three test cases, and then I like to write down my lessons here.

First it is the design of depth first search. The checking of our-of-index-range of the matrix, visited node, child node is not in Trie data structure object are those three important checkings for a complete test.

Second one is to understand Trie data structure. Trie is a recursive data structure, so it is important to identify current node matrix[row][col] with function argument TrieNode parentNode relationship. The design is to pass parentNode which is not null, so the child node may not be in Trie data structure object.

Third one is to write TrieNode Build function to construct a Trie tree object. It is not easy task, so please work on "a", one char word, and it should be two level, parent node is dummy head, and dummy head's child is 'a' instead.

What else can I write down to make this TrieNode class crafting more error-prone?

1. I change for(int i = 0; i < words.Length; i++) to foreach loop to make code clean, no need to use i to do any checking.
2. Dummy head is important, and also understand that the call is passed using parent node;
3. Statement: public TrieNode[] nodes = new TrieNode[26]; each nodes[i] is still null pointer.
4. Remove "iterate.word = word;" outside statement "foreach (char c in word)" in TrieNode class API defintion.
5. GetByIndex API of TrieNode should check pointer null first.

Template of DFS

1. Design a DFS function to search a matrix, please understand DFS and also backtracking.
2. Function name runDFS is good enough, TrieNode parentNode argument should be clearly defined, since current char may not be in Trie object.
3. Put all edge cases in one statement, do not define explanation variable "var visit = board[row][col]" before checking index range and also board's content has not been visited yet.
4. One word in dictionary can be a prefix in another word in dictionary, so it should continue to search. Termination should not put after the word is added to found string.
5. Think about time complexity using Trie compared to HashSet, and practice more often Trie to solve problems.
6. Discuss termination of DFS with interviewer or think about more test cases. It is safe to continue to search if a word is found, let it fall through the checking of index-out-range or char is not in the tree.

Template of TrieNode definition of Build

1. Trie is a recursive data structure, tree data structure;
2. Trie should start from a dummy hand for easy reference;
3. Child node is one of element of TrieNode[26] array
4. Child node is still null pointer even TrieNode[26] is called using statement " ... = new TrieNode();"
5. Clean up TrieNode Build API

Special case: binary tree
To expedite the process to craft a TrieNode class Build API, treat special case a binary tree and see how to make it work; left and right child map to index 0 and 1. If left child exist, then do nothing except going to left child for next iteration. If left child does not exist, then create one first. Go over each word in dictionary, build a binary tree to include all words, assuming that all chars are 'a' or 'b' in those words. Try to go over the following test case 3, build a trie by hand first, and then talk about how to write a trie version with size of 26 array.

For each word in dictionary, go through char by char, and then start from dummy head of Trie object, and then if child node is created then continue, otherwise create the tree object.

Test case Trie
I failed the test case 3, so I like to share this test case.

One word in dictionary can be a prefix in another word in dictionary, so it should continue to search. Depth first search algorithm's termination should not put after the word is added to found string.
In the above test case, "aaa" is the prefix of "aaaa".

Practice talk
I could not perform very well on Amazon code screen this March. The reason is that debugger is disabled, and my design is not relax to allow mistake happen. I write something to remind myself, focus on design when debugging, think about modifying design to make it more robust.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _212_word_search_warmup_June_16_20
{
    class Program
    {
        static void Main(string[] args)
        {
            //RunTestcase1();
            //RunTestcase2();
            RunTestcase3(); 
        }

        public static void RunTestcase1()
        {
            var board = new char[4][];

            board[0] = "oaan".ToCharArray();
            board[1] = "etae".ToCharArray();
            board[2] = "ihkr".ToCharArray();
            board[3] = "iflv".ToCharArray();

            var found = FindWords(board, new string[] { "oath", "pea", "eat", "rain" }); 
        }

        public static void RunTestcase2()
        {
            var board = new char[1][];

            board[0] = "a".ToCharArray();            

            var found = FindWords(board, new string[] { "b"}); 
        }


        public static void RunTestcase3()
        {
            //[["a","b"],["a","a"]]
            // ["aba","baa","bab","aaab","aaa","aaaa","aaba"]
            var board = new char[2][];

            board[0] = "ab".ToCharArray();
            board[1] = "aa".ToCharArray();

            var found = FindWords(board, new string[] { "aba", "baa", "bab", "aaab", "aaa", "aaaa", "aaba" });

            // ["aba","aaa","baa","aaba"]
            // ["aaa","aaab","aaba","aba","baa"]  expected - mine is missing: "aaab"
        }

        /// <summary>
        /// design Trie class 
        /// </summary>
        class TrieNode
        {
            public TrieNode[] nodes = new TrieNode[26];
            private string word;

            /// <summary>
            /// Design Trie class
            /// Please use the following test cases:
            /// ["a"]
            /// </summary>
            /// <param name="words"></param>
            /// <returns></returns>
            public TrieNode Build(string[] words)
            {
                if (words == null)
                {
                    return new TrieNode(); 
                }

                var original = new TrieNode(); // dummy head                
                
                var length = words.Length;   // ["oath",""]
                foreach (var word in words)
                {
                    var iterate = original;  // start from root char again                    

                    foreach (char c in word)
                    {                                                                       
                        int index = c - 'a';
                        if (iterate.nodes[index] == null)  // caught by online judge
                        {
                            iterate.nodes[index] = new TrieNode();
                        }

                        // go to next trie node  
                        iterate = iterate.nodes[index];                        
                    }

                    iterate.word = word;
                }

                return original; 
            }

            public bool IsWord()
            {
                return word != null;
            }

            public string GetWord()
            {
                return word; 
            }

            public bool IsUnitialized()
            {
                return nodes == null; 
            }

            public void Initialize()
            {
                nodes = new TrieNode[26];
            }

            public TrieNode GetByIndex(int index)
            {
                if (nodes[index] == null)
                    return null;

                return nodes[index];
            }
        }

        /// <summary>
        /// Code review on June 16, 2020
        /// warmup practice
        /// 1. Design backtracking, walk through the example "oath" to explain to myself 
        /// how 'o','a','t','h' is marked as '#', after the word "oath" is added to the hashset, 
        /// all matrix's positions have original chars back. 
        /// 2. I did not fully understand how to apply backtracking back in June 2019, so I wrote my experience
        /// on Lowest common ancestor showcase on Leetocode discuss
        /// 3. This is perfect time for me to master the backtracking in DFS. 
        /// Facts:
        /// Sometimes one word is another word's prefix in dictionary. 
        /// So do not stop search if the word is added to found hashset. 
        /// </summary>
        /// <param name="board"></param>
        /// <param name="words"></param>
        /// <returns></returns>
        public static IList<string> FindWords(char[][] board, string[] words)
        {
            if (board == null || words == null)
            {
                return new List<string>(); 
            }

            // build a trie
            var trie = new TrieNode(); 
            trie = trie.Build(words);  // caught by debugger            

            var rows = board.Length;
            var columns = board[0].Length;

            var set = new HashSet<string>(); 

            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < columns; col++)
                {
                    runDFS(board, row, col, trie, set);
                }
            }

            return set.ToList(); 
        }

        /// <summary>
        /// Design requirement: 
        /// TrieNode
        /// Make sure that parentNode is not null all the time
        /// current node is one of parentNode's child
        /// </summary>
        /// <param name="board"></param>
        /// <param name="words"></param>
        /// <param name="found"></param>
        private static void runDFS(char[][] board, int row, int col, TrieNode parentNode, HashSet<string> found)
        {
            var rows = board.Length;
            var columns = board[0].Length;
            var visitedChar = '#';            

            // out of range or visited already
            // or current node trie[visit - 'a'] is not in Trie
            if (row < 0 || row >= rows || col < 0 || col >= columns || 
                board[row][col] == visitedChar ||
                parentNode.GetByIndex(board[row][col]-'a') == null
                )  
            {
                return; 
            }

            var visit = board[row][col];
            var child = parentNode.GetByIndex(board[row][col] - 'a');

            // work on trie
            if (child.IsWord())
            {
                found.Add(child.GetWord());
                //return;  // June 16, 2020 case 3: sometimes a word is another word's prefix in dictionary. So continue to search. 
            }

            // Design DFS with backtracking 
            var current = board[row][col];
           
            // mark visited
            board[row][col] = visitedChar;            
            
            // Four directions - clockwise, top, right, down, left
            runDFS(board, row - 1, col, child, found);
            runDFS(board, row, col + 1, child, found);
            runDFS(board, row + 1, col, child, found);
            runDFS(board, row, col - 1, child, found);

            //backtracking
            board[row][col] = current; 
        }
    }
}

Comment

Bigtable lecture notes: How to improve my reading skills? | Distributed systems: Rutgers university

Jan. 10, 2022

Introduction

It is hard for me to write a very good article about Bigtable, so I like to copy the lecture note and then read word by word. I will write down what I learn each time I read the lecture notes. 

Here is the link of lecture notes.

 

Bigtable

A NoSQL wide-column single-table database

Paul Krzyzanowski

November 3, 2021

Goal: How can we build an ultra-high performance, low-latency storage service for large-scale structured and semi-structured data?

Introduction

Traditional relational databases present a view of multiple tables, each containing rows and named columns. Queries, mostly performed in SQL (Structured Query Language) allow one to extract specific columns from a row where certain conditions are met (e.g., a column has a specific value). Moreover, one can perform queries across multiple tables (this is the “relational” part of a relational database). For example, a table of students may include a student’s name, ID number, and contact information. A table of grades may include a student’s ID number, course number, and grade. We can construct a query that extracts a grades by name by searching for the ID number in the student table and then matching that ID number in the grade table.

With traditional relational databases, we expect ACID guarantees: that transactions will be atomic, consistent, isolated, and durable. This includes operations that access or modify multiple fields, multiple rows, and multiple tables. The CAP theorem proved that is not possible to guarantee consistency while providing high availability and network partition tolerance. Partitions are unavailable in distributed systems, so the design choice is between high availability and consistency. ACID databases choose consistency, which usually involves locking and waiting: a transaction needs to update all replicas and cannot have some concurrent transactions work with old data while others access new data. In distributed architectures, we often choose to give up consistency in order to provide high availability. This makes ACID databases unattractive for highly distributed environments and led to the emergence of alternate data stores that are targeted to high availability and high performance. These data stores are often referred to as NoSQL databases.

Another aspect of conventional database systems is that they often do not do well with tables containing huge amounts of columns or even fields that contain huge amounts of data. Adding additional fields to a column (hence changing the schema of the database) can be a time-consuming task.

Here, we will look at the structure and capabilities of Bigtable. It is not a relational database; it is just a table but one that is designed to support efficient lookups and handle data on a huge scale. It is also designed as a wide-column store. This means that each row of a table can support a huge number of columns and the specific column names may vary from row to row.

Bigtable

Bigtable is a distributed storage system that is structured as a large table: one that may be petabytes in size and distributed among tens of thousands of machines. It is designed for storing items such as billions of URLs, with many versions per page; over 100 TB of satellite image data; hundreds of millions of users; and performing thousands of queries a second.

Bigtable was developed at Google in has been in use since 2005 in dozens of Google services. An open source version, HBase, was created by the Apache project on top of the Hadoop core (using the Hadoop Distributed File System, HDFS, instead of GFS and using Apache Zookeeper instead of Google’s Chubby).

Bigtable is designed with semi-structured data storage in mind. It is a large map where every item is indexed by a row key, column key, and a timestamp. Each value within the map is an array of bytes that is interpreted by the application. Clients can look up a row key and then iterate over all of its columns and over versions of data wihtin each column. Every read or write of data to a row is atomic, regardless of how many diferent columns are read or written within that row.

It is easy enough to picture a simple table but let us examine a few characteristics of Bigtable and what makes it special:

map

A map is an associative array; a data structure that allows one to look up a value to a corresponding key quickly. Bigtable is a collection of (key, value) pairs where the key identifies a row and the value is the set of columns.

persistant

The data is stored persistently on disk.

distributed

Bigtable’s data is distributed among many independent machines. At Google, Bigtable was built on top of GFS (Google File System)1. The Apache open source version of Bigtable, HBase, is built on top of HDFS (Hadoop Distributed File System) or Amazon S3. The table is broken up among along rows, so a sequence of adjacent rows will be managed by the same server. A row itself is never distributed.

sparse

The table is sparse, meaning that different rows in a table may use vastly different columns (there could be millions), with many – or even most – of the columns empty for a particular row.

sorted

In most databases or object stores, data is not sorted. A key is hashed to find its a position in a table. Bigtable, on the other hand, sorts its data by keys. This helps keep related data close together, usually on the same machine — assuming that one structures keys in such a way that sorting brings the data together. For example, if domain names are used as keys in a Bigtable, it makes sense to store them in reverse order to ensure that related domains are close together. For example:

• edu.rutgers.cs
• edu.rugtgers.nb
• edu.rutgers.www

multidimensional

A table is indexed by rows. Each row contains one or more named column families. Column families are a way of grouping columns and are defined when the table is first created. Within a column family, one may have one or more named columns. These can be defined dynamically at any time and there is essentially no limit to the number of columns within a column family. All data within a column family is usually of the same type. The implementation of Bigtable compresses all the columns within a column family together. Rows, column families and columns provide a three-level naming hierarchy to identify data. For example:

To get data from Bigtable, you need to provide a fully-qualified name for a row in the form column-family:column. For example, users:homer or sysinfo:cpu. Since you can have an unlimited number of columns that can be added dynamically, Bigtable provides iterators to allow clients to discover and iterate over all columns within a column family.

time-based

Time is another dimension in Bigtable data. Every column family may keep multiple versions of column family data. If an application does not specify a timestamp, it will retrieve the latest version of the column family. Alternatively, it can specify a timestamp and get the latest version that is earlier than or equal to that timestamp.

time-based is related to column family, not column. - Jan. 10, 2022 5:46 PM

Columns and column families

Let’s look at a sample slice of a table that stores web pages (this example is from Google’s paper on Bigtable). The row key is the page URL. For example, com.cnn.www.

Various attributes of the page are stored in column families. A contents column family contains page contents (there are no columns within this column family). A language column family contains the language identifier for the page. Finally, an anchor column family contains the text of various anchors from other web pages. The column name is the URL of the page making the reference. These three column families underscore a few points.

A column may be a single short value, as seen in the language column family. This is our classic database view of columns. In Bigtable, however, there is no type associated with the column. It is just a bunch of bytes.

The data in a column family may also be large, as in the contents column family.

The anchor column family illustrates the extra hierarchy created by having columns within a column family. It also illustrates the fact that columns can be created dynamically (one for each external anchor), unlike column families.

Finally, it illustrates the sparse aspect of Bigtable. In this example, the list of columns within the anchor column family will likely vary tremendously for each URL. Each column name within anchor is the name of the URL that contains a link to the URL indicated by the row key. The value of the column is the text on the page that contains the link. For example, cnnsi.com contains a link with the text CNN that links to www.cnn.com. The interesting feature of a wide-column store such as Bigtable is that the name of the column is itself a form of a value. A client can iterate through all the column names within anchor to get a list of URLs that contain links to a specific web page (the row key).

In all, we may have a huge number (e.g., hundreds of thousands or millions) of columns overall but the column family within each row will often have only a tiny fraction of them populated. While the number of column families will typically be small in a table (at most hundreds), the number of columns is unlimited.

Rows and partitioning

A table is logically split among rows into multiple subtables called tablets. A tablet is a set of consecutive rows of a table and is the unit of distribution and load balancing within Bigtable. Because the table is always sorted alphabetically by row, reads of short ranges of rows are efficient: one typically communicates with one or a small number of machines. Hence, a key to ensuring a high degree of locality is to select row keys properly (as in the earlier example of using domain names in reverse order).

What is a tablet? A tablet is a set of consecutive rows of a table and is the unit of distribution and load balancing within Bigtable. 

1. A set of rows
2. A set of consecutive rows
3. A set of consecutive rows of a table
4. unit of distribution - What is the unit of distribution?
5. load balancing 
6. load balancing within Bigtable
7. What is a tablet? Think about, and talk about rows, a set of rows - consecutive rows
8. Read again

Timestamps

Each column family cell can contain multiple versions of content. For example, in the earlier example, we may have several timestamped versions of page contents associated with a URL. Each version is identified by a 64-bit timestamp that either represents real time or is a value assigned by the client. Reading column data retrieves the most recent version if no timestamp is specified or the latest version that is earlier than a specified timestamp.

A table is configured with per-column-family settings for garbage collection of old versions. A column family can be defined to keep only the latest n versions or to keep only the versions written since some time t.

Implementation

Bigtable comprises a client library (linked with the user’s code), a master server that coordinates activity, and many tablet servers. Tablet servers can be added or removed dynamically. If the master dies, another master can take over.

The master assigns tablets to tablet servers and balances tablet server load. It is also responsible for garbage collection of files in GFS and managing schema changes (table and column family creation). As such, a tablet server is responsible for tablets but the tablets do not necessarily live on that node since any node can access any data within GFS.

Each tablet server manages a set of tablets (typically 10–1,000 tablets per server). It handles read/write requests to the tablets it manages and splits tablets when a tablet gets too large. Client data does not move through the master; clients communicate directly with tablet servers for reads/writes. The internal file format for storing data is Google’s SSTable, which is a persistent, ordered, immutable map from keys to values. Rows of data are always kept sorted by the row key.

Study notes:

1. Tablet server
2. Each tablet server manages a set of tablets 
3. how many tablets - 10 - 1,000 tablets per server
4. SSTable - internal file format for storing data - MemTable and SSTable
5. SSTable - a persistent, ordered, immutable map from keys to values
6. Rows of data are always kept sorted by the row key

Bigtable uses the Google File System (GFS) for storing both data files and logs. A cluster management system contains software for scheduling jobs, monitoring health, and dealing with failures.

Chubby

Chubby is a highly available and persistent distributed lock service that manages leases for resources and stores configuration information. The service runs with five active replicas, one of which is elected as the master to serve requests. A majority must be running for the service to work. It uses a Paxos distributed consensus algorithm to keep the replicas consistently synchronized. Chubby provides a namespace of files & directories. Each file or directory can be used as a lock.

In Bigtable, Chubby is used to:

• ensure there is only one active master
• store the bootstrap location of Bigtable data
• discover tablet servers
• store Bigtable schema information
• store access control lists

Startup and growth

A table starts off with just one tablet. As the table grows, it is split into multiple tablets. By default, a table is split at around 100 to 200 MB.

Locating rows within a Bigtable is managed in a three-level hierarchy. The root (top-level) tablet stores the location of all Metadata tablets in a special Metadata table. This root tablet is simply the first tablet in the set of tablets that comprise the Metadata table. Each Metadata table contains the location of user data tablets. This table is keyed by node IDs and each row identifies a tablet’s table ID and end row. For efficiency, the client library caches tablet locations.

A tablet is assigned to one tablet server at a time. Chubby keeps track of tablet servers. When a tablet server starts, it creates and acquires an exclusive lock on a uniquely-named file in a Chubby servers directory. The master monitors this directory to discover new tablet servers.

When the master starts, it:

• Grabs a unique master lock in Chubby (to prevent multiple masters from starting)
• Scans the servers directory in Chubby to find live tablet servers
• Communicates with each tablet server to discover what tablets are assigned to each server. This is important because the master might be recovering for a failed master and tablets have already been allocated to tablet servers.
• Scans the Metadata table to learn the full set of tablets
• Builds a set of unassigned tablet servers. These are eligible for tablet assignment and the master will choosing a tablet server and send it a tablet load request.

Fault tolerance and replication

Some of the fault tolerance for Bigtable is provided by Google and Chubby. GFS, for example, provides configurable levels of replication of file data and Chubby’s cell of replicated servers minimizes its downtime.

A master is responsible for detecting when a specific tablet server is not functioning. It does this by asking the tablet server for status of its lock (recall that Chubby grants locks). If the tablet server cannot be reached or has lost its lock, the master attempts to grab that server’s lock. If it succeeds, then it surmises the tablet server is dead or cannot contact Chubby. In this case, the master moves the tablets that were previously assigned to that server into an unassigned state.

When a master’s Chubby lease expires, it kills itself. This does not change the assignment of tablets to servers, however. Google’s cluster management system periodically checks for the liveness of a master. If it detects a non-responding master, it starts one up, which grabs a lock from Chubby. The new master contacts Chubby to find all the live servers goes through the startup phase described earlier.

A Bigtable can be configured for replication onto multiple Bigtable clusters in different data centers to ensure availability. Data propagation is asynchronous and results an eventually consistent model.

References

• Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber, Bigtable: A Distributed Storage System for Structured Data, Google, Inc. OSDI 2006: The definitive paper on Bigtable.

• Google, Overview of Bigtable, Google Cloud Documentation. This describes the current Google Cloud offering of Bigtable. Note that GFS has been replaced with Colossus (a newer distributed file system) and tablet servers are now called Bigtable nodes.

• Ilya Grigorik, SSTable and Log Structured Storage: LevelDB, igvita.com, February 26, 2012: _a description of the SSTable (Sorted String Table) used in Bigtable.

• Cloud Bigtable: A publicly-available version of Bigtable, part of the Google Cloud Platform

• Google, Bigtable for Cassandra users, Google Cloud – Cloud Architecture Center.

• Robin Harris, Google’s Bigtable Distributed Storage System](http://storagemojo.com/2006/09/07/googles-bigtable-distributed-storage-system-pt-i/), StorageMojo.com

• Apache HBase: An open-source project based on the design of Bigtable.

• Understanding HBase and Bigtable, Jumoojw.com

This is an updated version to one that was originally published in November 2011.