Skip to content

popoto.fields.existence_filter

popoto.fields.existence_filter

ExistenceFilter and FrequencySketch — probabilistic data structures as Popoto fields.

ExistenceFilter wraps a Bloom filter implemented with Redis strings (SETBIT/GETBIT) and Lua scripts. Answers "have I ever stored a record matching this fingerprint?" in O(1). No Redis modules required — works on both Redis and Valkey.

FrequencySketch wraps a Count-Min Sketch implemented with Redis hashes (HINCRBY/HGET) and Lua scripts. Provides approximate frequency counting for fingerprints. No Redis modules required — works on both Redis and Valkey.

Design

Both fields are "side-effect fields" — they do not store a value on the model instance. They only maintain probabilistic indexes via on_save() hooks. This follows the same pattern as SortedFieldMixin maintaining a sorted set index.

Hash functions: ExistenceFilter uses the Kirsch–Mitzenmacher double hashing optimization: h_i(x) = (h1(x) + i * h2(x)) mod m. Two hash functions simulate k independent Bloom-row hashes. The pair is versioned per filter (#775): v2 uses 32-bit FNV-1a over the bytes forward and reversed, with all arithmetic exact in Lua doubles; v1 (DJB2 plus an FNV-1-shaped multiply) loses low-order bits past 2^53. v1 is still the default for a new filter, because a process running pre-#775 code reads every filter with the v1 hash; v2 is opt-in (ExistenceFilter(hash_version=2) for new filters, rebuild_indexes(bloom_hash_version=2) to convert existing ones) once every process runs this version. See BLOOM_V2_HEADER. FrequencySketch uses independent per-row polynomial hashes: each of the depth rows has its own prime multiplier and modulus, forming a practically pairwise-independent family that restores the standard CMS error bound.

Tokenization: On save, fingerprint strings are automatically tokenized into individual words. Each token is added to the bloom filter / count-min sketch separately. This enables word-level queries: saving "kubernetes deployment guide" allows might_exist("kubernetes") to return True. Tokenization lowercases, splits on non-word characters, filters tokens shorter than 3 characters, and removes common English stop words. If tokenization produces zero tokens, the raw fingerprint is used as a fallback.

Redis Key Patterns
  • Bloom filter: $EF:{ClassName}:{field_name} — single Redis string (bit array, followed by a 4-byte version marker on v2 filters)
  • Bloom rebuild lock: $EF:{ClassName}:{field_name}:rebuild — a string holding the token of the one rebuild converting the filter to v2 (expires unless that rebuild keeps renewing it)
  • Bloom rebuild staging: $EF:{ClassName}:{field_name}:rebuild:staging — the v2 filter that rebuild is filling (same expiry). One fixed name: the lock's token decides who may renew, swap or drop it
  • Count-Min Sketch: $FS:{ClassName}:{field_name} — single Redis hash
Valkey Compatibility

Uses only core Redis commands: SETBIT, GETBIT, HINCRBY, HGET, EVAL. No BF., CMS., or other module commands. Works identically on Redis and Valkey.

Example

from popoto import Model, KeyField, Field from popoto.fields.existence_filter import ExistenceFilter, FrequencySketch

class Memory(Model): agent_id = KeyField() topic = Field(type=str) bloom = ExistenceFilter( error_rate=0.01, capacity=100_000, fingerprint_fn=lambda inst: inst.topic, ) freq = FrequencySketch( fingerprint_fn=lambda inst: inst.topic, )

After saving some memories...

if Memory.bloom.definitely_missing("kubernetes"): print("No memories about kubernetes") else: results = Memory.query.filter(agent_id="agent-1")

count = Memory.freq.get_frequency("kubernetes")

BloomRebuildError

Bases: RuntimeError

A v2 bloom rebuild could not start or could not swap its result in.

Raised by Model.rebuild_indexes(bloom_hash_version=2). Whenever it is raised the live filter is the one that was there before: a rebuild only replaces it in a single atomic compare-and-rename, never partly.

Source code in src/popoto/fields/existence_filter.py
class BloomRebuildError(RuntimeError):
    """A v2 bloom rebuild could not start or could not swap its result in.

    Raised by ``Model.rebuild_indexes(bloom_hash_version=2)``. Whenever it is
    raised the live filter is the one that was there before: a rebuild only
    replaces it in a single atomic compare-and-rename, never partly.
    """

BloomRebuildInProgressError

Bases: BloomRebuildError

Another process holds this filter's v2 rebuild lock.

Raised before rebuild_indexes() has changed anything -- no index is deleted and no filter touched -- so the caller can simply retry once the other rebuild has finished (by which time the conversion it asked for is usually already done). lock_key, holder and expires_in_ms say which rebuild holds it and when the lock lapses if that rebuild has died.

Source code in src/popoto/fields/existence_filter.py
class BloomRebuildInProgressError(BloomRebuildError):
    """Another process holds this filter's v2 rebuild lock.

    Raised before ``rebuild_indexes()`` has changed anything -- no index is
    deleted and no filter touched -- so the caller can simply retry once the
    other rebuild has finished (by which time the conversion it asked for is
    usually already done). ``lock_key``, ``holder`` and ``expires_in_ms`` say
    which rebuild holds it and when the lock lapses if that rebuild has died.
    """

    def __init__(self, lock_key: str, holder: "str | None", expires_in_ms: int):
        self.lock_key = lock_key
        self.holder = holder
        self.expires_in_ms = expires_in_ms
        super().__init__(
            f"{lock_key} is held by another bloom rebuild (token {holder!r}); "
            f"only one rebuild of a filter runs at a time. Nothing was changed. "
            f"Retry once it finishes; if that rebuild died, its lock lapses in "
            f"{max(expires_in_ms, 0)} ms."
        )

BloomRebuildLostLockError

Bases: BloomRebuildError

The rebuild's lock lapsed before its swap, so the swap was refused.

Every record was re-saved (the other indexes are rebuilt), but the v2 staging filter was discarded and the live filter is unchanged -- still complete for every token it held. Rerun the rebuild to convert it.

Source code in src/popoto/fields/existence_filter.py
class BloomRebuildLostLockError(BloomRebuildError):
    """The rebuild's lock lapsed before its swap, so the swap was refused.

    Every record was re-saved (the other indexes are rebuilt), but the v2
    staging filter was discarded and the live filter is unchanged -- still
    complete for every token it held. Rerun the rebuild to convert it.
    """

BloomLockRenewer

Renews v2 rebuild locks on a timer for as long as they are held.

Model.rebuild_indexes(bloom_hash_version=2) holds each filter's lock from before step 1 (deleting the other indexes) until the swap. Renewal must not depend on what the rebuild is doing at the time: step 1 can run for seconds on a large store without visiting a record (PR #801 review, N1), so a background thread renews every third of Defaults.BLOOM_REBUILD_LOCK_TTL_MS, through the token-checked renew script. async_rebuild_indexes runs rebuild_indexes in a worker thread on Redis, so it gets the same renewer.

Use as a context manager around the work. The thread is started on entry and stopped and joined on exit, whatever ends the block (an exception, KeyboardInterrupt), so it never outlives the rebuild. It is a daemon too, so a hard interpreter exit is never held up by it.

A renewal that finds its lock lost (lapsed, or taken over by another rebuild) records the field in :attr:lost and stops renewing it; the caller refuses that filter's swap. A pause of the whole process (SIGSTOP, a VM freeze) pauses this thread with it, so the lock still lapses then -- and the swap's own compare-and-rename refuses it.

Source code in src/popoto/fields/existence_filter.py
class BloomLockRenewer:
    """Renews v2 rebuild locks on a timer for as long as they are held.

    ``Model.rebuild_indexes(bloom_hash_version=2)`` holds each filter's lock
    from before step 1 (deleting the other indexes) until the swap. Renewal
    must not depend on what the rebuild is doing at the time: step 1 can run
    for seconds on a large store without visiting a record (PR #801 review,
    N1), so a background thread renews every third of
    ``Defaults.BLOOM_REBUILD_LOCK_TTL_MS``, through the token-checked renew
    script. ``async_rebuild_indexes`` runs ``rebuild_indexes`` in a worker
    thread on Redis, so it gets the same renewer.

    Use as a context manager around the work. The thread is started on
    entry and stopped and joined on exit, whatever ends the block (an
    exception, ``KeyboardInterrupt``), so it never outlives the rebuild. It
    is a daemon too, so a hard interpreter exit is never held up by it.

    A renewal that finds its lock lost (lapsed, or taken over by another
    rebuild) records the field in :attr:`lost` and stops renewing it; the
    caller refuses that filter's swap. A pause of the whole process
    (``SIGSTOP``, a VM freeze) pauses this thread with it, so the lock still
    lapses then -- and the swap's own compare-and-rename refuses it.
    """

    def __init__(self, model_class: Any, held: "list[tuple[Any, str]]"):
        self._model_class = model_class
        self._held = list(held)
        self._stop = threading.Event()
        self._thread: "threading.Thread | None" = None
        #: Fields whose lock a renewal found lost. Their swap is refused.
        self.lost: "list[Any]" = []

    @staticmethod
    def interval_s() -> float:
        """A third of the lock TTL, read at call time (it is a tuning
        constant tests patch)."""
        from .constants import Defaults

        return Defaults.BLOOM_REBUILD_LOCK_TTL_MS / 3000.0

    def __enter__(self) -> "BloomLockRenewer":
        if self._held:
            self._thread = threading.Thread(
                target=self._run,
                name=f"popoto-bloom-renew-{self._model_class.__name__}",
                daemon=True,
            )
            self._thread.start()
        return self

    def __exit__(self, *exc: Any) -> None:
        self.stop()

    def stop(self) -> None:
        """Stop renewing and wait for the thread to end. Idempotent."""
        self._stop.set()
        thread, self._thread = self._thread, None
        if thread is not None:
            thread.join()

    def _run(self) -> None:
        while not self._stop.wait(self.interval_s()):
            self.renew_once()

    def renew_once(self) -> None:
        """Renew every lock still held; record any found lost."""
        for pair in list(self._held):
            field, token = pair
            try:
                ok = field._renew_v2_rebuild(self._model_class, token)
            except Exception:
                # A transient error is not a lost lock: try again next
                # interval. If the lock does lapse meanwhile, the next
                # renewal (or the swap) finds out.
                logger.warning(
                    "%s.rebuild_indexes(): renewing the v2 rebuild lock on %s "
                    "failed; retrying",
                    self._model_class.__name__,
                    field._rebuild_lock_key(self._model_class),
                    exc_info=True,
                )
                continue
            if not ok:
                # By identity: Field.__eq__ builds a query, not a bool.
                self._held = [h for h in self._held if h is not pair]
                self.lost.append(field)
                logger.warning(
                    "%s.rebuild_indexes(): the v2 rebuild lock on %s lapsed; "
                    "its swap will be refused and the filter left unchanged",
                    self._model_class.__name__,
                    field._rebuild_lock_key(self._model_class),
                )

interval_s() staticmethod

A third of the lock TTL, read at call time (it is a tuning constant tests patch).

Source code in src/popoto/fields/existence_filter.py
@staticmethod
def interval_s() -> float:
    """A third of the lock TTL, read at call time (it is a tuning
    constant tests patch)."""
    from .constants import Defaults

    return Defaults.BLOOM_REBUILD_LOCK_TTL_MS / 3000.0

stop()

Stop renewing and wait for the thread to end. Idempotent.

Source code in src/popoto/fields/existence_filter.py
def stop(self) -> None:
    """Stop renewing and wait for the thread to end. Idempotent."""
    self._stop.set()
    thread, self._thread = self._thread, None
    if thread is not None:
        thread.join()

renew_once()

Renew every lock still held; record any found lost.

Source code in src/popoto/fields/existence_filter.py
def renew_once(self) -> None:
    """Renew every lock still held; record any found lost."""
    for pair in list(self._held):
        field, token = pair
        try:
            ok = field._renew_v2_rebuild(self._model_class, token)
        except Exception:
            # A transient error is not a lost lock: try again next
            # interval. If the lock does lapse meanwhile, the next
            # renewal (or the swap) finds out.
            logger.warning(
                "%s.rebuild_indexes(): renewing the v2 rebuild lock on %s "
                "failed; retrying",
                self._model_class.__name__,
                field._rebuild_lock_key(self._model_class),
                exc_info=True,
            )
            continue
        if not ok:
            # By identity: Field.__eq__ builds a query, not a bool.
            self._held = [h for h in self._held if h is not pair]
            self.lost.append(field)
            logger.warning(
                "%s.rebuild_indexes(): the v2 rebuild lock on %s lapsed; "
                "its swap will be refused and the filter left unchanged",
                self._model_class.__name__,
                field._rebuild_lock_key(self._model_class),
            )

ExistenceFilter

Bases: Field

Bloom filter for O(1) probabilistic membership checks.

Implemented with Redis SETBIT/GETBIT and Lua scripts. No Redis modules required -- works on both Redis and Valkey.

ExistenceFilter is a "side-effect field" that does not store a value on the model instance. It maintains a Bloom filter index via on_save() hooks. On query, might_exist() checks the filter; definitely_missing() is its inverse.

False positives are possible (might_exist returns True for an item never added). False negatives are impossible (definitely_missing never returns True for an item that was added).

Parameters:

Name Type Description Default
error_rate

Target false positive rate. Default 0.01 (1%).

required
capacity

Expected number of distinct items. Default 100,000.

required
fingerprint_fn

Callable that takes a model instance and returns a string fingerprint. This is required -- there is no default.

required
Redis Key

$EF:{ClassName}:{field_name} -- single Redis string used as bit array.

hash_version: The hash a missing filter is created with: 1 (default) or 2. An existing filter is always read and written with the hash it was built with, whatever this says.

Hash version (#775): v1 packs similar tokens onto few bits (low-order bits are lost past 2^53 in Lua's doubles), so its false-positive rate is far above error_rate for tokens shaped like the ones it holds; it never gives a false negative. v2 is exact, and marks itself with four bytes after its bit array. v2 is opt-in: pre-#775 code reads and writes every filter with the v1 hash, so a v2 filter gives false negatives to any process still running it. Upgrade every process first, then opt in -- hash_version=2 here for new filters, and Model.rebuild_indexes(bloom_hash_version=2) to convert existing ones (one rebuild at a time per filter, swapped in atomically). hash_version() says which one a filter is, and check_indexes() lists v1 filters under legacy_hash.

Example

class Memory(Model): topic = Field(type=str) bloom = ExistenceFilter( error_rate=0.01, capacity=100_000, fingerprint_fn=lambda inst: inst.topic, )

memory = Memory(topic="kubernetes") memory.save()

Memory.bloom.might_exist(Memory, "kubernetes") # True Memory.bloom.definitely_missing(Memory, "new-topic") # True

Source code in src/popoto/fields/existence_filter.py
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
class ExistenceFilter(Field):
    """Bloom filter for O(1) probabilistic membership checks.

    Implemented with Redis SETBIT/GETBIT and Lua scripts.
    No Redis modules required -- works on both Redis and Valkey.

    ExistenceFilter is a "side-effect field" that does not store a value on the
    model instance. It maintains a Bloom filter index via on_save() hooks. On
    query, might_exist() checks the filter; definitely_missing() is its inverse.

    False positives are possible (might_exist returns True for an item never
    added). False negatives are impossible (definitely_missing never returns
    True for an item that was added).

    Args:
        error_rate: Target false positive rate. Default 0.01 (1%).
        capacity: Expected number of distinct items. Default 100,000.
        fingerprint_fn: Callable that takes a model instance and returns a
            string fingerprint. This is required -- there is no default.

    Redis Key:
        ``$EF:{ClassName}:{field_name}`` -- single Redis string used as bit array.

        hash_version: The hash a *missing* filter is created with: ``1``
            (default) or ``2``. An existing filter is always read and written
            with the hash it was built with, whatever this says.

    Hash version (#775):
        v1 packs similar tokens onto few bits (low-order bits are lost past
        2^53 in Lua's doubles), so its false-positive rate is far above
        ``error_rate`` for tokens shaped like the ones it holds; it never
        gives a false negative. v2 is exact, and marks itself with four bytes
        after its bit array. **v2 is opt-in**: pre-#775 code reads and writes
        every filter with the v1 hash, so a v2 filter gives false negatives
        to any process still running it. Upgrade every process first, then
        opt in -- ``hash_version=2`` here for new filters, and
        ``Model.rebuild_indexes(bloom_hash_version=2)`` to convert existing
        ones (one rebuild at a time per filter, swapped in atomically).
        ``hash_version()`` says which one a filter is, and
        ``check_indexes()`` lists v1 filters under ``legacy_hash``.

    Example:
        class Memory(Model):
            topic = Field(type=str)
            bloom = ExistenceFilter(
                error_rate=0.01,
                capacity=100_000,
                fingerprint_fn=lambda inst: inst.topic,
            )

        memory = Memory(topic="kubernetes")
        memory.save()

        Memory.bloom.might_exist(Memory, "kubernetes")  # True
        Memory.bloom.definitely_missing(Memory, "new-topic")  # True
    """

    # Override Field defaults -- ExistenceFilter does not store a value
    type: type = str
    null: bool = True
    default = None

    # Export/import: the bit array is deliberately NOT carried, and #556
    # settled that as a permanent contract rather than pending work. A bit is
    # not decomposable to a record: hash collisions mean several records set
    # the same bit, which is exactly why on_delete() is a no-op here. But
    # unlike the mutation stream, the destination does not need the source's
    # array -- importing a record calls on_save(), which sets that record's
    # own bits. A filter rebuilt over the imported set is *more* accurate
    # than a carried one, because it carries no bits for records that were
    # never imported. Rebuild is the better answer, not the fallback.
    roundtrip_policy: str = "partial"
    roundtrip_note: str = (
        "Bloom filter bits are not carried; the destination's filter is "
        "rebuilt by the imported records' own saves, which is more accurate "
        "than carrying bits set by records outside the export. Permanent "
        "contract, not pending work."
    )

    def __init__(self, **kwargs):
        self.error_rate = kwargs.pop("error_rate", 0.01)
        self.capacity = kwargs.pop("capacity", 100_000)
        self.fingerprint_fn = kwargs.pop("fingerprint_fn", None)
        # Stored under another name: ``hash_version`` is the method that
        # reports an existing filter's version.
        self.new_filter_hash_version = kwargs.pop(
            "hash_version", BLOOM_DEFAULT_HASH_VERSION
        )
        if self.new_filter_hash_version not in BLOOM_HASH_VERSIONS:
            raise ValueError(
                f"ExistenceFilter hash_version must be one of "
                f"{BLOOM_HASH_VERSIONS}, got {self.new_filter_hash_version!r}"
            )
        # Do not pass our custom kwargs to Field.__init__
        super().__init__(**kwargs)

    def _compute_params(self):
        """Derive Bloom filter parameters from error_rate and capacity.

        Returns:
            Tuple of (m, k) where m is total bits and k is number of hash functions.
        """
        # m = -capacity * ln(error_rate) / (ln(2)^2)
        m = int(-self.capacity * math.log(self.error_rate) / (math.log(2) ** 2))
        # k = (m / capacity) * ln(2)
        k = max(1, int((m / self.capacity) * math.log(2)))
        return m, k

    def _compute_fingerprint(self, model_instance):
        """Compute fingerprint string from a model instance.

        Delegates to the module-level _compute_fingerprint_impl helper.
        """
        return _compute_fingerprint_impl(self, model_instance)

    def _bloom_key(self, model_instance):
        """Build the Redis key for this Bloom filter.

        Returns:
            str: Key like ``$EF:{ClassName}:{field_name}``.
        """
        class_name = type(model_instance).__name__
        return f"$EF:{class_name}:{self.name}"

    def _class_bloom_key(self, model_class: Any) -> str:
        """``$EF:{ClassName}:{field_name}`` from the model class."""
        return f"$EF:{model_class.__name__}:{self.name}"  # type: ignore[attr-defined]

    def hash_version(self, model_class: Any) -> "int | None":
        """The hash version this field's Redis filter is built with (#775).

        ``2`` for a v2 filter, ``1`` for a v1 one (every filter built before
        #775, and every filter created since unless the field opts in with
        ``hash_version=2``), ``None`` when the filter does not exist yet.
        Always ``None`` off Redis: Postgres keeps an exact token table, not a
        bit array, so it has no hash to version.
        """
        if _search_backend(model_class) is not None:
            return None
        key = self._class_bloom_key(model_class)
        m, _k = self._compute_params()
        client = get_REDIS_DB()
        hb = bloom_header_offset(m)
        if client.getrange(key, hb, hb + len(BLOOM_V2_HEADER) - 1) == BLOOM_V2_HEADER:
            return 2
        return 1 if client.exists(key) else None

    def _rebuild_lock_key(self, model_class: Any) -> str:
        """``$EF:{Class}:{field}:rebuild``: the v2 rebuild's lock."""
        return self._class_bloom_key(model_class) + BLOOM_REBUILD_SUFFIX

    def _rebuild_staging_key(self, model_class: Any) -> str:
        """``$EF:{Class}:{field}:rebuild:staging``: the v2 filter a rebuild
        is filling. Owned by whichever token the lock holds."""
        return self._class_bloom_key(model_class) + BLOOM_REBUILD_STAGING_SUFFIX

    def _rebuild_keys(self, model_class: Any) -> "tuple[str, str, str]":
        """``KEYS`` for every rebuild script: filter, lock, staging key."""
        return (
            self._class_bloom_key(model_class),
            self._rebuild_lock_key(model_class),
            self._rebuild_staging_key(model_class),
        )

    def _begin_v2_rebuild(self, model_class: Any) -> "str | None":
        """Take this filter's v2 rebuild lock and open its staging key.

        Returns this rebuild's token, or ``None`` when the filter is already
        v2 and needs no conversion. The caller re-saves every record (which
        dual-writes v2 bits into the staging key, as does every save racing
        the rebuild), keeps the lock renewed with :meth:`_renew_v2_rebuild`
        (``Model.rebuild_indexes`` does it from a :class:`BloomLockRenewer`
        thread), then calls :meth:`_finish_v2_rebuild` -- or
        :meth:`_abort_v2_rebuild`.

        A missing filter is converted too: the rebuild creates it as v2.
        A staging key a dead rebuild left is deleted in the same atomic step
        that takes the lock.

        Raises:
            BloomRebuildInProgressError: another rebuild holds the lock.
                Nothing has been changed.
        """
        if self.hash_version(model_class) == 2:
            return None
        import uuid

        from .constants import Defaults

        lock = self._rebuild_lock_key(model_class)
        token = uuid.uuid4().hex
        m, _k = self._compute_params()
        got = run_lua(
            get_REDIS_DB(),
            BLOOM_REBUILD_BEGIN_LUA,
            3,
            *self._rebuild_keys(model_class),
            token,
            m,
            Defaults.BLOOM_REBUILD_LOCK_TTL_MS,
        )
        if int(got[0]) != 1:
            holder = got[1].decode() if isinstance(got[1], bytes) else got[1]
            raise BloomRebuildInProgressError(lock, holder or None, int(got[2]))
        return token

    def _renew_v2_rebuild(self, model_class: Any, token: str) -> bool:
        """Extend the lock and staging key; ``False`` once the lock is lost."""
        from .constants import Defaults

        renewed = run_lua(
            get_REDIS_DB(),
            BLOOM_REBUILD_RENEW_LUA,
            3,
            *self._rebuild_keys(model_class),
            token,
            Defaults.BLOOM_REBUILD_LOCK_TTL_MS,
        )
        return int(renewed) == 1

    def _finish_v2_rebuild(self, model_class: Any, token: str) -> None:
        """Swap the finished v2 staging key over the live filter.

        One Lua compare-and-rename: the swap happens only while ``token``
        still holds the lock. Readers see the complete old filter up to that
        step and the complete v2 filter from it on.

        Raises:
            BloomRebuildLostLockError: the lock lapsed or passed to another
                rebuild; the live filter is untouched, and so is the staging
                key of any rebuild that took the lock over.
        """
        m, _k = self._compute_params()
        swapped = run_lua(
            get_REDIS_DB(),
            BLOOM_REBUILD_SWAP_LUA,
            3,
            *self._rebuild_keys(model_class),
            token,
            m,
        )
        if int(swapped) != 1:
            self._refuse_v2_swap(model_class, token)

    def _refuse_v2_swap(self, model_class: Any, token: str) -> None:
        """Abandon this rebuild and raise ``BloomRebuildLostLockError``."""
        from .constants import Defaults

        self._abort_v2_rebuild(model_class, token)
        raise BloomRebuildLostLockError(
            f"{self._rebuild_lock_key(model_class)}: this rebuild no longer "
            f"held the lock at its swap (it went "
            f"{Defaults.BLOOM_REBUILD_LOCK_TTL_MS} ms without renewal, or its "
            f"staging key was removed), so its v2 filter was discarded. The "
            f"live filter is unchanged and complete for every token it held. "
            f"Rerun the rebuild."
        )

    def _abort_v2_rebuild(self, model_class: Any, token: str) -> None:
        """Release the lock and drop the staging key, if ``token`` still
        holds the lock (or nobody does). Never touches another rebuild's."""
        run_lua(
            get_REDIS_DB(),
            BLOOM_REBUILD_ABORT_LUA,
            3,
            *self._rebuild_keys(model_class),
            token,
        )

    def stale_rebuild_staging(self, model_class: Any) -> "list[str]":
        """``[staging key]`` when a staging key exists with no lock -- left
        by a rebuild that died -- else ``[]``; ``check_indexes()`` lists it.
        Nothing reads it, no save writes it (saves write it only under a
        lock), it expires on its own, and the next v2 rebuild of this filter
        deletes it. Two ``EXISTS`` in one ``MULTI``, no keyspace scan.
        Always ``[]`` off Redis."""
        if _search_backend(model_class) is not None:
            return []
        staging = self._rebuild_staging_key(model_class)
        pipe = get_REDIS_DB().pipeline(transaction=True)
        pipe.exists(staging)
        pipe.exists(self._rebuild_lock_key(model_class))
        has_staging, has_lock = pipe.execute()
        return [staging] if has_staging and not has_lock else []

    @classmethod
    def on_save(
        cls,
        model_instance,
        field_name,
        field_value,
        pipeline=None,
        **kwargs,
    ):
        """Add the model instance's fingerprint tokens to the Bloom filter.

        Called automatically by Model.save() for each field. Computes the
        fingerprint, tokenizes it into individual words, and runs
        BLOOM_ADD_MULTI_LUA to set bits for each token. If tokenization
        produces no tokens, falls back to adding the raw fingerprint.

        Args:
            model_instance: The model instance being saved.
            field_name: Name of this field on the model.
            field_value: Current field value (unused -- ExistenceFilter is side-effect only).
            pipeline: Optional Redis pipeline for batch operations.
            **kwargs: Additional context.

        Returns:
            The pipeline if provided, otherwise the Lua script result.
        """
        field = model_instance._meta.fields[field_name]
        fingerprint = field._compute_fingerprint(model_instance)
        key = field._bloom_key(model_instance)
        lock = key + BLOOM_REBUILD_SUFFIX
        staging = key + BLOOM_REBUILD_STAGING_SUFFIX
        m, k = field._compute_params()
        client = (
            pipeline if isinstance(pipeline, redis.client.Pipeline) else get_REDIS_DB()
        )
        if field.new_filter_hash_version == 2:
            add_one, add_multi = BLOOM_ADD_V2_LUA, BLOOM_ADD_MULTI_V2_LUA
        else:
            add_one, add_multi = BLOOM_ADD_LUA, BLOOM_ADD_MULTI_LUA
        tokens = tokenize(fingerprint)
        if not tokens:
            # Fallback: add the raw fingerprint lowercased (handles empty strings,
            # short tokens, redis keys, etc.)
            run_lua(client, add_one, 3, key, lock, staging, fingerprint.lower(), m, k)
        else:
            run_lua(client, add_multi, 3, key, lock, staging, m, k, *tokens)
        return pipeline if pipeline else None

    @classmethod
    def on_delete(
        cls,
        model_instance,
        field_name,
        field_value,
        pipeline=None,
        **kwargs,
    ):
        """No-op. Bloom filters do not support removal by design.

        Bloom filters guarantee zero false negatives. Removing items would
        violate this guarantee because multiple items may share bit positions.
        Stale positives are harmless for a pre-filter use case.

        Returns:
            The pipeline if provided, otherwise None.
        """
        return pipeline if pipeline else None

    def might_exist(self, model_class, fingerprint):
        """Check if a fingerprint might exist in the Bloom filter.

        The query is tokenized using the same rules as on_save(). If the query
        produces tokens, returns True if ANY token is found in the filter.
        If tokenization produces no tokens, checks the raw lowercased query
        (matching the on_save fallback behavior).

        Returns True if the fingerprint is possibly in the set (may be a false
        positive). Returns False if the fingerprint is definitely not in the set
        (guaranteed correct).

        Args:
            model_class: The Model class to check against.
            fingerprint: The fingerprint string to look up.

        Returns:
            bool: True if possibly present, False if definitely absent.
        """
        backend = _search_backend(model_class)
        if backend is not None:
            return backend.membership_query(
                model_class._meta.spec,
                self.name,  # type: ignore[attr-defined]
                _query_tokens(fingerprint),
                mode="any",
            )
        key = f"$EF:{model_class.__name__}:{self.name}"
        m, k = self._compute_params()
        query_str = str(fingerprint)
        tokens = tokenize(query_str)
        if not tokens:
            # Fallback: check the raw lowercased query (matches on_save fallback)
            result = run_lua(
                get_REDIS_DB(), BLOOM_EXISTS_LUA, 1, key, query_str.lower(), m, k
            )
            return bool(result)
        # Check if ANY token is in the bloom filter
        for token in tokens:
            result = run_lua(get_REDIS_DB(), BLOOM_EXISTS_LUA, 1, key, token, m, k)
            if bool(result):
                return True
        return False

    def definitely_missing(self, model_class, fingerprint):
        """Check if a fingerprint is definitely not in the Bloom filter.

        Convenience inverse of might_exist(). When this returns True, the caller
        can skip expensive retrieval entirely.

        Args:
            model_class: The Model class to check against.
            fingerprint: The fingerprint string to look up.

        Returns:
            bool: True if definitely absent, False if possibly present.
        """
        return not self.might_exist(model_class, fingerprint)

    def fill_ratio(self, model_class):
        """Diagnostic: compute the proportion of set bits in the Bloom filter.

        Useful for monitoring capacity usage. When fill_ratio approaches 0.5,
        the false positive rate starts degrading beyond the configured error_rate.

        Args:
            model_class: The Model class whose Bloom filter to inspect.

        Returns:
            float: Ratio of set bits to total bits (0.0 to 1.0).
                Returns 0.0 if the Bloom filter key doesn't exist yet.
        """
        m, k = self._compute_params()
        backend = _search_backend(model_class)
        if backend is not None:
            # Postgres has no bit array. Report the fill a bloom of these
            # parameters would have after the distinct tokens actually stored,
            # 1 - e^(-k n / m): the same capacity signal, 0.0 when empty.
            n = backend.membership_size(model_class._meta.spec, self.name)  # type: ignore[attr-defined]
            return 1.0 - math.exp(-k * n / m) if m > 0 else 0.0
        if m <= 0:
            return 0.0
        key = f"$EF:{model_class.__name__}:{self.name}"
        # Count only the bit array, bytes [0, ceil(m/8)): a v2 filter's
        # version marker follows it and is not filter state. A v1 filter's
        # string never reaches that offset, so the range is all of it.
        set_bits = get_REDIS_DB().bitcount(key, 0, bloom_header_offset(m) - 1)
        return set_bits / m

    def might_exist_batch(self, model_class, fingerprints):
        """Check multiple fingerprints against the Bloom filter in one round-trip.

        Each fingerprint is tokenized using the same rules as might_exist().
        A fingerprint is considered a hit if ANY of its tokens is found in the
        filter. Uses a single Lua EVAL call for all tokens, then maps results
        back to the original fingerprints.

        Args:
            model_class: The Model class to check against.
            fingerprints: List of fingerprint strings to check.

        Returns:
            dict[str, bool]: Mapping of fingerprint -> might_exist result.
                Returns empty dict for empty input list.
        """
        if not fingerprints:
            return {}

        key = f"$EF:{model_class.__name__}:{self.name}"
        m, k = self._compute_params()

        # Tokenize each fingerprint and build a flat token list with a mapping
        # back to the original fingerprint.
        all_tokens = []
        # Maps: token index in all_tokens -> list of fingerprint strings
        token_to_fingerprints = []
        fingerprint_order = []
        seen_fingerprints = set()

        for fp in fingerprints:
            if fp in seen_fingerprints:
                continue
            seen_fingerprints.add(fp)
            fingerprint_order.append(fp)

            query_str = str(fp)
            tokens = tokenize(query_str)
            if not tokens:
                # Fallback: use raw lowercased query (matches might_exist behavior)
                tokens = [query_str.lower()]

            for token in tokens:
                all_tokens.append(token)
                token_to_fingerprints.append(fp)

        if not all_tokens:
            return {fp: False for fp in fingerprint_order}

        backend = _search_backend(model_class)
        if backend is not None:
            # Postgres: one exact lookup for every token.
            raw_results = backend.membership_query(
                model_class._meta.spec, self.name, all_tokens, mode="each"  # type: ignore[attr-defined]
            )
        else:
            # Single Lua EVAL for all tokens
            raw_results = run_lua(
                get_REDIS_DB(), BLOOM_EXISTS_BATCH_LUA, 1, key, m, k, *all_tokens
            )

        # Map token results back to fingerprints (ANY token hit = fingerprint hit)
        result = {fp: False for fp in fingerprint_order}
        for i, token_result in enumerate(raw_results):
            if bool(token_result):
                result[token_to_fingerprints[i]] = True

        return result

    def might_exist_count(self, model_class, fingerprints):
        """Count how many fingerprints might exist in a single round-trip.

        Convenience wrapper around might_exist_batch(). Returns the number
        of fingerprints for which might_exist would return True.

        Args:
            model_class: The Model class to check against.
            fingerprints: List of fingerprint strings to check.

        Returns:
            int: Number of fingerprints that might exist.
        """
        batch_result = self.might_exist_batch(model_class, fingerprints)
        return sum(1 for v in batch_result.values() if v)

hash_version(model_class)

The hash version this field's Redis filter is built with (#775).

2 for a v2 filter, 1 for a v1 one (every filter built before

775, and every filter created since unless the field opts in with

hash_version=2), None when the filter does not exist yet. Always None off Redis: Postgres keeps an exact token table, not a bit array, so it has no hash to version.

Source code in src/popoto/fields/existence_filter.py
def hash_version(self, model_class: Any) -> "int | None":
    """The hash version this field's Redis filter is built with (#775).

    ``2`` for a v2 filter, ``1`` for a v1 one (every filter built before
    #775, and every filter created since unless the field opts in with
    ``hash_version=2``), ``None`` when the filter does not exist yet.
    Always ``None`` off Redis: Postgres keeps an exact token table, not a
    bit array, so it has no hash to version.
    """
    if _search_backend(model_class) is not None:
        return None
    key = self._class_bloom_key(model_class)
    m, _k = self._compute_params()
    client = get_REDIS_DB()
    hb = bloom_header_offset(m)
    if client.getrange(key, hb, hb + len(BLOOM_V2_HEADER) - 1) == BLOOM_V2_HEADER:
        return 2
    return 1 if client.exists(key) else None

stale_rebuild_staging(model_class)

[staging key] when a staging key exists with no lock -- left by a rebuild that died -- else []; check_indexes() lists it. Nothing reads it, no save writes it (saves write it only under a lock), it expires on its own, and the next v2 rebuild of this filter deletes it. Two EXISTS in one MULTI, no keyspace scan. Always [] off Redis.

Source code in src/popoto/fields/existence_filter.py
def stale_rebuild_staging(self, model_class: Any) -> "list[str]":
    """``[staging key]`` when a staging key exists with no lock -- left
    by a rebuild that died -- else ``[]``; ``check_indexes()`` lists it.
    Nothing reads it, no save writes it (saves write it only under a
    lock), it expires on its own, and the next v2 rebuild of this filter
    deletes it. Two ``EXISTS`` in one ``MULTI``, no keyspace scan.
    Always ``[]`` off Redis."""
    if _search_backend(model_class) is not None:
        return []
    staging = self._rebuild_staging_key(model_class)
    pipe = get_REDIS_DB().pipeline(transaction=True)
    pipe.exists(staging)
    pipe.exists(self._rebuild_lock_key(model_class))
    has_staging, has_lock = pipe.execute()
    return [staging] if has_staging and not has_lock else []

on_save(model_instance, field_name, field_value, pipeline=None, **kwargs) classmethod

Add the model instance's fingerprint tokens to the Bloom filter.

Called automatically by Model.save() for each field. Computes the fingerprint, tokenizes it into individual words, and runs BLOOM_ADD_MULTI_LUA to set bits for each token. If tokenization produces no tokens, falls back to adding the raw fingerprint.

Parameters:

Name Type Description Default
model_instance

The model instance being saved.

required
field_name

Name of this field on the model.

required
field_value

Current field value (unused -- ExistenceFilter is side-effect only).

required
pipeline

Optional Redis pipeline for batch operations.

None
**kwargs

Additional context.

{}

Returns:

Type Description

The pipeline if provided, otherwise the Lua script result.

Source code in src/popoto/fields/existence_filter.py
@classmethod
def on_save(
    cls,
    model_instance,
    field_name,
    field_value,
    pipeline=None,
    **kwargs,
):
    """Add the model instance's fingerprint tokens to the Bloom filter.

    Called automatically by Model.save() for each field. Computes the
    fingerprint, tokenizes it into individual words, and runs
    BLOOM_ADD_MULTI_LUA to set bits for each token. If tokenization
    produces no tokens, falls back to adding the raw fingerprint.

    Args:
        model_instance: The model instance being saved.
        field_name: Name of this field on the model.
        field_value: Current field value (unused -- ExistenceFilter is side-effect only).
        pipeline: Optional Redis pipeline for batch operations.
        **kwargs: Additional context.

    Returns:
        The pipeline if provided, otherwise the Lua script result.
    """
    field = model_instance._meta.fields[field_name]
    fingerprint = field._compute_fingerprint(model_instance)
    key = field._bloom_key(model_instance)
    lock = key + BLOOM_REBUILD_SUFFIX
    staging = key + BLOOM_REBUILD_STAGING_SUFFIX
    m, k = field._compute_params()
    client = (
        pipeline if isinstance(pipeline, redis.client.Pipeline) else get_REDIS_DB()
    )
    if field.new_filter_hash_version == 2:
        add_one, add_multi = BLOOM_ADD_V2_LUA, BLOOM_ADD_MULTI_V2_LUA
    else:
        add_one, add_multi = BLOOM_ADD_LUA, BLOOM_ADD_MULTI_LUA
    tokens = tokenize(fingerprint)
    if not tokens:
        # Fallback: add the raw fingerprint lowercased (handles empty strings,
        # short tokens, redis keys, etc.)
        run_lua(client, add_one, 3, key, lock, staging, fingerprint.lower(), m, k)
    else:
        run_lua(client, add_multi, 3, key, lock, staging, m, k, *tokens)
    return pipeline if pipeline else None

on_delete(model_instance, field_name, field_value, pipeline=None, **kwargs) classmethod

No-op. Bloom filters do not support removal by design.

Bloom filters guarantee zero false negatives. Removing items would violate this guarantee because multiple items may share bit positions. Stale positives are harmless for a pre-filter use case.

Returns:

Type Description

The pipeline if provided, otherwise None.

Source code in src/popoto/fields/existence_filter.py
@classmethod
def on_delete(
    cls,
    model_instance,
    field_name,
    field_value,
    pipeline=None,
    **kwargs,
):
    """No-op. Bloom filters do not support removal by design.

    Bloom filters guarantee zero false negatives. Removing items would
    violate this guarantee because multiple items may share bit positions.
    Stale positives are harmless for a pre-filter use case.

    Returns:
        The pipeline if provided, otherwise None.
    """
    return pipeline if pipeline else None

might_exist(model_class, fingerprint)

Check if a fingerprint might exist in the Bloom filter.

The query is tokenized using the same rules as on_save(). If the query produces tokens, returns True if ANY token is found in the filter. If tokenization produces no tokens, checks the raw lowercased query (matching the on_save fallback behavior).

Returns True if the fingerprint is possibly in the set (may be a false positive). Returns False if the fingerprint is definitely not in the set (guaranteed correct).

Parameters:

Name Type Description Default
model_class

The Model class to check against.

required
fingerprint

The fingerprint string to look up.

required

Returns:

Name Type Description
bool

True if possibly present, False if definitely absent.

Source code in src/popoto/fields/existence_filter.py
def might_exist(self, model_class, fingerprint):
    """Check if a fingerprint might exist in the Bloom filter.

    The query is tokenized using the same rules as on_save(). If the query
    produces tokens, returns True if ANY token is found in the filter.
    If tokenization produces no tokens, checks the raw lowercased query
    (matching the on_save fallback behavior).

    Returns True if the fingerprint is possibly in the set (may be a false
    positive). Returns False if the fingerprint is definitely not in the set
    (guaranteed correct).

    Args:
        model_class: The Model class to check against.
        fingerprint: The fingerprint string to look up.

    Returns:
        bool: True if possibly present, False if definitely absent.
    """
    backend = _search_backend(model_class)
    if backend is not None:
        return backend.membership_query(
            model_class._meta.spec,
            self.name,  # type: ignore[attr-defined]
            _query_tokens(fingerprint),
            mode="any",
        )
    key = f"$EF:{model_class.__name__}:{self.name}"
    m, k = self._compute_params()
    query_str = str(fingerprint)
    tokens = tokenize(query_str)
    if not tokens:
        # Fallback: check the raw lowercased query (matches on_save fallback)
        result = run_lua(
            get_REDIS_DB(), BLOOM_EXISTS_LUA, 1, key, query_str.lower(), m, k
        )
        return bool(result)
    # Check if ANY token is in the bloom filter
    for token in tokens:
        result = run_lua(get_REDIS_DB(), BLOOM_EXISTS_LUA, 1, key, token, m, k)
        if bool(result):
            return True
    return False

definitely_missing(model_class, fingerprint)

Check if a fingerprint is definitely not in the Bloom filter.

Convenience inverse of might_exist(). When this returns True, the caller can skip expensive retrieval entirely.

Parameters:

Name Type Description Default
model_class

The Model class to check against.

required
fingerprint

The fingerprint string to look up.

required

Returns:

Name Type Description
bool

True if definitely absent, False if possibly present.

Source code in src/popoto/fields/existence_filter.py
def definitely_missing(self, model_class, fingerprint):
    """Check if a fingerprint is definitely not in the Bloom filter.

    Convenience inverse of might_exist(). When this returns True, the caller
    can skip expensive retrieval entirely.

    Args:
        model_class: The Model class to check against.
        fingerprint: The fingerprint string to look up.

    Returns:
        bool: True if definitely absent, False if possibly present.
    """
    return not self.might_exist(model_class, fingerprint)

fill_ratio(model_class)

Diagnostic: compute the proportion of set bits in the Bloom filter.

Useful for monitoring capacity usage. When fill_ratio approaches 0.5, the false positive rate starts degrading beyond the configured error_rate.

Parameters:

Name Type Description Default
model_class

The Model class whose Bloom filter to inspect.

required

Returns:

Name Type Description
float

Ratio of set bits to total bits (0.0 to 1.0). Returns 0.0 if the Bloom filter key doesn't exist yet.

Source code in src/popoto/fields/existence_filter.py
def fill_ratio(self, model_class):
    """Diagnostic: compute the proportion of set bits in the Bloom filter.

    Useful for monitoring capacity usage. When fill_ratio approaches 0.5,
    the false positive rate starts degrading beyond the configured error_rate.

    Args:
        model_class: The Model class whose Bloom filter to inspect.

    Returns:
        float: Ratio of set bits to total bits (0.0 to 1.0).
            Returns 0.0 if the Bloom filter key doesn't exist yet.
    """
    m, k = self._compute_params()
    backend = _search_backend(model_class)
    if backend is not None:
        # Postgres has no bit array. Report the fill a bloom of these
        # parameters would have after the distinct tokens actually stored,
        # 1 - e^(-k n / m): the same capacity signal, 0.0 when empty.
        n = backend.membership_size(model_class._meta.spec, self.name)  # type: ignore[attr-defined]
        return 1.0 - math.exp(-k * n / m) if m > 0 else 0.0
    if m <= 0:
        return 0.0
    key = f"$EF:{model_class.__name__}:{self.name}"
    # Count only the bit array, bytes [0, ceil(m/8)): a v2 filter's
    # version marker follows it and is not filter state. A v1 filter's
    # string never reaches that offset, so the range is all of it.
    set_bits = get_REDIS_DB().bitcount(key, 0, bloom_header_offset(m) - 1)
    return set_bits / m

might_exist_batch(model_class, fingerprints)

Check multiple fingerprints against the Bloom filter in one round-trip.

Each fingerprint is tokenized using the same rules as might_exist(). A fingerprint is considered a hit if ANY of its tokens is found in the filter. Uses a single Lua EVAL call for all tokens, then maps results back to the original fingerprints.

Parameters:

Name Type Description Default
model_class

The Model class to check against.

required
fingerprints

List of fingerprint strings to check.

required

Returns:

Type Description

dict[str, bool]: Mapping of fingerprint -> might_exist result. Returns empty dict for empty input list.

Source code in src/popoto/fields/existence_filter.py
def might_exist_batch(self, model_class, fingerprints):
    """Check multiple fingerprints against the Bloom filter in one round-trip.

    Each fingerprint is tokenized using the same rules as might_exist().
    A fingerprint is considered a hit if ANY of its tokens is found in the
    filter. Uses a single Lua EVAL call for all tokens, then maps results
    back to the original fingerprints.

    Args:
        model_class: The Model class to check against.
        fingerprints: List of fingerprint strings to check.

    Returns:
        dict[str, bool]: Mapping of fingerprint -> might_exist result.
            Returns empty dict for empty input list.
    """
    if not fingerprints:
        return {}

    key = f"$EF:{model_class.__name__}:{self.name}"
    m, k = self._compute_params()

    # Tokenize each fingerprint and build a flat token list with a mapping
    # back to the original fingerprint.
    all_tokens = []
    # Maps: token index in all_tokens -> list of fingerprint strings
    token_to_fingerprints = []
    fingerprint_order = []
    seen_fingerprints = set()

    for fp in fingerprints:
        if fp in seen_fingerprints:
            continue
        seen_fingerprints.add(fp)
        fingerprint_order.append(fp)

        query_str = str(fp)
        tokens = tokenize(query_str)
        if not tokens:
            # Fallback: use raw lowercased query (matches might_exist behavior)
            tokens = [query_str.lower()]

        for token in tokens:
            all_tokens.append(token)
            token_to_fingerprints.append(fp)

    if not all_tokens:
        return {fp: False for fp in fingerprint_order}

    backend = _search_backend(model_class)
    if backend is not None:
        # Postgres: one exact lookup for every token.
        raw_results = backend.membership_query(
            model_class._meta.spec, self.name, all_tokens, mode="each"  # type: ignore[attr-defined]
        )
    else:
        # Single Lua EVAL for all tokens
        raw_results = run_lua(
            get_REDIS_DB(), BLOOM_EXISTS_BATCH_LUA, 1, key, m, k, *all_tokens
        )

    # Map token results back to fingerprints (ANY token hit = fingerprint hit)
    result = {fp: False for fp in fingerprint_order}
    for i, token_result in enumerate(raw_results):
        if bool(token_result):
            result[token_to_fingerprints[i]] = True

    return result

might_exist_count(model_class, fingerprints)

Count how many fingerprints might exist in a single round-trip.

Convenience wrapper around might_exist_batch(). Returns the number of fingerprints for which might_exist would return True.

Parameters:

Name Type Description Default
model_class

The Model class to check against.

required
fingerprints

List of fingerprint strings to check.

required

Returns:

Name Type Description
int

Number of fingerprints that might exist.

Source code in src/popoto/fields/existence_filter.py
def might_exist_count(self, model_class, fingerprints):
    """Count how many fingerprints might exist in a single round-trip.

    Convenience wrapper around might_exist_batch(). Returns the number
    of fingerprints for which might_exist would return True.

    Args:
        model_class: The Model class to check against.
        fingerprints: List of fingerprint strings to check.

    Returns:
        int: Number of fingerprints that might exist.
    """
    batch_result = self.might_exist_batch(model_class, fingerprints)
    return sum(1 for v in batch_result.values() if v)

FrequencySketch

Bases: Field

Count-Min Sketch for approximate frequency queries.

Implemented with Redis hashes and Lua scripts. No Redis modules required -- works on both Redis and Valkey.

FrequencySketch is a "side-effect field" that maintains a Count-Min Sketch alongside the model. Each save increments counters for the fingerprint. get_frequency() returns the approximate count.

The Count-Min Sketch may overcount (never undercount). The error bound depends on width and depth parameters.

Parameters:

Name Type Description Default
width

Number of counters per row. Default 2003 (prime, minimises hash collision).

required
depth

Number of hash functions (rows). Default 7.

required
fingerprint_fn

Callable that takes a model instance and returns a string fingerprint. This is required -- there is no default.

required
Redis Key

$FS:{ClassName}:{field_name} -- single Redis hash with row:column field names and integer counter values.

Example

class Memory(Model): topic = Field(type=str) freq = FrequencySketch( fingerprint_fn=lambda inst: inst.topic, )

memory = Memory(topic="kubernetes") memory.save() memory.save() # increment again

Memory.freq.get_frequency(Memory, "kubernetes") # ~2

Source code in src/popoto/fields/existence_filter.py
class FrequencySketch(Field):
    """Count-Min Sketch for approximate frequency queries.

    Implemented with Redis hashes and Lua scripts.
    No Redis modules required -- works on both Redis and Valkey.

    FrequencySketch is a "side-effect field" that maintains a Count-Min Sketch
    alongside the model. Each save increments counters for the fingerprint.
    get_frequency() returns the approximate count.

    The Count-Min Sketch may overcount (never undercount). The error bound
    depends on width and depth parameters.

    Args:
        width: Number of counters per row. Default 2003 (prime, minimises hash collision).
        depth: Number of hash functions (rows). Default 7.
        fingerprint_fn: Callable that takes a model instance and returns a
            string fingerprint. This is required -- there is no default.

    Redis Key:
        ``$FS:{ClassName}:{field_name}`` -- single Redis hash with
        ``row:column`` field names and integer counter values.

    Example:
        class Memory(Model):
            topic = Field(type=str)
            freq = FrequencySketch(
                fingerprint_fn=lambda inst: inst.topic,
            )

        memory = Memory(topic="kubernetes")
        memory.save()
        memory.save()  # increment again

        Memory.freq.get_frequency(Memory, "kubernetes")  # ~2
    """

    # Override Field defaults -- FrequencySketch does not store a value
    MAX_DEPTH = 7
    type: type = str
    null: bool = True
    default = None

    # Export/import: the sketch counters are deliberately NOT carried, and
    # #556 settled that as a permanent contract rather than pending work.
    # A counter is shared by every value that hashes to it, so no record's
    # contribution can be isolated -- the same reason on_delete() is a no-op.
    # What the destination gets instead is a sketch rebuilt from the imported
    # saves: frequencies are lower than the source's, because the source
    # counted saves the destination never received. That is the honest
    # reading -- "how often has this been seen *here*" -- and it is why the
    # counters are not carried rather than merely not yet carried.
    roundtrip_policy: str = "partial"
    roundtrip_note: str = (
        "Count-Min Sketch counters are not carried; the destination's sketch "
        "counts only the saves it observes, so frequencies restart from the "
        "import rather than continuing the source's totals. Permanent "
        "contract, not pending work."
    )

    def __init__(self, **kwargs):
        if "hash_version" in kwargs:
            # Field.__init__ ignores keywords it does not know, so without
            # this an ExistenceFilter argument passed here by analogy would
            # construct silently and do nothing.
            raise TypeError(
                "FrequencySketch has no hash_version argument: the bloom hash "
                "versions (#775) apply to ExistenceFilter only"
            )
        self.width = kwargs.pop("width", 2003)
        self.depth = kwargs.pop("depth", 7)
        self.fingerprint_fn = kwargs.pop("fingerprint_fn", None)
        super().__init__(**kwargs)
        if not (1 <= self.depth <= self.MAX_DEPTH):
            raise ValueError(
                f"FrequencySketch depth must be between 1 and {self.MAX_DEPTH}, got {self.depth}. "
                f"The P/M hash tables have {self.MAX_DEPTH} entries."
            )

    def _compute_fingerprint(self, model_instance):
        """Compute fingerprint string from a model instance.

        Delegates to the module-level _compute_fingerprint_impl helper.
        """
        return _compute_fingerprint_impl(self, model_instance)

    def _cms_key(self, model_instance):
        """Build the Redis key for this Count-Min Sketch.

        Returns:
            str: Key like ``$FS:{ClassName}:{field_name}``.
        """
        class_name = type(model_instance).__name__
        return f"$FS:{class_name}:{self.name}"

    @classmethod
    def on_save(
        cls,
        model_instance,
        field_name,
        field_value,
        pipeline=None,
        **kwargs,
    ):
        """Increment the Count-Min Sketch counters for this instance's fingerprint tokens.

        Called automatically by Model.save() for each field. Tokenizes the
        fingerprint and increments counters for each token individually.
        If tokenization produces no tokens, falls back to the raw fingerprint.

        Args:
            model_instance: The model instance being saved.
            field_name: Name of this field on the model.
            field_value: Current field value (unused).
            pipeline: Optional Redis pipeline for batch operations.
            **kwargs: Additional context.

        Returns:
            The pipeline if provided, otherwise the Lua script result.
        """
        field = model_instance._meta.fields[field_name]
        fingerprint = field._compute_fingerprint(model_instance)
        key = field._cms_key(model_instance)
        client = (
            pipeline if isinstance(pipeline, redis.client.Pipeline) else get_REDIS_DB()
        )
        tokens = tokenize(fingerprint)
        if not tokens:
            # Fallback: increment the raw fingerprint lowercased
            run_lua(
                client,
                CMS_INCR_LUA,
                1,
                key,
                fingerprint.lower(),
                field.width,
                field.depth,
            )
        else:
            run_lua(
                client, CMS_INCR_MULTI_LUA, 1, key, field.width, field.depth, *tokens
            )
        return pipeline if pipeline else None

    @classmethod
    def on_delete(
        cls,
        model_instance,
        field_name,
        field_value,
        pipeline=None,
        **kwargs,
    ):
        """No-op. Count-Min Sketch does not support decrement.

        CMS counters are monotonically increasing. Decrementing would
        violate the "never undercount" guarantee.

        Returns:
            The pipeline if provided, otherwise None.
        """
        return pipeline if pipeline else None

    def get_frequency(self, model_class, fingerprint):
        """Query the approximate frequency of a fingerprint.

        The query is tokenized using the same rules as on_save(). If the query
        produces tokens, returns the minimum frequency across those tokens
        (conservative estimate). If tokenization produces no tokens, queries
        the raw lowercased fingerprint (matching the on_save fallback).

        Returns the Count-Min Sketch estimate. This value may overcount
        but never undercounts.

        Args:
            model_class: The Model class to query against.
            fingerprint: The fingerprint string to look up.

        Returns:
            int: Approximate frequency count. Returns 0 if the fingerprint
                has never been seen or the CMS key doesn't exist yet.
        """
        backend = _search_backend(model_class)
        if backend is not None:
            counts = backend.membership_query(
                model_class._meta.spec,
                self.name,  # type: ignore[attr-defined]
                _query_tokens(fingerprint),
                mode="count",
            )
            return min(counts) if counts else 0
        key = f"$FS:{model_class.__name__}:{self.name}"
        query_str = str(fingerprint)
        tokens = tokenize(query_str)
        if not tokens:
            # Fallback: query the raw lowercased fingerprint
            result = run_lua(
                get_REDIS_DB(),
                CMS_QUERY_LUA,
                1,
                key,
                query_str.lower(),
                self.width,
                self.depth,
            )
            return int(result) if result else 0
        # For multi-token queries, return min frequency (conservative)
        min_freq = None
        for token in tokens:
            result = run_lua(
                get_REDIS_DB(), CMS_QUERY_LUA, 1, key, token, self.width, self.depth
            )
            freq = int(result) if result else 0
            if min_freq is None or freq < min_freq:
                min_freq = freq
        return min_freq if min_freq is not None else 0

on_save(model_instance, field_name, field_value, pipeline=None, **kwargs) classmethod

Increment the Count-Min Sketch counters for this instance's fingerprint tokens.

Called automatically by Model.save() for each field. Tokenizes the fingerprint and increments counters for each token individually. If tokenization produces no tokens, falls back to the raw fingerprint.

Parameters:

Name Type Description Default
model_instance

The model instance being saved.

required
field_name

Name of this field on the model.

required
field_value

Current field value (unused).

required
pipeline

Optional Redis pipeline for batch operations.

None
**kwargs

Additional context.

{}

Returns:

Type Description

The pipeline if provided, otherwise the Lua script result.

Source code in src/popoto/fields/existence_filter.py
@classmethod
def on_save(
    cls,
    model_instance,
    field_name,
    field_value,
    pipeline=None,
    **kwargs,
):
    """Increment the Count-Min Sketch counters for this instance's fingerprint tokens.

    Called automatically by Model.save() for each field. Tokenizes the
    fingerprint and increments counters for each token individually.
    If tokenization produces no tokens, falls back to the raw fingerprint.

    Args:
        model_instance: The model instance being saved.
        field_name: Name of this field on the model.
        field_value: Current field value (unused).
        pipeline: Optional Redis pipeline for batch operations.
        **kwargs: Additional context.

    Returns:
        The pipeline if provided, otherwise the Lua script result.
    """
    field = model_instance._meta.fields[field_name]
    fingerprint = field._compute_fingerprint(model_instance)
    key = field._cms_key(model_instance)
    client = (
        pipeline if isinstance(pipeline, redis.client.Pipeline) else get_REDIS_DB()
    )
    tokens = tokenize(fingerprint)
    if not tokens:
        # Fallback: increment the raw fingerprint lowercased
        run_lua(
            client,
            CMS_INCR_LUA,
            1,
            key,
            fingerprint.lower(),
            field.width,
            field.depth,
        )
    else:
        run_lua(
            client, CMS_INCR_MULTI_LUA, 1, key, field.width, field.depth, *tokens
        )
    return pipeline if pipeline else None

on_delete(model_instance, field_name, field_value, pipeline=None, **kwargs) classmethod

No-op. Count-Min Sketch does not support decrement.

CMS counters are monotonically increasing. Decrementing would violate the "never undercount" guarantee.

Returns:

Type Description

The pipeline if provided, otherwise None.

Source code in src/popoto/fields/existence_filter.py
@classmethod
def on_delete(
    cls,
    model_instance,
    field_name,
    field_value,
    pipeline=None,
    **kwargs,
):
    """No-op. Count-Min Sketch does not support decrement.

    CMS counters are monotonically increasing. Decrementing would
    violate the "never undercount" guarantee.

    Returns:
        The pipeline if provided, otherwise None.
    """
    return pipeline if pipeline else None

get_frequency(model_class, fingerprint)

Query the approximate frequency of a fingerprint.

The query is tokenized using the same rules as on_save(). If the query produces tokens, returns the minimum frequency across those tokens (conservative estimate). If tokenization produces no tokens, queries the raw lowercased fingerprint (matching the on_save fallback).

Returns the Count-Min Sketch estimate. This value may overcount but never undercounts.

Parameters:

Name Type Description Default
model_class

The Model class to query against.

required
fingerprint

The fingerprint string to look up.

required

Returns:

Name Type Description
int

Approximate frequency count. Returns 0 if the fingerprint has never been seen or the CMS key doesn't exist yet.

Source code in src/popoto/fields/existence_filter.py
def get_frequency(self, model_class, fingerprint):
    """Query the approximate frequency of a fingerprint.

    The query is tokenized using the same rules as on_save(). If the query
    produces tokens, returns the minimum frequency across those tokens
    (conservative estimate). If tokenization produces no tokens, queries
    the raw lowercased fingerprint (matching the on_save fallback).

    Returns the Count-Min Sketch estimate. This value may overcount
    but never undercounts.

    Args:
        model_class: The Model class to query against.
        fingerprint: The fingerprint string to look up.

    Returns:
        int: Approximate frequency count. Returns 0 if the fingerprint
            has never been seen or the CMS key doesn't exist yet.
    """
    backend = _search_backend(model_class)
    if backend is not None:
        counts = backend.membership_query(
            model_class._meta.spec,
            self.name,  # type: ignore[attr-defined]
            _query_tokens(fingerprint),
            mode="count",
        )
        return min(counts) if counts else 0
    key = f"$FS:{model_class.__name__}:{self.name}"
    query_str = str(fingerprint)
    tokens = tokenize(query_str)
    if not tokens:
        # Fallback: query the raw lowercased fingerprint
        result = run_lua(
            get_REDIS_DB(),
            CMS_QUERY_LUA,
            1,
            key,
            query_str.lower(),
            self.width,
            self.depth,
        )
        return int(result) if result else 0
    # For multi-token queries, return min frequency (conservative)
    min_freq = None
    for token in tokens:
        result = run_lua(
            get_REDIS_DB(), CMS_QUERY_LUA, 1, key, token, self.width, self.depth
        )
        freq = int(result) if result else 0
        if min_freq is None or freq < min_freq:
            min_freq = freq
    return min_freq if min_freq is not None else 0

bloom_header_offset(m)

Byte offset of the v2 version marker: the first byte past m bits.

Source code in src/popoto/fields/existence_filter.py
def bloom_header_offset(m: int) -> int:
    """Byte offset of the v2 version marker: the first byte past ``m`` bits."""
    return (m + 7) // 8