[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.
would it be better to throw an exception here?  Just in case something goes wrong and you end up here, you get a stack trace which will pinpoint the problem.