CS Fundamentals Trainer · Guias

Motores de armazenamento: B-trees e LSM trees

Como as B-trees atualizam páginas no lugar e as LSM trees acrescentam, descarregam e compactam, com amplificação de escrita, de leitura e de espaço medidas, Bloom filters, estratégias de compactação e quando escolher cada uma.

35 min de leitura

Todo banco de dados precisa responder a duas perguntas: como encontro uma linha rapidamente? e como altero os dados em disco sem perdê-los? As duas respostas clássicas são a B-tree, que mantém os dados ordenados em páginas de tamanho fixo que ela atualiza no lugar, e a log-structured merge tree (LSM tree), que nunca atualiza no lugar: ela acrescenta a um log e ordena e mescla em segundo plano. O Postgres, o InnoDB do MySQL, o SQLite e a maioria dos bancos relacionais usam B-trees; o RocksDB, o LevelDB, o Cassandra, o HBase e o ScyllaDB usam LSM trees. Nenhuma é melhor. Elas trocam amplificação de escrita, amplificação de leitura e amplificação de espaço entre si, e entender essa troca é como se escolhe entre elas e se ajusta qualquer uma.

Este guia constrói as duas do zero. Medi o SQLite (uma B-tree de verdade) e escrevi pequenas simulações de uma B+tree e de uma LSM tree, de modo que todo número abaixo pode ser reproduzido a partir do apêndice. Ele se apoia em índices de banco de dados, na hierarquia de memória e nas ideias de página e cache de sistemas operacionais.

Três tipos de evidência, mantidos separados. Os números deste guia vêm de três fontes diferentes, que não devem ser confundidas: | Rótulo | O que é | Quanto confiar | |---|---|---| | SQLite real | medido no SQLite, um motor B-tree de produção, nesta máquina virtual | comportamento real, mas um só motor, uma só máquina e um conjunto de dados pequeno | | B+tree de brinquedo / LSM de brinquedo | meus modelos em Python que contam páginas e entradas; eles não guardam dados e não têm disco, travas nem custo de CPU | a direção e a ordem de grandeza de um efeito (por exemplo, "a compactação em camadas escreve menos"); nunca a velocidade de um banco de dados real | | Documentação | o que dizem os manuais e os artigos dos motores; não foi executado aqui | tão boa quanto a fonte | O título de cada experimento abaixo diz qual dos três ele é. O brinquedo não tem um motor LSM real para comparar, porque o RocksDB e bibliotecas semelhantes não puderam ser instalados no sandbox; portanto, nenhuma medição aqui compara uma B-tree real com uma LSM tree real. A seção 4.1 mostra o quanto a resposta muda com as configurações e a carga de trabalho.

1. A restrição: discos gostam de I/O grande e sequencial

O armazenamento é lido e escrito em blocos (4 KB ou mais), e um bloco custa o mesmo quer você queira 1 byte ou todos os 4.096. Flash e discos também preferem o acesso sequencial ao acesso aleatório. Nesta máquina virtual (uma medição real, não um modelo), escrever blocos de 4 KB um após o outro, com um flush a cada 64 escritas, rodou a cerca de 207 MB/s, e as mesmas escritas em lugares aleatórios de um arquivo de 1 GB, a cerca de 92 MB/s, pouco mais de duas vezes mais lento. Em um disco giratório a diferença é de duas ordens de grandeza, e em SSDs as escritas aleatórias também desgastam o dispositivo mais depressa, porque a flash precisa apagar um bloco grande para reescrever uma página. Um motor de armazenamento é, em boa parte, uma estratégia para transformar as escritas pequenas e aleatórias da aplicação em algo de que o dispositivo gosta.

Três números descrevem qualquer motor:

Não dá para minimizar os três ao mesmo tempo (a "conjectura RUM": leituras, atualizações, memória). Cada design escolhe um canto.

2. A B-tree

Uma B-tree (em bancos de dados, quase sempre uma B+tree) guarda chaves ordenadas em páginas. As páginas internas guardam chaves e ponteiros para páginas filhas; as páginas folha guardam os registros (ou ponteiros para eles) e são ligadas às vizinhas para que varreduras por intervalo possam percorrer as folhas.

Diagram: A B+tree: few levels, wide pages

