path: root/java/com/google/setfilters/cuckoofilter/CuckooFilter.java

// Copyright 2022 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package com.google.setfilters.cuckoofilter;

import com.google.common.hash.Funnel;
import com.google.common.hash.HashCode;
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.Random;

/**
 * A space efficient, probabilistic multiset data structure that supports membership check,
 * insertion, and deletion of the elements.
 *
 * <p>Cuckoo filter enables tradeoffs between its space efficiency and the false positive
 * probability of the membership check.
 *
 * <p>See the original paper https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf for more
 * details.
 *
 * <p>This class is not thread-safe.
 */
public final class CuckooFilter<T> {
  private final CuckooFilterConfig config;
  private final CuckooFilterTable table;
  private final Funnel<? super T> funnel;
  private final Random random;

  /** Counts the total number of elements in the cuckoo filter. */
  private long count;

  /** Instantiates a new cuckoo filter. */
  public static <T> CuckooFilter<T> createNew(CuckooFilterConfig config, Funnel<? super T> funnel) {
    Random random = new Random();
    CuckooFilterTable table =
        CuckooFilterTable.create(config.size(), config.useSpaceOptimization(), random);
    return new CuckooFilter<T>(config, table, funnel, random);
  }

  /**
   * Instantiates a cuckoo filter from serialized cuckoo filter table.
   *
   * <p>Note that {@link SerializedCuckooFilterTable} does not contain any data on {@link
   * CuckooFilterConfig.HashFunction}, {@link CuckooFilterConfig.Strategy}, or {@link Funnel} used,
   * so it is up to the user to supply appropriate hash function, strategy, and funnel that were
   * used to generate the {@link SerializedCuckooFilterTable}.
   */
  public static <T> CuckooFilter<T> createFromSerializedTable(
      SerializedCuckooFilterTable serializedTable,
      CuckooFilterConfig.HashFunction hashFunction,
      CuckooFilterConfig.Strategy strategy,
      Funnel<? super T> funnel) {
    Random random = new Random();
    CuckooFilterTable table = CuckooFilterTable.createFromSerialization(serializedTable, random);
    return new CuckooFilter<T>(
        CuckooFilterConfig.newBuilder()
            .setSize(table.size())
            .setHashFunction(hashFunction)
            .setStrategy(strategy)
            .build(),
        table,
        funnel,
        random);
  }

  private CuckooFilter(
      CuckooFilterConfig config, CuckooFilterTable table, Funnel<? super T> funnel, Random random) {
    this.config = config;
    this.table = table;
    this.funnel = funnel;
    this.random = random;
    count = 0;
  }

  /**
   * Returns true if {@code element} is in the cuckoo filter.
   *
   * <p>By the probabilistic nature of the cuckoo filter data structure, this method may return a
   * false positive result. In other words, this method may incorrectly return true for an element
   * that was actually never inserted. This probability can depend on various factors, including the
   * size of the cuckoo filter and the hash function used.
   *
   * <p>However, it is guaranteed that this method never returns a false negative result, as long as
   * {@code delete} method is called on an element that exists in the filter. Please see {@code
   * delete} method for more details.
   */
  public boolean contains(T element) {
    HashCode hash = config.hashFunction().hash(element, funnel);
    long fingerprint =
        config.strategy().computeFingerprint(hash, config.size().fingerprintLength());
    int bucketIndex = config.strategy().computeBucketIndex(hash, config.size().bucketCount());
    int otherBucketIndex =
        config
            .strategy()
            .computeOtherBucketIndex(
                fingerprint, bucketIndex, config.size().bucketCount(), config.hashFunction());
    return table.contains(bucketIndex, fingerprint)
        || table.contains(otherBucketIndex, fingerprint);
  }

  /**
   * Inserts {@code element} to the cuckoo filter, returning true if the element was inserted
   * successfully.
   *
   * <p>Insertion of {@code element} will fail if there is no room for {@code element}. Note that
   * even when the insertion of {@code element} fails, it is possible for another element to be
   * inserted successfully. Even then, the insertion failure should be a good indicator that the
   * filter is getting close to its maximum capacity.
   */
  public boolean insert(T element) {
    HashCode hash = config.hashFunction().hash(element, funnel);
    long fingerprint =
        config.strategy().computeFingerprint(hash, config.size().fingerprintLength());
    int bucketIndex = config.strategy().computeBucketIndex(hash, config.size().bucketCount());
    int otherBucketIndex =
        config
            .strategy()
            .computeOtherBucketIndex(
                fingerprint, bucketIndex, config.size().bucketCount(), config.hashFunction());

    // First attempt to insert the fingerprint to one of the two assigned buckets.
    if (attemptInsertion(fingerprint, bucketIndex, otherBucketIndex)) {
      count++;
      return true;
    }

    // If both buckets are full, execute insertion with repeated replacements algorithm.
    int startBucketIndex = (random.nextInt(2) == 0) ? bucketIndex : otherBucketIndex;
    boolean inserted = insertWithRepeatedReplacements(fingerprint, startBucketIndex);
    if (inserted) {
      count++;
    }
    return inserted;
  }

