💻 computer science

Onyx: Cost-Efficient Disk-Oblivious ANN Search

O artigo apresenta o Onyx, um sistema de busca de vizinhos mais próximos aproximados (ANN) otimizado para ambientes de execução confiável (TEE) que, ao inverter a estratégia de design tradicional minimizando o consumo de largura de banda na camada de ANN e o número de acessos na camada ORAM, alcança redução significativa de custos e latência em comparação com soluções existentes.

Autores originais: Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa

Publicado 2026-04-23

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem um arquivo secreto de milhões de documentos (como mensagens de chat, histórico de navegação ou dados médicos) e precisa consultá-los rapidamente usando Inteligência Artificial. Para economizar dinheiro, você decide guardar esses dados em um servidor na nuvem de terceiros, em vez de manter tudo no seu próprio computador.

O problema? O dono do servidor (o "hospedeiro") pode espionar como você acessa os dados. Mesmo que os dados estejam criptografados, se ele vir que você foi até o "armário 5", depois ao "armário 12" e depois ao "armário 5" de novo, ele pode deduzir o que você está procurando. É como se você fosse a uma biblioteca e o bibliotecário anotasse exatamente quais livros você puxava da prateleira, permitindo que ele adivinhasse seus interesses.

Para resolver isso, existe uma tecnologia chamada ORAM (Memória RAM Obliviosa), que funciona como um "mágico" que embaralha os pedidos para que ninguém saiba o que você realmente quer. Mas, até agora, esse mágico era muito lento e caro. Era como pedir para um mágico buscar um livro, mas ele tivesse que abrir e fechar todas as portas da biblioteca a cada passo, gastando horas e energia.

Aqui entra o Onyx, a nova solução apresentada neste artigo.

A Metáfora do "Detetive e o Guarda"

O Onyx funciona como uma equipe de dois especialistas trabalhando juntos, em vez de um único generalista tentando fazer tudo. Eles "viraram o jogo" (inverteram o design) para ser mais eficiente.

1. O Detetive Inteligente (Onyx-ANNS)

Antes, o sistema tentava buscar tudo de uma vez só para garantir que não perdesse nenhum dado. Era como se, para achar uma agulha num palheiro, você tivesse que levar todo o palheiro para fora da biblioteca para inspecionar. Isso gastava muita "largura de banda" (a velocidade da internet).

O Onyx-ANNS é um detetive esperto. Ele usa um "rascunho" ou um "resumo" pequeno dos dados.

Como funciona: Em vez de pegar o livro inteiro (que é pesado), ele pega apenas um pequeno bilhete com dicas sobre o livro. Ele usa essas dicas para descartar 90% dos livros que não são o que você quer.
O resultado: Ele só pede o livro completo (pesado) para os poucos que realmente parecem promissores. Isso economiza uma quantidade enorme de dados trafegando pela rede.

2. O Guarda Ágil (Onyx-ORAM)

Antes, o sistema de "mágico" (ORAM) era otimizado para fazer o mínimo de movimentos possível, mas isso exigia que ele carregasse caixas gigantes, desperdiçando espaço e tempo.

O Onyx-ORAM é um guarda que sabe que, se o Detetive trouxer caixas menores (graças ao passo anterior), ele pode se mover muito mais rápido.

Como funciona: Ele usa uma estrutura de árvore mais rasa e inteligente (como uma escada curta e larga em vez de uma escada de caracol longa e estreita). Como as caixas são menores e mais leves, ele consegue fazer mais movimentos por segundo sem se cansar.
O resultado: Ele esconde o padrão de acesso (quem pediu o quê) de forma muito mais rápida e barata.

A Grande Virada: "Menos é Mais"

A genialidade do Onyx está em inverter a lógica:

Antes: Tentava-se economizar o número de vezes que se ia até o disco (acessos), mas isso forçava a baixar dados grandes e pesados, gastando muita banda.
Com o Onyx: Aceita-se fazer um pouco mais de "passinhos" (acessos), mas cada passo carrega apenas um bilhete pequeno e leve. Como o "mágico" (ORAM) é muito eficiente com coisas pequenas, o sistema inteiro fica muito mais rápido e barato.

