Mailing-List: contact hadoop-dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: hadoop-dev@lucene.apache.org
Received-SPF: pass (asf.osuosl.org: local policy)
Mime-Version: 1.0 (Apple Message framework v749.3)
In-Reply-To: <8a8b9f3f0605141500n6575b73dgca3b7965ca71b22f@mail.gmail.com>
References: <8a8b9f3f0605141500n6575b73dgca3b7965ca71b22f@mail.gmail.com>
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
Message-Id: <1C4AA81B-4C69-42B0-8B40-E1598CCB8E77@media-style.com>
Content-Transfer-Encoding: 7bit
From: Stefan Groschupf <sg@media-style.com>
Subject: Re: HBase Design Ideas, Part I
Date: Mon, 15 May 2006 02:52:19 -0700
To: hadoop-dev@lucene.apache.org


Hi,
sounds pretty much similar to what I was thinking about,
just that I had used different terms and you description is much more  
elegant than my hand written notes.
Some comments below.

> ---------------------------------------------------------------------- 
> ----------
> I.  Table semantics
>
> An HBase consists of one or more HTables.  An HTable is a list of  
> rows,
> sorted alphabetically by "row name".  An HTable also has a series of
> "columns."  A row may or may not contain a value for a column.  The
> HTable representation is sparse, so if a row does not contain a value
> for a given column, there is no storage overhead.
>
> (Thus, there's not really a "schema" to an HTable.  Every  
> operation, even
> adding a column, is considered a row-centric operation.)
>
> The "current version" of a row is always available, timestamped  
> with its
> last modification date.  The system may also store previous  
> versions of a row,
> according to how the HTable is configured.
I was playing around with row and run in to several problems using  
the hadoop io package. (SequenceReader writer)
Optimal would be if a cell is a writable but having rowkey and cell  
key and value for each sell blows up disk usage.
Alternative we can have a row writable so we only one rowkey , n  
column key and n values.
In case a row has many column this scales very bad. For example my  
row key is a url and my column keys are user ids and the value are  
number of clicks.
if I want to get the number of clicks for a given url and user, I  
need to load the values for all other user as well. :(

I already posted a mail about this issue.
What we may be need is a Writer that can seek first for row key and  
than for column keys.
In general I agree with  sparse structure.


>
> Updates to a single row are always atomic and can affect one or  
> more columns.
>
> II.  System layout
>
> HTables are partitionable into contiguous row regions called HRegions.
> All machines in a pool run an HRegionServer.  A given HRegion is  
> served
> to clients by a single HRegionServer.  A single HRegionServer may be
> responsible for many HRegions.  The HRegions for a single HTable will
> be scattered across arbitrary HRegionServers.
>
> When a client wants to add/delete/update a row value, it must  
> locate the
> relevant HRegionServer.  It then contacts the HRegionServer and  
> communicates
> the updates.  There may be other steps, mainly lock-oriented ones.   
> But locating
> the relevant HRegionServers is a bare minimum.

My idea was to have the lock on the HRegionServer level, my ideas was  
that the client itself take care about replication,
means write the value to n servers that have the same replicatins of  
HRegions.

>
> The HBase system can repartition an HTable at any time.  For  
> example, many
> repeated inserts at a single location may cause a single HRegion to  
> grow
> very large.  The HBase would then try to split that into multiple  
> HRegions.
> Those HRegions may be served by the same HRegionServer as the
> original or may be served by a different one.
Would the node send out a message to request a split or does the  
master decide based on heart beat messages?
>
> Each HRegionServer sends a regular heartbeat to an HBaseMaster  
> machine.
> If the heartbeat for an HRegionServer fails, then the HBaseMaster  
> is responsible
> for reassigning its HRegions to other available HRegionServers.
>
> All HRegions are stored within DFS, so the HRegion is always  
> available, even
> in the face of machine failures.  The HRegionServers and DFS  
> DataNodes run
> on the same set of machines.  We would like for an HRegionServer to  
> always
> serve data stored locally, but that is not guaranteed when using  
> DFS.  We can
> encourage it by:
> 1) In the event of an insert-motivated HRegion move, the new  
> HRegionServer
> should always create a new DFS file for the new HRegion.  The DFS  
> rules of
> thumb will allocate the chunks locally for the HRegionServer.
> 2) In the even of a machine failure, we cannot do anything similar  
> to above.
> Instead, the HBaseMaster can ask DFS for hints as to where the  
> relevant
> file blocks are stored.  If possible, it will allocate the new
> HRegions to servers
> that physically contain the HRegion.
> 3) If necessary, we could add an API to DFS that demands block  
> replication
> to a given node.  I'd like to avoid this if possible.
My idea was to simply download the data to the node and read any time  
locally, but write into the dfs, since in my case write access can be  
slower but I needer very fast read access.

