{ "nbformat": 4, "nbformat_minor": 5, "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.10" } }, "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Giving Small Runs Better Bloom Filters\n", "\n", "Actual Bloom-filter probes on synthetic keys. The reported result counts false-positive table probes, not database I/O or latency. The continuous allocation model follows Monkey; the code is a small independent experiment.\n", "\n", "Extract the complete package and run from this directory. Python 3.10+, standard library. No network calls." ], "id": "cell-01" }, { "cell_type": "code", "metadata": {}, "source": [ "from pathlib import Path\n", "import runpy, json, csv\n", "ROOT = Path.cwd()\n", "assert (ROOT / 'experiment.py').is_file(), 'Open this notebook from its extracted topic folder.'\n", "experiment = runpy.run_path(str(ROOT / 'experiment.py'))" ], "execution_count": 1, "outputs": [], "id": "cell-02" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Run and check\n", "The script executes the experiment and its assertions, then writes the data and figures." ], "id": "cell-03" }, { "cell_type": "code", "metadata": {}, "source": [ "summary = experiment['run'](ROOT)\n", "print(json.dumps(summary, indent=2))" ], "execution_count": 2, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "{\n", " \"counts\": [\n", " 2000,\n", " 8000,\n", " 32000,\n", " 128000\n", " ],\n", " \"seeds\": [\n", " 11,\n", " 29,\n", " 47,\n", " 71,\n", " 101\n", " ],\n", " \"queries_per_seed\": 50000,\n", " \"total_absent_queries_per_policy\": 250000,\n", " \"filter_bytes_per_policy\": 212500,\n", " \"uniform_mean_probes_per_query\": 0.032848,\n", " \"optimized_mean_probes_per_query\": 0.01734,\n", " \"reduction_percent\": 47.21139795421334,\n", " \"uniform_seed_range\": [\n", " 0.03168,\n", " 0.03426\n", " ],\n", " \"optimized_seed_range\": [\n", " 0.0165,\n", " 0.01864\n", " ],\n", " \"no_false_negative_keys_checked\": 1700000,\n", " \"allocation_cases_passed\": 21,\n", " \"continuous_uniform_expected_probes\": 0.032770197872715845,\n", " \"continuous_optimized_expected_probes\": 0.016900541103991865,\n", " \"measurement\": \"Actual Python Bloom-filter bit probes on synthetic keys; not database I/O or latency\",\n", " \"python\": \"3.12.14\",\n", " \"hash\": \"SHAKE-256 pseudorandom 64-bit chunks per filter/key\",\n", " \"run_date\": \"2026-11-06\"\n", "}\n" ] } ], "id": "cell-04" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Inspect actual bytes and per-filter counts\n", "The two policies use the same total byte budget, keys, queries, and seeds. Query prefixes are absent from every run. All four filters are probed: no range pruning is modeled." ], "id": "cell-05" }, { "cell_type": "code", "metadata": {}, "source": [ "with (ROOT / 'data/filter-results.csv').open() as f:\n", " rows = list(csv.DictReader(f))\n", "for row in rows:\n", " if row['seed'] == '11':\n", " print(row)" ], "execution_count": 3, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "{'policy': 'uniform', 'seed': '11', 'level': '1', 'keys': '2000', 'filter_bytes': '2500', 'bits_per_key': '10.0', 'hashes': '7', 'queries': '50000', 'false_positives': '378', 'observed_fpr': '0.00756', 'finite_occupancy_approx_fpr': '0.008194712255680973'}\n", "{'policy': 'uniform', 'seed': '11', 'level': '2', 'keys': '8000', 'filter_bytes': '10000', 'bits_per_key': '10.0', 'hashes': '7', 'queries': '50000', 'false_positives': '449', 'observed_fpr': '0.00898', 'finite_occupancy_approx_fpr': '0.00819396959904672'}\n", "{'policy': 'uniform', 'seed': '11', 'level': '3', 'keys': '32000', 'filter_bytes': '40000', 'bits_per_key': '10.0', 'hashes': '7', 'queries': '50000', 'false_positives': '425', 'observed_fpr': '0.0085', 'finite_occupancy_approx_fpr': '0.00819378394820313'}\n", "{'policy': 'uniform', 'seed': '11', 'level': '4', 'keys': '128000', 'filter_bytes': '160000', 'bits_per_key': '10.0', 'hashes': '7', 'queries': '50000', 'false_positives': '371', 'observed_fpr': '0.00742', 'finite_occupancy_approx_fpr': '0.008193737537730022'}\n", "{'policy': 'optimized', 'seed': '11', 'level': '1', 'keys': '2000', 'filter_bytes': '4435', 'bits_per_key': '17.74', 'hashes': '12', 'queries': '50000', 'false_positives': '13', 'observed_fpr': '0.00026', 'finite_occupancy_approx_fpr': '0.00019912605825521003'}\n", "{'policy': 'optimized', 'seed': '11', 'level': '2', 'keys': '8000', 'filter_bytes': '14854', 'bits_per_key': '14.854', 'hashes': '10', 'queries': '50000', 'false_positives': '48', 'observed_fpr': '0.00096', 'finite_occupancy_approx_fpr': '0.000796906780796838'}\n", "{'policy': 'optimized', 'seed': '11', 'level': '3', 'keys': '32000', 'filter_bytes': '47875', 'bits_per_key': '11.96875', 'hashes': '8', 'queries': '50000', 'false_positives': '165', 'observed_fpr': '0.0033', 'finite_occupancy_approx_fpr': '0.003188801832595021'}\n", "{'policy': 'optimized', 'seed': '11', 'level': '4', 'keys': '128000', 'filter_bytes': '145336', 'bits_per_key': '9.0835', 'hashes': '6', 'queries': '50000', 'false_positives': '706', 'observed_fpr': '0.01412', 'finite_occupancy_approx_fpr': '0.012763956037650919'}\n" ] } ], "id": "cell-06" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Try the low-memory boundary\n", "A zero-bit filter always answers maybe. Equal-cardinality runs recover uniform allocation." ], "id": "cell-07" }, { "cell_type": "code", "metadata": {}, "source": [ "allocate = experiment['allocation']\n", "print('Equal sizes:', allocate([1000]*4, 40000))\n", "print('Low budget:', allocate([2000,8000,32000,128000], 170000))\n", "assert all(abs(x-10)<1e-9 for x in allocate([1000]*4, 40000))" ], "execution_count": 4, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "Equal sizes: [9.999999999999998, 9.999999999999998, 9.999999999999998, 9.999999999999998]\n", "Low budget: [8.739634572298439, 5.854244490520512, 2.968854408742584, 0.08346432696465673]\n" ] } ], "id": "cell-08" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Generated figures" ], "id": "cell-09" }, { "cell_type": "code", "metadata": {}, "source": [ "from IPython.display import SVG, display\n", "display(SVG(filename=str(ROOT / 'figures/allocation.svg')))" ], "execution_count": 5, "outputs": [ { "output_type": "display_data", "data": { "image/svg+xml": "Small runs receive more bits per key\n\n\nSmall runs receive more bits per key\nFilter memory is fixed at 212,500 bytes in both policies\n2,000 keys \u00b7 uniform\n\n10.00\n2,000 keys \u00b7 optimized\n\n17.74\n8,000 keys \u00b7 uniform\n\n10.00\n8,000 keys \u00b7 optimized\n\n14.85\n32,000 keys \u00b7 uniform\n\n10.00\n32,000 keys \u00b7 optimized\n\n11.97\n128,000 keys \u00b7 uniform\n\n10.00\n128,000 keys \u00b7 optimized\n\n9.08\nBits per key\n" }, "metadata": {} } ], "id": "cell-10" }, { "cell_type": "code", "metadata": {}, "source": [ "from IPython.display import SVG, display\n", "display(SVG(filename=str(ROOT / 'figures/probes.svg')))" ], "execution_count": 6, "outputs": [ { "output_type": "display_data", "data": { "image/svg+xml": "The same memory buys fewer false-positive probes\n\n\nThe same memory buys fewer false-positive probes\nActual filter queries; 250,000 absent keys per policy, averaged across five seeds\nUniform\n\n32.85\nOptimized\n\n17.34\nFalse-positive table probes per 1,000 absent lookups (lower is better)\n" }, "metadata": {} } ], "id": "cell-11" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sources\n", "- [Bigtable: A Distributed Storage System for Structured Data](https://static.usenix.org/events/osdi06/tech/chang/chang_html/index.html)\n", "- [Monkey: Optimal Navigable Key-Value Store](https://cs-people.bu.edu/mathan/publications/sigmod17-dayan.pdf)\n", "- [RocksDB Bloom Filter](https://github.com/meta/rocksdb/wiki/RocksDB-Bloom-Filter)" ], "id": "cell-12" } ] }