Como uma página guarda centenas de chaves, a árvore é muito rasa. Com uma página de 4 KB e 16 bytes por entrada de chave e ponteiro, uma página interna tem um fan-out de cerca de 250; três níveis de páginas internas indexam cerca de 250 × 250 × 250 ≈ 15 milhões de páginas folha, e quatro níveis alcançam bilhões de linhas. Uma busca em uma tabela de um bilhão de linhas lê cerca de quatro páginas, e os níveis do topo ficam no buffer pool, então na prática é uma leitura de disco. Essa é a grande força da B-tree: baixa amplificação de leitura, previsível.

As atualizações acontecem no lugar

Para inserir, ache a folha e adicione o registro. Se a folha está cheia, ela é dividida em duas páginas meio vazias e o pai ganha uma nova chave (que pode se dividir por sua vez, até a raiz). Para tornar isso seguro contra quedas, o motor primeiro acrescenta a mudança a um write-ahead log (WAL) e grava as páginas modificadas depois; após uma queda, ele reproduz o log. Então toda mudança é gravada duas vezes: uma no log, outra na página.

Experimento 1 (B+tree de brinquedo): fator de preenchimento e ordem das chaves

Construí uma B+tree com 40 registros por folha e inseri 100 000 chaves, uma vez em ordem crescente e outra em ordem aleatória:

Ordem de inserçãoPáginas folhaPreenchimento médioDivisões
chaves sequenciais2 500100%2 499
chaves aleatórias3 57470%3 573

Acrescentar na borda direita mantém todas as páginas cheias (a divisão deixa a página antiga cheia e começa uma nova). Inserções aleatórias dividem páginas ao meio repetidamente e se estabilizam em cerca de 70% de preenchimento (a média teórica é ln 2 ≈ 69%). Chaves aleatórias usam, portanto, cerca de 43% mais páginas para os mesmos dados, o que é mais espaço em disco e menos dados por linha de cache do buffer pool. Esta é a razão prática para ter cuidado com identificadores aleatórios como chaves primárias clusterizadas: um UUID aleatório insere em todo lugar, enquanto um id ordenado por tempo insere no fim. (O SQLite é mais esperto que o meu brinquedo no caso sequencial; em um teste com 300 000 linhas, o arquivo dele teve aproximadamente o mesmo tamanho nas duas ordens, mas inseriu as chaves sequenciais a 659 000 linhas por segundo contra 183 000 das aleatórias, 3,6 vezes mais rápido, porque inserções aleatórias tocam uma página diferente a cada vez e o cache de páginas de 2 MB que lhe dei não conseguia guardá-las.)

Experimento 2 (B+tree de brinquedo): amplificação de escrita das atualizações no lugar

Uma mudança em um registro de 100 bytes precisa reescrever a página inteira de 4 KB. Peguei uma árvore de 100 000 registros e inseri mais 20 000 aleatórios, gravando de volta cada página modificada depois de cada n inserções:

Gravação de volta a cadaEscritas de página por registroBytes gravados por byte de dados
1 inserção1,0041,0
10 inserções1,0040,9
100 inserções0,9940,6
1 000 inserções0,9338,0
10 000 inserções0,5622,8

Para escritas pequenas e aleatórias, uma B-tree grava cerca de 40 vezes mais bytes do que a aplicação pediu (e o WAL acrescenta mais). Só quando milhares de inserções compartilham uma página entre as gravações de volta (lotes grandes, ou um buffer pool que absorve muitas mudanças antes de um checkpoint) o custo cai. Motores reais o reduzem com buffer pools grandes e group commit, mas o fato fundamental permanece: uma atualização no lugar custa uma página.

Outros custos da B-tree

3. A LSM tree

Uma LSM tree vira o problema do avesso: nunca modifique nada em disco. As escritas são baratas porque vão só para a memória (e um log sequencial); a ordenação, a deduplicação e a limpeza são pagas depois, em lotes.

Diagram: The write path and read path of an LSM tree

  1. Uma escrita é acrescentada a um log (para durabilidade) e inserida em uma estrutura ordenada em memória, a memtable.
  2. Quando a memtable está cheia, ela é gravada em disco em uma passada sequencial como uma tabela ordenada imutável, uma SSTable (sorted string table), e começa uma nova memtable.
  3. As tabelas se acumulam. Uma leitura precisa verificar a memtable e depois as tabelas, das mais novas para as mais antigas, porque uma versão mais nova de uma chave esconde as mais antigas.
  4. Em segundo plano, a compactação mescla tabelas: combina várias tabelas ordenadas em uma, mantém apenas a versão mais nova de cada chave e descarta as chaves apagadas. Um delete é registrado como uma tombstone, um marcador que esconde valores mais antigos até a compactação remover os dois.

