5 problemas difíceis de pesquisa de vetores e como os resolvemos no Apache Cassandra

A pesquisa vetorial é um componente crítico das ferramentas generativas de IA devido à forma como a geração aumentada de recuperação (RAG) é semelhante. FLARE ajuda os LLMs a incorporar informações atualizadas e personalizadas, evitando alucinações . Ao mesmo tempo, a pesquisa vetorial é um recurso, não um produto – você precisa consultar vetores conforme eles se relacionam com o restante dos seus dados, não isoladamente, e você não deve precisar construir um pipeline para sincronizar o restante dos seus dados. dados com um armazenamento de vetores para fazer isso.

2023 viu uma explosão em produtos e projetos de busca de vetores, tornando a seleção entre eles um esforço sério. Ao pesquisar as opções, você precisará considerar os seguintes problemas difíceis e as diferentes abordagens para resolvê-los. Aqui, orientarei você nesses desafios e descreverei como o DataStax os enfrentou em nossa implementação de pesquisa vetorial para DataStax Astra DB e Apache Cassandra.

Visão geral do conteúdo

• A maldição da dimensionalidade
• Problema 1: expansão
• Problema 2: Coleta de lixo eficiente
• Barra lateral: Cargas de trabalho de aplicativos em nuvem
• Problema 3: Simultaneidade
• Problema 4: Uso eficaz do disco
• Problema 5: Composibilidade
• Embrulhar

A maldição da dimensionalidade

No centro desses problemas difíceis está o que os pesquisadores chamam de “ a maldição da dimensionalidade .” O que isso significa na prática é que algoritmos que funcionam para busca vetorial exata em espaços 2-D ou 3-D, como árvores kd , desmorona quando você chega a 10, 100 ou 1000 de dimensões em seus vetores. O resultado é que não há atalho para a busca exata de similaridade com vetores de alta dimensão; para obter resultados em tempo logarítmico, precisamos usar algoritmos de vizinho mais próximo aproximado (ANN), que trazem consigo desafios nas seguintes áreas.

Problema 1: expansão

Muitos algoritmos de busca vetorial foram projetados para conjuntos de dados que cabem na memória de uma única máquina, e este ainda é o único cenário testado por benchmarks anuais . (Ann-benchmarks restringe ainda mais seus testes a um único núcleo!) Isso pode ser adequado para trabalhos acadêmicos de um milhão de documentos ou linhas, mas já se passaram muitos anos desde que isso poderia ser considerado representativo de cargas de trabalho do mundo real.

Tal como acontece com qualquer outro domínio, a expansão requer replicação e particionamento, bem como subsistemas para lidar com a substituição de réplicas mortas, repará-las após uma partição de rede e assim por diante.

Essa foi fácil para nós: a replicação em expansão é o pão com manteiga do Cassandra, e combiná-la com o novo SAI do Cassandra-5.0 (Storage-Attached Indexing - consulte CEP-7 sobre como funciona e a documentação da SAI para saber como usá-lo) deu à nossa implementação de pesquisa vetorial poderosos recursos de expansão de forma eficaz e gratuita.

Problema 2: Coleta de lixo eficiente

Por “coleta de lixo”, quero dizer remover informações obsoletas do índice – limpando linhas excluídas e lidando com linhas cujo valor do vetor indexado foi alterado. Talvez não valha a pena mencionar isso – tem sido um problema mais ou menos resolvido há quarenta anos no mundo dos bancos de dados relacionais – mas os índices vetoriais são únicos.

O principal problema é que todos os algoritmos que conhecemos que fornecem pesquisas de baixa latência e resultados de alta recuperação são baseados em gráficos. Existem muitos outros algoritmos de indexação de vetores disponíveis – FAISS implementa muitos deles – mas todos eles são muito lentos para construir, muito lentos para pesquisar ou oferecem recall muito baixo (e às vezes todos os três!) para serem uma solução de uso geral. É por isso que todo banco de dados de vetores de produção que conheço usa um índice baseado em gráfico, o mais simples dos quais é o HNSW. Os gráficos hierárquicos navegáveis de pequenos mundos foram introduzido por Yury Malkov et al em 2016 ; o papel é bastante legível e eu o recomendo fortemente. Mais sobre HNSW abaixo.

