Revision 239d17a19c3cec16937aa4b6c56c90f4f217addf authored by Peter Dillinger on 18 December 2020, 22:29:48 UTC, committed by Facebook GitHub Bot on 18 December 2020, 22:31:03 UTC
Summary:
Primarily this change refactors the optimize_filters_for_memory
code for Bloom filters, based on malloc_usable_size, to also work for
Ribbon filters.

This change also replaces the somewhat slow but general
BuiltinFilterBitsBuilder::ApproximateNumEntries with
implementation-specific versions for Ribbon (new) and Legacy Bloom
(based on a recently deleted version). The reason is to emphasize
speed in ApproximateNumEntries rather than 100% accuracy.

Justification: ApproximateNumEntries (formerly CalculateNumEntry) is
only used by RocksDB for range-partitioned filters, called each time we
start to construct one. (In theory, it should be possible to reuse the
estimate, but the abstractions provided by FilterPolicy don't really
make that workable.) But this is only used as a heuristic estimate for
hitting a desired partitioned filter size because of alignment to data
blocks, which have various numbers of unique keys or prefixes. The two
factors lead us to prioritize reasonable speed over 100% accuracy.

optimize_filters_for_memory adds extra complication, because precisely
calculating num_entries for some allowed number of bytes depends on state
with optimize_filters_for_memory enabled. And the allocator-agnostic
implementation of optimize_filters_for_memory, using malloc_usable_size,
means we would have to actually allocate memory, many times, just to
precisely determine how many entries (keys) could be added and stay below
some size budget, for the current state. (In a draft, I got this
working, and then realized the balance of speed vs. accuracy was all
wrong.)

So related to that, I have made CalculateSpace, an internal-only API
only used for testing, non-authoritative also if
optimize_filters_for_memory is enabled. This simplifies some code.

Pull Request resolved: https://github.com/facebook/rocksdb/pull/7774

Test Plan:
unit test updated, and for FilterSize test, range of tested
values is greatly expanded (still super fast)

Also tested `db_bench -benchmarks=fillrandom,stats -bloom_bits=10 -num=1000000 -partition_index_and_filters -format_version=5 [-optimize_filters_for_memory] [-use_ribbon_filter]` with temporary debug output of generated filter sizes.

Bloom+optimize_filters_for_memory:

      1 Filter size: 197 (224 in memory)
    134 Filter size: 3525 (3584 in memory)
    107 Filter size: 4037 (4096 in memory)
    Total on disk: 904,506
    Total in memory: 918,752

Ribbon+optimize_filters_for_memory:

      1 Filter size: 3061 (3072 in memory)
    110 Filter size: 3573 (3584 in memory)
     58 Filter size: 4085 (4096 in memory)
    Total on disk: 633,021 (-30.0%)
    Total in memory: 634,880 (-30.9%)

Bloom (no offm):

      1 Filter size: 261 (320 in memory)
      1 Filter size: 3333 (3584 in memory)
    240 Filter size: 3717 (4096 in memory)
    Total on disk: 895,674 (-1% on disk vs. +offm; known tolerable overhead of offm)
    Total in memory: 986,944 (+7.4% vs. +offm)

Ribbon (no offm):

      1 Filter size: 2949 (3072 in memory)
      1 Filter size: 3381 (3584 in memory)
    167 Filter size: 3701 (4096 in memory)
    Total on disk: 624,397 (-30.3% vs. Bloom)
    Total in memory: 690,688 (-30.0% vs. Bloom)

Note that optimize_filters_for_memory is even more effective for Ribbon filter than for cache-local Bloom, because it can close the unused memory gap even tighter than Bloom filter, because of 16 byte increments for Ribbon vs. 64 byte increments for Bloom.

Reviewed By: jay-zhuang

Differential Revision: D25592970

Pulled By: pdillinger

