避免缓存击穿的利器之BloomFilter

Bloom Filter ༷ஷ

૲ᵇᬦᄁ࢏ҁ᝕᧍ғBloom Filter҂ฎ1970ଙኧӞӻݞ૲ᵇጱੜվৼ൉ڊጱ̶ਙਫᴬӤฎӞӻஉᳩጱԫ

ᬰګݻᰁ޾Ӟᔮڜᵋ๢ฉ੘ڍහ̶૲ᵇᬦᄁ࢏ݢզአԭ༄ᔱӞӻزᔰฎވࣁӞӻᵞݳӾ̶ਙጱսᅩฎᑮ

ᳵපሲ޾ັᧃ෸ᳵ᮷ᬱᬱ᩻ᬦӞᛱጱᓒဩ҅ᗌᅩฎํӞਧጱ᧏ᦩڦሲ޾ڢᴻࢯᵙ̶

ᶎᦶىᘶғӞᛱ᮷տࣁࢧᒼᖨਂڋᑯ҅౲ᘏၹᰁහഝ݄᯿ᬯӻ෸ײ୚ڊ๶҅ےړᶱߴ

Bloom Filter ܻቘ

૲ᵇᬦᄁ࢏ጱܻቘฎ҅୮Ӟӻزᔰᤩےفᵞݳ෸҅᭗ᬦKӻවڜڍහਖ਼ᬯӻزᔰฉ੘౮Ӟӻ֖හᕟӾጱK

ӻᅩ҅಩ਙժᗝԅ1̶༄ᔱ෸҅౯ժݝᥝ፡፡ᬯԶᅩฎӧฎ᮷ฎ1੪ҁय़ᕅ҂Ꭳ᭲ᵞݳӾํဌํਙԧғই

ຎᬯԶᅩํձ֜Ӟӻ0҅ڞᤩ༄زᔰӞਧӧࣁҔইຎ᮷ฎ1҅ڞᤩ༄زᔰஉݢᚆࣁ̶ᬯ੪ฎ૲ᵇᬦᄁ࢏ጱ

च๜௏మ̶

Bloom Filter᪙ܔߢ૶ڍහBit-Mapӧݶԏ॒ࣁԭғBloom Filterֵአԧkӻߢ૶ڍහ҅ྯӻਁᒧԀ᪙kӻ

bit੒ଫ̶՗ᘒᴳ֗ԧ٫ᑱጱ༷ሲ̶

ᓌܔጱ᧔Ӟӥ੪ฎ౯ժض಩౯ժහഝପጱහഝ᮷ے᫹ک౯ժጱᬦᄁ࢏Ӿ҅ྲইහഝପጱidሿࣁํғ1̵

2̵3

ᮎ੪አidғ1 ԅֺৼ՜ࣁӤࢶӾᕪᬦӣེhashԏݸ҅಩ӣེܻ๜꧊0ጱࣈොදԅ1

ӥེ౯ᬰ๶ັᧃইຎidԞฎ1 ᮎ౯੪಩1೭݄ӣེhash ݎሿ᪙Ӥᶎጱӣӻ֖ᗝਠقӞ໏҅ᮎ੪ᚆᦤกᬦ

ᄁ࢏Ӿํ1ጱ

ݍԏইຎӧӞ໏੪᧔กӧਂࣁԧ

ᮎଫአጱ࣋วࣁߺ᯾ޫҘӞᛱ౯ժ᮷տአ๶ᴠྊᖨਂڋᑯҁইຎӧᎣ᭲ᖨਂڋᑯฎࠨጱੜվ֎ӧᥝ፳

௒҅౯૪ᕪଆ֦ٵ॓অԧ҅փᭆᳪ ↓ ҂

ᓌܔ๶᧔੪ฎ֦හഝପጱid᮷ฎ1୏তᆐݸᛔीጱ҅ᮎ౯Ꭳ֦᭲ളݗฎ᭗ᬦidັᧃጱ҅౯੪೭ᨮහ݄ັ

ᧃ҅ᬯӻ෸ײ҅տݎሿᖨਂ᯾ᶎဌᬯӻහഝ҅౯݈݄හഝପັԞဌํ҅Ӟӻ᧗࿢ᬯ໏҅100ӻ҅1000