O desafio dos índices gráficos é que você não pode simplesmente extrair o nó antigo (associado ao vetor) quando uma linha ou documento é alterado; se você fizer isso mais de algumas vezes, seu gráfico não será mais capaz de cumprir seu propósito de direcionar BFS (pesquisa em largura) para áreas de maior similaridade com um vetor de consulta.

Portanto, você precisará reconstruir seus índices em algum momento para realizar essa coleta de lixo, mas quando — e como — você a organiza? Se você sempre reconstruir tudo quando as alterações forem feitas, você aumentará enormemente as gravações físicas realizadas; isso é chamado de amplificação de gravação. Por outro lado, se você nunca reconstruir, fará um trabalho extra filtrando linhas obsoletas no momento da consulta (“amplificação de leitura”).

Este é outro espaço problemático em que Cassandra vem trabalhando há anos. Como os índices SAI estão vinculados ao ciclo de vida do armazenamento principal, eles também participam do Cassandra compactação , que aumenta logaritmicamente as unidades de armazenamento para fornecer um equilíbrio saudável entre leituras e gravações.

Barra lateral: Cargas de trabalho de aplicativos em nuvem

O DataStax Astra DB baseia-se no Apache Cassandra para fornecer uma plataforma para cargas de trabalho de aplicativos em nuvem.

Isso significa cargas de trabalho que são:

• Simultaneidade massiva de milhares a milhões de solicitações por segundo, geralmente para recuperar apenas algumas linhas cada. É por isso que você não poderia executar o Netflix no Snowflake, mesmo que pudesse pagar: o Snowflake e sistemas analíticos semelhantes são projetados para lidar com apenas algumas solicitações simultâneas, cada uma executada por muitos segundos a minutos ou até mais.

  
  

• Maior que a memória Se o seu conjunto de dados cabe na memória de uma única máquina, quase não importa quais ferramentas você usa. Sqlite, MongoDB, MySQL – todos funcionarão bem. As coisas ficam mais desafiadoras quando esse não é o caso - e a má notícia é que os embeddings de vetores geralmente têm vários KB ou são cerca de uma ordem de magnitude maiores que os documentos típicos de banco de dados, portanto, você chegará a uma quantidade maior que a memória de forma relativamente rápida.

  
  

• Essencial para o aplicativo Se você não se importa se perder seus dados, seja porque não são tão importantes ou porque você pode reconstruí-los a partir da fonte real de registro, então, novamente, não importa quais ferramentas você usa. Bancos de dados como Cassandra e Astra DB são criados para manter seus dados disponíveis e duráveis, não importa o que aconteça.

Problema 3: Simultaneidade

Mencionei acima que o conhecido benchmarks anuais a comparação limita todos os algoritmos a um único núcleo. Embora isso nivele o campo de jogo, também prejudica aqueles que podem tirar proveito da principal fonte de melhoria de hardware nas últimas duas décadas.

Um problema relacionado é que o ann-benchmarks executa apenas um tipo de operação por vez: primeiro, ele constrói o índice e depois o consulta. Lidar com atualizações intercaladas com pesquisas é opcional – e provavelmente até uma desvantagem; se você sabe que não precisa lidar com atualizações, pode fazer muitas suposições simplificadoras que ficam bem em benchmarks artificiais.

Se você se preocupa em poder realizar diversas operações simultâneas com seu índice ou atualizá-lo depois de criado, será necessário se aprofundar um pouco mais para entender como ele funciona e quais compensações estão envolvidas.

Primeiro, todos os bancos de dados vetoriais de uso geral que conheço usam índices baseados em gráficos. Isso porque você pode começar a consultar um índice gráfico assim que o primeiro vetor for inserido. A maioria das outras opções exige que você crie o índice inteiro antes de consultá-lo ou pelo menos faça uma verificação preliminar dos dados para aprender algumas propriedades estatísticas.