fbshipit-source-id: 606fdaa025bb790d7e9c21601e8ea86e10541912
1 parent 04b3524
Raw File
INSTALL.md
## Compilation

**Important**: If you plan to run RocksDB in production, don't compile using default
`make` or `make all`. That will compile RocksDB in debug mode, which is much slower
than release mode.

RocksDB's library should be able to compile without any dependency installed,
although we recommend installing some compression libraries (see below).
We do depend on newer gcc/clang with C++11 support.

There are few options when compiling RocksDB:

* [recommended] `make static_lib` will compile librocksdb.a, RocksDB static library. Compiles static library in release mode.

* `make shared_lib` will compile librocksdb.so, RocksDB shared library. Compiles shared library in release mode.

* `make check` will compile and run all the unit tests. `make check` will compile RocksDB in debug mode.

* `make all` will compile our static library, and all our tools and unit tests. Our tools
depend on gflags. You will need to have gflags installed to run `make all`. This will compile RocksDB in debug mode. Don't
use binaries compiled by `make all` in production.

* By default the binary we produce is optimized for the platform you're compiling on
(`-march=native` or the equivalent). SSE4.2 will thus be enabled automatically if your
CPU supports it. To print a warning if your CPU does not support SSE4.2, build with
`USE_SSE=1 make static_lib` or, if using CMake, `cmake -DFORCE_SSE42=ON`. If you want
to build a portable binary, add `PORTABLE=1` before your make commands, like this:
`PORTABLE=1 make static_lib`.

## Dependencies