Percorra um pequeno exemplo. Ele tem uma memtable de quatro entradas, mescla o nível 0 no nível 1 quando existem duas tabelas e termina com a busca de uma chave que nunca foi gravada. Ligue a opção do Bloom filter para comparar o custo de leitura:

Interactive animation: lsm tree

Nesta execução, 12 escritas custam 19 entradas gravadas em disco: 12 em tabelas descarregadas mais 7 reescritas pela compactação (amplificação de escrita de 1,6 até agora; ela cresce à medida que os dados passam por mais níveis). E a busca da chave ausente precisou de 2 leituras de tabela sem filtros e nenhuma com eles.

Amplificação de leitura e Bloom filters

Uma busca pode ter de olhar em todas as tabelas, o que é a fraqueza da LSM tree. Duas ferramentas resolvem a maior parte:

Experimento 3 (LSM tree de brinquedo): o compromisso da compactação

Escrevi uma pequena LSM tree com uma memtable de 200 entradas e enviei a ela 300 000 escritas aleatórias para 100 000 chaves distintas, de modo que cada chave foi sobrescrita cerca de três vezes. Comparei a compactação em níveis (leveled; cada nível é uma sequência ordenada, um fator T maior que a de cima; os dados são reescritos a cada vez que descem) com a compactação por camadas de tamanho (size-tiered; quando existem T tabelas de tamanho parecido, mescle-as em uma tabela maior), com e sem Bloom filters (10 bits por chave):

EstratégiaTabelasAmplificação de escritaEspaçoLeituras de tabela por busca, chave presente (sem filtro / com filtro)Leituras de tabela, chave ausente (sem filtro / com filtro)
leveled, T = 10412,81,63x3,1 / 1,04,00 / 0,03
leveled, T = 469,11,48x5,2 / 1,06,00 / 0,05
size-tiered, T = 4104,91,77x8,1 / 1,110,00 / 0,08
size-tiered, T = 10223,11,88x18,3 / 1,122,00 / 0,19

Leia da esquerda para a direita:

(Os números de espaço são um instantâneo ao fim da execução e dependem de quando ocorreu a última compactação; o que importa é o formato. Motores reais, como o RocksDB, compactam arquivos individuais em segundo plano, em vez de níveis inteiros, então seus números são mais suaves.) Compare os 3 a 13 bytes escritos por byte na LSM tree de brinquedo com os 40 da B-tree de brinquedo: uma LSM tree transforma muitas escritas pequenas e aleatórias em poucas escritas grandes e sequenciais, e é por isso que ela serve para cargas de trabalho com muita escrita, como logs, séries temporais, mensageria e pipelines de ingestão.

Os custos de uma LSM tree

4. Escolhendo entre elas

B-treeLSM tree
Caminho de escritaatualizações de página no lugar, mais um WALsequencial: log, memtable, flush, compactação
Amplificação de escritaalta para escritas pequenas e aleatórias (cerca de 40 no brinquedo), menor com lotesmenor, ajustável pela estratégia de compactação (3 a 13 no brinquedo)
Leituras pontuaisprevisíveis: cerca de 3 a 4 páginas, em geral uma leitura de discovárias tabelas, salvas pelos Bloom filters
Varreduras por intervaloexcelentes: siga os links das folhasmesclam várias fontes ordenadas, ainda sequenciais
Espaçofragmentação, páginas 70% cheiasversões obsoletas até a compactação, espaço temporário durante ela
Latênciaestávelboa em média, com latência de cauda por stalls e compactações
Transações e locksmaduros; uma linha mora em um só lugar, então travá-la é simplespossíveis (RocksDB, CockroachDB, TiDB), mas as versões de uma chave moram em muitas tabelas
Usuários típicosPostgres, MySQL InnoDB, SQLite, SQL Server, LMDB, a maioria dos sistemas de arquivosRocksDB, LevelDB, Cassandra, HBase, ScyllaDB, a família MergeTree do ClickHouse (ideia parecida) e a camada de armazenamento de muitos bancos SQL mais novos