Os Resultados na Vida Real

O artigo mostra que, ao usar essa dupla dinâmica:

Velocidade: O sistema é de 2 a 12 vezes mais rápido do que as soluções atuais.
Custo: Custa de 1,7 a 10 vezes menos para operar.
Privacidade: Mantém seus dados e suas consultas 100% secretos, mesmo contra um servidor mal-intencionado que observa tudo o que entra e sai do disco.

Resumo em uma frase

O Onyx é como ter um detetive que sabe exatamente o que procurar para não carregar peso desnecessário, combinado com um guarda que sabe usar essa leveza para se esconder de forma ultra-rápida, permitindo que você use IA privada na nuvem sem pagar uma fortuna ou esperar horas pelo resultado.

Título: Onyx: Busca ANN Oblivious em Disco com Eficiência de Custos

1. O Problema

A busca por vizinhos mais próximos aproximados (ANN - Approximate Nearest Neighbor) é fundamental para sistemas de IA modernos, como RAG (Retrieval-Augmented Generation), motores de busca e sistemas de recomendação. À medida que esses sistemas migram para infraestrutura de terceiros (nuvem) e lidam com dados sensíveis, a privacidade torna-se crítica.

Limitações das Soluções Atuais:
- Criptografia Pura: Apenas criptografar os dados não é suficiente. Ataques de abuso de vazamento (leakage-abuse attacks) permitem que um provedor de serviço infira consultas e recupere o conjunto de dados observando os padrões de acesso ao disco (sequência de leituras/escritas).
- ORAM (Oblivious RAM): Técnicas clássicas como ORAM podem ocultar esses padrões, mas são extremamente caras em termos de desempenho e custo quando aplicadas a índices massivos em disco.
- Ambientes de Execução Confiáveis (TEEs): Executar a lógica dentro de um TEE (como SGX ou SEV-SNP) protege a memória, mas o disco externo permanece fora da zona de confiança. Se o índice for armazenado em SSDs externos para economizar custos (já que manter tudo na memória do TEE é proibitivo), o padrão de acesso ao disco ainda vaza informações.
- Ineficiência do Design Atual: A solução mais avançada atual, Compass, tenta combinar ORAM e ANN, mas falha em otimizar para o cenário de disco. Ela minimiza o número de acessos no nível do ANN (trazendo blocos grandes) e a largura de banda no nível do ORAM. Isso resulta em um sistema que consome excessivamente tanto a largura de banda do SSD quanto o número de operações de I/O, gerando alta latência e custos elevados.

2. Metodologia e Abordagem

O Onyx propõe uma co-projeto (co-design) fundamentalmente invertido entre o algoritmo de busca ANN e o protocolo ORAM, otimizado especificamente para SSDs.

A Inversão do Design:

Design Antigo: ANN minimiza acessos (trazendo dados grandes) $\rightarrow$ ORAM minimiza largura de banda.
Design Onyx:
1. Camada ANN (Onyx-ANNS): Minimiza o consumo de largura de banda. Aproveita a natureza aproximada da busca ANN para usar representações intermediárias compactas, evitando o transporte de vetores de alta precisão desnecessários.
2. Camada ORAM (Onyx-ORAM): Minimiza o número de acessos (I/O operations). Como não há limites inferiores fundamentais para o número de acessos no ORAM (diferente da largura de banda), o sistema foca em reduzir a contagem de I/O.

Componentes Principais:

Onyx-ANNS (Motor de Busca ANN):
- Decoupling (Desacoplamento): Separa a fase de traversal (navegação pelo grafo) da fase de refinement (refinamento com vetores precisos).
- Hints de Poda Compactos: Introduz uma representação intermediária compacta (pruning hints, $H_{prn}$ ) que é buscada junto com a lista de vizinhos durante a travessia.
- Estratégia de 3 Passos:
  1. Travessia: Busca blocos pequenos contendo listas de adjacência e hints de poda (256–512 bytes).
  2. Poda: Filtra os candidatos usando os hints (sem acesso ao disco adicional).
  3. Refinamento: Busca apenas os vetores de alta precisão ( $F$ ) para o pequeno subconjunto de candidatos restantes.