No entanto, ainda existem detalhes importantes de implementação, mesmo dentro da categoria de índice gráfico. Por exemplo, inicialmente pensamos que poderíamos economizar tempo usando a implementação do índice HNSW do Lucene, como fazem o MongoDB Elastic e o Solr. Mas aprendemos rapidamente que Lucene oferece apenas construção de índice não simultâneo e de thread único. Ou seja, você não pode consultá-lo enquanto ele está sendo construído (o que deve ser um dos principais motivos para usar essa estrutura de dados!) nem permitir que vários threads o construam simultaneamente.

O artigo da HNSW sugere que uma abordagem de bloqueio refinada pode funcionar, mas fomos além e construímos um índice sem bloqueio. Este é de código aberto em JVetor .

O JVector dimensiona atualizações simultâneas linearmente para pelo menos 32 threads. Este gráfico tem escala logarítmica nos eixos x e y, mostrando que duplicar a contagem de threads reduz pela metade o tempo de construção.

Mais importante ainda, a simultaneidade sem bloqueio do JVector beneficia cargas de trabalho mais realistas ao misturar pesquisas com atualizações. Aqui está uma comparação do desempenho do Astra DB (usando JVector) em comparação com o Pinecone em diferentes conjuntos de dados. Embora o Astra DB seja cerca de 10% mais rápido que o Pinecone para um conjunto de dados estáticos, ele é de 8 a 15 vezes mais rápido ao indexar novos dados. Escolhemos o melhor nível de pod disponível com Pinecone (tipo de pod: p2 e tamanho de pod: x8, com 2 pods por réplica) com base em suas recomendações para maior rendimento e menor latência. A Pinecone não divulga a que recursos físicos isto corresponde. No lado do Astra DB, escolhemos o modelo de implantação PAYG padrão e não precisamos nos preocupar em escolher os recursos, pois ele não tem servidor. Os testes foram realizados usando NoSQLBench .

O Astra DB faz isso enquanto mantém maior recall e precisão ( F1 é uma combinação de recall e precisão ) :

Problema 4: Uso eficaz do disco

Começamos com o Algoritmo de indexação de gráfico HNSW porque é rápido construir o índice, rápido para consultar, altamente preciso e simples de implementar. No entanto, tem uma desvantagem bem conhecida: requer muita memória.

Um índice HNSW é uma série de camadas, onde cada camada acima da camada base tem aproximadamente 10% do número de nós da anterior. Isso permite que as camadas superiores atuem como uma lista de pulos, permitindo que a pesquisa se concentre na vizinhança direita da camada inferior que contém todos os vetores.

No entanto, esse design significa que (em comum com todos os índices de gráficos) você não pode dizer “O cache de disco nos salvará”, porque, diferentemente das cargas de trabalho normais de consulta de banco de dados, cada vetor no gráfico tem uma chance quase igual de ser relevante para uma pesquisa. (A exceção são as camadas superiores, que podemos armazenar em cache.)

Esta é a aparência de um perfil de exibição de um conjunto de dados vetoriais de 100 milhões de pedaços de artigos da Wikipedia (cerca de 120 GB em disco) em minha área de trabalho com 64 GB de RAM, quando estávamos usando o Lucene:

Cassandra passa quase todo o tempo esperando para ler os vetores do disco.

Para resolver esse problema, implementamos um algoritmo mais avançado chamado DiskANN e o abrimos como um mecanismo de busca vetorial incorporado e independente, JVetor . (Especificamente, JVector implementa a versão incremental do DiskANN descrita no FreshDiskANN artigo.) Resumidamente, DiskANN usa um gráfico de nível único com bordas mais longas que HNSW e um layout otimizado de vetores e vizinhos para reduzir IOPS de disco e mantém uma representação compactada de vetores na memória para acelerar cálculos de similaridade. Isso resulta na triplicação do rendimento da carga de trabalho da Wikipédia.

Aqui está a aparência do HNSW versus DiskANN em um cenário puramente incorporado, sem componentes cliente/servidor. Isso mede a velocidade de pesquisa do conjunto de dados Deep100M em Lucene (HNSW) e JVector (DiskANN). O índice Lucene é de 55 GB, incluindo o índice e os vetores brutos. O índice JVector é de 64 GB. A pesquisa foi realizada no meu MacBook de 24 GB, que possui cerca de um terço da memória necessária para manter o índice na RAM.

