Database Internals. A Deep Dive into How Distributed Data Systems Work - Helion

ebook

Autor: Alex Petrov
ISBN: 978-14-920-4030-9
stron: 376, Format: ebook
Data wydania: 2019-09-13
Księgarnia: Helion

Cena książki: 186,15 zł (poprzednio: 216,45 zł)
Oszczędzasz: 14% (-30,30 zł)

Osoby, które kupiły tę książkę, wybierały także »

When it comes to choosing, using, and maintaining a database, understanding its internals is essential. But with so many distributed databases and tools available today, it’s often difficult to understand what each one offers and how they differ. With this practical guide, Alex Petrov guides developers through the concepts behind modern database and storage engine internals.

Throughout the book, you’ll explore relevant material gleaned from numerous books, papers, blog posts, and the source code of several open source databases. These resources are listed at the end of parts one and two. You’ll discover that the most significant distinctions among many modern databases reside in subsystems that determine how storage is organized and how data is distributed.

This book examines:

Storage engines: Explore storage classification and taxonomy, and dive into B-Tree-based and immutable Log Structured storage engines, with differences and use-cases for each
Storage building blocks: Learn how database files are organized to build efficient storage, using auxiliary data structures such as Page Cache, Buffer Pool and Write-Ahead Log
Distributed systems: Learn step-by-step how nodes and processes connect and build complex communication patterns
Database clusters: Which consistency models are commonly used by modern databases and how distributed storage systems achieve consistency

Osoby które kupowały "Database Internals. A Deep Dive into How Distributed Data Systems Work", wybierały także:

Windows Media Center. Domowe centrum rozrywki 66,67 zł, (8,00 zł -88%)
Ruby on Rails. Ćwiczenia 18,75 zł, (3,00 zł -84%)
DevOps w praktyce. Kurs video. Jenkins, Ansible, Terraform i Docker 190,00 zł, (39,90 zł -79%)
Przywództwo w świecie VUCA. Jak być skutecznym liderem w niepewnym środowisku 58,64 zł, (12,90 zł -78%)
Scrum. O zwinnym zarządzaniu projektami. Wydanie II rozszerzone 58,64 zł, (12,90 zł -78%)

Spis treści

Database Internals. A Deep Dive into How Distributed Data Systems Work eBook -- spis treści

Preface
- How to Contact Us
I. Storage Engines
1. Introduction and Overview
- DBMS Architecture
- Memory- Versus Disk-Based DBMS
  - Durability in Memory-Based Stores
- Column- Versus Row-Oriented DBMS
  - Row-Oriented Data Layout
  - Column-Oriented Data Layout
  - Distinctions and Optimizations
  - Wide Column Stores
- Data Files and Index Files
  - Data Files
  - Index Files
  - Primary Index as an Indirection
- Buffering, Immutability, and Ordering
- Summary
2. B-Tree Basics
- Binary Search Trees
  - Tree Balancing
  - Trees for Disk-Based Storage
- Disk-Based Structures
  - Hard Disk Drives
  - Solid State Drives
  - On-Disk Structures
- Ubiquitous B-Trees
  - B-Tree Hierarchy
  - Separator Keys
  - B-Tree Lookup Complexity
  - B-Tree Lookup Algorithm
  - Counting Keys
  - B-Tree Node Splits
  - B-Tree Node Merges
- Summary
3. File Formats
- Motivation
- Binary Encoding
  - Primitive Types
  - Strings and Variable-Size Data
  - Bit-Packed Data: Booleans, Enums, and Flags
- General Principles
- Page Structure
- Slotted Pages
- Cell Layout
- Combining Cells into Slotted Pages
- Managing Variable-Size Data
- Versioning
- Checksumming
- Summary
4. Implementing B-Trees
- Page Header
  - Magic Numbers
  - Sibling Links
  - Rightmost Pointers
  - Node High Keys
  - Overflow Pages
- Binary Search
  - Binary Search with Indirection Pointers
- Propagating Splits and Merges
  - Breadcrumbs
- Rebalancing
- Right-Only Appends
  - Bulk Loading
- Compression
- Vacuum and Maintenance
  - Fragmentation Caused by Updates and Deletes
  - Page Defragmentation
- Summary
5. Transaction Processing and Recovery
- Buffer Management
  - Caching Semantics
  - Cache Eviction
  - Locking Pages in Cache
  - Page Replacement
    - FIFO and LRU
    - CLOCK
    - LFU
- Recovery
  - Log Semantics
  - Operation Versus Data Log
  - Steal and Force Policies
  - ARIES
