Quais são as formas possíveis de evitar duplicatas quando você não pode adicionar um índice exclusivo

10

Estou preso em um problema de simultaneidade.

É um problema típico em que o usuário envia 2 ou 3 transações para persistir alguns dados que NÃO DEVEM SER duplicados no banco de dados, no caso de um registro duplicado, você deve retornar um erro.

Esse problema é fácil quando você pode adicionar um índice (exclusivo) a uma coluna onde você armazena um hash.

Mas, neste caso, eu tenho uma tabela enorme (provavelmente milhões de registros) e não posso simplesmente modificar a tabela.

De fato, temos uma coluna na qual armazenamos um hash dos dados que não devem ser duplicados, mas um índice exclusivo não foi definido.

Estou tentando no meu código java verificar se existe um pouco antes do flush, ainda recebendo duplicatas.

Minhas soluções possíveis para isso são:

  • Crie um gatilho que verifique se o hash que estou tentando inserir já existe na tabela.
  • Crie outra tabela para armazenar índices exclusivos para esta tabela e adicione uma chave estrangeira à tabela principal.
  • Sente-se na posição fetal e chore
database concurrency rafuru
fonte
Sua verificação do hash está falhando devido a colisões de hash ou um erro na verificação?
candied_orange
4
Não recebi sua pergunta. Então, em vez de indexar de uma vez por todas a sua enorme tabela com milhões de registros, você prefere ler para cada um dos próximos milhões de registros que você adicionará, os milhões existentes para procurar duplicatas? ou duplicar algumas informações e adicionar junções para fazer seu cheque?
Christophe
O problema é que, para fazer essa alteração, fui avisado de que precisamos de muito espaço e de um longo tempo de inatividade para nosso serviço, a fim de cumprir alguns requisitos, nosso serviço não pode ficar inativo por mais de 2 horas por mês. Sei que a melhor maneira é realizar uma manutenção nesta tabela, mas é algo que não posso fazer neste momento, por isso precisamos de uma solução alternativa.
Rafuru
4
Não entendi - por que adicionar um gatilho ou adicionar outra tabela para "emular" um índice leva menos tempo de inatividade do que apenas adicionar um índice à tabela existente?
Doc Brown
2
@rafuru: quem disse que você precisa criar um índice exclusivo? Um índice padrão e não exclusivo provavelmente terá tudo o que você precisa para encontrar rapidamente todas as linhas com o mesmo valor de hash.
Doc Brown

Respostas:

3

Existem alguns cenários possíveis que são fáceis de resolver e um cenário pernicioso que não é.

Para um usuário que insere um valor, insere o mesmo valor algum tempo depois, um simples SELECT antes que o INSERT detecte o problema. Isso funciona para o caso em que um usuário envia um valor e, algum tempo depois, outro usuário envia o mesmo valor.

Se o usuário enviar uma lista de valores com duplicatas - por exemplo, {ABC, DEF, ABC} - em uma única chamada do código, o aplicativo poderá detectar e filtrar as duplicatas, talvez causando um erro. Você também precisará verificar se o banco de dados não contém nenhum valor exclusivo antes da inserção.

O cenário complicado é quando a gravação de um usuário está dentro do DBMS ao mesmo tempo que a gravação de outro usuário e ele está gravando o mesmo valor. Então você tem uma corrida uma condição entre eles. Como o DBMS é (provavelmente - você não diz qual deles está usando) um sistema multitarefa preemptivo, qualquer tarefa pode ser pausada a qualquer momento de sua execução. Isso significa que a tarefa do usuário1 pode verificar se não há linha existente, a tarefa do usuário2 pode verificar se não há linha existente, a tarefa do usuário1 pode inserir essa linha e a tarefa do usuário2 pode inserir essa linha. Em cada momento, as tarefas são felizes individualmente e estão fazendo a coisa certa. Globalmente, no entanto, ocorre um erro.

Normalmente, um DBMS lidaria com isso colocando um bloqueio no valor em questão. Nesse problema, você está criando uma nova linha para que ainda não haja nada a ser bloqueado. A resposta é um bloqueio de intervalo. Como sugere, isso bloqueia uma faixa de valores, existindo ou não no momento. Uma vez bloqueado, esse intervalo não pode ser acessado por outra tarefa até que o bloqueio seja liberado. Para obter bloqueios de intervalo, você deve especificar e nível de isolamento SERIALIZABLE . O fenômeno de outra tarefa se esgueirar seguidamente após a verificação da tarefa é conhecido como registros fantasmas .

Definir o nível de isolamento como Serializable em todo o aplicativo terá implicações. O rendimento será reduzido. Outras condições de corrida que funcionaram bem o suficiente no passado podem começar a mostrar erros agora. Eu sugeriria defini-lo na conexão que executa seu código de indução de duplicado e deixar o restante do aplicativo como está.

Uma alternativa baseada em código é verificar depois da gravação e não antes. O mesmo acontece com INSERT e, em seguida, conte o número de linhas que possuem esse valor de hash. Se houver duplicados, reverter a ação. Isso pode ter alguns resultados perversos. Diga que a tarefa 1 grava e depois a tarefa 2. Em seguida, a tarefa 1 verifica e encontra uma duplicata. Ele retrocede, embora tenha sido o primeiro. Da mesma forma, ambas as tarefas podem detectar a duplicação e a reversão. Mas pelo menos você terá uma mensagem para trabalhar, um mecanismo de nova tentativa e nenhuma nova duplicata. As reversões são desaprovadas, como usar exceções para controlar o fluxo do programa. Note bem que todoso trabalho na transação será revertido, não apenas a gravação de indução de duplicação. E você precisará ter transações explícitas que podem reduzir a simultaneidade. A verificação duplicada será terrivelmente lenta, a menos que você tenha um índice no hash. Se você o fizer, poderá torná-lo único!

