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"

Transcript

2. 3,000,000,000 mensagens/dia
3. 3,000,000,000 mensagens/dia 1 terabyte por dia
4. 100,000,000,000 mensagens de retenção no índice 3,000,000,000 mensagens/dia 1 terabyte por dia
5. 3,000,000,000 mensagens/dia 1 terabyte por dia 100,000,000,000 mensagens de retenção no índice 3 máquinas 8GB de RAM em cada
6. LUCENE ESCALA? Full-text para Big Data com hardware modesto @JUANPLOPES TERM TERM TERM TERM TERM
7. 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
8. QUEM SOU EU? UMA PERGUNTA PROFUNDA GITHUB.COM TWITTER.COM /JUANPLOPES
11. 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
12. “fault tolerance” 40 ÍNDICE REMISSIVO QUERIES BOOLEANAS 41 43 “faixas de frequência” 40 43 45
13. ÍNDICE REMISSIVO QUERIES BOOLEANAS “fault tolerance” OR “faixas de frequência” 40 43 45 41
14. ÍNDICE REMISSIVO QUERIES BOOLEANAS “fault tolerance” AND “faixas de frequência” 40 43
15. SUBJECT Important! Don’t let this leak FROM John Doe <john.doe@mail.com> TO Alice Legit <alice@legit.com>, Bob Legit <bob@legit.com> BCC Eve Eavesdropper <eve@hacker.io> BODY Here is the password: pa$$word DOCUMENTO A UNIDADE BÁSICA DO LUCENE
16. SUBJECT Important! Don’t let this leak FROM John Doe <john.doe@mail.com> TO Alice Legit <alice@legit.com>, Bob Legit <bob@legit.com> BCC Eve Eavesdropper <eve@hacker.io> BODY Here is the password: pa$$word DOCUMENTO É PRECISO SEPARAR OS CAMPOS EM TOKENS
17. SUBJECT important! dont let this leak FROM john doe <john.doe@mail.com> TO alice legit <alice@legit.com>, bob legit <bob@legit.com> BCC eve eavesdropper <eve@hacker.io> BODY here is the password: pa$$word DOCUMENTO CADA TOKEN PRECISA ESTAR NORMALIZADO
18. DOCUMENTO RESULTADO: CAMPOS E TERMOS FROM doe, john, johndoe@mail.com TO alice, alice@legit.com, bob, bob@legit.com, legit BCC eavesdropper, eve, eve@hacker.io SUBJECT dont, leak, let, this BODY here, password
19. DOCUMENT DOCUMENTO RESULTADO: CAMPOS E TERMOS
20. DOCUMENT INDEX WRITER DOCUMENT #0 DOCUMENTO AO INDEXAR, RECEBE UM ID
21. SEGMENT #0 INDEX WRITER ESCREVE UM SEGMENTO POR VEZ
22. SEGMENT #0 INDEX WRITER ESCREVE UM SEGMENTO POR VEZ X #0 TERM_1: #0 TERM_3: #0 TERM_4: #0
23. 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
24. 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
25. 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
26. SEGMENT #1 INDEX WRITER ESCREVE UM SEGMENTO POR VEZ #0
27. SEGMENTOS SÃO IMUTÁVEIS. MESMO. -0 10 docs
28. -1 SEGMENTOS SÃO IMUTÁVEIS. MESMO. 10 docs
29. SEGMENTOS SÃO IMUTÁVEIS. MESMO. -1 10 docs -0 33 docs
30. SEGMENTOS SÃO IMUTÁVEIS. MESMO. -0 19 docs -3 10 docs -5 33 docs
31. SEGMENTOS CADA SEGMENTO É UM PEQUENO ÍNDICE INDEX READER INDEX READER INDEX READER -0 19 docs -3 10 docs -5 33 docs COMPOSITE READER
32. 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
33. 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
34. 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
35. 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
36. SEGMENTOS A ANATOMIA DO SEGMENTO #0 _0. FNM _0. FDX _0. TIM _0. TIP _0. FRQ _0. PRX _0. FDT _0. DEL _0. NRM
37. _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.
38. _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.
39. _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.
40. _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.
41. _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.
42. _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.
43. _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.
44. _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
45. 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
46. FILE FORMAT PRECISAMOS FALAR DE BYTES (BEM DE LEVE) TERM_2 2 3 5 6 7 9 12 13 TERM_3 TERM_1 Docs
47. FILE FORMAT PRECISAMOS FALAR DE BYTES (BEM DE LEVE) TERM_2 2 1 2 1 1 2 3 1 TERM_3 TERM_1 DocDeltas
48. 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
49. FILE FORMAT VENI VIDI V-INT 32-BIT LITTLE ENDIAN INT = 123,456,789 = 1
50. 32-BIT V-INT FILE FORMAT VENI VIDI V-INT = 123,456,789 = 1 = 128
51. 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
52. 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
53. VAMOS FALAR DE DESAFIOS? PRODUÇÃO, AINDA TEM TEMPO?
54. PROBLEMAS FALANDO EM INTEIROS DOCID :: INT32 i.e. DOCID < 2,147,483,648
55. _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
56. PROBLEMAS 100% DE OVERHEAD DE ÍNDICE? NEM PENSAR! LUCENE INDEX RAW STORAGE ID API QUERY MSGS
57. SOLUÇÃO? AGRUPAR MENSAGENS DOCUMENT MSG MSG MSG MSG MSG MSG
58. 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”
59. 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.
60. SOLUÇÃO [2]? ARMAZENAR ÍNDICES USANDO POSITIONS _0. PRX POSITIONS E PAYLOAD (TODO MUNDO ESQUECE DO PAYLOAD)
61. 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
62. 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.
63. 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 ... ...
64. SOLUÇÃO [2]? É NECESSÁRIO REIMPLEMENTAR A BUSCA A AND B 68 68 A B 1 5 10 1 2 5 68 A&B 1 5 13
65. ORDENAÇÃO PARCIAL TOP 1000 FROM 400,000,000 HEAP SELECT O(n log k) TEMPO O(k) MEMÓRIA
66. 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
67. 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.
68. PERGUNTAS? ENQUANTO ISSO, LINKS: juanlopes.net/qconrio2015 twitter.com/juanplopes github.com/juanplopes