In TestOrderedScanner, do you want to remove commented out code? Do you want to add a class comment that says this test depends/uses a 'special' version of HRegionServer. Would suggest that all classes that depend on this custom HRegionServer also get marked appropriately in their class comment (@see?): e.g. OrderedScanner won't work unless its going against the ordered HRS – same for OrderedHRegion.
Some classes are missing licenses.
I suppose package protection prevents you putting all these new classes into a new orderedregionserver package or into a subpackage named regionserver.ordered and client.ordered or some such?
You need to explain somewhere in javadoc what this OrderedRegionServer is, how it works, and how to enable it. Would suggest that the class comment in the OrderedRegionServer or in the Ordered Interface as good places (otherwise, should I put in place a package.html to which you can add?). What would be great is that the next time someone shows up asking how they can customize regionserver behavior, we can just point them to your OrderedRegionServer javadoc as an example.
Thanks for adding accessors rather than making data members protected in RegionServer and for making HStore, etc., subclassable.
Otherwise, the patch looks great.