Implementação de File Systems

Disco (blocos):
[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14]
[A ][A ][A ][  ][B ][B ][  ][  ][C  ][C  ][C  ][C  ][  ][  ][  ]

Diretório:
| Arquivo | Início | Tamanho |
|---------|--------|---------|
| A       |   0    |    3    |
| B       |   4    |    2    |
| C       |   8    |    4    |

+ Acesso sequencial E random rápidos (blocos contíguos = leitura linear)
+ Simples: diretório só precisa início + tamanho
- Fragmentação externa: espaço livre fragmentado impede alocação
- Arquivo não pode crescer (não há blocos contíguos após o final)
- Precisa saber o tamanho na criação

Usado: CD-ROMs, ISOs (arquivos de tamanho fixo)

Arquivo A começa no bloco 2:

Diretório:
| Arquivo | Início |
|---------|--------|
| A       |   2    |

Blocos no disco:
Bloco 2: [dados | ptr=7] --> Bloco 7: [dados | ptr=4] --> Bloco 4: [dados | ptr=-1]
                                                                      (fim do arquivo)

+ Sem fragmentação externa (qualquer bloco livre serve)
+ Arquivo pode crescer indefinidamente
- Acesso random LENTO: para ler bloco N, precisa seguir N ponteiros
- Espaço perdido com ponteiros (4 bytes por bloco)
- Se um ponteiro corrompe, perde o resto do arquivo

Variante: FAT (File Allocation Table)
  Todos os ponteiros em uma tabela separada na memória.
  FAT12/16/32 usam esta estratégia.

Inode do arquivo A:
+---------------------------+
| Metadados:                |
|   size: 48000 bytes       |
|   permissions: 0644       |
|   owner: marco (UID 1000) |
|   timestamps: ...         |
+---------------------------+
| Ponteiros diretos (12):   |
|   [0] --> bloco 42        |
|   [1] --> bloco 87        |
|   [2] --> bloco 15        |
|   ...                     |
|   [11] --> bloco 203      |
+---------------------------+
| Ponteiro indireto simples:|
|   --> bloco 500           |  bloco 500 contém mais ponteiros:
|       [0]-->bl.601        |  [601][602][603]...[1624]
|       ...                 |  (1024 ponteiros em um bloco de 4KB)
+---------------------------+
| Ponteiro indireto duplo:  |
|   --> bloco 700           |  bloco 700 aponta para blocos
|       que apontam para    |  que apontam para dados
|       blocos de dados     |  (1024 * 1024 = 1M blocos)
+---------------------------+
| Ponteiro indireto triplo: |
|   --> (3 níveis)          |  1024^3 = ~1 bilhão de blocos
+---------------------------+

Com blocos de 4KB:
  12 diretos:           48 KB
  Indireto simples:     4 MB
  Indireto duplo:       4 GB
  Indireto triplo:      4 TB
  Total máximo: ~4 TB por arquivo

ext4 usa "extents" em vez de ponteiros individuais:
  extent = (bloco_inicio, quantidade)
  Muito mais eficiente para arquivos grandes contíguos

Bitmap (usado pelo ext4):
  Um bit por bloco. 1 = ocupado, 0 = livre.
  [1][1][0][1][0][0][1][1][0][0][0][1]
   ^  ^     ^        ^  ^        ^
   ocupado  livre    ocupados    livre

  Para 1TB com blocos de 4KB: bitmap = 32MB
  Eficiente para busca de blocos contíguos

Lista encadeada:
  Lista ligada de blocos livres.
  + Sem desperdício de espaço
  - Lento para encontrar blocos contíguos

Agrupamento:
  Primeiro bloco livre aponta para N blocos livres.
  Compromisso entre bitmap e lista.

Operação: criar arquivo "relatorio.txt"
  1. Alocar inode
  2. Alocar blocos de dados
  3. Escrever dados nos blocos
  4. Atualizar diretório (nome -> inode)
  5. Atualizar bitmap de blocos livres

COM Journaling (ext4):
  1. Escrever no JOURNAL: "vou fazer operações 1-5"
  2. Executar operações 1-5 no disco
  3. Marcar no journal: "operações 1-5 concluídas"

  Se energia cai em 2:
    - Na recuperação, SO lê o journal
    - Vê operação incompleta
    - Refaz (redo) ou desfaz (undo) conforme necessário
    - Filesystem volta a estado consistente em segundos

SEM Journaling (ext2):
  Se energia cai em 2:
    - fsck (filesystem check) precisa varrer TODO o disco
    - Pode levar HORAS em discos grandes
    - Dados podem ser perdidos irrecuperavelmente

Modos de journaling no ext4:
  journal:  log de metadados E dados (mais seguro, mais lento)
  ordered:  log de metadados, dados escritos antes (default)
  writeback: log de metadados apenas (mais rápido, menos seguro)

# Ver filesystems montados
$ df -hT
Filesystem  Type   Size  Used Avail Use% Mounted on
/dev/sda1   ext4   50G   25G   23G  53% /
/dev/sda2   swap    4G   1G    3G   25% [SWAP]
tmpfs       tmpfs   8G   200M  7.8G  3% /tmp

# Ver detalhes do filesystem ext4
$ sudo dumpe2fs /dev/sda1 | head -20
Filesystem volume name:   rootfs
Block count:              13107200
Block size:               4096
Inode count:              3276800
Free blocks:              5898240
Free inodes:              3100000
Journal size:             128M

# Verificar integridade (offline)
$ sudo fsck /dev/sda1

# Ver info de um inode específico
$ stat -f /   # info do filesystem
$ debugfs -R "stat <262146>" /dev/sda1  # info de um inode

Filesystem (ext4)              Neon Postgres
=================              ==============

Bloco (4KB)                    Page (8KB)
  Unidade mínima de I/O          Unidade mínima de I/O

Inode                          Tuple header
  Metadados do arquivo            Metadados da row (xmin, xmax, ctid)
  Ponteiros para blocos           Ponteiro para dados na page

Diretório                      Index (B-tree)
  nome -> inode                   key -> tuple location

Bitmap de blocos livres        Free Space Map (FSM)
  Quais blocos estão livres       Quais pages têm espaço

Journaling                     WAL (Write-Ahead Log)
  Log de operações antes            Log de todas as mudanças
  de executar no disco              antes de aplicar nas pages
  Garante consistência             Garante ACID + replicação

  ext4 journal ~= Postgres WAL
  Mesmo conceito: escrever a intenção antes da ação.

  Neon vai além: o WAL é enviado para storage separado
  (page server), permitindo branching instantâneo
  (como git branch para o banco de dados).

class HarnessJournal:
    """WAL/Journaling para operações do harness."""

    def __init__(self):
        self.wal = []  # Write-Ahead Log

    def log_decision(self, title, rationale):
        # 1. Escrever no WAL primeiro (journal)
        entry = {
            "op": "INSERT",
            "table": "decisions",
            "data": {"title": title, "rationale": rationale},
            "status": "pending",
        }
        self.wal.append(entry)

        # 2. Executar no banco
        try:
            db.execute("INSERT INTO decisions ...")
            entry["status"] = "committed"
        except:
            # 3. Se falhar, WAL permite retry
            entry["status"] = "failed"
            self.replay_pending()

    def replay_pending(self):
        """Refaz operações pendentes (recovery)."""
        for entry in self.wal:
            if entry["status"] == "pending":
                db.execute(entry)  # redo