HBASE-3587: Eliminate use of ReadWriteLock in RegionObserver coprocessor invocation

Review Request #1681 - Created April 6, 2011 and updated

Gary Helmling
This patch eliminates the ReentrantReadWriteLock around the coprocessors collection in CoprocessorHost.  Since this lock was shared across the entire HRegion and obtained for each RegionObserver pre/post hook call, they were a significant point of contention between handler threads.

Since the coprocessor list is expected to be small (a few entries in most cases) and should very rarely change, I added a new utility class org.apache.hadoop.hbase.util.SortedCopyOnWriteSet, which uses an internal TreeSet instance for storage and creates a new copy on mutations.  The existing java.util.concurrent implementations -- CopyOnWriteArrayList and CopyOnWriteArraySet -- do not support sorting, which we need to order the coprocessors by priority.

The SortedCopyOnWriteSet implementation could be further optimized by replacing the internal TreeSet with an internal Object[], but this would add a bit more complexity to the implementation.  This would improve the iterator performance, but I'm not sure it would have a meaningful impact on most region operations which are far more likely to be performance bound elsewhere.
Profiled with put-based MR workload in EC2.  Don't have exact numbers on throughput (I was looking mostly at CPU utilization and contention), but request counts were considerably higher (up to several times) after applying the patch.
  1. +1
  2. Since the new class relies on SortedSet, I think E should be declared as extending (implementing) Comparable
    1. For better or worse, this is not the contract provided by SortedSet.  It's perfectly valid to use the constructor accepting a Comparator<E> when E in non-Comparable.
  1. +1 Nice one Gary.
  2. I had a chat with JD about this (on a completely different jira). The point he raised was a TreeSet is a badly designed interface in the sense that it can have a comparator/comparable check at compile time i.e., in the constructor that takes E, one can have a check whether E is instanceof Comparable or not otherwise, throw an exception. It sounds right to me. 
    Though you have documented this dependency but still want to know your opinion.
    1. I am aware of the limitations (hence the javadoc).  Though I think the poor interface is more of a compromise forced by Java's support for primitive types.  But when implementing a core java interface, I don't think we should change the semantics.  Moreover, in the case of coprocessors we actually want to use the Comparator version.
      As a side note, requiring E extends Comparable would prevent this from being used to store byte[], for example.  Not that we need that here, but it's something that's done quite a bit in HBase code.
  2. Do we need a lock for this method ?
    Is it possible that two threads compete setting internalSet ? If so, one E would be lost.
  2. This method is synchronized.
    Please ignore my previous comment.