Embed Size (px)
Citation preview
Você não precisa estar 100% certo
o tempo todo!
Algoritmos para consultar terabytes de dados
Fabiane Bizinella NardonTailTarget
@fabianenardon
SUAS RESPOSTAS DEVEM ESTAR SEMPRE CERTAS
ÀS VEZES 100% CERTAS
ÀS VEZES 98% CERTAS
2 Bilhões de tuplas / 71min 31 Milhões de tuplas / 3 seg
Fonte: http://highscalability.com/blog/2016/2/25/when-should-approximate-query-processing-be-used.html
QUAL O TAMANHO DA AMOSTRA QUE EU
PRECISO?
DEPENDE DE QUANTO VOCÊ ACEITA ERRAR
MARGEM DE ERRO:INTERVALO NO QUAL
ESPERO ENCONTRAR O DADO QUE QUERO MEDIR.
EXEMPLO:NÚMERO DE MULHERES NA INTERNET
COM 5% DE MARGEM DE ERRO. SE O NÚMERO ESTIMADO É DE 100 MILHÕES, ESPERO QUE O NÚMERO
REAL ESTEJA ENTRE 100 MILHÕES +/- 5%
NÍVEL DE CONFIANÇA:CERTEZA QUE O DADO QUE BUSCAMOS ESTÁ DENTRO
DA MARGEM DE ERRO
EXEMPLO:95% DE FATOR DE CERTEZA SIGNIFICA QUE EM 95% DOS
CASOS, O NÚMERO DE MULHERES ESTARÁ DENTRO
DE 100 MILHÕES +/- 5%
MARGEM DE ERRO
NÍVEL DE CONFIANÇA
TAMANHODA AMOSTRA
MARGEM DE ERRO NÍVEL DE
CONFIANÇA
TAMANHODA AMOSTRA
MARGEM DE ERRO
NÍVEL DE CONFIANÇ
A
TAMANHODA AMOSTRA
n = (z * stddev /mde)2
n = tamanho da amostrastddev = desvio padrão da população
mde = margem de erroz = Z-score
nreal = (n * p) / (n + p – 1)
n = tamanho da amostranreal= tamanho real da amostra
P = tamanho da população
n = (z * stddev /mde)2
Z-Score:
90% = 1.64595% = 1.9699% = 2.576
n = (z * stddev /mde)2
n = (2.576 * 0.5 / 0.01)2
n = 16.590
n = tamanho da amostrastddev = desvio padrão da população
mde = margem de erroz = Z-score
nreal = (n * p) / (n + p – 1)
nreal = (16590 * 100000) / (16590 + 100000 -1)
nreal = 14.229
n = tamanho da amostranreal= tamanho real da amostra
P = tamanho da população
P = 100.000 -> nreal = 14.229
P = 200.000 -> nreal = 15.317 P = 400.000 -> nreal = 15.927
P = 1.000.000 -> nreal = 16.317P = 10.000.000 -> nreal = 16.560
P = 200.000.000 -> nreal = 16.586P = 400.000.000 -> nreal = 16.587
P = 1.000.000.000 -> nreal = 16.587
POPULAÇÃO: 488.333.067
PROPORÇÃO POR GÊNERO:
AMOSTRA: 32.000M: 156.556.529 (32.05%)H: 95.148.646 (19.48%)
AMOSTRA: 16.000M: 158.036.788 (32.36%)H: 96.018.489 (19.66%)
COMO ESCOLHER OS ITENS DA AMOSTRA
SAMPLING WITH REPLACEMENT: ESCOLHE UM ITEM ALEATÓRIO
SUCESSIVAMENTE. MESMO ITEM PODE APARECER MAIS DE UMA
VEZ
SAMPLING WITHOUT REPLACEMENT:
ESCOLHE UM ITEM ALEATÓRIO E GARANTE QUE ELE SÓ APARECE
UMA VEZ NA AMOSTRA.
Random Sampling: Escolhe amostras aleatórias,
todas com o mesmo peso
Stratified Sampling: Divide a população em stratas
e faz uma amostra de cada strata separadamente
AMOSTRA RANDÔMICA
PARA CADA GRUPO AMOSTRAL, GUARDE:
TAMANHO DA AMOSTRATAMANHO REAL
IDENTIFICADOR DO GRUPO AMOSTRAL
EXTRAINDO AMOSTRAS DA BASE DE DADOS
ESTRATÉGIA 1: GRAVE NÚMERO RANDÔMICO
INDEXADO NO BANCO DE DADOS
{"_id": 1,"gender": "f","age": 24,"selector": 0.12412423
}
* MongoDB
int selector = 0;int sampleCount = 0;List<User> sample = new ArrayList<>();double prevSelector = -1;while (sampleCount < SAMPLE_SIZE) { /* Add to sample result of db.Users.find({ selector: { $gt: prevSelector}
}).limit(100);
Set last selector found to prevSelector */
sampleCount += sample.size();}
ESTRATÉGIA 2: USE MECANISMO DE
SAMPLING DO SEU BD
{"aggregations": { "sample": { "sampler": { "shard_size": 16000 }, "aggregations": { "views": { "terms": { "field": "gender“ }, "aggregations": { "unique_users": { "cardinality": { "field": "uid" } } } } } } }} * ElasticSearch
ESTRATÉGIA 3: USANDO SHARDING
SHARDING 1 SHARDING 2 SHARDING 3
ITEMS POR SHARDING = TAMANHO DA AMOSTRA / NÚMERO DE SHARDINGS
RANDOMKEYs RANDOMKEYs RANDOMKEYs
* Redis
PARA CADA GRUPO AMOSTRAL, GUARDE:
TAMANHO DA AMOSTRATAMANHO REAL
IDENTIFICADOR DO GRUPO AMOSTRAL
Ta = Tamanho da AmostraTp = Tamanho da PopulaçãoNa = Número de Itens na AmostraNp = Número de Itens na população
Np = Na * Tp / Ta
Exemplo:Ta = 1000Tp = 100.000Na = 400 Mulheres
Np = 400 * 100.000 / 1000 = 40.000
NÃO SEI O TAMANHO DA POPULAÇÃO.
E AGORA?
RESERVOIR SAMPLING
1 2 3 4 5
A B C D E
F
Random (0..1): 0.7K = Ta / i K = 5 / 6 = 0.83Se K > Random => TROCA!
RESERVOIR SAMPLINGDISTRIBUÍDO
1 2 3 4 5
A B C D E F G H I J K L M N O P Q R S T U V X Y W Z
1 2 3 4 5
A B C D E F G H I J K L M N O P Q R S T U V X Y W Z
1 2 3 4 5
A:0.1 B:0.3 C:0.2 D:0.7 E:0.9 F:0.11 G:0.4 H:0.6 I:0.76
J:0.8 K:0.2 L:0.54 M:0.4 N:0.21 O:0.33 P:0.56 Q:0.32 R:0.23
S:0.21 T:0.32 U:0.22 V:0.7 X:0.12 Y:0.23 W:0.3 Z:0.76
private SortedMap<Double, MyObject> reservoir;
...if (reservoir.size() < SAMPLE_SIZE) { reservoir.put(score, myObject);} else if (score > reservoir.firstKey()) { reservoir.remove(reservoir.firstKey()); reservoir.put(score, myObject);}
O L P I Z
1 2 3 4 5
A:0.1 B:0.3 C:0.2 D:0.7 E:0.9 F:0.11 G:0.4 H:0.6 I:0.76
J:0.8 K:0.2 L:0.54 M:0.4 N:0.21 O:0.33 P:0.56 Q:0.32 R:0.23
S:0.21 T:0.32 U:0.22 V:0.7 X:0.12 Y:0.23 W:0.3 Z:0.76
H:0.6 D:0.7 E:0.9 F:0.11 I:0.76 R:0.23 Q:0.32 O:0.33 L:0.54 P:0.56 S:0.21 U:0.22 Y:0.23 T:0.32 Z:0.76
COMBINER
import org.apache.crunch.lib.Sample;
Sample.reservoirSample(PCollection<T> input, int sampleSize)
Apache Crunch:
CONSULTAS APROXIMADAS
AGREGAÇÕESPROPORÇÕES
COUNT
Np = Na * Tp / Ta
400 * 100.000 / 1000=
40.000
SUM
Sp = Sa * Tp / Ta
600 * 100.000 / 1000=
60.000
AVERAGE
Ap = (Sa * Tp / Ta) / (Na * Tp / Ta)
(600 * 100.000 / 1000) /
(400 * 100.000 / 1000)=
1.5
Você não precisa estar 100% certo
o tempo todo!
Algoritmos em Java para consultar terabytes de dados
Fabiane Bizinella NardonTailTarget
@fabianenardon
