Projeto de arquitetura de nuvem

Question

Estou projetando uma arquitetura de nuvem na AWS para um sistema que processa um grande número de entidades. Espero que este seja o StackExchange correto para esta pergunta (SO não parece apropriado para mim - sinta-se livre para migrar a questão).

Descrição do problema

Eu tenho um número grande (vamos assumir n = 1 000 000 para este cenário) de entidades em um banco de dados (objetos acessíveis por suas chaves - basicamente um banco de dados noSQL). Eu tenho um algoritmo que é capaz de pegar dois objetos e produzir um valor indicando sua similaridade (digamos que o cálculo leva aproximadamente 10ms).

O sistema deve ser capaz de comparar uma entidade arbitrária com TODAS as entidades em meu banco de dados e também identificar todas as duplicidades no meu banco de dados (isso significa uma comparação de cada entidade em relação à outra entidade!).

Design

• DynamoDB (ou armazenamento noSQL semelhante para minhas entidades)
• Processador - serviço principal em execução no EC2 que carregará todas as chaves de entidade e colocará solicitações de cálculos em uma fila escalonável (SQS) - atribuir carga de trabalho para outros trabalhadores
• Fila de carga de trabalho - fila com solicitações de computação
• Trabalhadores - serviços implantados no ElasticBeanstalk conectados à fila de carga de trabalho. Trabalhadores se conectam ao banco de dados, buscam as entidades a serem comparadas e executam o algoritmo
• ResultsDB - banco de dados relacional ou não relacional com resultados dos trabalhadores

Eu coloquei no papel e fiz algumas estimativas básicas (com um número razoável de funcionários usando vários threads cada) e descobri que leva muito tempo para realizar a identificação de duplicidade - é razoavelmente bom para comparação "um contra todos" mas tentar realizar operações de 1000000 ^ 2 é simplesmente demais.

Eu estava pensando em usar o Hadoop com MapReduce, mas parece que eu teria que lançar um novo trabalho para cada comparação "um contra os outros" (e rodar milhões de empregos não parece muito rápido).

Portanto, ficaria muito feliz por qualquer sugestão de como melhorar meu design e superar essas armadilhas. Além disso, a tarefa (cada uma contra cada comparação) é mesmo factível sem a necessidade de executar centenas de instâncias poderosas (o preço também é uma limitação).

    

Answer 1

Se você está procurando por 'duplicatas', e sua métrica é euclidiana, então provavelmente você não precisa saber as distâncias entre objetos distantes. Pesquisando por algo como 'knn eficiente' provavelmente vai te colocar no caminho certo.

Analogia intuitiva: se você está procurando vizinhos a 50km de alguém na Grécia, não gaste muito tempo calculando as distâncias de todas as pessoas nos EUA. Essas distâncias nunca serão importantes para encontrar vizinhos.