Summary:
In block based table's hash index checking, when looking for a key that doesn't exist, there is a high chance that a false block is returned because of hash bucket conflicts. In this revision, another check is done to filter out some of those cases: comparing previous key of the block boundary to see whether the target block is what we are looking for.

In a favored test setting (bloom filter disabled, 8 L0 files), I saw about 80% improvements. In a non-favored test setting (bloom filter enabled, files are all in L1, files are all cached), I see the performance penalty is less than 3%.

Test Plan: make all check

Reviewers: haobo, ljin

Reviewed By: ljin

Subscribers: wuj, leveldb, zagfox, yhchiang

Differential Revision: https://reviews.facebook.net/D20595

Summary:
Contains:
- Implementation of TableReader based on Cuckoo Hashing
- Unittests for CuckooTableReader
- Performance test for TableReader

Test Plan:
make cuckoo_table_reader_test
./cuckoo_table_reader_test
make valgrind_check
make asan_check

Reviewers: yhchiang, sdong, igor, ljin

Reviewed By: ljin

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20511

Summary:
User gets undefinied error since the definition is not exposed.
Also re-enable the db test with only upper bound check

Test Plan: db_test, rate_limit_test

Reviewers: igor, yhchiang, sdong

Reviewed By: sdong

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20403

Summary:
Fixed compaction-related errors where number of input levels are hard-coded.
It's a bug found in compaction branch.
This diff will be pushed into master.

Test Plan:
export ROCKSDB_TESTS=Compact
make db_test -j32
./db_test
also passed the tests in compaction branch

Reviewers: igor, sdong, ljin

Reviewed By: ljin

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20577

Summary: I changed SpatialDB API so that we only specify list of indexes when we create the database. That way, whoever is querying the DB doesn't need to know the full list of indexes and their options.

Test Plan: spatial_db_test

Reviewers: yinwang

Reviewed By: yinwang

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20571

Summary:
Contains the following changes in CuckooTableBuilder:
- Take an extra parameter in constructor to identify last level file.
- Implement a better way to identify if a bucket has been inserted into the tree already during BFS search.
- Minor typos

Test Plan:
make cuckoo_table_builder
./cuckoo_table_builder
make valgrind_check

Reviewers: sdong, igor, yhchiang, ljin

Reviewed By: ljin

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20445

Summary:
Add compression type to options

make rocksdbjava
make sample

Reviewers: haobo, yhchiang, sdong, dhruba, rsumbaly, zzbennett, swapnilghike
Reviewed By: yhchiang, sdong
CC: leveldb

Differential Revision: https://reviews.facebook.net/D20463

Summary: As title.

Test Plan: Added test to column_family_test

Reviewers: ljin, yhchiang, sdong

Reviewed By: sdong

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20523

Summary:
  Modify a functioin TrimAppend in dbformat.h: IterKey. Write a test for it in dbformat_test
  Use IterKey in block::Iter to replace std::string to reduce malloc.

  Evaluate it using perf record.
  malloc: 4.26% -> 2.91%
  free: 3.61% -> 3.08%

Test Plan:
  make all check
  ./valgrind db_test dbformat_test

Reviewers: ljin, haobo, yhchiang, dhruba, igor, sdong

Reviewed By: sdong

Differential Revision: https://reviews.facebook.net/D20433

Summary:
This diff is adding spatial index support to RocksDB.

When creating the DB user specifies a list of spatial indexes. Spatial indexes can cover different areas and have different resolution (i.e. number of tiles). This is useful for supporting different zoom levels.