ӻ҅10000ӻޫҘ֦ጱDBच๜Ӥ੪ಔӧ֘ԧ҅ইຎࣁᖨਂ᯾ᶎےӤᬯӻ҅ฎӧฎ੪ӧਂࣁԧ֦҅ڣෙဌ

ᬯӻහഝ੪ӧ݄ັԧ҅ፗളreturnӞӻහഝԅᑮӧ੪অԧࡶ̶

ᬯሻ఺ᬯԍঅֵᮎํࠨᗌᅩԍҘํጱ҅౯ժള፳ஃӥ፡

Bloom Filterጱᗌᅩ

bloom filterԏಅզᚆ؉کࣁ෸ᳵ޾ᑮᳵӤጱපሲྲ᫾ṛ҅ฎࢩԅᇚᇗԧڣෙጱٵᏟሲ̵ڢᴻጱ׎ڥ௔

ਂࣁ᧏ڣ҅ݢᚆᥝັکጱزᔰଚဌํࣁ਻࢏Ӿ҅֕ฎhashԏݸ஑کጱkӻ֖ᗝӤ꧊᮷ฎ1̶ইຎ

bloom filterӾਂؙጱฎἓݷܔ҅ᮎԍݢզ᭗ᬦୌᒈӞӻጮݷܔ๶ਂؙݢᚆտ᧏ڣጱزᔰ̶

ڢᴻࢯᵙ̶Ӟӻනف਻࢏ጱزᔰฉ੘کbitහᕟጱkӻ֖ᗝӤฎ1҅ڢᴻጱ෸ײӧᚆᓌܔጱፗളᗝԅ

0҅ݢᚆտ୽ߥٌ՜زᔰጱڣෙ̶ݢզ᯻አCounting Bloom Filter

Bloom Filter ਫሿ

૲ᵇᬦᄁ࢏ํᦜग़ਫሿӨս۸҅GuavaӾ੪൉׀ԧӞᐿBloom Filterጱਫሿ̶

ࣁֵአbloom filter෸҅ᕰӧᬦጱӷᅩฎᶼ֌හഝᰁnզ݊๗๕ጱ᧏ڣሲfpp҅

ࣁਫሿbloom filter෸҅ᕰӧᬦጱӷᅩ੪ฎhashڍහጱᭌݐզ݊bitහᕟጱय़ੜ̶

੒ԭӞӻᏟਧጱ࣋ว҅౯ժᶼ֌ᥝਂጱහഝᰁԅn҅๗๕ጱ᧏ڣሲԅfpp҅ᆐݸᵱᥝᦇᓒ౯ժᵱᥝጱBitහ

ᕟጱय़ੜm҅զ݊hashڍහጱӻහk҅ଚᭌೠhashڍහ

(1)Bitහᕟय़ੜᭌೠ

̴̴໑ഝᶼ֌හഝᰁnզ݊᧏ڣሲfpp҅bitහᕟय़ੜጱmጱᦇᓒොୗғ

(2)ߢ૶ڍහᭌೠ

ኧᶼ֌හഝᰁnզ݊bitහᕟᳩଶm҅ݢզ஑کӞӻhashڍහጱӻහkғ

ߢ૶ڍහጱᭌೠ੒௔ᚆጱ୽ߥଫᧆฎஉय़ጱ҅Ӟӻঅጱߢ૶ڍහᥝᚆᬪ֒ᒵ༷ሲጱਖ਼ਁᒧԀฉ੘کݱӻ

Bit̶ᭌೠkӻӧݶጱߢ૶ڍහྲ᫾Ἃᅸ҅ӞᐿᓌܔጱොဩฎᭌೠӞӻߢ૶ڍහ҅ᆐݸᭆفkӻӧݶጱ݇

හ̶

ߢ૶ڍහӻහk̵֖හᕟय़ੜm̵ےفጱਁᒧԀහᰁnጱىᔮݢզ݇ᘍBloom Filters - the

math҅Bloom_filter-wikipedia

ᥝֵአBloomFilter҅ᵱᥝ୚فguava۱ғ

ၥᦶړӷྍғ

1̵ஃᬦᄁ࢏ӾනӞጯӡӻහ҅ᆐݸ݄ḵᦤᬯӞጯӡӻහฎވᚆ᭗ᬦᬦᄁ࢏

2̵ݚक़ತӞӡӻහ݄҅༄ḵᄋᗑԏṺጱහᰁ