- Resultado: Reduz drasticamente a largura de banda transferida, mantendo o número de acessos apenas ligeiramente aumentado (5–15%).
Onyx-ORAM (Cliente ORAM):
- Árvores Shallow (Pouco Profundas) e Locais: Utiliza uma árvore $d$ -ária (onde $d=8$ ) em vez de uma árvore binária. Isso reduz a profundidade da árvore e, consequentemente, o número de acessos por operação lógica.
- Otimizações de Localidade:
  - Metadados Locais: Armazena metadados de buckets localmente no TEE para evitar uma leitura de I/O por nível da árvore.
  - Leitura de Bucket Completo: Durante a evicção (reorganização), lê o bucket inteiro de uma vez (sequencialmente) em vez de fazer múltiplas leituras aleatórias.
- Equilíbrio: A combinação de árvores $d$ -árias com buckets grandes permite reduzir a contagem de acessos sem aumentar a largura de banda, resolvendo o conflito tradicional entre os dois recursos.

3. Contribuições Chave

Inversão do Paradigma de Co-design: Demonstra que, para SSDs, é mais eficiente ter um ANN que economiza largura de banda e um ORAM que economiza contagem de acessos, ao contrário das abordagens anteriores.
Novos Primitivos Co-Desenhados:
- Onyx-ANNS: Reduz a largura de banda em até 5x comparado ao DiskANN padrão, com aumento mínimo de acessos.
- Onyx-ORAM: Reduz a contagem de acessos em 2x e a largura de banda em 4.6x comparado a soluções baseadas em PathORAM otimizadas para localidade.
Análise Teórica e Prática: Fornece provas de segurança (indistinguibilidade baseada em jogos) e análise de overflow de stash para árvores $d$ -árias no contexto do ORAM.
Implementação e Avaliação: Implementação completa em TEE (AMD SEV-SNP) com avaliação em múltiplos conjuntos de dados reais (SIFT, MS-MARCO, WIKI, DEEP).

4. Resultados Experimentais

Os testes foram realizados comparando o Onyx com o estado da arte (Compass-in-TEE) e outras combinações de ORAM/ANN.

Desempenho (Latência e Throughput):
- O Onyx alcança 2.3x a 12.3x menor latência e 2.3x a 12.2x maior throughput comparado ao Compass-in-TEE.
- Mesmo contra combinações otimizadas de disco (RingORAM + DiskANN), o Onyx mantém uma vantagem de 2.5x a 9.5x em latência e throughput.
Eficiência de Custo:
- O Onyx é 1.7x a 9.9x mais barato (em termos de consultas por dólar) que o Compass-in-TEE.
- Em uma configuração de recursos modesta (1 vCPU, 4GB RAM, 1 SSD), o Onyx consegue hospedar um índice de 64 GB, sustentar 70 QPS com latência de 12 ms e recall de 90%, servindo mais de 8 milhões de consultas por dólar.
Escalabilidade: O sistema escala bem, mantendo a eficiência de custo mesmo com o aumento de recursos, ao contrário das soluções baseadas que exigem aumentos desproporcionais de SSD e CPU para obter ganhos marginais.

5. Significado e Impacto

O trabalho Onyx é significativo porque resolve o "gargalo de custo" que impedia a adoção prática de buscas ANN privadas em escala na nuvem.

Viabilidade Econômica: Demonstra que é possível executar buscas ANN privadas em TEEs com custos comparáveis a sistemas não privados, tornando a privacidade de dados acessível para aplicações de IA em larga escala (como assistentes pessoais e RAG corporativo).
Segurança Realista: Oferece garantias de privacidade contra provedores de nuvem maliciosos ou curiosos, protegendo tanto o conteúdo da consulta quanto a estrutura do índice, sem sacrificar a latência necessária para aplicações interativas.
Avanço em ORAM: Introduz otimizações fundamentais para ORAM em disco (árvores $d$ -árias e leitura de buckets completos) que podem ser aplicadas a outros sistemas de armazenamento confidencial.

Em resumo, o Onyx preenche a lacuna entre a segurança teórica (ORAM) e a eficiência prática necessária para a implantação de sistemas de IA confidenciais em infraestrutura de terceiros.