* You can link RocksDB with following compression libraries:
  - [zlib](http://www.zlib.net/) - a library for data compression.
  - [bzip2](http://www.bzip.org/) - a library for data compression.
  - [lz4](https://github.com/lz4/lz4) - a library for extremely fast data compression.
  - [snappy](http://google.github.io/snappy/) - a library for fast
      data compression.
  - [zstandard](http://www.zstd.net) - Fast real-time compression
      algorithm.

* All our tools depend on:
  - [gflags](https://gflags.github.io/gflags/) - a library that handles
      command line flags processing. You can compile rocksdb library even
      if you don't have gflags installed.

* If you wish to build the RocksJava static target, then cmake is required for building Snappy.

## Supported platforms

* **Linux - Ubuntu**
    * Upgrade your gcc to version at least 4.8 to get C++11 support.
    * Install gflags. First, try: `sudo apt-get install libgflags-dev`
      If this doesn't work and you're using Ubuntu, here's a nice tutorial:
      (http://askubuntu.com/questions/312173/installing-gflags-12-04)
    * Install snappy. This is usually as easy as:
      `sudo apt-get install libsnappy-dev`.
    * Install zlib. Try: `sudo apt-get install zlib1g-dev`.
    * Install bzip2: `sudo apt-get install libbz2-dev`.
    * Install lz4: `sudo apt-get install liblz4-dev`.
    * Install zstandard: `sudo apt-get install libzstd-dev`.

* **Linux - CentOS / RHEL**
    * Upgrade your gcc to version at least 4.8 to get C++11 support:
      `yum install gcc48-c++`
    * Install gflags:

              git clone https://github.com/gflags/gflags.git
              cd gflags
              git checkout v2.0
              ./configure && make && sudo make install

      **Notice**: Once installed, please add the include path for gflags to your `CPATH` environment variable and the
      lib path to `LIBRARY_PATH`. If installed with default settings, the include path will be `/usr/local/include`
      and the lib path will be `/usr/local/lib`.

    * Install snappy:

              sudo yum install snappy snappy-devel

    * Install zlib:

              sudo yum install zlib zlib-devel

    * Install bzip2:

              sudo yum install bzip2 bzip2-devel

    * Install lz4:

              sudo yum install lz4-devel

    * Install ASAN (optional for debugging):

              sudo yum install libasan

    * Install zstandard:

             wget https://github.com/facebook/zstd/archive/v1.1.3.tar.gz
             mv v1.1.3.tar.gz zstd-1.1.3.tar.gz
             tar zxvf zstd-1.1.3.tar.gz
             cd zstd-1.1.3
             make && sudo make install

* **OS X**:
    * Install latest C++ compiler that supports C++ 11:
        * Update XCode:  run `xcode-select --install` (or install it from XCode App's settting).
        * Install via [homebrew](http://brew.sh/).
            * If you're first time developer in MacOS, you still need to run: `xcode-select --install` in your command line.
            * run `brew tap homebrew/versions; brew install gcc48 --use-llvm` to install gcc 4.8 (or higher).
    * run `brew install rocksdb`

* **FreeBSD** (11.01):

    * You can either install RocksDB from the Ports system using `cd /usr/ports/databases/rocksdb && make install`, or you can follow the details below to install dependencies and compile from source code:

    * Install the dependencies for RocksDB:

        export BATCH=YES
        cd /usr/ports/devel/gmake && make install
        cd /usr/ports/devel/gflags && make install

        cd /usr/ports/archivers/snappy && make install
        cd /usr/ports/archivers/bzip2 && make install
        cd /usr/ports/archivers/liblz4 && make install
        cd /usr/ports/archivesrs/zstd && make install

        cd /usr/ports/devel/git && make install


    * Install the dependencies for RocksJava (optional):

        export BATCH=yes
        cd /usr/ports/java/openjdk7 && make install

    * Build RocksDB from source:
        cd ~
        git clone https://github.com/facebook/rocksdb.git
        cd rocksdb
        gmake static_lib

    * Build RocksJava from source (optional):
        cd rocksdb
        export JAVA_HOME=/usr/local/openjdk7
        gmake rocksdbjava

* **OpenBSD** (6.3/-current):

    * As RocksDB is not available in the ports yet you have to build it on your own:

    * Install the dependencies for RocksDB:

        pkg_add gmake gflags snappy bzip2 lz4 zstd git jdk bash findutils gnuwatch 

    * Build RocksDB from source:

        cd ~
        git clone https://github.com/facebook/rocksdb.git
        cd rocksdb
        gmake static_lib

    * Build RocksJava from source (optional):

        cd rocksdb
        export JAVA_HOME=/usr/local/jdk-1.8.0
        export PATH=$PATH:/usr/local/jdk-1.8.0/bin
        gmake rocksdbjava

* **iOS**:
  * Run: `TARGET_OS=IOS make static_lib`. When building the project which uses rocksdb iOS library, make sure to define two important pre-processing macros: `ROCKSDB_LITE` and `IOS_CROSS_COMPILE`.

* **Windows**:
  * For building with MS Visual Studio 13 you will need Update 4 installed.
  * Read and follow the instructions at CMakeLists.txt
  * Or install via [vcpkg](https://github.com/microsoft/vcpkg) 
       * run `vcpkg install rocksdb:x64-windows`

* **AIX 6.1**
    * Install AIX Toolbox rpms with gcc
    * Use these environment variables:
  
             export PORTABLE=1
             export CC=gcc
             export AR="ar -X64"
             export EXTRA_ARFLAGS=-X64
             export EXTRA_CFLAGS=-maix64
             export EXTRA_CXXFLAGS=-maix64
             export PLATFORM_LDFLAGS="-static-libstdc++ -static-libgcc"
             export LIBPATH=/opt/freeware/lib
             export JAVA_HOME=/usr/java8_64
             export PATH=/opt/freeware/bin:$PATH
  
* **Solaris Sparc**
    * Install GCC 4.8.2 and higher.
    * Use these environment variables:

             export CC=gcc
             export EXTRA_CFLAGS=-m64
             export EXTRA_CXXFLAGS=-m64
             export EXTRA_LDFLAGS=-m64
             export PORTABLE=1
             export PLATFORM_LDFLAGS="-static-libstdc++ -static-libgcc"

back to top