Databases and Tables

Primary Keys

Figure 6-5 shows a hypothetical representation of the physical layout of the Artists table, where with the Artist ID as the key, the remaining column data is stored as the value.

Being distributed, Spanner partitions the data automatically and distributes across its allotted node. The partitioning is done by Spanner along the primary key dimension. So, it’s important to choose the primary key carefully.

Choose a Key to Avoid Hotspots

Keys should be chosen so that they enable even distribution of the data and do not create a hotspot. So what is hot spotting? Assume that the database hosting the Artists table is on a two-node instance. This implies that the table’s data will be distributed across the two nodes along the primary key dimension, ArtistId. Figure 6-6 shows a hypothetical distribution of data across the two nodes.

Since the primary key called ArtistId is a monotonically increasing integer ID, as you start inserting new data, being incremental in nature, all the new additions will start to happen at the end of the key space. In effect, all inserts will start to happen only on Node 2. Figure 6-7 shows inserts of new the Artist IDs 6, 7, 8, 9, 10, 11, and 12.

This scenario illustrates hot spotting, as the load weighs down a single node only. This effectively kills parallelization in Spanner , therefore affecting performance. In order to handle such scenarios, you should avoid keys that are sequentially ordered or monotonically increasing, like the ArtistId column. Instead, you should choose a key that evenly distributes data and enables even distribution of workload (reads and writes) and does not create a hotspot.

However, if it is unavoidable and you have to use a sequentially ordered key, you should see if you can hash it. Hashing has the effect of distributing across different servers quite evenly. In the previous example, if you hash Artist IDs, even distribution can be achieved as the hash values of the ArtistId columns will contain random alphanumeric data, which is highly unlikely to be monotonically increasing or decreasing. As a result, the representation will be free of hot spotting.

Note

There are various other techniques defined on the product site that you should take into consideration for efficient selection of the key.

The next section looks at the way related tables should be created for efficient querying .

Interleaving

Spanner enables you to choose the physical representation of your table data based on your querying pattern. In order to handle relationships where tables are related and are frequently queried together, Spanner enables you to define hierarchical (parent-child) relationship between the tables, which enables efficient retrieval as the data of the hierarchically related tables will be co-located and stored together on the disk.

The relationship is defined by creating the child table (table containing related information) as an interleaved table of the parent (main) table.

As of now, the Albums table is created like any other normal table. With the key IDs of both tables (Artists and Albums), the physical layout of the data now looks like Figure 6-8.

As you can see, the data is stored in a contiguous space. In this case, it’s quite possible that, while distributing the data across nodes, rows of the Albums table end up on one node and the Artists table on the other node. This will be apt if you don’t have to query the tables together, but since in this case, you will be always querying Albums with reference to Artists, this representation will have a negative impact on performance. So in this case it’s apt to create Albums as an interleaved table of Artists. While you do so, you need to note that Spanner uses the primary key of the parent table to store the child data with the corresponding parent record. So as you interleave the table, primary key column(s) of the parent table are mandatorily prefixed to the primary key of the child table (in the same order starting with the same column as in the parent table). So, now the primary key of the Albums table will be composed of ArtistId and AlbumId. With the interleaving defined, the table schema is as shown in Table 6-6 and the physical layout of both the tables is as shown in Figure 6-9.

Table 6-6

Albums Table Schema

Column Name	Data Type
ArtistId	INT64	Primary Key (Column 1)
AlbumId	INT64	Primary Key (Column 2)
Album Title	STRING [50]

As you can see, the data is interleaved. Every row from the Artists table is followed by all its rows from the child Albums table, which is determined by the ArtistId column value. This entire representation looks like a big flat table.

In effect, this process of inserting the child rows between the parent rows along the primary key dimension is called interleaving. The child tables are called interleaved tables and the parent tables are called the root table or top-level tables. As can be seen, this will enable fast querying, as data that’s queried together is stored together.

So while designing your schema, it is important to identify the querying pattern to identify the tables that need to be co-located. That way, when you’re actually creating the tables, proper interleaving can be defined.

You are now familiar with two important design decisions—choosing the proper primary key to avoid hot spotting and identifying the querying pattern to interleave the related tables. The next step is to understand another interesting concept, splits .

Splits

As you know by now, Cloud Spanner uses the primary key dimension to partition the data. Splits determine the point within the dimension where the partitions should happen. In effect, splits are used by Cloud Spanner to logically group the rows so that they are independent of each other and can be moved around independently without impacting the other group of data and performance.

Cloud Spanner automatically splits when it deems necessary due to size or load. Splits are done at the root row boundaries, where root row is the row in the root table, so that the root row plus all its descendants (row tree) are always in a single split. Figure 6-10 shows a row tree, i.e., root row plus all its descendants.

Although you don’t control when or how to split, you can control the way you define the root table and the row tree. In effect, it’s important to choose the correct root table while designing the database to enable proper scaling.