Problema 5: Composibilidade

Componibilidade no contexto de sistemas de banco de dados refere-se à capacidade de integrar perfeitamente vários recursos e capacidades de maneira coerente. Isto é particularmente significativo quando se discute a integração de uma nova categoria de capacidade, como a busca vetorial. Aplicações que não sejam brinquedos sempre exigirão tanto clássicos CRUD recursos de banco de dados, bem como a nova pesquisa vetorial.

Considere o simples Bot de bate-papo com IA aplicativo de exemplo para Astra DB. Isso é o mais puro aplicativo RAG que você encontrará, usando a pesquisa vetorial para apresentar a documentação apropriada ao LLM para responder às perguntas do usuário. No entanto, mesmo uma demonstração simples como esta ainda precisa fazer consultas “normais” e não vetoriais ao Astra DB para recuperar o histórico de conversas, que também deve ser incluído em cada solicitação ao LLM para que ele possa “lembrar” o que já foi feito. aconteceu. Portanto, as principais consultas incluem:

1. Encontre os documentos (ou fragmentos de documentos) mais relevantes para a pergunta do usuário
2. Recuperar as últimas vinte mensagens da conversa do usuário

Num caso de uso mais realista, um dos nossos engenheiros de soluções trabalhou recentemente com uma empresa na Ásia que queria adicionar pesquisa semântica ao seu catálogo de produtos, mas também queria permitir a correspondência baseada em termos. Por exemplo, se o usuário pesquisar por [válvula esfera “vermelha”], ele deseja restringir a pesquisa a itens cuja descrição corresponda ao termo “vermelho”, não importa quão semanticamente semelhantes sejam os embeddings do vetor. A nova consulta principal (além das funcionalidades clássicas, como gerenciamento de sessões, histórico de pedidos e atualizações do carrinho de compras) é: Restringir os produtos àqueles que contêm todos os termos citados e, em seguida, encontrar o mais semelhante à pesquisa do usuário

Este segundo exemplo deixa claro que não apenas os aplicativos precisam da funcionalidade de consulta clássica e da pesquisa vetorial, mas também precisam ser capazes de usar elementos de cada um na mesma consulta.

O estado da arte atual neste jovem campo é tentar fazer o que chamo de consultas clássicas em um banco de dados “normal”, consultas vetoriais em um banco de dados vetorial e, em seguida, unir as duas de maneira ad hoc quando ambas são necessário ao mesmo tempo. Isso é propenso a erros, lento e caro; sua única virtude é que você pode fazê-lo funcionar até encontrar uma solução melhor.

No Astra DB, construímos (e abrimos o código-fonte) essa solução melhor, além do Cassandra SAI. Como o SAI permite a criação de tipos de índice personalizados que estão todos vinculados ao ciclo de vida estável e de compactação do Cassandra, é simples para o Astra DB permitir que os desenvolvedores misturem e combinem predicados booleanos, pesquisa baseada em termos e pesquisa vetorial, sem sobrecarga de gerenciar e sincronizar sistemas separados. Isso dá aos desenvolvedores que criam aplicativos generativos de IA recursos de consulta mais sofisticados que geram maior produtividade e tempo de lançamento no mercado mais rápido.

Embrulhar

Os mecanismos de pesquisa vetorial são um novo recurso importante de banco de dados com vários desafios arquitetônicos, incluindo expansão horizontal, coleta de lixo, simultaneidade, uso eficaz de disco e capacidade de composição. Acredito que, ao construir a pesquisa vetorial para o Astra DB, conseguimos aproveitar os recursos do Cassandra para oferecer a melhor experiência da categoria para desenvolvedores de aplicativos generativos de IA. Saiba mais sobre o Astra DB aqui , ou se você quiser se aproximar dos algoritmos de pesquisa vetorial, confira JVetor .

- Por Jonathan Ellis, DataStax