Regras práticas:

4.1 Quando o vencedor aparente se inverte

"LSM trees escrevem mais rápido, B-trees leem mais rápido" é uma boa primeira aproximação e uma má conclusão. Quatro coisas costumam virar o resultado de cabeça para baixo. Os dois primeiros conjuntos de números vêm dos modelos de brinquedo, as linhas do SQLite são do SQLite real, e o resto é documentação.

1. Estratégia e configuração de compactação (brinquedo). Escrevi 60.000 registros novos de 100 bytes em um armazenamento que já tinha 100.000 registros e contei os bytes escritos no armazenamento por byte de dados do usuário:

Motor e configuraçãoAmplificação de escrita (brinquedo)
B-tree, páginas modificadas gravadas de volta a cada inserção41,0
B-tree, gravadas de volta a cada 100 inserções40,5
B-tree, gravadas de volta a cada 10.000 inserções (um buffer pool muito grande)16,7
LSM, em níveis (leveled), T = 1012,2
LSM, em níveis (leveled), T = 411,4
LSM, por tamanho (size-tiered), T = 45,8
LSM, por tamanho (size-tiered), T = 103,0

A diferença entre "a B-tree" e "a LSM tree" vai de cerca de 14 vezes (41,0 contra 3,0) a cerca de 1,4 vez (16,7 contra 12,2), dependendo apenas de duas configurações. A compactação em camadas (tiered) escreve menos, mas deixa mais tabelas para pesquisar (veja abaixo); a em níveis escreve mais e lê menos. Não existe um único "custo de escrita da LSM". Observe também que, no brinquedo, a LSM nunca escreveu mais que a B-tree. Motores reais acrescentam custos que o brinquedo deixa de fora (a compactação disputando CPU e disco com o trabalho em primeiro plano, paradas de escrita quando a compactação fica para trás, o write-ahead log dos dois motores), e é aí que os benchmarks reais encontram casos que favorecem a B-tree.

2. Tamanho do cache e memória (SQLite real). Inseri 300.000 linhas com valores de 92 bytes no SQLite, com o journal e o fsync desligados para isolar a própria árvore:

ChavesCache de páginas de 0,5 MBCache de páginas de 64 MB
sequenciaiscerca de 902.000 inserções/scerca de 908.000 inserções/s
aleatóriascerca de 265.000 inserções/scerca de 507.000 inserções/s

Um cache maior deixou as inserções aleatórias cerca de 1,9 vez mais rápidas e não fez nada pelas sequenciais, porque os appends só tocam a borda direita da árvore. Um benchmark de B-tree com um conjunto de dados que cabe na memória diz, portanto, pouco sobre a mesma árvore quando os dados são dez vezes maiores que a memória. Os motores LSM têm seus próprios botões de memória (o tamanho do memtable, o cache de blocos, a memória gasta com filtros de Bloom), e um benchmark que cabe na memória esconde também o custo de compactação deles. Teste sempre com dados maiores que a RAM.

3. Distribuição de chaves e valores.

4. Formato da carga de trabalho.

Como decidir. O único procedimento confiável é rodar o motor candidato sobre uma cópia da sua própria carga de trabalho, com dados maiores que a memória, por tempo suficiente para chegar ao estado estável em que a compactação (ou o checkpointing) está rodando o tempo todo, e comparar a latência de cauda (p99), as amplificações de escrita, leitura e espaço, e o desgaste do disco, não apenas a vazão. Trate qualquer afirmação isolada de que "a B-tree é mais rápida" ou "a LSM é mais rápida", inclusive os números de brinquedo deste guia, como resposta para uma carga de trabalho e um conjunto de configurações.

Onde as ideias aparecem em outros lugares

5. Erros comuns

6. Coisas a mencionar em uma entrevista

Resumo rápido

Apêndice: o código dos experimentos

Os dois scripts são Python 3 só com a biblioteca padrão. O primeiro mede o SQLite (uma B-tree) e escritas brutas em disco em uma pequena máquina virtual, então seus números absolutos dependem da máquina e variam entre execuções. O segundo é um modelo, não um banco de dados: conta entradas e páginas em vez de guardar bytes, usa uma semente aleatória fixa e imprime exatamente as tabelas acima. Sua LSM tree mescla níveis inteiros (motores reais compactam arquivos individuais), conta cada entrada como um registro de 100 bytes e usa como Bloom filter um array de bits de verdade com 10 bits por chave. Trate suas cifras de amplificação como ilustrações dos trade-offs e não como previsões para o RocksDB ou o Cassandra.

