About the Authors xi
Foreword by Prof. Shuo-Yen Robert Li xv
Foreword by Prof. Weimin Zheng xvii
Preface xix
Acknowledgments xxi
Summary Evaluation for Promotional Purposes xxiii
1 Fundamentals of Distributed Storage 1
1.1 Introduction to Distributed Storage 1
1.1.1 Evolution of Storage Systems 2
1.1.2 Characteristics of Distributed Storage 4
1.2 Reliability of Distributed Storage 6
1.2.1 Availability and Reliability 6
1.2.2 Fault Tolerance 7
1.2.3 Reliability Metrics 10
1.3 Trends in Future Development 12
1.4 Chapter Summary 16
Discussion Questions 16
References 17
2 Codes for Distributed Storage 19
2.1 Preliminaries 20
2.1.1 MDS Codes and ECs 20
2.1.2 Classification of ECs 23
2.2 RS Codes 25
2.2.1 Original RS Code 25
2.2.2 CRS Code 26
2.2.2.1 Encoding Process of CRS Code 26
2.2.2.2 Decoding Process of CRS Code 29
2.3 Regenerating Codes 29
2.3.1 Introduction to RGCs 30
2.3.2 Constructions of RGCs 32
2.3.2.1 Interference Alignment 33
2.3.2.2 Repair by Transfer 35
2.3.2.3 Product-Matrix 37
2.3.3 Rack-aware Regenerating Codes 40
2.3.3.1 Cross-rack Repair Model 41
2.3.3.2 Optimal Trade-off in RRCs 42
2.3.3.3 Construction of Cross-rack RGCs 46
2.4 Array Codes 47
2.4.1 Introduction to Array Codes 47
2.4.2 A Coding Framework for Binary Array Codes 51
2.4.3 Binary Vandermonde Array Codes 53
2.4.3.1 Construction of BVACs 54
2.4.3.2 Decoding Methods of BVACs 56
2.4.4 Binary Cauchy Array Codes 59
2.4.4.1 Construction of BCACs 59
2.4.4.2 Decoding Methods of BCACs 61
2.4.5 Optimization of MDS Array Codes 65
2.4.5.1 Repair Bandwidth 65
2.4.5.2 Locally Repairable Property 67
2.4.5.3 Computational Complexity 68
2.5 Codes with Locality 70
2.5.1 Introduction to LRCs 71
2.5.1.1 Information Symbol Locality Locally Repairable Codes 71
2.5.1.2 All-symbol Locality Locally Repairable Codes 72
2.5.2 Locally Regenerating Codes 73
2.5.2.1 MSR-local Codes 74
2.5.2.2 MBR-local Codes 74
2.5.3 II Codes 76
2.6 Chapter Summary 81
Discussion Questions 81
References 83
3 Optimization for Practicality 93
3.1 Practicality in System Level 93
3.1.1 Distributed Storage Based on MDS Codes 93
3.1.1.1 Storage Coding Based on MDS Codes 94
3.1.1.2 Data Storage Device 94
3.1.2 Trade-off of Replication and ECs 96
3.1.3 Coding Optimization for Realistic Scenarios 98
3.1.3.1 Optimization for Heterogeneous Systems 98
3.1.3.2 Optimization for Block Distribution 99
3.1.3.3 Optimization for System-level Coding 100
3.2 Practical ECs 102
3.2.1 BRS Codes 102
3.2.1.1 Encoding Process of BRS Code 102
3.2.1.2 Decoding Process of BRS Code 103
3.2.2 Binary Regenerating Codes 105
3.2.2.1 BMSR Codes 108
3.2.2.2 BMBR Codes 111
3.2.3 Butterfly Codes 114
3.2.3.1 Encoding Process of Butterfly Codes 115
3.2.3.2 Decoding Process of Butterfly Codes 116
3.2.4 Clay Codes 118
3.2.5 Practical LRCs 124
3.2.5.1 LRCs inWAS 124
3.2.5.2 LRCs in HDFS-RAID 127
3.3 Chapter Summary 129
Discussion Questions 129
References 130
4 Optimization for Fault Recovery 133
4.1 Optimization Based on ECs 133
4.1.1 Fractional Repetition Codes 134
4.1.2 Self-repairing Codes 139
4.1.3 RGCs for Multiple Failed Nodes 141
4.2 Optimization Based on Network Topology 143
4.2.1 Repair Tree: Fast Repair for Single Node 143
4.2.1.1 Decomposing Computation 146
4.2.1.2 Repair Model 147
4.2.1.3 Construction of Repair Tree 149
4.2.2 Tree-Structured Repair Scheme for Multiple Nodes 151
4.2.2.1 Preliminaries 153
4.2.2.2 Modeling and Optimization of Tree-Structure Repair 155
4.3 Chapter Summary 159
Discussion Questions 159
References 160
5 Distributed Storage Systems 165
5.1 Background and Introduction 165
5.2 Tectonic: Facebook’s Scalable File Storage System 168
5.2.1 Overview 168
5.2.2 Architecture 169
5.2.3 Core Components and Functions 171
5.2.3.1 Chunk Store 171
5.2.3.2 Metadata Store 172
5.2.3.3 Client Library 173
5.2.3.4 Background Services 173
5.3 Ambry: LinkedIn’s Scalable Geo-distributed Object Storage System 174
5.3.1 Overview 174
5.3.2 Architecture 175
5.3.3 Core Components and Functions 179
5.3.3.1 Cluster Manager 179
5.3.3.2 Frontend Layer 179
5.3.3.3 Data Layer 182
5.3.3.4 Load Balancing 183
5.3.3.5 Replication 184
5.4 Evolution of Alibaba’s Cloud Block Storage 186
5.4.1 Elastic Block Storage I 186
5.4.2 Elastic Block Storage II 187
5.4.3 Elastic Block Storage III 190
5.5 Distributed Key-Value Storage Systems 192
5.5.1 Storage Engines 192
5.5.1.1 Hash Table 192
5.5.1.2 B+ Tree 194
5.5.1.3 LSM-Tree 195
5.5.2 Data Layout 197
5.5.3 Distributed Replication 198
5.5.4 Distributed Secondary Indexes 199
5.6 Chapter Summary 201
References 202
6 Integrating Blockchain in Distributed Storage Systems 207
6.1 Fundamentals of Blockchain 207
6.1.1 Introduction to Blockchain 207
6.1.2 Key Technologies 208
6.1.2.1 Smart Contracts 209
6.1.2.2 Consensus Mechanisms 209
6.2 Blockchain-based Decentralized Storage 217
6.2.1 InterPlanetary File System 217
6.2.1.1 System Architecture 218
6.2.1.2 Core Functions 219
6.2.1.3 Application Prospects 220
6.2.2 DDSs: Sia and Storj 221
6.2.2.1 Sia 221
6.2.2.2 Storj 226
6.3 DSS Based on Blockchain and Mimic Security 229
6.3.1 Background and Introduction 229
6.3.2 Mimic Distributed Secure Storage System 230
6.3.2.1 System Principle 230
6.3.2.2 System Architecture 232
6.3.2.3 Core Functions 234
6.3.3 Logging System Based on Consortium Blockchain 236
6.3.3.1 System Architecture 236
6.3.3.2 Core Function 237
6.4 Chapter Summary 240
References 241
7 Quantum Bit, Q-Computers, and Q-Networks 243
7.1 Fundamental Principles of Quantum Computing 243
7.1.1 The Concept and Properties of Quantum Bits 243
7.1.2 Quantum Gates and Quantum Circuits 252
7.1.2.1 The Bell Circuit 258
7.1.2.2 Reverse Bell Circuit 259
7.1.2.3 Greenberger-Horne-Zeilinger (GHZ) Circuit 259
7.2 Quantum Memory and Quantum Computer 263
7.2.1 Quantum Memory 263
7.2.1.1 Electromagnetically Induced Transparency Quantum Memory 264
7.2.1.2 DLCZ Memory Scheme 265
7.2.1.3 Quantum Memory Based on Faraday Interaction 266
7.2.1.4 Atomic Frequency Comb Quantum Memory 267
7.2.2 Quantum Computer 268
7.2.2.1 Ion Trap Quantum Computing 270
7.2.2.2 Superconducting Quantum Computing 271
7.2.2.3 Photonic Quantum Computing 271
7.2.2.4 Neutral Atom Quantum Computing 272
7.3 Quantum Secure Transmission 273
7.3.1 Quantum Key Distribution 274
7.3.2 Superdense Coding 276
7.3.3 Quantum Teleportation 277
7.3.4 Quantum Error Correction Codes 279
7.4 Quantum Computer Networks 282
7.4.1 Quantum Internet 282
7.4.2 Quantum Multi-identifier Network Architecture With Quantum Identifier 289
7.5 Chapter Summary 296
References 297
Index 301