>
> The mapping from row to HRegion (and hence, to HRegionServer) is  
> itself
> stored in a special HTable.  The HBaseMaster is the only client  
> allowed to
> write to this HTable.  This special HTable may itself be split into  
> several
> HRegions.  However, we only allow a hard-coded number of split-levels.
> The top level of this hierarchy must be easily-stored on a single  
> machine.
> That top-level table is always served by the HBaseMaster itself.
>
> III.  Client behavior
>
> Let's think about what happens when a client wants to add a row.
> 1) The client must compute what HRegion is responsible for the key
> it wants to insert into the HTable.  It must navigate the row->HRegion
> mapping, which is stored in an HTable.
>
> So the client first contacts the HBaseMaster for the top-level  
> table contents.
> It then steps downward through the table set, until it finds the  
> mapping for
> the target row.
>
> 2) The client contacts the HRegionServer responsible for the target  
> row,
> and asks to insert.  If the HRegionServer is no longer responsible  
> for the
> relevant HRegion, it returns a failure message and tells the client  
> to go
> back to step 1 to find the new correct HRegionServer.
My idea was in such a case the HRegionServer may be know the new  
location at least until the master is informed.
So getting a forward message could be faster than get an error and  
try ask for the target again.
>
> If the HRegionServer is the right place to go, it accepts the new  
> row from
> the client.  The HRegionServer guarantees that the insert is  
> atomic; it
> will not intermingle the insert with a competing insert for the  
> same row key.
> When the row is stored, the HRegionServer includes version and  
> timestamp
> information.
>
> 3) That's it!
>
> IV The HRegionServer
>
> Maintaining the data for a single HRegion is slightly complicated.   
> It's
> especially weird given the write-once semantics of DFS.  There are
> three important moving parts:
>
> 1) HBackedStore is a file-backed store for rows and their values.
> It is never edited in place.  It has B-Tree-like lookups for finding
> a row quickly.  HBackedStore is actually a series of on-disk stores,
> each store being tuned for a certain object size.  Thus, all the  
> "small"
> (in bytes) values for a row live within the same file, all the medium
> ones live in a separate file, etc.  There is only one HBackedStore
> for any single HRegion.
>
> 2) HUpdateLog is a log of updates to the HBackedStore.  It is backed
> by an on-disk file.  When making reads from the HBackedStore, it may
> be necessary to consult the HUpdateLog to see if any more-recent
> updates have been made.  There may be a series of HUpdateLogs
> for a single HRegion.
>
> 3) HUpdateBuf is an in-memory version of HUpdateLog.  It, too, needs
> to be consulted whenever performing a read.  There is only one
> HUpdateBuf for a single HRegion.
>
> Any incoming edit is first made directly to the HUpdateBuf.  Changes
> made to the HUpdateBuf are volatile until flushed to an HUpdateLog.
> The rate of flushes is an admin-configurable parameter.
>
> Periodically, the HBackedStore and the series of current HUpdateLogs
> are merged to form a new HBackedStore.  At that point, the old  
> HUpdateLog
> objects can be destroyed.  During this compaction process, edits are
> made to the HUpdateBuf.

Sounds great!
Looking forward to see that working.
Stefan