Returning to the example, you can see that there are a bunch of possible splits (as you are querying details of albums for a particular artist), each corresponding to a distinct value of the Artist ID, as shown in Figure 6-11.

These are groups of rows that can be moved around without affecting any of the other rows. Splits complement the data distribution in Spanner. Having looked at important concepts of choosing a proper primary key, interleaving, and splits, it’s time to look at the indexes .

Secondary Indexes

As you know by now, data is stored in sorted order by the primary key, so any query involving the primary key field will always result in faster querying. However, querying on other non-key fields will lead to full table scan, leading to slower query performances. In order to cater to this scenario, like other databases, Spanner enables you to create secondary indexes on the non-key fields.

So, if you query Fetch Artist ID's with LastName values in the Range specified, this index will be able to return results faster without any table scan as all the data is available within the index itself.

Read/Write

Figure 6-15 shows a read/write transaction and the operations that occur within it.

It first reads the amount from the table. Then it processes the data. Say, for example, that you check the amount. If it is greater than $100, you add $100’s to it. Finally, you save the updated data. Figure 6-16 shows the locking mechanism; the locks are acquired at each step.

As you can see, the read acquires a shared lock. Within the database at any point in time, you can have multiple concurrent transactions running. This lock enables the other transactions to continue reading. In effect, it does not block the other reads. When commit is initiated, it implies that the transaction is ready with the data to be applied back to the database. At this point it tries to acquire an exclusive lock on the data point. This will block all the new read requests for the data and will wait for the existing locks to be cleared. Once all the locks are cleared, it places the exclusive lock and applies all the writes. Once this is done, the lock is released. The Amount field will show the updated data.

Note that the updates in Cloud Spanner is not in-place updates, instead Spanner uses the MVCC (Multi Version Concurrent Control) method to modify the data. This implies that the writes do not overwrite the data. Instead, an immutable copy is created, which is timestamped with the write’s transaction commit time. In effect, Cloud Spanner maintains multiple immutable versions of data. The next section looks at the read only transaction mode.

Read Only

Figure 6-17 shows a read only transaction called TxnR.

As seen, you can have reads only with no updates. In general, you can use the reads to process and display the output to the end users. When you have multiple reads happening together, it’s best to use the read only transaction mode. In TxnR all reads will return the result as $1000, as the Begin transaction has captured a snapshot of the data, and all reads refer to that snapshot.

There might be cases where you need to do single read calls or need to read data in parallel. Cloud Spanner enables you to do this with single reads options, which are reads outside the context of a transaction. The single reads are the simplest and fastest operations in Spanner.

By default, the reads within a read only transaction and single reads pick the most recent timestamp; however, Cloud Spanner enables you to control the freshness of the data. At any point in time, Cloud Spanner can perform reads up to one hour in the past.

In effect, Cloud Spanner enables you to do two types of reads: strong reads and stale reads. Strong reads are the default reads that get the freshest data, wherein reads get to see the effect of all transactions that were committed prior to when the read started. Stale reads enable you to read past data and are further categorized into two types: exact staleness or bounded staleness. Exact staleness reads data at a user-specified timestamp, e.g., 2019-09-16T15:01:23. In bounded staleness, instead of specifying a timestamp, the user specifies a bound, such as 7s. Whenever the transaction is run based on the bound specified, Spanner chooses the newest timestamp within the bound. Bounded staleness is slower than the exact staleness reads; however, they return the freshest data. The read type is controlled by specifying the timestamp bound on the reads.

The read types are useful when you use read replicas to scale out reads. The read replicas can be a bit outdated. If the application is willing to tolerate staleness, then it can get faster responses, as they will be able to read from any nearest read replica and will not have to communicate with the leader replica, which may be geographically distant.

Now that you are familiar with the transaction modes available, let’s next look at the way Spanner handles concurrent transactions across its distributed environment.

Handling Multiple Transactions

Cloud Spanner provides the strictest concurrency control, which is external consistency. This implies that multiple transactions can run side-by-side on different servers (which are possibly spread out across different datacenters in different time zones) without causing any inconsistencies. Proper timestamping is mandatory for achieving external consistency. For this, Spanner uses TrueTime, a Google developed technology. This is a highly available, distributed clock enabling applications running on Google Servers to generate monotonically increasing timestamps without any need for global communication.

Read/Write Transactions

Let’s further assume you have two transactions running. The first transaction, called Tx1, is responsible for adjusting the advances taken and the second transaction, Tx2, adjusts the reimbursement amount. Figure 6-18 shows operations in transaction Tx1.

Figure 6-19 shows the operations in transaction Tx2.

Sequential Occurrence

Now you can see the concurrent occurrence of the two. Figure 6-20 shows the two transactions occurring one after another.

As TrueTime is used to ensure proper timestamping, TrueTime guarantees that because Tx2 starts to commit after Tx1 finishes, all readers of the database will observe that Tx1 occurred before Tx2. This guarantees no update is ever lost.

Simultaneous Occurrence

Let’s next look at the transactions starting side-by-side, as shown in Figure 6-21.

