This topic describes the commands supported by a TairBloom.

Overview

TairBloom is a Bloom filter that supports dynamic scaling. TairBloom is a space-efficient probabilistic data structure that consumes minimal memory to check whether an element exists. TairBloom supports dynamic scaling and maintains a stable false positive rate during scaling.

For Redis data structures, such as hashes, sets, and strings, you can use bitmaps to achieve similar features as TairBloom. However, these data structures may consume a large amount of memory, or fail to maintain a stable false positive rate during dynamic scaling. TairBloom can be used to check whether large volumes of data exist. In this case, a specific false positive rate is allowed. You can use the Bloom filter built in the TairBloom without further development or the need to create an extra Bloom filter.

Key features:

  • Consumes minimal memory.
  • Enables dynamic scaling.
  • Maintains a stable custom false positive rate during scaling.

Prerequisites

The commands described in this topic take effect only if the following conditions are met:

  • A performance-enhanced instance of ApsaraDB for Redis Enhanced Edition is used.
  • The TairBloom to be managed is stored on the performance-enhanced instance.

Commands

Table 1. TairBloom commands
Command Syntax Description
BF.RESERVE BF.RESERVE <key> <error_rate> <capacity> Creates an empty TairBloom filter with a specified capacity. The error_rate parameter specifies the false positive rate of the TairBloom filter.
BF.ADD BF.ADD <key> <item> Adds an item to a specified TairBloom filter.
BF.MADD BF.MADD <key> <item> [item...] Adds multiple items to a specified TairBloom filter.
BF.EXISTS BF.EXISTS <key> <item> Checks whether an item exists in a specified TairBloom filter.
BF.MEXISTS BF.MEXISTS <key> <item> [item...] Checks whether multiple items exist in a specified TairBloom filter.
BF.INSERT BF.INSERT <key> [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS <item... > Adds multiple items to a specified TairBloom filter. You can specify the capacity and false positive rate and specify whether to create a TairBloom filter if the TairBloom filter does not exist.
BF.DEBUG BF.DEBUG <key> Retrieves the information about a specified TairBloom filter. The information includes the number of layers, the number of items at each layer, and the false positive rate.
DEL DEL <key> [key ...] Deletes one or more TairBlooms.
Note The items added to a TairBloom cannot be deleted from the TairBloom. You can run the DEL command to delete the TairBloom.

BF.RESERVE

  • Syntax

    BF.RESERVE <key> <error_rate> <capacity>

  • Time complexity

    O(1)

  • Description

    This command is used to create an empty TairBloom filter with a specified capacity. The error_rate parameter specifies the false positive rate of the TairBloom filter.

  • Parameters and options
    Parameter/option Description
    key The key of the TairBloom filter that you want to manage.
    error_rate The expected false positive rate, which must be between 0 and 1. A lower value indicates higher memory and CPU usage by the TairBloom filter.
    capacity The initial capacity of the TairBloom filter. This is the maximum number of items that can be added to the TairBloom filter.

    If the number of items that have been added to the TairBloom filter exceeds the specified capacity, TairBloom expands the capacity by increasing the layers of the Bloom filter. During the scaling process, the number of items in the Tairbloom filter is increased exponentially while the performance is deceased on a linear scale. After a layer is added to the filter, to query a specified item, TairBloom may iterate through multiple layers of the filter. The capacity of each new layer is double that of the previous layer. If your workloads require high performance, we recommend that you add a proper number of items to the TairBloom. This avoids automatic scaling.

  • Returned values
    • OK: the operation is successful.
    • Otherwise, an exception is returned.

BF.ADD

  • Syntax

    BF.ADD <key> <item>

  • Time complexity

    O(log N). N specifies the number of layers of the TairBloom.

  • Description

    This command is used to add an item to a specified TairBloom filter.

  • Parameters and options
    Parameter/option Description
    key The key of the TairBloom filter that you want to manage.
    item The item that you want to add to the TairBloom filter.
  • Returned values
    • 1: the specified item does not exist in the filter.
    • 0: the specified item may exist in the filter.
    • Otherwise, an exception is returned.

BF.MADD

  • Syntax

    BF.MADD <key> <item> [item...]

  • Time complexity

    O(log N). N specifies the number of layers of the TairBloom.

  • Description

    This command is used to add multiple items to a specified TairBloom filter.

  • Parameters and options
    Parameter/option Description
    key The key of the TairBloom filter that you want to manage.
    item The items that you want to add to the TairBloom filter. You can specify multiple items.
  • Returned values
    • An array is returned if the operation is successful. In the returned array, each value can be 1 or 0. If a specified item does not exist, the value is 1. If a specified item may exist, the value is 0.
    • Otherwise, an exception is returned.

BF.EXISTS

  • Syntax

    BF.EXISTS <key> <item>

  • Time complexity

    O(log N). N specifies the number of layers of the TairBloom.

  • Description

    This command is used to check whether an item exists in a specified TairBloom filter.

  • Parameters and options
    Parameter/option Description
    key The key of the TairBloom filter that you want to manage.
    item The item that you want to query.
  • Returned values
    • 0: the specified item does not exist in the filter.
    • 1: the specified item may exist in the filter.
    • Otherwise, an exception is returned.

BF.MEXISTS

  • Syntax

    BF.MEXISTS <key> <item> [item...]

  • Time complexity

    O(log N). N specifies the number of layers of the TairBloom.

  • Description

    This command is used to check whether multiple items exist in a specified TairBloom filter.

  • Parameters and options
    Parameter/option Description
    key The key of the TairBloom filter that you want to manage.
    item The items that you want to query in the TairBloom filter. You can specify multiple items.
  • Returned values
    • An array is returned if the operation is successful. In the returned array, each value can be 1 or 0. If a specified item does not exist, the value is 0. If a specified item may exist, the value is 1.
    • Otherwise, an exception is returned.

BF.INSERT

  • Syntax

    BF.INSERT <key> [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS <item... >

  • Time complexity

    O(log N). N specifies the number of layers of the TairBloom.

  • Description

    This command is used to add multiple items to a specified TairBloom filter. If the TairBloom filter does not exist, you can specify the capacity and false positive rate and specify whether to create a TairBloom filter.

  • Parameters and options
    Parameter/option Description
    key The key of the TairBloom filter that you want to manage.
    CAPACITY The initial capacity of the TairBloom filter. This is the maximum number of items that can be added to the TairBloom filter. If the filter exists, you do not need to specify this parameter.

    If the number of items that have been added to the TairBloom filter exceeds the specified capacity, TairBloom expands the capacity by increasing the layers of the Bloom filter. During the scaling process, the number of items in the Tairbloom filter is increased exponentially while the performance is deceased on a linear scale. After a layer is added to the filter, to query a specified item, TairBloom may iterate through multiple layers of the filter. The capacity of each new layer is double that of the previous layer. If your workloads require high performance, we recommend that you add a proper number of items to the TairBloom. This avoids automatic scaling.

    ERROR The expected false positive rate. If the filter exists, you do not need to specify this parameter. The value must be between 0 and 1. A lower value indicates higher memory and CPU usage by the TairBloom filter.
    NOCREATE Specifies that a specified TairBloom filter is not automatically created if the filter does not exist. This parameter cannot be specified together with CAPACITY or ERROR.
    ITEMS All items that you want to add to the TairBloom filter.
  • Returned values
    • An array is returned if the operation is successful. In the returned array, each value can be 1 or 0. If a specified item does not exist, the value is 1. If a specified item may exist, the value is 0.
    • Otherwise, an exception is returned.

BF.DEBUG

  • Syntax

    BF.DEBUG <key>

  • Time complexity

    O(log N). N specifies the number of layers of the TairBloom.

  • Description

    This command is used to retrieve the information about a specified TairBloom filter. The information includes the number of layers, the number of items at each layer, and the false positive rate.

  • Parameters and options
    Parameter/option Description
    key The key of the TairBloom filter that you want to manage.
  • Returned values
    • An array is returned if the operation is successful. In the returned array, each value can be 1 or 0. If a specified item does not exist, the value is 1. If a specified item may exist, the value is 0.
    • Otherwise, an exception is returned.

Memory usage test result

Capacity false positive:0.01 false positive:0.001 false positive:0.0001
100000 0.12MB 0.25MB 0.25MB
1000000 2MB 2MB 4MB
10000000 16MB 32MB 32MB
100000000 128MB 256MB 256MB
1000000000 2GB 2GB 4GB