Computer Science › Sistemas
Distingue o trabalho real de um SGBD (escritas atômicas e duráveis, acesso compartilhado e concorrente de muitas aplicações ao mesmo tempo, sobreviver a um travamento no meio de uma escrita e uma interface de consulta declarativa sobre páginas brutas de disco) do que um esquema de arquivos planos no nível da aplicação (um CSV por entidade, analisado à mão) jamais consegue oferecer, usando o próprio enquadramento da disciplina do CMU 15-445 ('este curso é sobre o projeto/implementação de SGBDs... não sobre como usar um SGBD para construir aplicações') para definir o escopo de tudo o que vem a seguir: esta disciplina constrói o motor, não ensina o uso de SQL.
Define uma relação como Codd originalmente fez (um subconjunto do produto cartesiano de uma lista de domínios, exatamente a relação da teoria dos conjuntos e o produto cartesiano já construídos em `relations-and-their-properties` e `power-sets-and-cartesian-products`, agora reaplicados a linhas e colunas em vez de pares abstratos) e depois constrói à mão os operadores fechados centrais da álgebra relacional (σ seleção, π projeção, ∪, ∩, −, ×, ⋈ join) sobre um pequeno schema de duas tabelas, estabelecendo o alvo declarativo para o qual todo plano de consulta desta disciplina eventualmente compila.
Apresenta a página de banco de dados como a unidade de E/S de tamanho fixo contra o disco, exatamente o mesmo raciocínio baseado em blocos que `files-directories-and-inodes` já usou para explicar por que um sistema de arquivos lê e escreve em blocos fixos em vez de byte a byte. Depois trabalha a organização em heap file (uma coleção não ordenada de páginas mais um diretório de páginas rastreando as suas localizações) e o layout de página com slots que sistemas reais usam para que uma página de slots de tamanho fixo consiga guardar tuplas de tamanho variável e sobreviver a remoções sem deslocar toda tupla posterior.
O buffer pool é o cache de páginas do próprio SGBD, situado entre o motor de consultas e o disco, duplicando deliberadamente o que um cache de arquivos do SO já faz: contadores de pin, bits de sujo e uma política de substituição (clock/LRU, exatamente a mesma decisão de despejo que `page-replacement-policies` já resolveu para frames físicos) decidem quais páginas permanecem residentes. Ele também nomeia STEAL (despejar uma página suja antes que a sua transação confirme) e NO-FORCE (não forçar uma página suja para o disco no commit) como as duas escolhas de política do buffer pool que tornam a recuperação de travamentos, vários conceitos adiante, um problema real em vez de trivial.
Uma B+Tree mantém exatamente o mesmo tipo de invariante explícito de balanceamento que `avl-trees-the-balance-invariant` já provou ser necessário para evitar o problema de altura degenerada que `bst-performance-and-balance` levantou para uma árvore binária desbalanceada, mas o aplica a uma família estrutural genuinamente diferente: uma árvore m-ária (e não binária), com todo nó pelo menos meio cheio e toda folha na mesma profundidade, com o fanout escolhido para casar com o tamanho de uma página de disco, de modo que descer um nível custa exatamente uma E/S de página, resolvendo diretamente o ângulo de E/S de disco que o balanceamento de uma árvore binária sozinho nunca foi projetado para tratar.
Rastreia uma inserção completa em árvore B+ à mão numa pequena árvore real, cobrindo o caso que transborda uma folha e força uma divisão (redistribuir suas entradas uniformemente por duas folhas, copiar a chave do meio para cima no pai como separador) e o caso em que essa divisão se propaga para um nó interno (redistribuir uniformemente, mas empurrar a chave do meio para cima em vez de copiá-la, já que nós internos não armazenam dados), preservando o invariante meio-cheio em todo nível sem nunca rebalancear a árvore inteira.
Completa a árvore B+ rastreando uma remoção que faz uma folha cair abaixo do mínimo meio-cheio na mesma árvore construída no conceito anterior: o nó primeiro tenta emprestar (redistribuir) uma entrada de um irmão que tem espaço de sobra, e recorre a fundir com um irmão e remover a chave separadora agora vazia do pai apenas quando emprestar não é possível, incluindo o caso em que uma fusão se propaga para cima e encolhe a altura da árvore em um nível.
Constrói um índice hash residente em disco diretamente sobre a maquinaria de tabela hash em memória que `hashing-and-hash-functions` e `collision-resolution-open-addressing` já estabeleceram, mostrando exatamente o que muda quando um bucket é uma página de disco em vez de uma posição de array (páginas de overflow encadeadas a partir de um bucket cheio, esquemas de hashing extensível/linear que fazem o diretório crescer incrementalmente em vez de forçar um único rehash gigante de toda página) e por que um índice hash responde uma busca por igualdade em O(1) E/Ss de página, mas não consegue suportar uma consulta por intervalo de forma alguma.
Um guia de decisão concreto construído a partir dos números de custo reais dos quatro conceitos anteriores: uma carga de trabalho só de igualdade, sem consultas por intervalo, favorece a busca O(1) de um índice hash, enquanto qualquer coisa que precise de varreduras por intervalo, iteração ordenada ou saída ordenada precisa da travessia O(log n) de uma B+Tree, conferido com `mongodb-indexing-fundamentals` de `database-concepts`, que documenta um sistema real de produção usando por padrão índices B+Tree exatamente por esse motivo, a mesma família estrutural construída aqui do zero.
Um plano de consulta é uma árvore de operadores físicos, cada um implementando exatamente a mesma interface baseada em pull, de next() até se esgotar, que `iterators` já estabeleceu para percorrer qualquer coleção de forma uniforme: uma varredura sequencial puxa tuplas página por página pelo buffer pool, uma varredura por índice as puxa em vez disso pela B+Tree ou pelo índice hash construídos no bloco anterior, e o plano inteiro roda de forma preguiçosa, uma tupla por vez, dirigido inteiramente pelo operador raiz puxando repetidamente dos seus filhos.
Implementa o nested-loop join simples, uma tupla por vez, e conta o seu custo exato de E/S de páginas num pequeno exemplo de duas tabelas, e depois o melhora para o block nested-loop join lendo a relação externa o equivalente a um buffer inteiro de páginas por vez, em vez de uma tupla por vez. Os mesmos números trabalhados mostram concretamente por que a versão ingênua custa (páginas de R) × (páginas de S) buscas de página, enquanto a versão em blocos amortiza esse custo por um buffer inteiro de páginas externas a cada passada.
O sort-merge join reutiliza exatamente o passo de merge que `merge-sort-revisited` já construiu, agora aplicado a duas relações que já estão ordenadas (ou ordenadas externamente antes) pela chave de join, percorrendo os dois fluxos ordenados para frente juntos; o hash join, em vez disso, constrói uma tabela hash em memória sobre a chave de join da relação menor e a sonda uma vez por tupla da relação maior. Os dois são trabalhados sobre o mesmo conjunto de dados do conceito anterior, com o trade-off real tornado concreto: o sort-merge vence quando uma entrada já está ordenada ou a saída precisa sair ordenada, e o hash join vence nos demais casos, a menos que o lado de construção não caiba no buffer pool.
Uma única consulta declarativa tem muitos planos físicos equivalentes com custos reais muito diferentes. Este conceito constrói uma estimativa de custo a partir das mesmas cardinalidades de tabela e contagens de páginas já usadas nos conceitos de join, compara à mão duas ordens de join para uma pequena consulta de três tabelas e mostra que uma é mais barata, e distingue a otimização baseada em regras (heurísticas fixas, ex.: sempre empurrar seleções para baixo dos joins) da otimização baseada em custo (estimar e comparar custos num espaço de busca de planos), na profundidade Core-Tier2 que o ACM/IEEE CS2013 atribui a este tópico específico, e não num tratamento completo, de nível de pesquisa, dos internos de um otimizador de consultas.
Dá a Atomicidade, Consistência, Isolamento e Durabilidade suas definições reais e precisas em vez de apenas o acrônimo: Atomicidade como todas as escritas de uma transação surtindo efeito ou nenhuma delas, Consistência como um invariante de nível de aplicação que o SGBD impõe apenas indiretamente (dando as outras três garantias, não entendendo o invariante em si), Isolamento como transações concorrentes produzindo um resultado equivalente a alguma execução serial (uma de cada vez), Durabilidade como uma escrita confirmada sobrevivendo a qualquer travamento subsequente, fixando exatamente qual garantia cada um dos próximos cinco conceitos é individualmente responsável por entregar.
Antes de qualquer protocolo ser introduzido, este conceito mostra concretamente por que o isolamento é difícil: um agendamento trabalhado de duas transações sobre um par de contas bancárias (A, B), uma transação movendo dinheiro de A para B e outra somando o saldo total, que, rodado sem controle de concorrência algum, lê um valor desatualizado no meio da transferência e reporta um total errado, uma anomalia real de atualização perdida/leitura suja com números reais, estabelecendo o exato modo de falha concreto que os próximos três conceitos existem para evitar.
O Two-Phase Locking (2PL), uma fase de crescimento que só adquire locks compartilhados/exclusivos (a mesma primitiva de lock que `locks-and-atomic-hardware-primitives` já construiu, agora aplicada por tupla/página de banco de dados em vez de por variável de memória compartilhada) seguida de uma fase de encolhimento que só os libera, é aplicado ao exato agendamento de transferência entre contas do conceito anterior, desta vez serializado corretamente, e o 2PL Estrito (segurar todo lock até o commit/aborto, e não só até a fase de encolhimento começar) é introduzido como a versão que sistemas reais usam para evitar adicionalmente os abortos em cascata.
A fase de crescimento do 2PL pode entrar em deadlock exatamente do jeito que `deadlock-conditions-and-detection` já definiu um deadlock (um ciclo de transações, cada uma segurando um lock de que a próxima do ciclo precisa), só que na granularidade de tuplas/páginas de banco de dados em vez de recursos gerenciados pelo SO. Este conceito constrói a mesma técnica de detecção de ciclos no grafo de espera sobre um agendamento real de três transações, e depois acrescenta a alternativa de prevenção de deadlock (wait-die / wound-wait, usando os carimbos de início das transações para decidir quem aborta em vez de esperar) que um sistema pode usar no lugar de detectar ciclos depois do fato.
Os quatro níveis de isolamento do padrão SQL (READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE) são definidos aqui por exatamente qual anomalia cada um ainda permite, com um agendamento real trabalhado para cada uma: uma leitura suja (só no READ UNCOMMITTED), uma leitura não repetível (permitida abaixo do REPEATABLE READ) e uma leitura fantasma (uma nova linha que satisfaz o predicado de uma consulta anterior aparecendo ao consultar de novo, permitida abaixo do SERIALIZABLE). O conceito fecha com um enunciado honesto do que o SERIALIZABLE de fato promete (equivalência a alguma execução serial) contra o que ele custa em concorrência reduzida em relação aos níveis mais fracos.
O locking é pessimista: paga o custo da coordenação de antemão, supondo que conflitos são comuns. Este conceito cobre as duas alternativas reais que sistemas de produção de fato usam no lugar: o Controle de Concorrência Otimista (uma transação lê e calcula livremente, e depois valida contra escritores concorrentes só no momento do commit, abortando e tentando de novo num conflito detectado em vez de bloquear) e o Controle de Concorrência Multiversão (mantendo várias versões com carimbo de tempo de uma tupla, de modo que um leitor seja simplesmente encaminhado para a versão consistente com o seu próprio instante de início, nunca bloqueando num escritor concorrente), o mecanismo real por trás do isolamento por snapshot em sistemas de produção como o PostgreSQL.
A regra do Write-Ahead Logging (o registro de log de uma mudança precisa chegar ao armazenamento durável antes da página de dados que ele descreve) é exatamente a mesma garantia de durabilidade que `file-system-implementation-and-journaling` já construiu para o próprio journal de um sistema de arquivos, agora aplicada a páginas de banco de dados em vez de metadados do sistema de arquivos. Este conceito constrói o formato real de registro de log (um LSN globalmente único por registro, um pageLSN registrando a mudança mais recente aplicada a cada página, um flushedLSN rastreando até onde o próprio log foi escrito de forma durável) que permite a um SGBD rodar com segurança com as políticas de buffer pool STEAL e NO-FORCE nomeadas lá atrás em `buffer-pool-management`, sem jamais perder uma escrita confirmada.
Constrói o algoritmo de recuperação ARIES de três fases sobre um pequeno log real com um ponto de travamento real: a Análise reexecuta o log para frente a partir do último checkpoint para reconstruir exatamente quais transações e quais páginas ainda estavam em andamento no instante em que o sistema travou; o Redo repete a história, reaplicando toda mudança registrada em log independentemente de ela já ter chegado ao disco, para reconstruir o estado exato pré-travamento (não apenas o estado confirmado); o Undo então desfaz as transações que ainda estavam ativas no momento do travamento, escrevendo registros de log de compensação à medida que avança, de modo que um segundo travamento no meio do undo não refaça o mesmo rollback duas vezes.
Rastreia `UPDATE accounts SET balance = balance - 100 WHERE id = 42` de ponta a ponta por cada camada construída nesta disciplina: analisado contra o schema relacional e planejado num plano físico de varredura por índice seguida de mutação, a página alvo puxada pelo buffer pool, um lock exclusivo adquirido sob 2PL Estrito, a tupla modificada no lugar, um registro de WAL descarregado antes da página agora suja, e um epílogo de travamento e recuperação mostrando a análise/redo/undo do ARIES trazendo a mesma atualização de volta corretamente depois de um travamento no meio da transação. É o mesmo padrão de capstone de pipeline completo que `capstone-tracing-a-process-from-fork-to-page-fault-to-disk` já usou para rastrear uma única operação no nível do SO por cada camada de um sistema operacional.
Part of the Computer Science curriculum.
Distingue o trabalho real de um SGBD (escritas atômicas e duráveis, acesso compartilhado e concorrente de muitas aplicações ao mesmo tempo, sobreviver a um travamento no meio de uma escrita e uma interface de consulta declarativa sobre páginas brutas de disco) do que um esquema de arquivos planos no nível da aplicação (um CSV por entidade, analisado à mão) jamais consegue oferecer, usando o próprio enquadramento da disciplina do CMU 15-445 ('este curso é sobre o projeto/implementação de SGBDs... não sobre como usar um SGBD para construir aplicações') para definir o escopo de tudo o que vem a seguir: esta disciplina constrói o motor, não ensina o uso de SQL.
Define uma relação como Codd originalmente fez (um subconjunto do produto cartesiano de uma lista de domínios, exatamente a relação da teoria dos conjuntos e o produto cartesiano já construídos em `relations-and-their-properties` e `power-sets-and-cartesian-products`, agora reaplicados a linhas e colunas em vez de pares abstratos) e depois constrói à mão os operadores fechados centrais da álgebra relacional (σ seleção, π projeção, ∪, ∩, −, ×, ⋈ join) sobre um pequeno schema de duas tabelas, estabelecendo o alvo declarativo para o qual todo plano de consulta desta disciplina eventualmente compila.
Apresenta a página de banco de dados como a unidade de E/S de tamanho fixo contra o disco, exatamente o mesmo raciocínio baseado em blocos que `files-directories-and-inodes` já usou para explicar por que um sistema de arquivos lê e escreve em blocos fixos em vez de byte a byte. Depois trabalha a organização em heap file (uma coleção não ordenada de páginas mais um diretório de páginas rastreando as suas localizações) e o layout de página com slots que sistemas reais usam para que uma página de slots de tamanho fixo consiga guardar tuplas de tamanho variável e sobreviver a remoções sem deslocar toda tupla posterior.
O buffer pool é o cache de páginas do próprio SGBD, situado entre o motor de consultas e o disco, duplicando deliberadamente o que um cache de arquivos do SO já faz: contadores de pin, bits de sujo e uma política de substituição (clock/LRU, exatamente a mesma decisão de despejo que `page-replacement-policies` já resolveu para frames físicos) decidem quais páginas permanecem residentes. Ele também nomeia STEAL (despejar uma página suja antes que a sua transação confirme) e NO-FORCE (não forçar uma página suja para o disco no commit) como as duas escolhas de política do buffer pool que tornam a recuperação de travamentos, vários conceitos adiante, um problema real em vez de trivial.
Uma B+Tree mantém exatamente o mesmo tipo de invariante explícito de balanceamento que `avl-trees-the-balance-invariant` já provou ser necessário para evitar o problema de altura degenerada que `bst-performance-and-balance` levantou para uma árvore binária desbalanceada, mas o aplica a uma família estrutural genuinamente diferente: uma árvore m-ária (e não binária), com todo nó pelo menos meio cheio e toda folha na mesma profundidade, com o fanout escolhido para casar com o tamanho de uma página de disco, de modo que descer um nível custa exatamente uma E/S de página, resolvendo diretamente o ângulo de E/S de disco que o balanceamento de uma árvore binária sozinho nunca foi projetado para tratar.
Rastreia uma inserção completa em árvore B+ à mão numa pequena árvore real, cobrindo o caso que transborda uma folha e força uma divisão (redistribuir suas entradas uniformemente por duas folhas, copiar a chave do meio para cima no pai como separador) e o caso em que essa divisão se propaga para um nó interno (redistribuir uniformemente, mas empurrar a chave do meio para cima em vez de copiá-la, já que nós internos não armazenam dados), preservando o invariante meio-cheio em todo nível sem nunca rebalancear a árvore inteira.
Completa a árvore B+ rastreando uma remoção que faz uma folha cair abaixo do mínimo meio-cheio na mesma árvore construída no conceito anterior: o nó primeiro tenta emprestar (redistribuir) uma entrada de um irmão que tem espaço de sobra, e recorre a fundir com um irmão e remover a chave separadora agora vazia do pai apenas quando emprestar não é possível, incluindo o caso em que uma fusão se propaga para cima e encolhe a altura da árvore em um nível.
Constrói um índice hash residente em disco diretamente sobre a maquinaria de tabela hash em memória que `hashing-and-hash-functions` e `collision-resolution-open-addressing` já estabeleceram, mostrando exatamente o que muda quando um bucket é uma página de disco em vez de uma posição de array (páginas de overflow encadeadas a partir de um bucket cheio, esquemas de hashing extensível/linear que fazem o diretório crescer incrementalmente em vez de forçar um único rehash gigante de toda página) e por que um índice hash responde uma busca por igualdade em O(1) E/Ss de página, mas não consegue suportar uma consulta por intervalo de forma alguma.
Um guia de decisão concreto construído a partir dos números de custo reais dos quatro conceitos anteriores: uma carga de trabalho só de igualdade, sem consultas por intervalo, favorece a busca O(1) de um índice hash, enquanto qualquer coisa que precise de varreduras por intervalo, iteração ordenada ou saída ordenada precisa da travessia O(log n) de uma B+Tree, conferido com `mongodb-indexing-fundamentals` de `database-concepts`, que documenta um sistema real de produção usando por padrão índices B+Tree exatamente por esse motivo, a mesma família estrutural construída aqui do zero.
Um plano de consulta é uma árvore de operadores físicos, cada um implementando exatamente a mesma interface baseada em pull, de next() até se esgotar, que `iterators` já estabeleceu para percorrer qualquer coleção de forma uniforme: uma varredura sequencial puxa tuplas página por página pelo buffer pool, uma varredura por índice as puxa em vez disso pela B+Tree ou pelo índice hash construídos no bloco anterior, e o plano inteiro roda de forma preguiçosa, uma tupla por vez, dirigido inteiramente pelo operador raiz puxando repetidamente dos seus filhos.
Implementa o nested-loop join simples, uma tupla por vez, e conta o seu custo exato de E/S de páginas num pequeno exemplo de duas tabelas, e depois o melhora para o block nested-loop join lendo a relação externa o equivalente a um buffer inteiro de páginas por vez, em vez de uma tupla por vez. Os mesmos números trabalhados mostram concretamente por que a versão ingênua custa (páginas de R) × (páginas de S) buscas de página, enquanto a versão em blocos amortiza esse custo por um buffer inteiro de páginas externas a cada passada.
O sort-merge join reutiliza exatamente o passo de merge que `merge-sort-revisited` já construiu, agora aplicado a duas relações que já estão ordenadas (ou ordenadas externamente antes) pela chave de join, percorrendo os dois fluxos ordenados para frente juntos; o hash join, em vez disso, constrói uma tabela hash em memória sobre a chave de join da relação menor e a sonda uma vez por tupla da relação maior. Os dois são trabalhados sobre o mesmo conjunto de dados do conceito anterior, com o trade-off real tornado concreto: o sort-merge vence quando uma entrada já está ordenada ou a saída precisa sair ordenada, e o hash join vence nos demais casos, a menos que o lado de construção não caiba no buffer pool.
Uma única consulta declarativa tem muitos planos físicos equivalentes com custos reais muito diferentes. Este conceito constrói uma estimativa de custo a partir das mesmas cardinalidades de tabela e contagens de páginas já usadas nos conceitos de join, compara à mão duas ordens de join para uma pequena consulta de três tabelas e mostra que uma é mais barata, e distingue a otimização baseada em regras (heurísticas fixas, ex.: sempre empurrar seleções para baixo dos joins) da otimização baseada em custo (estimar e comparar custos num espaço de busca de planos), na profundidade Core-Tier2 que o ACM/IEEE CS2013 atribui a este tópico específico, e não num tratamento completo, de nível de pesquisa, dos internos de um otimizador de consultas.
Dá a Atomicidade, Consistência, Isolamento e Durabilidade suas definições reais e precisas em vez de apenas o acrônimo: Atomicidade como todas as escritas de uma transação surtindo efeito ou nenhuma delas, Consistência como um invariante de nível de aplicação que o SGBD impõe apenas indiretamente (dando as outras três garantias, não entendendo o invariante em si), Isolamento como transações concorrentes produzindo um resultado equivalente a alguma execução serial (uma de cada vez), Durabilidade como uma escrita confirmada sobrevivendo a qualquer travamento subsequente, fixando exatamente qual garantia cada um dos próximos cinco conceitos é individualmente responsável por entregar.
Antes de qualquer protocolo ser introduzido, este conceito mostra concretamente por que o isolamento é difícil: um agendamento trabalhado de duas transações sobre um par de contas bancárias (A, B), uma transação movendo dinheiro de A para B e outra somando o saldo total, que, rodado sem controle de concorrência algum, lê um valor desatualizado no meio da transferência e reporta um total errado, uma anomalia real de atualização perdida/leitura suja com números reais, estabelecendo o exato modo de falha concreto que os próximos três conceitos existem para evitar.
O Two-Phase Locking (2PL), uma fase de crescimento que só adquire locks compartilhados/exclusivos (a mesma primitiva de lock que `locks-and-atomic-hardware-primitives` já construiu, agora aplicada por tupla/página de banco de dados em vez de por variável de memória compartilhada) seguida de uma fase de encolhimento que só os libera, é aplicado ao exato agendamento de transferência entre contas do conceito anterior, desta vez serializado corretamente, e o 2PL Estrito (segurar todo lock até o commit/aborto, e não só até a fase de encolhimento começar) é introduzido como a versão que sistemas reais usam para evitar adicionalmente os abortos em cascata.
A fase de crescimento do 2PL pode entrar em deadlock exatamente do jeito que `deadlock-conditions-and-detection` já definiu um deadlock (um ciclo de transações, cada uma segurando um lock de que a próxima do ciclo precisa), só que na granularidade de tuplas/páginas de banco de dados em vez de recursos gerenciados pelo SO. Este conceito constrói a mesma técnica de detecção de ciclos no grafo de espera sobre um agendamento real de três transações, e depois acrescenta a alternativa de prevenção de deadlock (wait-die / wound-wait, usando os carimbos de início das transações para decidir quem aborta em vez de esperar) que um sistema pode usar no lugar de detectar ciclos depois do fato.
Os quatro níveis de isolamento do padrão SQL (READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE) são definidos aqui por exatamente qual anomalia cada um ainda permite, com um agendamento real trabalhado para cada uma: uma leitura suja (só no READ UNCOMMITTED), uma leitura não repetível (permitida abaixo do REPEATABLE READ) e uma leitura fantasma (uma nova linha que satisfaz o predicado de uma consulta anterior aparecendo ao consultar de novo, permitida abaixo do SERIALIZABLE). O conceito fecha com um enunciado honesto do que o SERIALIZABLE de fato promete (equivalência a alguma execução serial) contra o que ele custa em concorrência reduzida em relação aos níveis mais fracos.
O locking é pessimista: paga o custo da coordenação de antemão, supondo que conflitos são comuns. Este conceito cobre as duas alternativas reais que sistemas de produção de fato usam no lugar: o Controle de Concorrência Otimista (uma transação lê e calcula livremente, e depois valida contra escritores concorrentes só no momento do commit, abortando e tentando de novo num conflito detectado em vez de bloquear) e o Controle de Concorrência Multiversão (mantendo várias versões com carimbo de tempo de uma tupla, de modo que um leitor seja simplesmente encaminhado para a versão consistente com o seu próprio instante de início, nunca bloqueando num escritor concorrente), o mecanismo real por trás do isolamento por snapshot em sistemas de produção como o PostgreSQL.
A regra do Write-Ahead Logging (o registro de log de uma mudança precisa chegar ao armazenamento durável antes da página de dados que ele descreve) é exatamente a mesma garantia de durabilidade que `file-system-implementation-and-journaling` já construiu para o próprio journal de um sistema de arquivos, agora aplicada a páginas de banco de dados em vez de metadados do sistema de arquivos. Este conceito constrói o formato real de registro de log (um LSN globalmente único por registro, um pageLSN registrando a mudança mais recente aplicada a cada página, um flushedLSN rastreando até onde o próprio log foi escrito de forma durável) que permite a um SGBD rodar com segurança com as políticas de buffer pool STEAL e NO-FORCE nomeadas lá atrás em `buffer-pool-management`, sem jamais perder uma escrita confirmada.
Constrói o algoritmo de recuperação ARIES de três fases sobre um pequeno log real com um ponto de travamento real: a Análise reexecuta o log para frente a partir do último checkpoint para reconstruir exatamente quais transações e quais páginas ainda estavam em andamento no instante em que o sistema travou; o Redo repete a história, reaplicando toda mudança registrada em log independentemente de ela já ter chegado ao disco, para reconstruir o estado exato pré-travamento (não apenas o estado confirmado); o Undo então desfaz as transações que ainda estavam ativas no momento do travamento, escrevendo registros de log de compensação à medida que avança, de modo que um segundo travamento no meio do undo não refaça o mesmo rollback duas vezes.
Rastreia `UPDATE accounts SET balance = balance - 100 WHERE id = 42` de ponta a ponta por cada camada construída nesta disciplina: analisado contra o schema relacional e planejado num plano físico de varredura por índice seguida de mutação, a página alvo puxada pelo buffer pool, um lock exclusivo adquirido sob 2PL Estrito, a tupla modificada no lugar, um registro de WAL descarregado antes da página agora suja, e um epílogo de travamento e recuperação mostrando a análise/redo/undo do ARIES trazendo a mesma atualização de volta corretamente depois de um travamento no meio da transação. É o mesmo padrão de capstone de pipeline completo que `capstone-tracing-a-process-from-fork-to-page-fault-to-disk` já usou para rastrear uma única operação no nível do SO por cada camada de um sistema operacional.