{"id":13767,"date":"2015-06-19T19:00:45","date_gmt":"2015-06-19T22:00:45","guid":{"rendered":"https:\/\/www.psafe.com\/blog\/?p=13767"},"modified":"2022-04-26T23:49:10","modified_gmt":"2022-04-27T02:49:10","slug":"o-que-e-bloom-filter","status":"publish","type":"post","link":"https:\/\/www.psafe.com\/blog\/o-que-e-bloom-filter\/","title":{"rendered":"Estrutura de dados: Voc\u00ea sabe o que \u00e9 Bloom Filter?"},"content":{"rendered":"\n

Numa oportunidade anterior falamos sobre o sistema de c\u00f3digo aberto Cassandra<\/a>, que \u00e9 usado para gerenciar grandes volumes de dados em tempo real. Isso permite uma resposta r\u00e1pida quando acontecem falhas. A quest\u00e3o \u00e9 que esse sistema, que \u00e9 extremamente r\u00e1pido em escrituras e leituras, deve em boa parte suas caracter\u00edsticas a uma estrutura de dados chamada Bloom Filter.<\/p>\n\n\n\n

Essa ferramenta \u00e9 uma maneira muito eficiente de perguntar se tem dados num conjunto ou n\u00e3o (usado por Cassandra para evitar muitos acessos sem resultados). Em outras palavras est\u00e1 desenhado para nos dizer, instantaneamente, se um elemento est\u00e1 presente num conjunto.<\/p>\n\n\n\n

Trata-se de um algoritmo que pode mostrar falsos positivos, mas nunca falsos negativos. Conhecer essa probabilidade de ocorr\u00eancia desses erros e fazer consultas estando ciente que podem acontecer \u00e9 vital na hora de construir as gigantescas bases de dados que fazem poss\u00edveis numerosas aplica\u00e7\u00f5es.<\/p>\n\n\n\n

Como funciona?<\/h2>\n\n\n\n

Ele atua com dois elementos. Um chamado de array<\/strong> de m <\/strong>bits, inicializado a zero, e um conjunto de k <\/strong>fun\u00e7\u00f5es hash que, colocado um dado, gerar\u00e1 n\u00fameros entre zero e m-1. <\/strong><\/p>\n\n\n\n

Quando um especialista insere um dado, ele vai passar pelas fun\u00e7\u00f5es hash, que indicar\u00e3o a posi\u00e7\u00e3o do array onde se mudar\u00e1 seus valores a 1. \u00c9 um processo complexo, mas que servir\u00e1 quando chegarem novas cadeias e queiramos saber se um elemento h\u00e1 ou n\u00e3o dentro de um conjunto.<\/p>\n\n\n\n

O principal \u00e9 ficar seguro que algumas posi\u00e7\u00f5es do array gerada por algumas fun\u00e7\u00f5es hash nos d\u00ea zero.<\/p>\n\n\n\n

\u00c9 como um jogo de quem \u00e9 quem, mas com muito suspeitos. O jogador \u201cA\u201d agrega suspeitos, enquanto o jogador \u201cB\u201d questiona sobre o jogador \u201cA\u201d em base aos atributos dos suspeitos. Levando isso para \u00e1rea t\u00e9cnica, esses suspeitos seriam os dados e seus atributos as fun\u00e7\u00f5es hash. A lista total de atributos que tenha o jogador \u201cA\u201d seria o array de bits.<\/p>\n\n\n\n

Vejamos um exemplo:<\/strong><\/h3>\n\n\n\n

Mark Zuckerberg<\/strong><\/p>\n\n\n\n

  • Atributos: \u201cRico\u201d, \u201cJovem\u201d e \u201cAmericano\u201d.<\/li><\/ul>\n\n\n\n

    Tom Hanks<\/strong><\/p>\n\n\n\n

    • Atributos: \u201cRico\u201d, \u201cAtor\u201d e \u201cAmericano\u201d.<\/li><\/ul>\n\n\n\n

      Vamos supor que o jogador \u201cA\u201d coloca como suspeito o Mark Zuckerberg, o que significa que agora esse jogador tem como qualidades: \u201cRico\u201d, \u201cJovem\u201d e \u201cAmericano\u201d. Assim quando o jogador \u201cB\u201d perguntar por Tom Hanks, apesar dele ter as qualidades \u201cRico\u201d e \u201cAmericano\u201d n\u00e3o tem \u201cJovem\u201d, sabemos ent\u00e3o que o Tom Hanks n\u00e3o \u00e9 um dos suspeitos.<\/p>\n\n\n\n

      \u00c9 assim como funciona Bloom Filter, mas com muitos mais dados e jogadores. Todo um ex\u00e9rcito de informa\u00e7\u00e3o ao servi\u00e7o dos especialistas.<\/p>\n","protected":false},"excerpt":{"rendered":"

      Uma ferramenta que serve para conhecer se uma informa\u00e7\u00e3o est\u00e1 dentro de um conjunto de dados. Bloom Filter funciona com grandes volumes de informa\u00e7\u00e3o. <\/p>\n","protected":false},"author":114,"featured_media":68418,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","ngg_post_thumbnail":0,"footnotes":""},"categories":[6],"tags":[808,11968],"class_list":["post-13767","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-mercado","tag-apache","tag-definicao"],"_links":{"self":[{"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/posts\/13767","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/users\/114"}],"replies":[{"embeddable":true,"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/comments?post=13767"}],"version-history":[{"count":0,"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/posts\/13767\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/media\/68418"}],"wp:attachment":[{"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/media?parent=13767"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/categories?post=13767"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.psafe.com\/blog\/wp-json\/wp\/v2\/tags?post=13767"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}