- Concurrency Control
  - Serializability
  - Transaction Isolation
  - Read and Write Anomalies
  - Isolation Levels
  - Optimistic Concurrency Control
  - Multiversion Concurrency Control
  - Pessimistic Concurrency Control
  - Lock-Based Concurrency Control
    - Deadlocks
    - Locks
    - Latches
    - Readers-writer lock
    - Latch crabbing
    - Blink-Trees
- Summary
6. B-Tree Variants
- Copy-on-Write
  - Implementing Copy-on-Write: LMDB
- Abstracting Node Updates
- Lazy B-Trees
  - WiredTiger
  - Lazy-Adaptive Tree
- FD-Trees
  - Fractional Cascading
  - Logarithmic Runs
- Bw-Trees
  - Update Chains
  - Taming Concurrency with Compare-and-Swap
  - Structural Modification Operations
  - Consolidation and Garbage Collection
- Cache-Oblivious B-Trees
  - van Emde Boas Layout
- Summary
7. Log-Structured Storage
- LSM Trees
  - LSM Tree Structure
    - Two-component LSM Tree
    - Multicomponent LSM Trees
    - In-memory tables
  - Updates and Deletes
  - LSM Tree Lookups
  - Merge-Iteration
  - Reconciliation
  - Maintenance in LSM Trees
    - Leveled compaction
    - Size-tiered compaction
- Read, Write, and Space Amplification
  - RUM Conjecture
- Implementation Details
  - Sorted String Tables
  - Bloom Filters
  - Skiplist
  - Disk Access
  - Compression
- Unordered LSM Storage
  - Bitcask
  - WiscKey
- Concurrency in LSM Trees
- Log Stacking
  - Flash Translation Layer
  - Filesystem Logging
- LLAMA and Mindful Stacking
  - Open-Channel SSDs
- Summary
Part I Conclusion
II. Distributed Systems
8. Introduction and Overview
- Concurrent Execution
  - Shared State in a Distributed System
- Fallacies of Distributed Computing
  - Processing
  - Clocks and Time
  - State Consistency
  - Local and Remote Execution
  - Need to Handle Failures
  - Network Partitions and Partial Failures
  - Cascading Failures
- Distributed Systems Abstractions
  - Links
    - Fair-loss link
    - Message acknowledgments
    - Message retransmits
    - Problem with retransmits
    - Message order
    - Exactly-once delivery
- Two Generals Problem
- FLP Impossibility
- System Synchrony
- Failure Models
  - Crash Faults
  - Omission Faults
  - Arbitrary Faults
  - Handling Failures
  - Summary
9. Failure Detection
- Heartbeats and Pings
  - Timeout-Free Failure Detector
  - Outsourced Heartbeats
- Phi-Accural Failure Detector
- Gossip and Failure Detection
- Reversing Failure Detection Problem Statement
- Summary
10. Leader Election
- Bully Algorithm
- Next-In-Line Failover
- Candidate/Ordinary Optimization
- Invitation Algorithm
- Ring Algorithm
- Summary
11. Replication and Consistency
- Achieving Availability
- Infamous CAP
  - Use CAP Carefully
  - Harvest and Yield
- Shared Memory
- Ordering
- Consistency Models
  - Strict Consistency
  - Linearizability
    - Linearization point
    - Cost of linearizability
  - Sequential Consistency
  - Causal Consistency
    - Vector clocks
- Session Models
- Eventual Consistency
- Tunable Consistency
- Witness Replicas
- Strong Eventual Consistency and CRDTs
- Summary
12. Anti-Entropy and Dissemination
- Read Repair
- Digest Reads
- Hinted Handoff
- Merkle Trees
- Bitmap Version Vectors
- Gossip Dissemination
  - Gossip Mechanics
  - Overlay Networks
  - Hybrid Gossip
  - Partial Views
- Summary
13. Distributed Transactions
- Making Operations Appear Atomic
- Two-Phase Commit
  - Cohort Failures in 2PC
  - Coordinator Failures in 2PC
- Three-Phase Commit
  - Coordinator Failures in 3PC
- Distributed Transactions with Calvin
- Distributed Transactions with Spanner
- Database Partitioning
  - Consistent Hashing
- Distributed Transactions with Percolator
- Coordination Avoidance
- Summary
14. Consensus
- Broadcast
- Atomic Broadcast
  - Virtual Synchrony
  - Zookeeper Atomic Broadcast (ZAB)
- Paxos
  - Paxos Algorithm
  - Quorums in Paxos
  - Failure Scenarios
  - Multi-Paxos
  - Fast Paxos
  - Egalitarian Paxos
  - Flexible Paxos
  - Generalized Solution to Consensus
    - Generalized Paxos algorithm
- Raft
  - Leader Role in Raft
  - Failure Scenarios
- Byzantine Consensus
  - PBFT Algorithm
  - Recovery and Checkpointing
- Summary
Part II Conclusion
A. Bibliography
Index