O SQLite como uma B-tree de verdade, e escritas em disco sequenciais contra aleatórias

import sqlite3, os, random, time, hashlib

def run(kind, n=300_000):
    path = f"/var/tmp/lsm/{kind}.db"
    for ext in ("", "-wal", "-journal"):
        if os.path.exists(path + ext): os.remove(path + ext)
    db = sqlite3.connect(path); db.execute("pragma journal_mode=off"); db.execute("pragma synchronous=off"); db.execute("pragma cache_size=-2048")  # a 2 MB page cache
    db.execute("create table t(k text primary key, v text) without rowid")
    keys = [f"{i:012d}" for i in range(n)] if kind == "sequential" else [hashlib.md5(str(i).encode()).hexdigest()[:12] for i in range(n)]
    payload = "x" * 80
    t0 = time.perf_counter()
    for i in range(0, n, 10000):
        db.executemany("insert into t values (?,?)", [(k, payload) for k in keys[i:i+10000]]); db.commit()
    dt = time.perf_counter() - t0
    pages = db.execute("pragma page_count").fetchone()[0]; ps = db.execute("pragma page_size").fetchone()[0]
    raw = n * (12 + 80)
    rnd = random.Random(1); probe = [rnd.choice(keys) for _ in range(20000)]
    t1 = time.perf_counter()
    for k in probe: db.execute("select v from t where k=?", (k,)).fetchone()
    lt = time.perf_counter() - t1
    return f"{kind:>10}: {n/dt:>9,.0f} inserts/s, file {pages*ps/1e6:5.1f} MB for {raw/1e6:4.1f} MB of data (x{pages*ps/raw:.2f}), {20000/lt:>8,.0f} lookups/s"
print("SQLite (a B-tree), page size 4096, 2 MB cache, 300,000 rows of 92 bytes:")
for kind in ("sequential", "random"): print(" ", run(kind))