Each element inserted into SpatialDB has:
* a bounding box, which determines how will the element be indexed
* string blob, which will usually be WKB representation of the polygon (http://en.wikipedia.org/wiki/Well-known_text)
* feature set, which is a map of key-value pairs, where value can be int, double, bool, null or a string. FeatureSet will be a set of tags associated with geo elements (for example, 'road': 'highway' and similar)
* a list of indexes to insert the element in. For example, small river element will be inserted in index for high zoom level, while country border will be inserted in all indexes (including the index for low zoom level).

Each query is executed on single spatial index. Query guarantees that it will return all elements intersecting the specified bounding box, but it might also return some extra non-intersecting elements.

Test Plan: Added bunch of unit tests in spatial_db_test

Reviewers: dhruba, yinwang

Reviewed By: yinwang

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20361

Summary:
Add the missing ROCKSDB_JAR variable in Makefile, which is mistakenly
removed in https://reviews.facebook.net/D20289.

Test Plan:
export ROCKSDB_JAR=
make rocksdbjava

Summary:
Update header inclusion as include/utilities/*.h has been moved to
include/rocksdb/utilities/*.h

Test Plan: make rocksdbjava

Reviewers: ljin, sdong, igor

Reviewed By: igor

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20517

Summary:
Fixed the following compile error by replacing pow by shift, as it computes
power of 2.

util/options_builder.cc:133:14: error: no member named 'pow' in namespace 'std'
        std::pow(2, std::max(0, std::min(3, level0_stop_writes_trigger -
        ~~~~~^
1 error generated.
make: *** [util/options_builder.o] Error 1

Test Plan: make success in mac and linux

Reviewers: ljin, igor, sdong

Reviewed By: sdong

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20475

Summary:
Fixed a bug in Compaction.cc where input_levels_ was not properly resized.
Without this fix, there would be invalid access in input_levels_ when more
than two levels are involved in one compaction run.

This fix will go to master instead of compaction branch.

Test Plan: tested in compaction branch.

Reviewers: ljin, sdong, igor

Reviewed By: igor

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20481

Summary:
All public headers need to be under `include/rocksdb` directory. Otherwise, clients include our header files like this:

    #include <rocksdb/db.h>
    #include <utilities/backupable_db.h> // still our public header!

Also, internally, we include:

    #include "utilities/backupable/backupable_db.h" // internal header
    #include "utilities/backupable_db.h" // public header

which is confusing.

This way, when we install rocksdb as a system library, we can just copy `include/rocksdb` directory to system's header files. We can't really copy `utilities` directory to system's header files.

Test Plan: compiles

Reviewers: dhruba, ljin, yhchiang, sdong

Reviewed By: sdong

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20409

Summary:
Add a function GetOptions(), where based on four parameters users give: read/write amplification threshold, memory budget for mem tables and target DB size, it picks up a compaction style and parameters for them. Background threads are not touched yet.

One limit of this algorithm: since compression rate and key/value size are hard to predict, it's hard to predict level 0 file size from write buffer size. Simply make 1:1 ratio here.

Sample results: https://reviews.facebook.net/P477

Test Plan: Will add some a unit test where some sample scenarios are given and see they pick the results that make sense

Reviewers: yhchiang, dhruba, haobo, igor, ljin

Reviewed By: ljin

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D18741

Summary:
This diff merges pull request 208.  Contributor: ankgup87

[Java] Optimize statistics collector
* Optimize statistics collector by collecting statistics of multiple DBs in a single thread rather than starting up a new thread for each DB.
* Also, fix packaging of jnilib file on OS_X platform.
* Diff review: https://reviews.facebook.net/D20265

[Java] Add documentation on interdependency of dispose call of RocksObjects
* Remove transferCppRawPointersOwnershipFrom function.
  - This function was setting opt.filter_ and thus filter_ to be null. This way there is no
    one holding reference for filter object and can thus be GC'd which is not the intention.
    Replaced it with storeOptionsInstace which stores options instance. Options class
    internally holds Filter instance. Thus when Options is GC'd, filter reference
    will be GC'd automatically.
* Added documentation explaining interdependency of Filter, Options and DB.
* Diff review: https://reviews.facebook.net/D20379

Test Plan:
described in their diff reviews

Reviewers:  haobo sdong swapnilghike zzbennett rsumbaly yhchiang

Reviewed by: yhchiang

Summary:
This diff merges pull request #208.  Contributor: ankgup87

[Java] Optimize statistics collector
* Optimize statistics collector by collecting statistics of multiple DBs in a single thread rather than starting up a new thread for each DB.
* Also, fix packaging of jnilib file on OS_X platform.
* Diff review: https://reviews.facebook.net/D20265

[Java] Add documentation on interdependency of dispose call of RocksObjects
* Remove transferCppRawPointersOwnershipFrom function.
  - This function was setting opt.filter_ and thus filter_ to be null. This way there is no
    one holding reference for filter object and can thus be GC'd which is not the intention.
    Replaced it with storeOptionsInstace which stores options instance. Options class
    internally holds Filter instance. Thus when Options is GC'd, filter reference
    will be GC'd automatically.
* Added documentation explaining interdependency of Filter, Options and DB.
* Diff review: https://reviews.facebook.net/D20379

Test Plan:
described in their diff reviews

Reviewers:  haobo sdong swapnilghike zzbennett rsumbaly yhchiang

Reviewed by: yhchiang

Summary: Fixes some memory leaks in cuckoo_builder_test.cc. This also fixed broken valgrind_check tests

Test Plan:
make valgrind_check
./cuckoo_builder_test
Currently running make check all. I shall update once it is done.

Reviewers: ljin, sdong, yhchiang, igor

Reviewed By: igor

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20385

Summary:
Add setCacheNumShardBits() and cacheNumShardBits() to Options.  This allows
developers to control the number of shards for the block cache.

Test Plan:
make rocksdbjava
cd java
make db_bench
./jdb_bench.sh --cache_size=1048576 --cache_numshardbits=6

Reviewers: sdong, ljin, ankgup87

Reviewed By: ankgup87

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D19347

Summary:
Fixed some make and linking issues of RocksDBJava. Specifically:
* Add JAVA_LDFLAGS, which does not include gflags
* rocksdbjava library now uses JAVA_LDFLAGS instead of LDFLAGS
* java/Makefile now includes build_config.mk
* rearrange make rocksdbjava workflow to ensure the library file is correctly
  included in the jar file.

Test Plan:
make rocksdbjava
make jdb_bench
java/jdb_bench.sh

Reviewers: dhruba, swapnilghike, zzbennett, rsumbaly, ankgup87

Reviewed By: ankgup87

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20289

Summary: Add a parameter path_id to DB::CompactRange(), to indicate where the output file should be placed to.

Test Plan: add a unit test

Reviewers: yhchiang, ljin

Reviewed By: ljin

Subscribers: xjin, igor, dhruba, MarkCallaghan, leveldb

Differential Revision: https://reviews.facebook.net/D20085

Summary:
Fixed the following compile error.

./table/cuckoo_table_builder.h:72:22: error: private field 'key_length_' is not used [-Werror,-Wunused-private-field]
  const unsigned int key_length_;
                     ^
1 error generated.

Test Plan: make

Reviewers: sdong, ljin, radheshyamb, igor

Reviewed By: igor

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20349

Summary:
Cuckoo Hashing based SST table builder. Contains:
- Cuckoo Hashing logic and file storage logic.
- Unit tests for logic

Test Plan:
make cuckoo_table_builder_test
./cuckoo_table_builder_test
make check all

Reviewers: yhchiang, igor, sdong, ljin

Reviewed By: ljin

Subscribers: dhruba, leveldb

Differential Revision: https://reviews.facebook.net/D19545

Summary:
also make it aware of column family
output from db_bench

```
** Compaction Stats [default] **
Level Files Size(MB) Score Read(GB)  Rn(GB) Rnp1(GB) Write(GB) Wnew(GB) RW-Amp W-Amp Rd(MB/s) Wr(MB/s)  Rn(cnt) Rnp1(cnt) Wnp1(cnt) Wnew(cnt)  Comp(sec) Comp(cnt) Avg(sec) Stall(sec) Stall(cnt) Avg(ms)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  L0    14      956   0.9      0.0     0.0      0.0       2.7      2.7    0.0   0.0      0.0    111.6        0         0         0         0         24        40    0.612      75.20     492387    0.15
  L1    21     2001   2.0      5.7     2.0      3.7       5.3      1.6    5.4   2.6     71.2     65.7       31        43        55        12         82         2   41.242      43.72      41183    1.06
  L2   217    18974   1.9     16.5     2.0     14.4      15.1      0.7   15.6   7.4     70.1     64.3       17       182       185         3        241        16   15.052       0.00          0    0.00
  L3  1641   188245   1.8      9.1     1.1      8.0       8.5      0.5   15.4   7.4     61.3     57.2        9        75        76         1        152         9   16.887       0.00          0    0.00
  L4  4447   449025   0.4     13.4     4.8      8.6       9.1      0.5    4.7   1.9     77.8     52.7       38        79       100        21        176        38    4.639       0.00          0    0.00
 Sum  6340   659201   0.0     44.7    10.0     34.7      40.6      6.0   32.0  15.2     67.7     61.6       95       379       416        37        676       105    6.439     118.91     533570    0.22
 Int     0        0   0.0      1.2     0.4      0.8       1.3      0.5    5.2   2.7     59.1     65.6        3         7         9         2         20        10    2.003       0.00          0    0.00
Stalls(secs): 75.197 level0_slowdown, 0.000 level0_numfiles, 0.000 memtable_compaction, 43.717 leveln_slowdown
Stalls(count): 492387 level0_slowdown, 0 level0_numfiles, 0 memtable_compaction, 41183 leveln_slowdown

** DB Stats **
Uptime(secs): 202.1 total, 13.5 interval
Cumulative writes: 6291456 writes, 6291456 batches, 1.0 writes per batch, 4.90 ingest GB
Cumulative WAL: 6291456 writes, 6291456 syncs, 1.00 writes per sync, 4.90 GB written
Interval writes: 1048576 writes, 1048576 batches, 1.0 writes per batch, 836.0 ingest MB
Interval WAL: 1048576 writes, 1048576 syncs, 1.00 writes per sync, 0.82 MB written

Test Plan: ran it

Reviewers: sdong, yhchiang, igor

Reviewed By: igor

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D19917

Summary:
  Add block_restart_interval in db_bench, default value 16

Test Plan:
  make

Reviewers: sdong

Reviewed By: sdong

Differential Revision: https://reviews.facebook.net/D20331

Summary:
Suggested by @dhruba from the other diff, here is the improved
comments for parameters of the function

Test Plan: none

Reviewers: dhruba, sdong, igor

Reviewed By: igor

Subscribers: dhruba, leveldb

Differential Revision: https://reviews.facebook.net/D19623

Summary: Adding check for zero size index

Test Plan: ./build_tools/regression_build_test.sh

Reviewers: yhchiang, sdong

Reviewed By: sdong

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20259

Summary: Fixed the Java compilation error caused by PlainTableFactory API change.

Test Plan:
make rocksdbjava
make jdb_bench
cd java;./jdb_bench.sh

Reviewers: sdong, ljin, ankgup87, swapnilghike, zzbennett, rsumbaly, igor

Reviewed By: igor

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20295

Fix clang compiler warnings

Summary: Updating HISTORY.md to reflect changes in PlainTable index

Test Plan: no need

Reviewers: sdong

Reviewed By: sdong

Subscribers: leveldb

Differential Revision: https://reviews.facebook.net/D20229