com.google.guava

guava

23.0

/**

*

*/

public class TestBloomFilter {

private static int total = 1000000;

private static BloomFilter bf =

BloomFilter.create(Funnels.integerFunnel(), total);

// private static BloomFilter bf =

BloomFilter.create(Funnels.integerFunnel(), total, 0.001);

public static void main(String[] args) {

// ڡত۸1000000๵හഝکᬦᄁ࢏Ӿ

for (int i = 0; i < total; i++) {

bf.put(i);

ᬩᤈᕮຎғ

ᬩᤈᕮຎᤒᐏ҅᭭ܲᬯӞጯӡӻࣁᬦᄁ࢏Ӿጱහ෸҅᮷ᤩᦩڦڊ๶ԧ̶Ӟӡӻӧࣁᬦᄁ࢏Ӿጱහ҅᧏օ

ԧ320ӻ҅Კ᧏ሲฎ0.03ૢݦ̶

፡ӥBloomFilterጱრᎱғ

}

// ܃ᯈ૪ࣁᬦᄁ࢏Ӿጱ꧊҅ฎވํ܃ᯈӧӤጱ

for (int i = 0; i < total; i++) {

if (!bf.mightContain(i)) {

System.out.println("ํࣕՈᭈᚙԧ~~~");

}

}

// ܃ᯈӧࣁᬦᄁ࢏Ӿጱ10000ӻ꧊҅ํग़੝܃ᯈڊ๶

int count = 0;

for (int i = total; i < total + 10000; i++) {

if (bf.mightContain(i)) {

count++;

}

}

System.out.println("᧏օጱහᰁғ" + count);

}

}

public static BloomFilter create(Funnel funnel, int

expectedInsertions) {

return create(funnel, (long) expectedInsertions);

}

public static BloomFilter create(Funnel funnel, long

expectedInsertions) {

return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we

always get 5 hash functions

}

BloomFilterӞوࢥӻcreateොဩ҅ӧᬦ๋ᕣ᮷ฎᩳݻᒫࢥӻ̶፡Ӟӥྯӻ݇හጱތԎғ

funnelғහഝᔄࣳ(Ӟᛱฎ᧣አFunnelsૡٍᔄӾጱ)

expectedInsertionsғ๗๕ൊفጱ꧊ጱӻහ

fpp Კ᧏ሲ(ἕᦊ꧊ԅ0.03)

strategy ߢ૶ᓒဩ(౯Ԟӧ౜ࠨ఺௏)Bloom Filterጱଫአ

ࣁ๋ݸӞӻcreateොဩӾ҅ᦡᗝӞӻෙᅩғ

ӤᶎጱnumBits҅ᤒᐏਂӞጯӡӻintᔄࣳහਁ҅ᵱᥝጱ֖හԅ7298440҅700ग़ӡ̶֖ቘᦞӤਂӞጯӡӻ

හ҅Ӟӻintฎ4ਁᜓ32֖҅ᵱᥝ481000000=3200ӡ̶֖ইຎֵአHashMap݄ਂ҅ೲHashMap50%ጱਂ

ؙපሲ҅ᵱᥝ6400ӡ̶֖ݢզ፡ڊBloomFilterጱਂؙᑮᳵஉੜ҅ݝํHashMapጱ1/10ૢݦ

ӤᶎጱnumHashFunctions҅ᤒᐏᵱᥝ5ӻڍහ݄ਂᬯԶහਁ

ֵአᒫӣӻcreateොဩ҅౯ժᦡᗝӥᲙ᧏ሲғ

public static BloomFilter create(

Funnel funnel, long expectedInsertions, double fpp) {

return create(funnel, expectedInsertions, fpp,

BloomFilterStrategies.MURMUR128_MITZ_64);

}

static BloomFilter create(

Funnel funnel, long expectedInsertions, double fpp,

Strategy strategy) {

......

}

ٚᬩᤈ፡፡ғ

ྌ෸᧏օጱහᰁԅ4҅Კ᧏ሲԅ0.04%ૢݦ̶

୮Კ᧏ሲᦡԅ0.0003෸҅ಅᵱᥝጱ֖හԅ16883499҅1600ӡ֖҅ᵱᥝ12ӻڍහ