Como você comentou, a solução real é um índice exclusivo. Parece-me que isso deve caber na sua janela de manutenção (apesar de você conhecer melhor o seu sistema). Digamos que o hash tenha oito bytes. Para cem milhões de linhas, são cerca de 1 GB. A experiência sugere que um pouco de hardware processaria essas muitas linhas em um ou dois minutos, no máximo. A verificação e a eliminação duplicadas serão adicionadas a isso, mas podem ser scripts com antecedência. Este é apenas um aparte, no entanto.

Michael Green
fonte
2

De fato, temos uma coluna na qual armazenamos um hash dos dados que não devem ser duplicados, mas um índice exclusivo não foi definido.

A verificação de colisões de hash é um bom primeiro passo, mas cuidado, você não pode garantir que o mesmo programa produza o mesmo hash nos mesmos dados se for reiniciado . Muitas funções hash "rápidas" usam uma impressão embutida que é propagada no início do programa. Use um hash criptográfico se o hash precisar ser sempre o mesmo, não importa como, neste aplicativo. Observe que você não precisa de um hash criptográfico bom ou seguro.

O segundo passo é realmente verificar a igualdade de dados, pois mesmo as melhores funções de hash às vezes resultam em colisões, pois você está (geralmente) reduzindo a entropia de seus dados.

Então:

Etapa 1: verifique se há uma colisão em um hash criptográfico

Etapa 2: se os hashes corresponderem, verifique se os dados reais são os mesmos

Turksarama
fonte
Não vejo como isso responde à pergunta. Vamos assumir por um momento que a coluna de hash disponível é preenchida por uma função de hash determinística (caso contrário, qualquer tentativa de utilizá-la não faria sentido). Para meu entendimento, o problema é que não há índice nessa coluna de hash no banco de dados; portanto, mesmo a primeira etapa da sua resposta - verificar se há uma colisão - ainda exigiria uma verificação completa da tabela para cada novo registro em uma tabela com vários milhões de registros, o que provavelmente se tornará muito lento.
Doc Brown
É o melhor que você pode fazer sem criar um índice, que é o que a pergunta estava sendo feita. Uma varredura de hash pelo menos significa que você só precisa verificar uma coluna, o que é muito mais rápido do que a verificação, no entanto, quantas colunas elas teriam que verificar.
Turksarama
Tenho certeza de que, mesmo quando a criação de um índice não é possível (o que provavelmente é o caso), a sugestão original dos OPs de " criar outra tabela para armazenar índices exclusivos para essa tabela e adicionar uma chave estrangeira à tabela principal " gera muito mais sentido.
Doc Brown
Hash determinístico e hash criptográfico são dois conceitos ortogonais, não são? um hash criptográfico pode não ser determinístico e vice-versa um hash determinístico pode muito bem não ter força criptográfica.
Newtopian
Eles não são a mesma coisa, mas também não são ortogonais. Os hashes criptográficos são um subconjunto de hashes determinísticos, mas ninguém realmente se incomoda em fazer hashes determinísticos não criptográficos, a menos que você queira especificamente que seja reversível por algum motivo.
Turksarama
2

Crie uma nova tabela com uma chave primária exclusiva

No lado do cliente, comece a gerar GUIDs para cada registro, para que você possa detectar reenvios simples.

Coloque novos registros na nova tabela para que, pelo menos, você seja bom para receber novos dados.

Tenha uma coluna na nova tabela "CheckedAgainstOldData"

Tenha uma tarefa de back-end que faça o que você faz com a verificação lenta lenta de hash para verificar se ele pode encontrar uma duplicata nos dados antigos e definir o sinalizador de acordo, rejeite as duplicatas nesse momento, enviando uma notificação de volta ao cliente.

Enquanto isso, tenha outra tarefa de back-end que move os dados da tabela antiga para a nova, verificando se há duplicatas na verificação de hash e gerando o GUID.

Você pode deixar essa tarefa em execução por vários dias (se necessário), transferindo os dados sem tempo de inatividade.

Após a conclusão da transferência, você pode desativar o processo lento "CheckedAgainstOldData". e transfira todos os dados para uma única tabela.

Francamente, se o problema for tão ruim quanto o descrito e o software for antigo, você terá milhares de duplicatas.

Ewan
fonte
1

Supondo que os dados provenientes do "usuário" signifiquem alguém sentado em um teclado e que os enganos surjam de dois usuários inserindo os mesmos dados no mesmo momento. Tente adicionar uma função que causa um atraso aleatório no início do gatilho. Dê um mínimo do tempo que for necessário para gravar um novo registro na tabela e provavelmente um máximo de não mais do que um nanocentro. Dessa forma, quando você recebe solicitações fraudulentas, a primeira deve ser feita e o gatilho de existência deve retroceder o resultado correto. (Esclarecimento: cada chamada deve ter seu próprio tempo de atraso aleatório exclusivo, seguindo os mesmos princípios do protocolo ALOHA )

Gregor y
fonte