Checkpoints & Shadow Paging

Duration: 12 min

This video lesson is available to enrolled students.

Return to /learn/DSSSB-TGT-COMPUTER-SCIENCE-PAPER-2/data-base-management-system/database-recovery/advanced-recovery-algorithms/asset-checkpoints-shadow-paging after enrolling

Inside: a video lesson and guided study material.

Module outline

  1. About Course: About the Course
  2. Programming, Data Structures, OOP & Java: C Fundamentals, Control Flow, Functions, Arrays & Pointers, Storage Classes, Structures & Enums, DMA, Macros, Scoping & File Handling, Introduction to DS, Array, Stack, Queue, Linked List, Tree, Graphs, Hashing, Java, OOPS with C++, Java Fundamentals, Array, String, IO & References, Language Design, Intro to Compilers, Visual Basics, Syntax Analysis: Bottom-Up, Object Oriented Technology
  3. Computer Networks, TCP/IP & Network Security: Introduction to CN, Data Communication, DLL: Flow Control, DLL: Access Control, DLL: Error Control, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware basics, Network Access Technologies, Network Security, Society, Law & Ethics, Cloud Computing, Mobile Computing, Net Layer:Routing Protocol, Cyber Safety and Security
  4. Teaching Methodology: वृद्धि और विकास / Growth and Development, Concept of Pedagogy, विकास के सिद्धांत / Theories of Development, समावेशी शिक्षा / Inclusive Education, Experiential Pedagogy, आकलन और मूल्यांकन / Assessment and Evaluation, समाजीकरण और जेंडर / Socialisation and Gender, National Education Policy (NEP) 2020, संज्ञानात्मक प्रक्रियाएँ / Cognitive Processes, शिक्षण योजना और शिक्षण कौशल / Teaching Planning and Teaching Skills, Personality Development, शिक्षण विधियाँ / Teaching Methods, अधिगम और व्यवहारवादी सिद्धांत / Learning and Behavioural Theories, Learners & Learning Process, Factors Affecting Teaching, शिक्षण विधियाँ एवं उपागम / Teaching Methods and Approaches, शिक्षण-अधिगम प्रक्रिया एवं कक्षा प्रबंधन / Teaching-Learning Process and Classroom Management, शिक्षण सहायक सामग्री एवं शैक्षिक तकनीकी / Teaching Aids and Educational Technology, सूक्ष्म शिक्षण एवं कक्षा संप्रेषण / Microteaching and Classroom Communication, आकलन एवं मूल्यांकन / Assessment and Evaluation, पाठ्यचर्या, कला एवं सह-शैक्षिक क्षेत्र / Curriculum, Arts and Co-curricular Areas, दिव्यांग बच्चों की शिक्षा / Education of Children with Disabilities, शिक्षक: गुण, व्यावसायिक नैतिकता एवं विकास / Teacher: Qualities, Professional Ethics and Development
  5. Digital Electronics / Boolean Logic: Digital Systems & Boolean Basics, Logic Gates & Hardware, Boolean Expression, Boolean Minimization, Combinational Circuit, Sequential Circuits, Number System, Number Representation, Analog-Digital Conversion
  6. Operating Systems & Linux: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Threads & Process Creation, Deadlock, Memory Management, Virtual Memory, File Management, Disc Scheduling, Unix OS, Linux OS, Distributed Systems, Windows OS
  7. Data Base Management System: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, Relational Algebra, SQL, File Organization & Indexing, Transaction Management, Concurrency Control, Database Security & Authorization, Database Recovery, Data Warehousing & Mining
  8. Internet & Web Technologies: Website, Browser & Services, Internet Fundamentals, Web Design & Development, Protocols & Services, Web Publishing & Hosting, Server Side & Security, HTML Basics, CSS, Emerging Technologies, JavaScript-Basics, .Net Programming, Electronic Data Interchange and E-Commerce, XML
  9. Computer Fundamentals, IT Basics & Architecture: Basics of COA, Cache Memory Organization, Input Output Organisation, Register Transfer and Microoperations, Control Unit Design, Programming the Basic Computer, Terms & Abbreviations, MS Office Applications, Instr Formats & Modes, Floating Point Rep, कंप्यूटर के मूल सिद्धांत / Computer Fundamentals, साइबर सुरक्षा / Cyber Safety and Security, कंप्यूटर सॉफ़्टवेयर / Computer Software, ऑपरेटिंग सिस्टम / Operating System, वर्ड प्रोसेसिंग (MS Word) / Word Processing (MS Word), कंप्यूटर नेटवर्क / Computer Networks, प्रेज़ेंटेशन (MS PowerPoint) / Presentation Software (MS PowerPoint)
  10. Python Language: Introduction to Python, Tokens, Variables, Data Types, I/O, Operators & Expressions, Control Flow & Looping, Collections & Strings, Functions & Modules, File Handling & Data Analysis
  11. Software Engineering: Fundamentals of Software Engineering, Software Requirements and Quality Assurance, Software Design, Estimation and Metrics, Software Testing, Software Maintenance and Configuration Management, extras, Fundamentals of Systems and Information Systems
  12. Design & Analysis of Algorithms: Algorithm Analysis, Time Complexity Analysis, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Minimum Spanning Trees, Shortest Path Algos, Advanced Algorithms
  13. Mathematics - I, II, III, IV: Permutation and Combination, Logarithm, Linear Algebra, Algebra, Calculus, Trigonometry, Vectors, Set Theory, Functions, Relations, Propositional and Predicate Logic, Research Process Steps, Graph Theory, समुच्चय, संबंध, फलन और विविक्त गणित / Sets, Relations, Functions and Discrete Mathematics, संख्या पद्धति और संख्या सिद्धांत / Number Systems and Number Theory, यूक्लिडीय ज्यामिति और क्षेत्रमिति / Euclidean Geometry and Mensuration, सांख्यिकी और प्रायिकता / Statistics and Probability, निर्देशांक ज्यामिति, सदिश और त्रिविमीय ज्यामिति / Coordinate Geometry, Vectors and 3D Geometry, बहुपद, समीकरण और सम्मिश्र संख्याएँ / Polynomials, Equations and Complex Numbers, समतल क्षेत्रमिति / Plane Mensuration, प्रतिचयन / Sampling, प्रतिशत / Percentage, सरलीकरण, घातांक और करणी / Simplification, Indices and Surds, अनुपात और समानुपात / Ratio and Proportion
  14. Computer Graphics, Multimedia & Mobile Computing: Basics of Computer Graphics, 2-D Geometrical Transforms and Viewing, 3-D Object Representation, Geometric Transformations and Viewing, Multimedia
  15. Emerging Trends: Emerging Tech Trends, Knowledge Representation, Natural Language Processing, व्यापार, विपणन एवं उपभोक्ता संरक्षण / Trade, Marketing and Consumer Protection
  16. Statistical Techniques: Probability, Statistics
  17. Interpolation - DI: आँकड़ा निर्वचन / Data Interpretation
  18. Basis of Physics: वैज्ञानिक उपलब्धियाँ और अनुसंधान / Scientific Achievements and Research
  19. Previous Year Paper:
  20. Business Studies and Management: Business Communication, प्रबंध के सिद्धांत एवं कार्य / Principles and Functions of Management, लेखांकन के आधार एवं लेन-देनों का अभिलेखन / Accounting Fundamentals and Recording of Transactions, Business Economics, ह्रास, अंतिम खाते व कंप्यूटरीकृत लेखांकन / Depreciation, Final Accounts and Computerised Accounting, Knowledge Management & New Economy
