Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Lucene Escala? Full-text para Big Data com hard...

Lucene Escala? Full-text para Big Data com hardware modesto

Slides for my talk at QConRio 2015: [pt-br] "Lucene Escala? Full-text para Big Data com hardware modesto"

Juan Lopes

August 28, 2015
Tweet

More Decks by Juan Lopes

Other Decks in Programming

Transcript

  1. QUEM SOU EU? UMA PERGUNTA PROFUNDA PAI DO MIGUEL GERENTE

    DE PAPINHAS SUPERVISOR DE BRINCADEIRAS PROGRAMADOR @INTELIE MAGO DOS COMPILADORES CO-DIRETOR DE TRETAS CORPORATIVAS MESTRANDO @IME/UERJ CIÊNCIAS COMPUTACIONAIS VICIADO EM COMPETIÇÕES DE PROGRAMAÇÃO
  2. F faixas de frequência 40, 43, 45 FAT 17 fault

    tolerance 40, 41, 43 FCC 17, 45 fibra óptica 41, 43 G gateway 41, 99 ÍNDICE REMISSIVO POUCA GENTE USA, MAS É ÚTIL 40 41 43 45 17 99
  3. SUBJECT Important! Don’t let this leak FROM John Doe <[email protected]>

    TO Alice Legit <[email protected]>, Bob Legit <[email protected]> BCC Eve Eavesdropper <[email protected]> BODY Here is the password: pa$$word DOCUMENTO A UNIDADE BÁSICA DO LUCENE
  4. SUBJECT Important! Don’t let this leak FROM John Doe <[email protected]>

    TO Alice Legit <[email protected]>, Bob Legit <[email protected]> BCC Eve Eavesdropper <[email protected]> BODY Here is the password: pa$$word DOCUMENTO É PRECISO SEPARAR OS CAMPOS EM TOKENS
  5. SUBJECT important! dont let this leak FROM john doe <[email protected]>

    TO alice legit <[email protected]>, bob legit <[email protected]> BCC eve eavesdropper <[email protected]> BODY here is the password: pa$$word DOCUMENTO CADA TOKEN PRECISA ESTAR NORMALIZADO
  6. DOCUMENTO RESULTADO: CAMPOS E TERMOS FROM doe, john, [email protected] TO

    alice, [email protected], bob, [email protected], legit BCC eavesdropper, eve, [email protected] SUBJECT dont, leak, let, this BODY here, password
  7. SEGMENT #0 INDEX WRITER ESCREVE UM SEGMENTO POR VEZ X

    #0 TERM_1: #0 TERM_3: #0 TERM_4: #0
  8. SEGMENT #0 INDEX WRITER ESCREVE UM SEGMENTO POR VEZ Y

    #1 TERM_1: #0 TERM_3: #0, #1 TERM_4: #0 TERM_2: #1 TERM_5: #1
  9. SEGMENT #0 INDEX WRITER ESCREVE UM SEGMENTO POR VEZ Z

    #2 TERM_1: #0, #2 TERM_3: #0, #1, #2 TERM_4: #0 TERM_2: #1, #2 TERM_5: #1
  10. SEGMENT #0 INDEX WRITER ESCREVE UM SEGMENTO POR VEZ TERM_1:

    #0, #2 TERM_3: #0, #1, #2 TERM_2: #1, #2 TERM_5: #1 TERM_4: #0
  11. SEGMENTOS CADA SEGMENTO É UM PEQUENO ÍNDICE INDEX READER INDEX

    READER INDEX READER -0 19 docs -3 10 docs -5 33 docs COMPOSITE READER
  12. SEGMENTOS ID DO DOCUMENTO MUDA POR READER -0 19 docs

    -3 10 docs -5 33 docs INDEX READER -8 62 docs 0..9 10..42 43..61 0..61
  13. SEGMENTOS ÁS VEZES É PRECISO FAZER MERGE -0 90 docs

    -8 87 docs -1 44 docs -0 41 docs -0 33 docs -4 30 docs -0 25 docs -0 22 docs -0 18 docs -3 10 docs -1 5 docs -0 3 docs
  14. SEGMENTOS ÁS VEZES É PRECISO FAZER MERGE -0 90 docs

    -8 87 docs -1 44 docs -0 41 docs -0 33 docs -4 30 docs -0 25 docs -0 22 docs -0 18 docs -3 10 docs -1 5 docs -0 3 docs -0 30 docs
  15. SEGMENTOS ÁS VEZES É PRECISO FAZER MERGE -0 90 docs

    -8 87 docs -1 44 docs -0 41 docs -0 33 docs -4 30 docs -0 25 docs -0 22 docs -0 30 docs
  16. SEGMENTOS A ANATOMIA DO SEGMENTO #0 _0. FNM _0. FDX

    _0. TIM _0. TIP _0. FRQ _0. PRX _0. FDT _0. DEL _0. NRM
  17. _0. NRM _0. FDX _0. TIM _0. TIP _0. FRQ

    _0. PRX _0. FDT _0. DEL SEGMENTOS A ANATOMIA DO SEGMENTO #0 _0. FNM FNM: FIELD NAMES Mantém informações sobre quais campos existem no segmento, bem como o tipo do campo em cada documento.
  18. _0. NRM _0. FDX _0. TIM _0. TIP _0. PRX

    _0. FDT _0. FRQ _0. FNM _0. DEL SEGMENTOS A ANATOMIA DO SEGMENTO #0 DEL: DELETED DOCS Arquivo mutável. Guarda IDs de documentos deletados do índice.
  19. _0. NRM _0. FDT _0. FDX _0. DEL _0. FNM

    _0. TIM _0. TIP _0. PRX _0. FRQ SEGMENTOS A ANATOMIA DO SEGMENTO #0 THE POSTINGS FORMAT São o coração do Lucene. O formato mudou consideravelmente no Lucene 4.0.0.
  20. _0. NRM _0. PRX _0. FRQ _0. DEL _0. FDX

    _0. FDT _0. FNM SEGMENTOS A ANATOMIA DO SEGMENTO #0 _0. TIM _0. TIP TIM E TIP: TERM INDEX Armazenam os termos. O TIP é um “índice do índice” e permite navegar mais rapidamente dentro do TIM.
  21. _0. NRM _0. FDT _0. FDX _0. DEL _0. FNM

    _0. TIM _0. TIP _0. PRX _0. FRQ SEGMENTOS A ANATOMIA DO SEGMENTO #0 FRQ: FREQUENCIES Armazenam quais documentos contém cada termo, bem como a frequência que os termos aparecem.
  22. _0. NRM _0. FDT _0. FDX _0. TIM _0. TIP

    _0. DEL _0. FNM _0. FRQ _0. PRX SEGMENTOS A ANATOMIA DO SEGMENTO #0 PRX: POSITIONS Opcional. Armazena as posições em que cada termo aparece nos documentos.
  23. _0. NRM _0. TIM _0. TIP _0. DEL _0. FNM

    _0. FRQ _0. PRX _0. FDT _0. FDX SEGMENTOS A ANATOMIA DO SEGMENTO #0 FDX E FDT: STORED FIELDS Armazena certos campos indexados por documento. FDX indexa o conteúdo em FDT.
  24. _0. FDT _0. FDX _0. TIM _0. TIP _0. DEL

    _0. FNM _0. FRQ _0. PRX SEGMENTOS A ANATOMIA DO SEGMENTO #0 NRM: NORMS Armazena informações para ajudar na ordenação de resultados relevantes. _0. NRM
  25. Perceba que estes slides não falam de TermVectors. É proposital.

    Lucene não é banco de dados. SEGMENTOS TERM VECTORS CONSIDERED HARMFUL _0. TVD _0. TVX _0. TVF
  26. FILE FORMAT PRECISAMOS FALAR DE BYTES (BEM DE LEVE) TERM_2

    2 3 5 6 7 9 12 13 TERM_3 TERM_1 Docs
  27. FILE FORMAT PRECISAMOS FALAR DE BYTES (BEM DE LEVE) TERM_2

    2 1 2 1 1 2 3 1 TERM_3 TERM_1 DocDeltas
  28. FILE FORMAT PRECISAMOS FALAR DE BYTES (BEM DE LEVE) TERM_2

    2 1 2 1 1 2 3 1 TERM_3 TERM_1 Não vi vantagem. Ainda são 32 bits! DocDeltas
  29. FILE FORMAT VENI VIDI V-INT DE ATÉ CUSTA 0 127

    1 byte 128 16,383 2 bytes 16,384 2,097,151 3 bytes 2,097,152 268,435,455 4 bytes 268,435,456 4,294,967,296 5 bytes
  30. VANTAGENS MENOS ESPAÇO MENOS I/O DESVANTAGENS IMPOSSÍVEL ITERAR AO CONTRÁRIO

    DIFÍCIL ACESSO ALEATÓRIO MAIOR CUSTO DE PROCESSAMENTO FILE FORMAT VENI VIDI V-INT
  31. _0. FDX _0. TIM _0. TIP _0. FRQ _0. PRX

    _0. FDT PROBLEMAS O QUE CRESCE NO ÍNDICE? TERM INDEX TERMO EM UTF8 + BYTES CONSTANTES / TERMO FREQUENCIES AND POSITIONS ~2 BYTES / TERMO DISTINTO / DOCUMENTO A PRINCÍPIO, SEM POSITIONS STORED FIELDS SOMENTE ID, 16 BYTES / DOCUMENTO + OVERHEAD 8 BYTES / DOCUMENTO
  32. SOLUÇÃO? AGRUPAR MENSAGENS VANTAGENS MENOS TERMOS DISTINTOS MENOR OVERHEAD COM

    STORED FIELDS MENOS DOCIDs ÍNDICE MENOR (MENOS I/O) DESVANTAGENS OVERHEAD DE FILTRO PÓS QUERY SEM QUERIES “AND” E “NOT”
  33. SOLUÇÃO? TEM UM PROBLEMÃO TERMS: A, B, C A, B

    B, C A AND C → TRUE ERRADO: Deveria ser false, pois nenhuma mensagem individual contém A e C. A AND NOT C → FALSE ERRADO: Deveria ser true, pois há uma mensagem que contém A e não contém C.
  34. DOCUMENT #42 SOLUÇÃO [2]? ARMAZENAR ÍNDICES USANDO POSITIONS A, B,

    C, E A, C A, D, E . . . 0 1 2 SEGMENT A: 42 (0, 1, 2, ...) B: 42 (0, ...) C: 42 (0, 1, ...) D: 42 (2, ...) E: 42 (0, 2, ...) INDEX
  35. SOLUÇÃO [2]? ARMAZENAR ÍNDICES USANDO POSITIONS ❖ ATÉ 1024 MENSAGENS

    POR DOCUMENTO ❖ SE < 64 MENSAGENS EM UM MESMO TERMO, USAR POSITIONS. ❖ SE > 64 MENSAGENS, ARMAZENAR UM BITSET COM 128 BYTES NO PAYLOAD (TAMBÉM NO PRX) POIS GERALMENTE CADA POSITION CONSOME 2 BYTES ❖ GARANTE MÁXIMO DE 128 BYTES / TERMO / DOCUMENTO. GERALMENTE MUITO MENOS.
  36. A B SOLUÇÃO [2]? É NECESSÁRIO REIMPLEMENTAR A BUSCA A

    AND B 53 55 63 68 78 80 88 ... ... 44 45 47 68 88 95 98 ... ...
  37. ORDENAÇÃO PARCIAL TOP 1000 FROM 400,000,000 HEAP SELECT O(n log

    k) TEMPO O(k) MEMÓRIA QUICK SELECT O(n) TEMPO O(n) MEMÓRIA
  38. CONCLUSÃO JÁ TOMEI TEMPO DEMAIS DE VOCÊS Bibliotecas são feitas

    de forma genérica para atender razoavelmente o máximo de casos. Ás vezes, para permitir grandes volumes sem uma infraestrutura colossal, é preciso entender como customizar a ferramenta para suas necessidades.