޾Ӥᶎ੒ྲݢզ፡ڊ҅Კ᧏ሲ᩼य़҅ಅᵱᑮᳵ޾෸ᳵ᩼ੜ҅Კ᧏ሲ᩼ੜ҅ಅᵱᑮᳵ޾෸ᳵᕅय़

ଉᥠጱپӻଫአ࣋วғ

cerberusࣁතᵞፊഴහഝጱ෸ײ, ํጱᔮᕹጱፊഴᶱᰁտஉय़, ᵱᥝ༄ັӞӻፊഴᶱጱݷਁฎވ૪ᕪ

ᤩᦕ୯کdbᬦԧ, ইຎဌํጱᦾ੪ᵱᥝٟفdb.

ᆻᡩᬦᄁ૪ಬکጱurl੪ӧٚಬ҅ݢአbloom filterᬦᄁ

࣯࣍ᮒկᬦᄁ̶ইຎአߢ૶ᤒ҅ྯਂؙӞՊӻ emailࣈ࣎҅੪ᵱᥝ 1.6GBጱٖਂҁአߢ૶ᤒਫሿጱ

ٍ֛ېဩฎਖ਼ྯӞӻ emailࣈ࣎੒ଫ౮Ӟӻكਁᜓጱמ௳೰ᕖ҅ᆐݸਖ਼ᬯԶמ௳೰ᕖਂفߢ૶ᤒ҅

ኧԭߢ૶ᤒጱਂؙපሲӞᛱݝํ 50%҅ࢩྌӞӻ emailࣈ࣎ᵱᥝܛአ܈مӻਁᜓ̶ӞՊӻࣈ࣎य़ᕅ

ᥝ 1.6GB҅ܨ܈مՊਁᜓጱٖਂ҂̶ࢩྌਂᨼپ܈Պӻᮒկࣈ࣎ݢᚆᵱᥝӤጯ GBጱٖਂ̶ᘒ

Bloom Filterݝᵱᥝߢ૶ᤒ 1/8ک 1/4 ጱय़ੜ੪ᚆᥴ٬ݶ໏ጱᳯ̶᷌

ᅩىဳ҅ӧᭁ᪠

অԧݱ֖҅զӤ੪ฎᬯᓤ෈ᒍጱق᮱ٖ਻ԧ҅ᚆ፡کᬯ᯾ጱՈޚ҅᮷ฎՈ಍̶

౯ݸᶎտྯޮ᮷ๅෛپᓤӞᕚ԰ᘶᗑय़ܯᶎᦶ޾ଉአದ๞຾ፘىጱ෈ᒍ҅ᶋଉఽᨀՈ಍ժᚆ፡کᬯ᯾҅

ইຎᬯӻ෈ᒍٟ஑ᬮӧᲙ҅ᥧ஑̿යӰ̀౯ํᅩӳᥜጱᦾ ࿢ᅩᩩ

࿢ىဳ

࿢ړՁ

੒ำካ౯๶᧔

፥ጱ ᶋଉํአѺѺѺ

ڠ֢ӧฃ҅ݱ֖ጱඪ೮޾ᦊݢ҅੪ฎ౯ڠ֢ጱ๋य़ۖێ҅౯ժӥᓤ෈ᒍᥠѺ

යӰ | ෈ ܻ̓ڠ̈́

ইຎ๜ᓤܗਮํձ֜Კ᧏҅᧗ಢᦧ೰ර҅ӧᙯఽᄶ Ѻ

private static BloomFilter bf =

BloomFilter.create(Funnels.integerFunnel(), total, 0.0003);

෈ᒍྯޮ೮ᖅๅෛ҅ݢզஙמ൤ᔱ̿ ӣॡৼයӰ ̀ᒫӞ෸ᳵᴅ᧛޾؛ๅҁྲܗਮ෱Ӟکӷᓤ

ߴ҂҅๜෈ GitHub https://github.com/JavaFamily ૪ᕪත୯҅ํӞᕚय़ܯᶎᦶᅩ௏ᖌ੕ࢶ҅

Ԟෆቘԧஉग़౯ጱ෈໩ཻ҅ᬨStar޾ਠ࠺҅य़ਹᶎᦶݢզ݇ᆙᘍᅩ॔ԟ҅૶๕౯ժӞ᩸ํᅩӳ

ᥜ̶

本文整理自实践经验，如有问题欢迎交流讨论。