{"type":"excalidraw","version":2,"source":"https://AwesomeSystemDesign.dev","elements":[{"angle":0,"strokeColor":"#6577aa","backgroundColor":"#eef1fc","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-1"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-1"}],"updated":0,"link":null,"locked":false,"id":"shape-0","type":"rectangle","seed":41,"x":16,"y":16,"width":288,"height":68,"customData":{"revealStep":1}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-1"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-1","type":"text","seed":114,"x":36,"y":35.7,"width":248,"height":28.6,"fontSize":22,"fontFamily":1,"text":"Bloom Filter","originalText":"Bloom Filter","textAlign":"left","verticalAlign":"middle","containerId":"shape-0","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":1}},{"angle":0,"strokeColor":"#628572","backgroundColor":"#edf5ee","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-2"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-3"}],"updated":0,"link":null,"locked":false,"id":"shape-2","type":"rectangle","seed":187,"x":16,"y":128,"width":288,"height":264.8,"customData":{"revealStep":2}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-2"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-3","type":"text","seed":260,"x":36,"y":146,"width":248,"height":228.8,"fontSize":22,"fontFamily":1,"text":"A probabilistic data\nstructure:\n\"Key might exist\"\n(can be wrong —\nfalse positive)\n\"Key definitely does\nnot exist\" (never\nwrong)","originalText":"A probabilistic data\nstructure:\n\"Key might exist\"\n(can be wrong —\nfalse positive)\n\"Key definitely does\nnot exist\" (never\nwrong)","textAlign":"left","verticalAlign":"middle","containerId":"shape-2","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":2}},{"angle":0,"strokeColor":"#a68a53","backgroundColor":"#fff7e6","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-3"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-5"}],"updated":0,"link":null,"locked":false,"id":"shape-4","type":"rectangle","seed":333,"x":16,"y":436.8,"width":288,"height":121.8,"customData":{"revealStep":3}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-3"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-5","type":"text","seed":406,"x":36,"y":454.8,"width":248,"height":85.8,"fontSize":22,"fontFamily":1,"text":"Bit array: [0 1 0 1 1\n0 0 1 0 1 0 0 1 0 0\n1]","originalText":"Bit array: [0 1 0 1 1\n0 0 1 0 1 0 0 1 0 0\n1]","textAlign":"left","verticalAlign":"middle","containerId":"shape-4","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":3}},{"angle":0,"strokeColor":"#9180ac","backgroundColor":"#f4effb","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-4"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-7"}],"updated":0,"link":null,"locked":false,"id":"shape-6","type":"rectangle","seed":479,"x":16,"y":602.6,"width":288,"height":236.20000000000002,"customData":{"revealStep":4}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-4"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-7","type":"text","seed":552,"x":36,"y":620.6,"width":248,"height":200.20000000000002,"fontSize":22,"fontFamily":1,"text":"Insert \"user:42\":\nhash1(\"user:42\") = 3\n→ set bit 3\nhash2(\"user:42\") = 7\n→ set bit 7\nhash3(\"user:42\") = 12\n→ set bit 12","originalText":"Insert \"user:42\":\nhash1(\"user:42\") = 3\n→ set bit 3\nhash2(\"user:42\") = 7\n→ set bit 7\nhash3(\"user:42\") = 12\n→ set bit 12","textAlign":"left","verticalAlign":"middle","containerId":"shape-6","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":4}},{"angle":0,"strokeColor":"#6577aa","backgroundColor":"#eef1fc","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-5"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-9"}],"updated":0,"link":null,"locked":false,"id":"shape-8","type":"rectangle","seed":625,"x":16,"y":882.8000000000001,"width":288,"height":264.8,"customData":{"revealStep":5}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-5"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-9","type":"text","seed":698,"x":36,"y":900.8000000000001,"width":248,"height":228.8,"fontSize":22,"fontFamily":1,"text":"Check \"user:99\":\nhash1(\"user:99\") = 5 →\nbit 5 = 0 →\nDEFINITELY NOT\nHERE\n→ Skip this SSTable\nentirely (no disk\nI/O!)","originalText":"Check \"user:99\":\nhash1(\"user:99\") = 5 →\nbit 5 = 0 →\nDEFINITELY NOT\nHERE\n→ Skip this SSTable\nentirely (no disk\nI/O!)","textAlign":"left","verticalAlign":"middle","containerId":"shape-8","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":5}},{"angle":0,"strokeColor":"#628572","backgroundColor":"#edf5ee","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-6"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-11"}],"updated":0,"link":null,"locked":false,"id":"shape-10","type":"rectangle","seed":771,"x":16,"y":1191.6000000000001,"width":288,"height":207.6,"customData":{"revealStep":6}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-6"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-11","type":"text","seed":844,"x":36,"y":1209.6000000000001,"width":248,"height":171.6,"fontSize":22,"fontFamily":1,"text":"False positive rate\nwith 10 bits/key, 3\nhash functions:\n~1% → 99% of\nunnecessary disk\nreads avoided","originalText":"False positive rate\nwith 10 bits/key, 3\nhash functions:\n~1% → 99% of\nunnecessary disk\nreads avoided","textAlign":"left","verticalAlign":"middle","containerId":"shape-10","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":6}},{"angle":0,"strokeColor":"#a68a53","backgroundColor":"#fff7e6","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-7"],"frameId":null,"roundness":null,"boundElements":[{"type":"text","id":"shape-13"}],"updated":0,"link":null,"locked":false,"id":"shape-12","type":"rectangle","seed":917,"x":16,"y":1443.2,"width":288,"height":179,"customData":{"revealStep":7}},{"angle":0,"strokeColor":"#394557","backgroundColor":"transparent","fillStyle":"solid","strokeWidth":1.5,"strokeStyle":"solid","roughness":0.7,"opacity":100,"version":1,"versionNonce":1,"isDeleted":false,"groupIds":["step-7"],"frameId":null,"roundness":null,"boundElements":null,"updated":0,"link":null,"locked":false,"id":"shape-13","type":"text","seed":990,"x":36,"y":1461.2,"width":248,"height":143,"fontSize":22,"fontFamily":1,"text":"Memory: 1.25 bytes\nper key\n10B keys × 1.25\nbytes = ~12.5 GB\n(fits in RAM)","originalText":"Memory: 1.25 bytes\nper key\n10B keys × 1.25\nbytes = ~12.5 GB\n(fits in RAM)","textAlign":"left","verticalAlign":"middle","containerId":"shape-12","lineHeight":1.3,"autoResize":false,"customData":{"revealStep":7}}],"appState":{"viewBackgroundColor":"#fbfbf8","gridSize":null},"files":{}}