Support transparent salting of row key

[jtaylor-sfdc]

To prevent hot spotting on writes:

• “Salt” row key on upsert by mod-ing with cluster size
• Query for fully qualified key by inserting salt byte
• Range scan by concatenating results of scan over all possible salt bytes

Or alternately

• Define column used for hash to derive row key prefix

[jtaylor-sfdc]

At a high level, we'll provide a way of declaring that a table is "salted" in our DDL and then transparently insert a byte at the beginning of the row key on upsert. For any query, we'll insert an "or" of each possible bucket value where we form the start/stop of the scan. This will cause the query to get run everywhere. We'll have a special case when we know the full row key not to do this, but to insert the correct byte.

Detail on how to implement this:

1. Define a SALT_BUCKETS property that can be defined in the CREATE TABLE statement to declare how many buckets there are:

   CREATE TABLE foo (
       host VARCHAR,
       date DATE
       CONSTRAINT pk PRIMARY KEY (host, date))
   SALT_BUCKETS=20
   

2. Pull this out of the properties Map in MetaDataClient.createTable and create a new SALT_BUCKETS column in SYSTEM.TABLE to store this.

3. On any Put (PRowImpl), hash the row key mod-ed by the saltBuckets and store this as the first byte of the row key.

4. When we compute what the start/stop scan key is (WhereOptimizer), first add an "or" case (i.e. a List<byte[]> of each possible bucket byte, using the new mechanism being added by @ryang-sfdc for this issue) before we start computing the key. Include a special case at the end for the case of a fully qualified row key, since we don't need the "or" in that case.

5. In PTable, add a single byte PColumn as the first column for the salt bucket value.

6. In RowProjector, add one to the index passed in to skip over the salt bucket column.

Down the road, we can allow ALTER TABLE to increase, but not decrease the number of salt buckets. This would make is so that a point get would need to go everywhere too, though, so it's debatable that we'd want to allow it.

[tonyhuang]

Hi James, couple questions for this:

1. Are we still going to guarantee that the order of return is the same as the order of insertion for a table with buckets turned on?
2. Do we need to do anything when the statement has no "where" clause with it?

[jtaylor-sfdc]

Good questions. No, I think we can return the rows in any order (otherwise, we'd have to sort as you've alluded to which would be too expensive. If the user wanted them sorted, then could add an order by clause.
With no where clause, as far as I can think, I don't think we'd need to do anything.

[jtaylor-sfdc]

Implemented now. Great job, @tonyhuang