Main Memory Management on Relational Database Systems

Description

This book provides basic knowledge about main memory management in relational databases as it is needed to support large-scale applications processed completely in memory. In business operations, real-time predictability and high speed is a must. Hence every opportunity must be exploited to improve performance, including reducing dependency on the hard disk, adding more memory to make more data resident in the memory, and even deploying an in-memory system where all data can be kept in memory. The book provides one chapter for each of the main related topics, i.e. the memory system, memory management, virtual memory, and databases and their memory systems, and it is complemented by a short survey of six commercial systems: TimesTen, MySQL, VoltDB, Hekaton, HyPer/ScyPer, and SAP HANA. Preface Acknowledgements Contents Chapter 1 The Memory System 1.1 Von Neumann Architecture 1.2 Memory 1.3 Memory Organization 1.4 Memory Technologies 1.4.1 Register 1.4.2 Cache 1.4.3 SRAM: Static Random Access Memory 1.4.4 DRAM: Dynamic Random Access Memory 1.4.5 Flash Memory 1.4.6 NVM: Non Volatile Memory 1.4.7 Magnetic Disks 1.5 NUMA: Non-Uniform Memory Access Chapter 2 Memory Management 2.1 Background 2.2 Address Binding 2.3 Logical and Physical Address Space 2.4 Dynamic Loading 2.5 Dynamic Linking and Shared Libraries 2.6 Swapping 2.6.1 Standard Swapping 2.7 Cache Management 2.7.1 Cache Misses 2.7.2 Writing into the Cache 2.7.3 Cache Associativity 2.7.4 Block Replacement 2.7.5 Multilevel Caches 2.8 Contiguous Memory Allocation 2.9 Fragmentation 2.10 Segmentation 2.11 Paging 2.11.1 Hardware Support 2.11.2 Shared Memory 2.12 Page Table Organization 2.12.1 Hierarchical Paging 2.12.2 Hashed Page Table 2.12.3 Inverted Page Table 2.13 Memory Protection 2.13.1 Protection in Contiguous Memory Allocation 2.13.2 Protection in Paged Memory Chapter 3 Virtual Memory 3.1 Basic Concepts 3.1.1 Page Access 3.1.2 The TLB: Translation Lookaside Buffer 3.1.3 Virtualization Challenges 3.2 Demand Paging 3.2.1 Basic Concepts 3.2.2 Performance Considerations 3.3 Page Replacement 3.3.1 Basic Page Replacement 3.3.2 FIFO and Optimal Page Replacement 3.3.3 LRU Page Replacement 3.3.4 LRU Approximation Page Replacement 3.3.5 Counting Based Page Replacement 3.3.6 Page Buffering 3.3.7 Applications and Page Replacement 3.4 Allocation of Frames 3.4.1 Allocation Algorithms 3.4.2 Allocation Scope 3.4.3 Non Uniform Memory Access considerations 3.5 Memory Protection on Virtual Memory 3.6 Thrashing 3.6.1 TheWorking Set Model 3.6.2 Page Fault Frequency 3.7 A Common Framework for Managing Memory 3.7.1 Block Placement 3.7.2 Block Access 3.7.3 Block Replacement in Cache Miss 3.7.4 Parallelism and Memory Hierarchy 3.8 Other Considerations 3.8.1 Pre-Paging 3.8.2 Page Size 3.8.3 TLB Reach 3.8.4 Inverted Page Table 3.8.5 Program Structure 3.8.6 Page Locking 3.8.7 Memory Mapped Files 3.8.8 Kernel Memory Allocation 3.8.9 Virtual Machines 3.9 Hardware Memory Management Real Examples 3.9.1 Memory Management in the IA-32 Architecture 3.9.2 Memory Management in the AMD64 Architecture Chapter 4 Databases and the Memory System 4.1 Database Management System 4.1.1 Data-Definition Language Commands 4.1.2 Query Processing 4.1.3 Storage and Buffer Management 4.1.4 Transaction Processing 4.1.5 The Query Processor 4.2 In-Memory Data Bases 4.3 Types of Databases 4.3.1 The Object Model 4.3.2 In-Memory NoSQL Databases 4.4 The Relational Model 4.4.1 Relational Database Storage Structures 4.4.2 User Interface 4.4.3 DatabaseWorkload 4.5 Database Storage Management 4.5.1 Data on External Storage 4.5.2 File Organization 4.5.3 Indexing 4.6 Index Data Structures 4.7 Storing Data: Disks and Files 4.7.1 The Memory Hierarchy 4.7.2 Disks 4.7.3 Redundant Array of Independent Disks 4.7.4 Disk Space Management 4.7.5 Buffer Management 4.7.6 Data Storage Implementation 4.7.7 Page Formats 4.7.8 Fixed Length Records 4.7.9 Variable Length Records 4.7.10 Record Formats 4.8 Tree Structured Indexes 4.8.1 Indexed Sequential Access Method (ISAM) 4.8.2 B+Trees 4.9 Hash Based Indexes 4.9.1 Static Hashing 4.9.2 Extensible Hashing 4.9.3 Linear Hashing Chapter 5 Database Systems: Real Examples 5.1 TimesTen In-Memory Database 5.1.1 Overview 5.1.2 Memory Management 5.2 MySQL Database 5.2.1 Background 5.2.2 Architecture 5.2.3 Storage Engines 5.3 H-Store / VoltDB Data Base Systems 5.3.1 Transaction Processing 5.3.2 Data Overflow 5.3.3 Fault Tolerance 5.4 Hekaton Data Base System 5.4.1 Multi-version Concurrency Control 5.4.2 Latch-Free Bw-Tree 5.4.3 Siberia in Hekaton 5.5 HyPer/ScyPer Data Base Systems 5.5.1 Snapshot in HyPer 5.5.2 Register-Conscious Compilation 5.5.3 ART Indexing 5.6 SAP HANA Data Base System 5.6.1 Relational Stores 5.6.2 Rich Data Analytics Support 5.6.3 Temporal Query References