The read’s acquire shared lock is in both transactions. As the write of Tx1 starts to commit prior to Tx2, Tx1 tries to acquire an exclusive lock. It will wait for the Tx2 acquired read lock to be released. In this scenario, Spanner uses the wound-and-wait algorithm and aborts transaction Tx2 so that Tx1 can acquire and continue with its update. Figure 6-22 shows the read locks acquired.

Figure 6-23 shows transaction Tx2 being aborted so that Tx1 can continue with its updates.

In this process, the Tx2 commit fails and will be retried later. This is done to avoid deadlock. In addition, this also guarantees that no updates are ever lost if multiple concurrent transactions start, as at any point in time only one will be updating the data and the other will retry after some time. Under the hood, the age of each transaction is used to resolve the conflicting lock issue. The younger transaction will wait, but an older transaction will wound (abort) a younger transaction. By giving priority to the older transaction, Spanner ensures that eventually every transaction gets a chance to update.

Data Invalidated

Let’s next look at the case shown in Figure 6-24, when Tx1 reads and changes Salary data and Tx2 reads the same data.

Since Tx2 started earlier than the Tx1 commit, it will read the Salary value, which is already invalidated due to changes made by Tx1. In this case as well, Tx2 will be terminated so that the update of Tx1 is not overwritten. In effect, prior to making the update, the transaction waits for the read locks to be released and also validates that all the read locks it acquired within the transaction are still valid. This implies no change is made to it after it has read the data.

Different Fields Updates

Take a look at the transaction shown in Figure 6-25.

Transaction Tx1 is working on the Salary field, whereas Tx2 works on the Processed On field. It is quite likely that both transactions will attempt to update the same row of data simultaneously. However, unlike the previous scenario, where transaction Tx2 was aborted to avoid the deadlock situation, here, both transactions will be executed successfully. This is due to the fact that Cloud Spanner locks at the cell level (a row and a column). The row is the same but the columns that both transactions are working on are different. So, there will be no conflict, as the cells that will be updated are different.

Blind Writes

Let’s now look at the scenario of concurrent read/write transactions, where you have only write operations that are not followed by any reads. Such operations are called blind writes. Inserting the current month’s salary details in the Salary table is an example. Write locks are usually exclusive, where only one writer updates the data. Although this prevents data corruption by preventing the race condition on the data, it does impact the throughput.

With blind writes in Spanner, the write locks are allowed to be shared. This is possible due to usage of TrueTime. TrueTime guarantees a unique timestamp to each transaction, so multiple blind writes can run in parallel, thereby updating the same data without worrying about data corruption or loss. This feature not only avoids race conditions but also brings in significant throughput for blind writes .

Read/Write with Read Only

Now you have a scenario of read/write and read only transactions running side-by-side, as shown in Figure 6-26.

As you can see, the read only transactions Txr1 and Txr2 are interleaved in between the two read/write transactions, Tx1 and Tx2. You can further assume the Salary table data is as shown in Tables 6-18 through 6-20 at various timestamps.

Table 6-18

Salary Data at t0

Employee ID	Month	Salary	Processed On
1	Aug 2019	$1000	23rd Aug 2019

Table 6-19

Salary Data at t1

Employee ID	Month	Salary	Processed On
1	Aug 2019	$500	23rd Aug 2019

Table 6-20

Salary Data at t2

Employee ID	Month	Salary	Processed On
1	Aug 2019	$10000	23rd Aug 2019

Here are values read in each:

• In Txr1, all reads will show values, as on timestamp t0, which is $1000 only, as it started prior to the Tx1 commit and the snapshot taken was of timestamp t0. All reads within the transaction return the value from the snapshot, so even though the second read is after the Tx1 commit timestamp, the changes will not be reflected in this transaction read.

• The change of the Tx1 commit will be visible in the Txr2 read, as the snapshot for this transaction is after the Tx1 commit. Every read in this transaction will show $500. As with Txr1, reads in Txr2 will not show the changes made in transaction Tx2.

This guarantees safety against non-repeatable reads and dirty reads. Non-repeatable reads are reads within a transaction that see different values due to interleaved read/write transactions. Dirty reads are reads that see a change that has not yet been committed.

Having looked at the way operations happen in Spanner, it’s time to go back and look at the way Spanner carries out the read/write operations across its distributed dataset.

Writes

Irrespective of whether the write involves a single node or is multi-node, a write is marked to be committed only when write-quorum is achieved or, in other words, the majority of voting replicas (replicas who are eligible to vote for a write commit) agree to commit the write. Writes always happen on the leader replica and the non-witness replicas of the replica set. The next section covers read operations.

Reads

As you already know by now, reads can be part of read/write transactions as well as read only transactions. Reads that are part of the read/write transactions will always be served by the leader replica, as it requires locking. Reads that are part of read only transactions (or single reads) can be served from any replica. The need to communicate with the leader replica depends on the read type method: strong or stale.

If you do stale reads, then you can proceed without Step 2.b.(ii).