# raw disk: appending 4 KB blocks against rewriting random blocks of a 1 GB file, flushing every 64 writes
def disk(kind, n=20000, size=1 << 30):
    path = "/var/tmp/lsm/blob"; 
    fd = os.open(path, os.O_RDWR | os.O_CREAT); os.ftruncate(fd, size); buf = os.urandom(4096); rnd = random.Random(2)
    t = time.perf_counter()
    for i in range(n):
        off = i * 4096 if kind == "append" else rnd.randrange(size // 4096) * 4096
        os.pwrite(fd, buf, off)
        if i % 64 == 63: os.fdatasync(fd)
    dt = time.perf_counter() - t; os.close(fd); os.remove(path); return n * 4096 / dt / 1e6
print(f"4 KB writes with an fdatasync every 64 writes: append {disk('append'):.0f} MB/s, random in place {disk('random'):.0f} MB/s")

Uma B+tree de brinquedo e uma LSM tree de brinquedo com Bloom filters

import bisect, random, math, hashlib

# ===================== a toy B+tree: leaves hold up to LEAF records (a 4 KB page of ~100-byte records) =====================
LEAF = 40
class BPlusLeafs:
    """Only the leaf level matters for the questions below, so the interior is a sorted list of leaf minimums."""
    def __init__(self): self.leaves = [[]]; self.mins = [None]; self.splits = 0
    def find(self, k): return max(0, bisect.bisect_right(self.mins[1:], k)) if len(self.leaves) > 1 else 0
    def insert(self, k):
        i = self.find(k); leaf = self.leaves[i]; bisect.insort(leaf, k); touched = {i}
        if len(leaf) > LEAF:
            if i == len(self.leaves) - 1 and k == leaf[-1]:      # appending at the right edge: split off just the new record
                new = [leaf.pop()]
            else:                                                  # otherwise split in half
                half = len(leaf) // 2; new = leaf[half:]; del leaf[half:]
            self.leaves.insert(i + 1, new); self.mins.insert(i + 1, new[0]); self.splits += 1; touched.add(i + 1)
        return touched
    def fill(self): return sum(map(len, self.leaves)) / (len(self.leaves) * LEAF)

def btree_experiment(n=100_000):
    print("B+tree leaf pages, 100,000 inserts, 40 records per page:")
    for kind in ("sequential", "random"):
        t = BPlusLeafs(); keys = list(range(n)) if kind == "sequential" else random.Random(5).sample(range(10**9), n)
        for k in keys: t.insert(k)
        print(f"  {kind:>10} keys: {len(t.leaves):>5} leaf pages, average fill {t.fill()*100:.0f}%, {t.splits} page splits")
    # write amplification: after every `batch` inserts all modified pages are written back in full (4096 bytes)
    print("page writes per record, when modified pages are written back after every `batch` inserts (record = 100 bytes, page = 4096 bytes):")
    keys = random.Random(7).sample(range(10**9), 200_000)
    t = BPlusLeafs()
    for k in keys[:100_000]: t.insert(k)          # a tree that already holds 100,000 records
    for batch in (1, 10, 100, 1000, 10000):
        dirty = set(); writes = 0; n_ins = 0
        for k in keys[100_000:100_000 + 20_000]:
            # a split moves page numbers, so count by id of the page object
            i = t.find(k); leaf = t.leaves[i]; before = id(leaf)
            t.insert(k); dirty.add(before); n_ins += 1
            if n_ins % batch == 0: writes += len(dirty); dirty = set()
        writes += len(dirty)
        print(f"  batch {batch:>5}: {writes/n_ins:5.2f} page writes per inserted record = {writes*4096/(n_ins*100):6.1f} bytes written per byte of data")

# ===================== a toy LSM tree =====================
class Bloom:
    def __init__(self, n, bits_per_key=10):
        self.m = max(8, n * bits_per_key); self.k = max(1, round(bits_per_key * math.log(2))); self.bits = bytearray(self.m // 8 + 1)
    def _h(self, x):
        d = hashlib.blake2b(str(x).encode(), digest_size=16).digest(); a = int.from_bytes(d[:8], "big"); b = int.from_bytes(d[8:], "big") | 1
        return ((a + i * b) % self.m for i in range(self.k))
    def add(self, x):
        for h in self._h(x): self.bits[h >> 3] |= 1 << (h & 7)
    def __contains__(self, x): return all(self.bits[h >> 3] & (1 << (h & 7)) for h in self._h(x))

class Table:
    def __init__(self, keys, bloom_bits):
        self.keys = sorted(set(keys)); self.bloom = Bloom(len(self.keys), bloom_bits) if bloom_bits else None
        for k in self.keys: self.bloom and self.bloom.add(k)

class LSM:
    """Entries are keys only (every key is a 100-byte record). `written` counts every entry written to 'disk' by flushes and compactions."""
    def __init__(self, strategy, T=10, mem=200, bloom_bits=10):
        self.strategy, self.T, self.mem, self.bits = strategy, T, mem, bloom_bits
        self.memtable = set(); self.levels = [[]]; self.written = 0; self.user = 0
    def put(self, k):
        self.memtable.add(k); self.user += 1
        if len(self.memtable) >= self.mem: self.flush()
    def flush(self):
        t = Table(self.memtable, self.bits); self.memtable = set(); self.written += len(t.keys)
        self.levels[0].append(t); self.compact()
    def merge(self, tables):
        keys = set(); [keys.update(t.keys) for t in tables]
        out = Table(keys, self.bits); self.written += len(out.keys); return out
    def compact(self):
        if self.strategy == "tiered":
            lvl = 0
            while lvl < len(self.levels) and len(self.levels[lvl]) >= self.T:
                merged = self.merge(self.levels[lvl]); self.levels[lvl] = []
                if lvl + 1 == len(self.levels): self.levels.append([])
                self.levels[lvl + 1].append(merged); lvl += 1
        else:  # leveled: level 0 collects up to 4 tables; level i >= 1 is one sorted run holding at most mem * 4 * T**i entries
            if len(self.levels[0]) >= 4:
                self.push(0)
            lvl = 1
            while lvl < len(self.levels) and self.levels[lvl] and len(self.levels[lvl][0].keys) > self.mem * 4 * self.T ** lvl:
                self.push(lvl); lvl += 1
    def push(self, lvl):
        if lvl + 1 == len(self.levels): self.levels.append([])
        merged = self.merge(self.levels[lvl] + self.levels[lvl + 1]); self.levels[lvl] = []; self.levels[lvl + 1] = [merged]
    def get(self, k):
        """Returns (found, tables whose data had to be read)."""
        if k in self.memtable: return True, 0
        reads = 0
        for lvl in self.levels:
            for t in reversed(lvl):
                if t.bloom is not None and k not in t.bloom: continue
                reads += 1                                   # read the table (a disk read)
                if bisect.bisect_left(t.keys, k) < len(t.keys) and t.keys[bisect.bisect_left(t.keys, k)] == k: return True, reads
        return False, reads
    def tables(self): return sum(len(l) for l in self.levels)
    def stored(self): return sum(len(t.keys) for l in self.levels for t in l)

def lsm_experiment(n=300_000):
    print(f"LSM tree, {n:,} random writes to 100,000 distinct keys (so keys are overwritten about 3 times), memtable of 200 entries:")
    rnd = random.Random(9); space_keys = [rnd.randrange(10**12) for _ in range(100_000)]; keys = [rnd.choice(space_keys) for _ in range(n)]
    absent = [rnd.randrange(10**12) for _ in range(2000)] 
    for strategy, T in (("leveled", 10), ("leveled", 4), ("tiered", 4), ("tiered", 10)):
        for bits in (0, 10):
            db = LSM(strategy, T, bloom_bits=bits)
            for k in keys: db.put(k)
            present = [rnd.choice(keys) for _ in range(2000)]
            rp = sum(db.get(k)[1] for k in present) / 2000; ra = sum(db.get(k)[1] for k in absent) / 2000
            if bits == 0 or True:
                print(f"  {strategy:>7} T={T:>2} bloom={'on ' if bits else 'off'}: {db.tables():>2} tables, write amplification {db.written/db.user:5.1f}, space {db.stored()/len(set(keys)):.2f}x, table reads per lookup: present {rp:4.1f}, absent {ra:4.2f}")

def lsm_vs_btree_bytes():
    print("bytes written to storage per byte of user data (random inserts, 100-byte records, 4 KB pages):")
    print("  B-tree, write-back after every insert: 4096/100 = 41 bytes (plus the write-ahead log)")
    print("  B-tree, one write-back per 1,000 inserts into 100,000 leaf pages: see the table above")

if __name__ == "__main__":
    btree_experiment(); lsm_experiment()

Quando o vencedor se inverte: SQLite com caches e ordens de chave diferentes, e os modelos de brinquedo com configurações diferentes

Salve o script de brinquedo da seção anterior do apêndice como toy.py (ele só define classes quando importado) e este como reversal.py na mesma pasta. A parte 1 precisa apenas do sqlite3 da biblioteca padrão; seus tempos variam conforme a máquina. A parte 2 usa os modelos de brinquedo, portanto conta entradas e páginas e não guarda dados.

"""When does the apparent winner between a B-tree and an LSM tree flip?
Part 1 uses SQLite, a real B-tree. Part 2 uses the toy models from the other script (toy.py): they count entries and pages,
they are not databases, so their numbers show the direction of an effect and not the speed of any real engine."""
import os, random, sqlite3, time, bisect
import toy

# ---------------------------------------------------------------- part 1: real SQLite
def sqlite_insert(keys, cache_kb, path="/tmp/rev.db"):
    for ext in ("", "-journal", "-wal"):
        try: os.remove(path + ext)
        except FileNotFoundError: pass
    db = sqlite3.connect(path)
    db.execute("pragma journal_mode=off"); db.execute("pragma synchronous=off"); db.execute(f"pragma cache_size=-{cache_kb}")
    db.execute("create table t(k integer primary key, v blob)")
    v = b"x" * 92
    t = time.perf_counter()
    db.executemany("insert into t values (?, ?)", ((k, v) for k in keys))
    db.commit(); dt = time.perf_counter() - t
    pages = db.execute("pragma page_count").fetchone()[0]; db.close(); os.remove(path)
    return dt, pages

def part1(n=300_000):
    rnd = random.Random(1)
    seq = list(range(n)); rand = rnd.sample(range(10**9), n)
    print(f"SQLite (a real B-tree), {n:,} inserts of 92-byte values, journal and fsync off to isolate the tree itself:")
    for label, keys in (("sequential keys", seq), ("random keys", rand)):
        for kb in (512, 65_536):
            dt, pages = sqlite_insert(keys, kb)
            print(f"  {label:>15}, page cache {kb//1024 if kb >= 1024 else 0.5:>4} MB: {n/dt:>9,.0f} inserts/s, {pages:,} pages in the file")

# ---------------------------------------------------------------- part 2: toy models
def btree_write_amp(keys, preload, batch):
    """Page writes (4096 bytes) per 100-byte record when dirty pages are written back every `batch` inserts."""
    t = toy.BPlusLeafs()
    for k in preload: t.insert(k)
    dirty, writes, n = set(), 0, 0
    for k in keys:
        before = id(t.leaves[t.find(k)]); t.insert(k); dirty.add(before); n += 1
        if n % batch == 0: writes += len(dirty); dirty = set()
    writes += len(dirty)
    return writes * 4096 / (n * 100)

def lsm_run(keys, strategy, T, bits=10, preload=(), checkpoints=None, probe=None):
    """Loads `preload` first (a store that already holds data), then counts only the writes made for `keys`."""
    db = toy.LSM(strategy, T, bloom_bits=bits)
    for k in preload: db.put(k)
    db.written, db.user = 0, 0
    samples = []
    for n, k in enumerate(keys, 1):
        db.put(k)
        if checkpoints and n in checkpoints: samples.append(probe(db))
    return db, samples

def scan_tables(db, lo, hi):
    """Tables whose key range overlaps [lo, hi]: every one of them has to be read for a range scan (a Bloom filter cannot help)."""
    c = 0
    for lvl in db.levels:
        for t in lvl:
            if t.keys and t.keys[0] <= hi and t.keys[-1] >= lo: c += 1
    return c

def part2():
    rnd = random.Random(3)
    W = 60_000                                                       # writes measured, on top of a store that already holds 100,000 records
    pre = rnd.sample(range(10**12), 100_000)
    hot_space = rnd.sample(pre, 200)                                 # 200 keys that already exist
    workloads = {
        "every write is a new key": [rnd.randrange(10**12) for _ in range(W)],
        "200 hot keys overwritten again and again": [rnd.choice(hot_space) for _ in range(W)],
    }
    print(f"\nToy models: {W:,} writes of 100-byte records into a store that already holds {len(pre):,} records")
    print("  (a) write amplification = bytes written to storage per byte the application wrote (the B-tree figure excludes its write-ahead log)")
    for name, keys in workloads.items():
        row = [f"B-tree write-back every {b:>6}: {btree_write_amp(keys, pre, b):5.1f}" for b in (1, 100, 10_000)]
        row += [f"LSM {s} T={T}: {lsm_run(keys, s, T, preload=pre)[0].written / len(keys):4.1f}" for s, T in (("leveled", 10), ("leveled", 4), ("tiered", 4), ("tiered", 10))]
        print(f"   {name}\n     " + "\n     ".join(row))
    print("  (b) read side after loading new keys; averaged over 10 checkpoints, because the number of tables rises and falls as compactions run")
    keys = workloads["every write is a new key"]
    absent = [rnd.randrange(10**12) for _ in range(500)]
    cps = set(range(W // 10, W + 1, W // 10))
    def probe(db):
        ra = sum(db.get(k)[1] for k in absent) / len(absent)
        starts = [rnd.randrange(10**12) for _ in range(100)]
        return db.tables(), ra, sum(scan_tables(db, a, a + 10**9) for a in starts) / 100
    for s, T in (("leveled", 10), ("tiered", 4), ("tiered", 10)):
        for bits in (0, 10):
            _, smp = lsm_run(keys, s, T, bits, preload=pre, checkpoints=cps, probe=probe)
            m = lambda i: sum(x[i] for x in smp) / len(smp)
            print(f"     LSM {s:>7} T={T:>2} bloom={'on ' if bits else 'off'}: {m(0):4.1f} tables on average (max {max(x[0] for x in smp)}), reads for an absent key {m(1):5.2f}, tables to read for a short range {m(2):4.1f}")
    print("     B-tree: a lookup reads 3 to 4 pages (the upper levels are cached); a range scan reads the leaf pages it covers")

if __name__ == "__main__":
    part1(); part2()

Fontes

Pratique este tema: Databases

Mais guias