AI summary & chapters

AI Summary

An AI-generated summary of this video lecture.

This educational video provides a comprehensive overview of database recovery techniques, focusing on checkpoints and shadow paging. The lecture begins by explaining the inefficiency of redoing or undoing all transactions from a log after a system failure, especially when the log is long. To address this, it introduces checkpoints as a mechanism to periodically save the state of the database, reducing recovery time. The video then transitions to shadow paging, an alternative to log-based recovery. It explains that shadow paging uses two page tables: a current page table and a shadow page table. The current page table is used for all data accesses during a transaction, while the shadow page table is stored in nonvolatile storage. The core idea is that when a page is written for the first time, a copy is made to an unused page, and the current page table is updated to point to this copy. The video uses diagrams to illustrate the process of a transaction beginning, where the current page table is copied to the shadow page table, and the shadow page table is saved. It also shows how to recover from a failure by discarding the current page table and making the shadow page table the new current one. Finally, the video discusses the advantages and disadvantages of shadow paging, noting that it eliminates the overhead of writing log records and makes recovery trivial, but it suffers from data fragmentation and requires expensive garbage collection. A potential optimization is mentioned: using a B+ tree structure for the page table to only copy the paths to updated leaf nodes, rather than the entire table.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The video begins with a slide titled 'Checkpoints'. It explains that redoing or undoing all transactions from a log can be very slow, especially if the system has been running for a long time, as it may require redoing transactions that have already been committed. To streamline the recovery process, the video introduces the concept of periodically performing checkpoints. The steps for a checkpoint are listed: 1) Output all log records currently in main memory to stable storage. 2) Output all modified buffer blocks to the disk. 3) Write a log record <checkpoint> to stable storage, along with a list L of all transactions active at the time of the checkpoint. The slide also notes that all updates are stopped during the checkpointing process.

  2. 2:00 – 5:00 02:00-05:00

    The video transitions to a new topic, 'Shadow Paging', which is presented as an alternative to log-based recovery. The slide explains that in this technique, the database is considered to be made up of fixed-size disk blocks or pages. The core idea is to maintain two page tables during a transaction's lifetime: the current page table and the shadow page table. The current page table is used for all data item accesses, while the shadow page table is stored in nonvolatile storage. This allows the state of the database prior to transaction execution to be recovered. The slide concludes by stating that this technique provides atomicity and durability.

  3. 5:00 – 10:00 05:00-10:00

    This segment details the mechanics of shadow paging. The first slide explains that at the start, both the current and shadow page tables are identical, and only the current page table is used for data access. When a page is written for the first time, a copy of that page is made to an unused page, the current page table is updated to point to this copy, and the update is performed on the copy. A diagram titled 'Sample Page Table' illustrates this, showing a page table with pointers to pages on disk, and a 'free page' pointer. The next slide, 'Example of Shadow Paging', shows a visual representation of the two page tables. It demonstrates that when a transaction modifies a page, the current page table is updated to point to a new copy of that page, while the shadow page table remains unchanged, preserving the pre-transaction state.

  4. 10:00 – 11:32 10:00-11:32

    The final segment covers the commit and recovery process. A flowchart shows that when a transaction begins, the current page table is copied to the shadow page table, which is then saved. To recover from a failure, the current page table is discarded, and the shadow page table becomes the new current page table. The slide on committing a transaction outlines three steps: flush modified pages to disk, output the current page table to disk, and make the current page table the new shadow page table by updating a pointer. The video concludes with a slide on the advantages and disadvantages. Advantages include no overhead for writing log records and trivial recovery. Disadvantages include data fragmentation and expensive garbage collection, which can be mitigated by using a B+ tree structure for the page table.

The video presents a logical progression from a common recovery problem to a specific solution. It starts by identifying the performance bottleneck of log-based recovery, which is the need to process a potentially massive log after a crash. The solution, checkpoints, is introduced as a way to create a 'snapshot' of the database state, reducing the amount of work needed for recovery. The video then pivots to a fundamentally different approach: shadow paging. This technique avoids the log entirely by using a copy-on-write strategy with two page tables. The core concept is that the shadow page table acts as a persistent, unmodified backup of the database state before a transaction started. This allows for a simple and fast recovery by simply discarding the current, potentially corrupted, state and reverting to the shadow state. The video effectively contrasts the two methods, highlighting the trade-offs: checkpoints are a modification of the log-based approach, while shadow paging is a complete alternative that offers faster recovery at the cost of increased storage overhead and complexity in managing data fragmentation.

Loading lesson…