hbase-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Bryan Duxbury <br...@rapleaf.com>
Subject Re: Clarification: Merging and getRowKeyAtOrBefore
Date Fri, 27 Jun 2008 04:26:34 GMT
My replies to the second question inline. Feel free to ask follow ups.


On Jun 26, 2008, at 5:24 PM, Andra Adams wrote:

> Hi,
> I've been looking through the HBase code and I was wondering if I  
> could get some clarification on two points.
> 1. Why doesn't HRegion's static merge method check that the two  
> regions specified are adjacent?
> As far as I can tell, HRegion's merge method is called from the  
> Merge tool which gets its region names from command line  
> arguments.  As far as I can see, merging non-adjacent regions would  
> break many of the assertions that HBase depends on, yet all calls  
> to HRegion's merge method result in a merged region.  So how come  
> the caller of the Merge tool is being trusted to ensure the  
> adjacency of the regions it is specifying on the command line?   
> ( Although admittedly, the adjacency check could be quite  
> computationally-expensive since it would involve a complete scan of  
> all regions in the "parent" META table (either .META. or -ROOT-) to  
> ensure that there are no regions in the "daughter" (either a user  
> table or .META.) table that have a start key between the end key  
> and start key of the regions being asked to merge).
> 2.  Can I get an overview of the algorithm used to determine the  
> best candidate key in HStore's getRowKeyAtOrBefore (including  
> Memcache's internalGetRowKeyAtOrBefore, and HStore's  
> rowAtOrBeforeFromMapFile)?
> I'm having trouble figuring out why HStore's getFull method looks  
> through the mc, snapshot and storefiles in reverse chronological  
> order (i.e. mc, then snapshot, then store files), while the  
> getRowKeyAtOrBefore looks through the storefiles, then the mc, then  
> the snapshot (in apparently no chronological order...?).  Why does  
> getFull create a map of deletes (and older entries check this map  
> before inserting their values in the results map), while  
> getRowAtOrBefore opts to remove entries from the results map if a  
> delete is found at a later time?
> Aside from the difference in style between getFull and  
> getRowAtOrBefore, I'm also wondering why the discovery of a deleted  
> value sometimes removes that key from the candidateKeys map, and  
> other times is simply ignored.  (It could be that I'm missing some  
> of the concepts behind the algorithm).

The idea of getRowKeyAtOrBefore is to discover the row that comes  
immediately before or right upon the search row. This is used  
exclusively when trying to locate which region a key resides in. The  
reasoning behind this is a little tricky. Regions in HBase are keyed  
on their start row, which is inclusive. The end row is implied by the  
presence of the next region. So, when you have an arbitrary key you'd  
like to perform some operation on, you need to find the region which  
contains it, which you can only know by scanning past it.

getRowKeyAtOrBefore is a specific, internal-only RPC method that does  
this operation. In order to actually do the work, at the HStore  
level, we have to decide amongst the possible keys that presented by  
the memcache (including the snapshot) and all of the store files. The  
order here is unimportant, because ultimately, we're going to have to  
look at every one of those things unless we encounter a precise  
match. Moreover, there could be deletes in any one of them, so we  
have to carry the candidates along with us and apply the deletes  
where they are required. The reasoning here is that if a row is  
completely deleted, that is, all cells are suppressed by deletes,  
even if it matches precisely, we don't want to return it as a  
candidate key. Deletes are ignored when the don't apply to the data  
we've already found, usually because there's a newer piece of data  
than there is a delete (this is simply a memory optimization).

Likewise, getFull tries to find a whole row of information about a  
key at a time. We need to follow deletes around here for the same  
reason that we do it in regular get: we don't want to return deleted  
data. We go in reverse chronological order here because that allows  
the most recent data to easily take precedence.

> Thanks,
> Andra
> andra.adams@sun.com

View raw message