1 00:00:00,000 --> 00:00:14,880 [Music] Welcome to course 101, TiDB  Technical Essentials. This is module 3 TiKV.  2 00:00:14,880 --> 00:00:21,060 My name is Jeff, and I'm your instructor for  this module. Once you complete this module,   3 00:00:21,060 --> 00:00:27,900 you will be able to understand the architecture  and role of TiKV, understand TiKV data persistence   4 00:00:27,900 --> 00:00:35,100 and reads, understand how TiKV provides MVCC  and distributed transaction support, 5 00:00:36,060 --> 00:00:42,960 understand the distributed consistency of  TiKV based on the Raft algorithm, and finally   6 00:00:42,960 --> 00:00:49,440 understand TiKV's coprocessor. In the previous  module, we learned that TiDB server is a stateless   7 00:00:49,440 --> 00:00:54,840 SQL layer that exposes the connection endpoint  of the MySQL protocol to the outside world. 8 00:00:55,680 --> 00:01:01,320 SQL processing is not very useful without  storage. That's where TiKV comes in.   9 00:01:01,320 --> 00:01:09,540 The core function of TiKV is data persistence.  TiKV stores OLTP data in the TiDB database.   10 00:01:10,200 --> 00:01:14,160 This capability is implemented  by an embedded RocksDB server.   11 00:01:14,760 --> 00:01:19,500 TiDB is a distributed storage engine.  The data is spread out into regions. 12 00:01:19,500 --> 00:01:25,920 The Raft consensus algorithm is used to ensure  strong consistency of data in this distributed   13 00:01:25,920 --> 00:01:33,300 environment. Each region and its replicas form a  Raft group and the combination of multiple Raft   14 00:01:33,300 --> 00:01:39,480 groups is called multi Raft. We will introduce  replication and leader election and Raft,   15 00:01:39,480 --> 00:01:46,140 as well as data writing, reading, splitting, and  merging based on the Raft consensus algorithm. 16 00:01:47,160 --> 00:01:53,700 Later, we will introduce the TiKV co-processor  capability. This provides TiDB with the ability   17 00:01:53,700 --> 00:01:59,040 to execute SELECT operations that are  pushed down from TiDB server. We can use   18 00:01:59,040 --> 00:02:05,400 this function component to hand over some SQL  calculations, such as filtering, aggregation,   19 00:02:05,400 --> 00:02:13,140 projection to TiKV to complete. There is no need  to return all the data in TiKV to the TiDB server 20 00:02:13,140 --> 00:02:18,120 via the network, nor is it necessary for the  TiDB server to do all the query processing/ 21 00:02:18,120 --> 00:02:24,420 This saves network bandwidth and CPU load  on the TiDB server. Plus, and this is important, 22 00:02:25,260 --> 00:02:31,020 the coprocessor allows TiDB to distribute  processing across multiple TiKV nodes. 23 00:02:32,880 --> 00:02:39,000 RocksDB is a persistent embedded key  value store. RocksDB is optimized for   24 00:02:39,000 --> 00:02:46,560 flash storage with minimal latency, and uses log  structured merge trees or LSM trees for storage. 25 00:02:48,660 --> 00:02:53,400 So let's talk about some of the characteristics. It is a high performance key value database.   26 00:02:54,240 --> 00:02:58,980 It has perfect durability mechanism,  while guaranteeing performance and safety.   27 00:02:59,640 --> 00:03:06,060 Good support for range queries. It's designed for  application servers that need to store terabytes   28 00:03:06,060 --> 00:03:11,520 of data to local flash or RAM. And it's  optimized for small and medium key values   29 00:03:11,520 --> 00:03:19,140 stored on high-speed devices. Once again, can be  stored in flash or directly in memory. Finally, 30 00:03:19,140 --> 00:03:25,140 performance increases linearly with the number of  CPUs, making it friendly to multi-core systems. 31 00:03:26,160 --> 00:03:31,740 Let's look at how Rocksdb writes data.  RocksDB uses the data structure of the   32 00:03:31,740 --> 00:03:38,220 LSM tree to store key value data. And LSM tree  will insert, modify, delete all data stored in   33 00:03:38,220 --> 00:03:43,740 memory. And when such operations reach a certain  amount of data, it's written to disk and batch.   34 00:03:44,400 --> 00:03:49,080 When writing to disk, the previous data  will be merged. During the merge process,   35 00:03:49,080 --> 00:03:52,380 the original data is not modified like a B+ tree, 36 00:03:52,380 --> 00:04:00,600 new data is inserted directly. Thus, avoiding  random writes. The structure of the LSM tree spans   37 00:04:00,600 --> 00:04:07,920 memory and disk, and contains several parts such  as MemTable, immutable MemTable and SST table.  38 00:04:09,600 --> 00:04:15,240 We explain the workflow of the LSM tree in its  related components with a single write operation 39 00:04:15,240 --> 00:04:19,860 in the figure. First, we  back up the disk via write  40 00:04:19,860 --> 00:04:25,980 ahead logging, or WAL, to prevent data  loss. WAL is a series of techniques used   41 00:04:25,980 --> 00:04:30,060 in relational database systems to  provide atomicity and persistence. 42 00:04:30,060 --> 00:04:36,780 These are two of the ACID properties on systems  that use write ahead logging. All modifications   43 00:04:36,780 --> 00:04:41,040 to the data must be written to the log file,  before they are committed to the database.   44 00:04:41,700 --> 00:04:45,540 Once write ahead logging is complete  data is written to MemTable. 45 00:04:46,200 --> 00:04:50,460 MemTable is an in-memory data structure  that stores the data before it is written   46 00:04:50,460 --> 00:04:54,840 to disk. MemTable can use data  structures such as skip list or   47 00:04:54,840 --> 00:04:57,600 search trees to organize data and maintain order.  48 00:04:58,440 --> 00:05:05,940 MemTable services both reads and writes. New  writes always insert data into MemTable, and read   49 00:05:05,940 --> 00:05:12,600 operations always query MemTable before querying  the RocksDB sorted string table or SST file, 50 00:05:13,500 --> 00:05:19,380 because the data in MemTable is always up to  date. Let me repeat that the data in MemTable   51 00:05:19,380 --> 00:05:26,040 is always up to date. When MemTable reaches  a pre-specified size MemTable is converted   52 00:05:26,040 --> 00:05:31,320 to an immutable MemTable The immutable  MemTable is a memory-based data structure   53 00:05:31,320 --> 00:05:35,760 that cannot be modified. Once again  immutable MemTable cannot be modified.   54 00:05:36,360 --> 00:05:41,580 During this process, the MemTable is  transformed into an intermediate form of an SST.   55 00:05:42,300 --> 00:05:46,380 The goal is to not block writes  during the staging process. 56 00:05:47,880 --> 00:05:52,860 Writes can be processed by the new MemTable  without waiting for a lock. A new MemTable   57 00:05:52,860 --> 00:05:58,620 is created to handle the new data. A background  thread will drop the contents of this MemTable   58 00:05:58,620 --> 00:06:05,580 into an SST file as a collection of ordered key  value pairs, which is the structure of data in   59 00:06:05,580 --> 00:06:12,540 the LSM Tree on disk. The data in MemTable will eventually be converted to an SST and   60 00:06:12,540 --> 00:06:18,600 saved to disk. Once this process completes the  existing MemTable is destroyed and the write   61 00:06:18,600 --> 00:06:25,500 ahead log file containing the data related to the  new mem data can be deleted. Next, we will focus   62 00:06:25,500 --> 00:06:31,200 on the way RocksDB files are organized. Files on  the disk are organized in multiple layers. Let's   63 00:06:31,200 --> 00:06:39,480 call them level one, level two, etc. A special  layer level 0, or L0, will contain data that   64 00:06:39,480 --> 00:06:46,920 has just been dropped from MemTable. Each layer  except level zero is an independent sort results.  65 00:06:48,240 --> 00:06:53,880 At each layer, except level zero, the  data is split into multiple SST files. 66 00:06:54,720 --> 00:07:01,200 The keys in each SST files is in sorted order. If we need to locate a key, we first find the   67 00:07:01,200 --> 00:07:06,780 start and end keys of the files in two  parts. We locate which file has this key   68 00:07:06,780 --> 00:07:14,760 and access the location in the file. In general, it's a binary search of all keys in that layer.  69 00:07:14,760 --> 00:07:19,920 The goal of compression is to limit of these  layers. The data size will trigger compaction   70 00:07:19,920 --> 00:07:25,860 to the next layer, and the size goal is usually  an exponential increase of the previous layer.   71 00:07:26,400 --> 00:07:32,700 For write ahead logs, WAL, serializes  MemTable operations and stores them in   72 00:07:32,700 --> 00:07:38,880 log files on the permanent media. In the  event of a crash the write ahead log file   73 00:07:38,880 --> 00:07:43,200 can be used to rebuild the MemTable to help  recover the database to a consistent state. 74 00:07:44,760 --> 00:07:51,480 When a MemTable is safely placed on persistent  media, the associated WAL log or write ahead log   75 00:07:51,480 --> 00:07:57,660 becomes out of date and then archived. The final  archived logs are deleted from the hard drive  76 00:07:57,660 --> 00:08:04,800 after a specified time period. At this point, the  data has been persisted. We can see that the write   77 00:08:04,800 --> 00:08:12,060 ahead log guarantees that write will not be lost.  Next, let's cover delete operations. When there's   78 00:08:12,060 --> 00:08:17,400 a delete operation, it's not necessary to find  the corresponding data on disk like a B+ tree   79 00:08:17,400 --> 00:08:24,000 and delete it. You only need to insert a piece of  data into MemTable as a flag, such as delete key   80 00:08:24,000 --> 00:08:31,200 1233. That's an example. When the read operation  reads this flag in MemTable, it will know that   81 00:08:31,200 --> 00:08:36,900 the key has been deleted. Then, in log merging,  the data marked for deletion will be deleted.   82 00:08:36,900 --> 00:08:42,780 During the merge process, the update operation  is similar to the delete operation. Update only   83 00:08:42,780 --> 00:08:48,840 operates on the MemTable. It writes a flag, and  then the actual update operation is delayed and   84 00:08:48,840 --> 00:08:54,120 completed at the time of merge. And random  writes will be changed to a sequential write. 85 00:08:55,860 --> 00:09:00,780 Since the data is stored in RocksDB, the  queries must be completed through RocksDB.   86 00:09:01,500 --> 00:09:06,840 First, let's understand the RocksDB query  operation. The query operation needs to read   87 00:09:06,840 --> 00:09:15,720 MemTable, immutable MemTable, and then disk, which  is really SST files. And that's SST tables zero,   88 00:09:15,720 --> 00:09:20,700 SST table one ... You get the  picture. You need to iterate through   89 00:09:20,700 --> 00:09:25,380 all the collections in reverse order in this  example. it is important to note that if one   90 00:09:25,380 --> 00:09:29,940 piece of data does not exist in all data  sets, the search will be repeated in vain.   91 00:09:30,660 --> 00:09:37,620 Fortunately, RocksDB uses Bloom Filters to speed up  read operations. When the Bloom Filter determines   92 00:09:37,620 --> 00:09:45,060 that there is no data to read in the corresponding  SS table. The SS table is skipped. RocksDB also   93 00:09:45,060 --> 00:09:52,260 has a block cache function. We can set a space in  memory for the block cache. This cache contains   94 00:09:52,260 --> 00:09:58,800 data that we access often, so the query operation  will prefer to read data from the block cache. If   95 00:09:58,800 --> 00:10:04,200 the data is not in the block cache, then it uses  MemTable read process, described in the diagram. 96 00:10:06,660 --> 00:10:12,960 We've seen that TiKV integrates RocksDB for  basic data persistence. Next we will look at   97 00:10:12,960 --> 00:10:19,140 another feature of RocksDB: column families. A  column family is a database object that contains   98 00:10:19,140 --> 00:10:24,720 columns of related data. TiKV uses column  families for transaction support. Support   99 00:10:25,560 --> 00:10:32,760 for column families began in RocksDB 3.0.  Each RocksDB key value pair corresponds to a   100 00:10:32,760 --> 00:10:38,880 unique column family. If a column family is not  specified, the key value pair will correspond   101 00:10:38,880 --> 00:10:45,120 to the default column family, which is also the  default column family, for the Rocksdb instance.   102 00:10:45,840 --> 00:10:51,300 Column families provide a way to logically  fragment a database. Some of its features include,   103 00:10:51,300 --> 00:10:57,540 support for cross column atomic writing,  consistent view across column families,   104 00:10:58,440 --> 00:11:01,980 allows different configurations  for different column families,   105 00:11:02,940 --> 00:11:10,140 and add remove column family instantly, both  operations are very fast, Another thing we   106 00:11:10,140 --> 00:11:14,460 need to note is that, the main implementation idea  of the column family is that, they share a write   107 00:11:14,460 --> 00:11:21,000 ahead log, but they do not share a MemTable,  and table files. Atomic writing is achieved by   108 00:11:21,000 --> 00:11:28,260 sharing write ahead logs by isolating MemTable and  table files. We can configure each column family   109 00:11:28,260 --> 00:11:35,160 independently and quickly delete them. We can only  delete this write ahead log file, if all column   110 00:11:35,160 --> 00:11:41,280 families have been flushed. This ensures that all  your column families will be flushed regularly.   111 00:11:42,060 --> 00:11:47,580 At this point, we've introduced column families.  We know that Rocksdb instances can have multiple   112 00:11:47,580 --> 00:11:54,180 column families. Each column family corresponds  to a key value pair, and each column family has   113 00:11:54,180 --> 00:12:00,180 a MemTable, and table files of their own.  But column families share a write ahead log.