  /**
   * Deletes {@code element} from the cuckoo filter, returning true if the element was deleted
   * successfully.
   *
   * <p>It is critical for {@code delete} to be called on an already existing element. Otherwise,
   * the filter may incorrectly delete a wrong element. When this happens, it is possible for {@code
   * contains} method to return a false negative result.
   */
  public boolean delete(T element) {
    HashCode hash = config.hashFunction().hash(element, funnel);
    long fingerprint =
        config.strategy().computeFingerprint(hash, config.size().fingerprintLength());
    int bucketIndex = config.strategy().computeBucketIndex(hash, config.size().bucketCount());
    int otherBucketIndex =
        config
            .strategy()
            .computeOtherBucketIndex(
                fingerprint, bucketIndex, config.size().bucketCount(), config.hashFunction());
    boolean deleted =
        table.delete(bucketIndex, fingerprint) || table.delete(otherBucketIndex, fingerprint);
    if (deleted) {
      count--;
    }
    return deleted;
  }

  /** Returns the size of the cuckoo filter. */
  public CuckooFilterConfig.Size size() {
    return config.size();
  }

  /** Returns the count of the elements in the cuckoo filter. */
  public long count() {
    return count;
  }

  /**
   * Returns the ratio of the total number of elements in the cuckoo filter and the theoretical max
   * capacity.
   *
   * <p>The returned value is in range [0, 1].
   */
  public double load() {
    return count / ((double) config.size().bucketCount() * config.size().bucketCapacity());
  }

  /**
   * Serializes the state of the cuckoo filter table.
   *
   * <p>Note that this method does not serialize hash function, strategy, and funnel. When
   * instantiating a cuckoo filter from the returned {@link SerializedCuckooFilterTable}, it is up
   * to the user to supply appropriate hash function, strategy, and funnel that were used.
   */
  public SerializedCuckooFilterTable serializeTable() {
    return table.serialize();
  }

  /**
   * Attempts to insert {@code fingerprint} to one of the buckets with indices {@code bucketIndex}
   * and {@code otherBucketIndex}, returning true when successful. Returns false if both buckets are
   * full and the insertion failed.
   */
  private boolean attemptInsertion(long fingerprint, int bucketIndex, int otherBucketIndex) {
    if (!table.isFull(bucketIndex)) {
      table.insertWithReplacement(bucketIndex, fingerprint);
      return true;
    }
    if (!table.isFull(otherBucketIndex)) {
      table.insertWithReplacement(otherBucketIndex, fingerprint);
      return true;
    }
    return false;
  }

  /**
   * Randomly traverses the cuckoo graph to find an available bucket for insertion.
   *
   * <p>At a high level, this algorithm starts at vertex {@code bucketIndex} and performs a random
   * walk of length at most {@link CuckooFilterConfig.Strategy#maxReplacementCount}. If an available
   * bucket is found, the algorithm "pushes" all the fingerprints (edges) that are visited (note
   * that in the cuckoo graph, the edges are the fingerprints) to their alternate buckets, and make
   * room for {@code fingerprint} to be inserted.
   *
   * <p>If during the random walk an available bucket is not found, the insertion fails and the
   * method returns false.
   *
   * <p>Note that it is possible to deterministically find an available bucket by performing breadth
   * first search in the cuckoo graph, but this is usually slower and the extra chance of successful
   * insertion is negligibly small in practice.
   */
  private boolean insertWithRepeatedReplacements(long fingerprint, int bucketIndex) {
    List<Integer> visitedBucketIndices = new ArrayList<>();
    List<Long> replacedFingerprints = new ArrayList<>();

    long currFingerprint = fingerprint;
    int currBucketIndex = bucketIndex;
    visitedBucketIndices.add(-1); // Just for index alignment purpose.
    replacedFingerprints.add(currFingerprint);
    for (int i = 0; i < config.strategy().maxReplacementCount(); i++) {
      Optional<Long> replacedFingerprint =
          table.insertWithReplacement(currBucketIndex, currFingerprint);
      // Found an available bucket, and the insertion is successful.
      if (replacedFingerprint.isEmpty()) {
        return true;
      }

      visitedBucketIndices.add(currBucketIndex);
      replacedFingerprints.add(replacedFingerprint.get());

      currFingerprint = replacedFingerprint.get();
      currBucketIndex =
          config
              .strategy()
              .computeOtherBucketIndex(
                  currFingerprint,
                  currBucketIndex,
                  config.size().bucketCount(),
                  config.hashFunction());
    }

    // Failed to find a bucket to insert. Reverse the replacements and declare that the insertion
    // failed.
    for (int i = visitedBucketIndices.size() - 1; i > 0; i--) {
      int previousBucketIndex = visitedBucketIndices.get(i);
      table.delete(previousBucketIndex, replacedFingerprints.get(i - 1));
      table.insertWithReplacement(previousBucketIndex, replacedFingerprints.get(i));
    }
    return false;
  }
}