hadoop-common-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Cafarella" <michael.cafare...@gmail.com>
Subject HBase Design Ideas, Part I
Date Sun, 14 May 2006 22:00:03 GMT
Hi everyone,

I've written up a design that I've been working on for a little bit, for
a project I'll call "HBase".  The idea is for Hadoop to implement something
similar in spirit to BigTable.  That is, a distributed data store that
places a greater emphasis on scalability than on SQL compatibility
or traditional transactional correctness.

BigTable is neither completely described anywhere, nor is it
necessarily exactly what we want.  So I'm not trying to clone BigTable,
but I am going to draw on it a lot.

My personal view is that BigTable is a great "physical layer" but not yet
a great database system.  A major thing it lacks is a good query language.
Another, freely admitted by the Google people, is any kind of inter-row
locking.  I'm not going to try to solve all these problems, but I would
like HBase to be extendible enough that it's easy to add new query
languages or primitives.

In this mail, I'll describe a system that's pretty similar to BigTable.
I'll send a second one that describes what we might want to change
or add.

Please let me know what you think!

Thanks,
--Mike

--------------------------------------------------------------------------------
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.

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.

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.

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.

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.

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.

Mime
View raw message