antonio leandro

enciclopédia

estruturas e algoritmos

as ideias pequenas que sustentam as grandes: bloom, hyperloglog, cache, árvores para hardware novo.

17 verbetes, 6 no caminho mínimo, 14 lidos na íntegra · do que mais pesa para o que menos

muda como você pensa

  1. Probabilistic Counting Algorithms for Data Base Applicationsdá para contar quantos elementos distintos há num arquivo gigante sem guardar nenhum deles: os zeros à direita dos hashes já dizem a cardinalidade, com 64 palavras de memória e uma passada · núcleo
  2. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Webhash clássico remapeia quase tudo quando o número de buckets muda: dê a cada bucket pontos num círculo e mande o item ao mais próximo — entrar ou sair um bucket mexe só na fatia dele, e visões diferentes convergem sem conversa · núcleo
  3. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithmtrocar a média geométrica pela harmônica no mesmo observável do loglog derruba o erro padrão para 1,04/√m: 1,5 kB de registradores estimam mais de 10⁹ elementos distintos com 2% de erro, numa passada só · núcleo
  4. Designing Access Methods: The RUM Conjecturetodo método de acesso paga em três moedas — leitura, escrita e espaço — e fixar um teto em duas delas cria um piso na terceira: não existe estrutura universalmente ótima, só escolha de dívida · núcleo
  5. SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Cacheso objeto que sobrevive à eviction não precisa voltar para a cabeça da fila: deixá-lo onde está transforma o clock numa peneira que despeja o objeto novo e impopular primeiro — e o hit vira a escrita de um bit, sem lock · núcleo

vale o tempo

  1. Skip Lists: A Probabilistic Alternative to Balanced Treesdá para trocar rotação por sorteio: se cada nó decide no dado quantos ponteiros de atalho carrega, a busca continua logarítmica e a inserção deixa de ser um algoritmo — vira um splice de ponteiros · núcleo
  2. ARC: A Self-Tuning, Low Overhead Replacement Cachedá para ter recência e frequência sem escolher entre as duas: duas listas lru, um catálogo fantasma do tamanho do cache e uma regra de aprendizado que move a fronteira entre elas a cada miss
  3. Skip Graphsdá para ter árvore balanceada em rede p2p sem hashear chave: se cada nó é o topo da própria skip list, a ordem das chaves sobrevive — e com ela range query e localidade — sem criar ponto único de falha
  4. Network Applications of Bloom Filters: A Surveyonde existe uma lista e o espaço é caro, troque a lista por um filtro de bloom — a pergunta de projeto deixa de ser quantos bits cabem e passa a ser quanto custa um falso positivo naquele ponto do sistema
  5. Isolation Forestanomalia não precisa de um modelo do que é normal: basta contar quantos cortes aleatórios são necessários para isolar um ponto — quem cai cedo é o suspeito
  6. Cuckoo Filter: Practically Better Than Bloomdá para ter deleção num filtro de conjunto sem pagar espaço nem velocidade: guarde só fingerprints numa tabela cuckoo densa e derive a posição alternativa de cada item a partir do próprio fingerprint, com um xor
  7. Segcache: a memory-efficient and scalable in-memory key-value cache for small objectso gargalo do cache in-memory não é o algoritmo de despejo: é metadado por objeto e lixo expirado — organizar a memória em segmentos indexados por ttl corta 22-60% da ram e ainda escala quase linearmente

para aprofundar

  1. How to break softwareplano de teste escrito antes de o produto ficar testável já nasce vencido: quem acha bug é o julgamento do testador durante a sessão, com ferramenta coletando dado e nunca decidindo o que olhar · pelo resumo
  2. RadixZip: Linear Time Compression of Token Streamstoken, não byte, é a unidade certa para comprimir log e dado tabular — e o paper afirma dar conta disso em tempo linear no tamanho da entrada · pelo resumo
  3. Better bitmap performance with Roaring bitmapscomprimir bitmap com run-length encoding custa o acesso aleatório; particionar o universo em blocos de 65.536 e escolher bitmap ou array por densidade comprime mais, roda mais rápido e devolve a busca binária
  4. C/C++ Thread Safety Analysiscorrida de dados vira erro de tipo: se o programador declara qual lock protege qual dado, o compilador cobra a disciplina — e o custo de anotar, o argumento clássico contra isso, não impediu a adoção · pelo resumo
  5. Cold-RL: Learning Cache Eviction with Offline Reinforcement Learning for NGINXdá para aprender a política de eviction dentro do nginx sem estourar o orçamento de microssegundos: um modelo de 10 mil parâmetros olha a cauda do lru, tem 500 µs para responder, e cai de volta no lru quando falha