[SPARK-2365] Add IndexedRDD, an efficient updatable key-value store

This PR adds IndexedRDD, an efficient key-value store built on RDDs. IndexedRDD extends `RDD[(Long, V)]` by enforcing key uniqueness and pre-indexing the entries for efficient joins and point lookups, updates, and deletions. See [SPARK-2365](https://issues.apache.org/jira/browse/SPARK-2365) for the motivation behind IndexedRDD.

IndexedRDD is implemented by (1) hash-partitioning the entries by key, (2) maintaining a hash index within each partition, and (3) using purely functional (immutable and efficiently updatable) data structures to enable efficient modifications and deletions.

As a result, this PR also introduces package-private implementations of three purely functional data structures: ImmutableVector, ImmutableLongOpenHashSet, and ImmutableBitSet.

GraphX will be the first user of IndexedRDD. This PR uses IndexedRDD to replace the current implementation of VertexRDD.

## Usage

Here is a usage example for IndexedRDD:

```scala
import org.apache.spark.rdd.IndexedRDD

// Create an RDD of key-value pairs with Long keys.
val rdd = sc.parallelize((1 to 1000000).map(x => (x.toLong, 0)))
// Construct an IndexedRDD from the pairs, hash-partitioning and indexing
// the entries.
val indexed = IndexedRDD(rdd).cache()

// Perform a point update.
val indexed2 = indexed.put(1234L, 10873).cache()
// Perform a point lookup. Note that the original IndexedRDD remains
// unmodified.
indexed2.get(1234L) // => Some(10873)
indexed.get(1234L) // => Some(0)

// Efficiently join derived IndexedRDD with original.
val indexed3 = indexed.innerJoin(indexed2) { (id, a, b) => b }.filter(_._2 != 0)
indexed3.collect // => Array((1234L, 10873))

// Perform insertions and deletions.
val indexed4 = indexed2.put(-100L, 111).delete(Array(998L, 999L)).cache()
indexed2.get(-100L) // => None
indexed4.get(-100L) // => Some(111)
indexed2.get(999L) // => Some(0)
indexed4.get(999L) // => None
```

## Benchmarks

### Benefits

**Faster joins.** Joining pair RDDs requires hashing all elements in both RDDs. Joining a pair RDD with an existing IndexedRDD hashes only the elements in the pair RDD, and joining two IndexedRDDs sharing the same index does not require any hash lookups. Joining a pair RDDs with 8M elements with a small one with 8 elements using `PairRDDFunctions.join` takes 11.8 s, while joining an IndexedRDD with the small pair RDD takes 0.126 s (**94x speedup**).

**Faster lookups.** Including task launch delay, `PairRDDFunctions.lookup` on an 8-partition RDD with 8M elements takes 82 ms, while `IndexedRDD.get` takes 6 ms (**14x speedup**). Without task launch delay, the equivalent operation on a single partition takes 47.9 ms vs. 609 ns (**78,600x speedup**).

**Faster updates.** Including task launch delay, `RDD.map` to update a single element from an 8-partition RDD with 8M elements takes 108 ms, while `IndexedRDD.put` takes 25 ms (**4.3x speedup**). Without task launch delay, the equivalent operation on a single partition takes 59.7 ms vs. 1.03 microseconds (**58,000x speedup**).

**Faster deletions.** Including task launch delay, `RDD.filter` to delete a single element from an 8-partition RDD with 8M elements takes 132 ms, while `IndexedRDD.delete` takes 25 ms (**5.3x speedup**). Without task launch delay, the equivalent operation on a single partition takes 59.8 ms vs. 557 ns (**107,000x speedup**).

### Overheads

#### Immutable data structures

Summary: Low memory overhead (7-18%); substantial but manageable scan overhead (1.6-6.6x).

Operation (1M elems) | Array[Long] | ImmutableVector[Long] | Overhead
--- | --- | --- | ---
Element lookup | 19.9 ns | 40.8 ns | 2x
Sequential scan | 3.35 ms | 14.1 ms | 4.2x
Memory usage | 8,000,016 bytes | 9,419,496 bytes | 1.18x

Operation (1M elems) | Array[Object] | ImmutableVector[Object] | Overhead
--- | --- | --- | ---
Sequential scan | 7.3411 ms | 11.5333 ms | 1.6x
Memory usage | 20,000,016 bytes | 21,419,440 bytes | 1.07x

Operation (1M capacity, 100 nonzeros) | Spark BitSet | ImmutableBitSet | Overhead
--- | --- | --- | ---
Element lookup | 19.3 ns | 30.9 ns | 1.6x
Sequential scan | 0.517 ms | 3.42 ms | 6.6x
Memory usage | 125,040 bytes | 147,384 bytes | 1.18x

Operation (1M elems) | OpenHashSet[Long] | ImmutableLongOpenHashSet | Overhead
--- | --- | --- | ---
Hash lookup | 103 ns | 338 ns | 3.3x
Memory usage | 17,039,576 bytes | 20,062,704 bytes | 1.18x

#### IndexedRDD

Operation (8M elems across 8 partitions) | RDD[(Long, Int)] | IndexedRDD[Int] | Overhead
--- | --- | --- | ---
Scan (`mapValues`) | 135 ms | 522 ms | 3.9x
Zip/Join (`zip`/`innerJoin`) | 168 ms | 610 ms | 3.6x

<!--
#### End-to-end impact on GraphX

PageRank for 10 iterations on a randomly-generated graph with 10M vertices and 1.27B edges, using EdgePartition2D across 256 partitions on 16 m2.4xlarge nodes, slowed down from 403 s (9bad0b7) to 493 s: **1.22x** overhead.
-->

### Scaling

Scaling for IndexedRDDPartition point lookups (IndexedRDDPartition.get): approximately logarithmic in the dataset size, from 241 ns on 10,001 elements to 654 ns for 990,001 elements.

Scaling for IndexedRDDPartition point updates (IndexedRDDPartition.put on an existing element): approximately logarithmic in the dataset size, from 356 ns on 10,001 elements to 913 ns for 990,001 elements.

Scaling for IndexedRDDPartition point insertions (IndexedRDDPartition.put on a nonexistent element): approximately logarithmic in the hashtable capacity, from 17.0 microseconds on 10,001 elements to 595 microseconds for 990,001 elements.

Scaling for IndexedRDDPartition point deletions (IndexedRDDPartition.delete): approximately logarithmic in the dataset size, from 209 ns on 10,001 elements to 474 ns for 990,001 elements.
Optimization: we should batch updates to the same leaf node to avoid temporarily allocating up to 32x the needed memory