Mailing-List: contact common-commits-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Reply-To: common-dev@hadoop.apache.org
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
From: Apache Wiki <wikidiffs@apache.org>
To: Apache Wiki <wikidiffs@apache.org>
Date: Sat, 02 Apr 2011 18:55:17 -0000
Message-ID: <20110402185517.57275.64020@eos.apache.org>
Subject: 
 =?utf-8?q?=5BHadoop_Wiki=5D_Update_of_=22Hbase/DesignOverview=22_by_DougM?=
 =?utf-8?q?eil?=

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Hadoop Wiki" for ch=
ange notification.

The "Hbase/DesignOverview" page has been changed by DougMeil.
The comment on this change is: Per stack, this page is now directing reader=
s to the HBase book..
http://wiki.apache.org/hadoop/Hbase/DesignOverview?action=3Ddiff&rev1=3D21&=
rev2=3D22

--------------------------------------------------

- '''This page was created on 06.03.09 and now is in progress of constructi=
on....'''
- =3D Table of Contents =3D
  =

+ The HBase design overview can now be found in the HBase book at [[http://=
hbase.apache.org/book.html#datamodel]] =

-  * [[#intro|Introduction]]
-  * [[#datamodel|Data Model]]
-   * [[#conceptual|Conceptual View]]
-   * [[#internal|Internal View]]
-  * [[#api|API]]
-  * [[#design|Architecture Design]]
-   * [[#master|HBaseMaster]]
-   * [[#hregionserv|HRegionServer]]
-   * [[#client|HBase Client]]
-  * [[#impl|Implementation]]
- <<Anchor(intro)>>
- =3D Introduction =3D
  =

- This paper is HBase oriented analogue of Google [[http://labs.google.com/=
papers/bigtable.html|Bigtable paper]]. This paper will be self-sufficient. =

- =

- HBase is an [[http://apache.org/|Apache]] open source project whose goal =
is to provide Bigtable-like storage for the Hadoop Distributed Computing En=
vironment. HBase leverages the distributed data storage provided by the [[h=
ttp://hadoop.apache.org/core/docs/current/hdfs_design.html|Hadoop Distribut=
ed File System (HDFS)]] and use [[http://hadoop.apache.org/zookeeper/docs/c=
urrent/zookeeperOver.html|ZooKeeper]] for coordination between HBase nodes.
- =

- Data is logically organized into tables, rows and columns. An iterator-li=
ke interface is available for scanning through a row range and, of course, =
there is the ability to retrieve a column value for a specific row key. Any=
 particular column may have multiple versions for the same row key.
- =

- <<Anchor(datamodel)>>
- =3D Data Model =3D
- =

- Applications store data rows in labeled tables. A data row has a sortable=
 row key and an arbitrary number of columns. The table is stored sparsely, =
so that rows in the same table can have widely varying numbers of columns.
- =

- HBase table is three dimensional sorted map. It maps from Cartesian produ=
ct of row key, column key and timestamp to cell value:
- =

- '''(row:byte[] x column:byte[] x timestamp:Long) -> byte[]'''
- =

- A column name has the form ''"<family>:<label>"'' where <family> and <lab=
el> can be arbitrary byte arrays. A table enforces its set of <family>s (ca=
lled ''"column families"''). Adjusting the set of families is done by perfo=
rming administrative operations on the table. However, new <label>s can be =
used in any write operation without pre-announcing it. HBase stores column =
families physically close on disk, so the items in a given column family sh=
ould have roughly the same read/write characteristics and contain similar d=
ata.
- =

- Only a single row at a time may be locked by default. Row writes are alwa=
ys atomic, but it is also possible to lock a single row and perform both re=
ad and write operations on that row atomically.
- =

- An extension was added recently to allow multi-row locking, but this is n=
ot the default behavior and must be explicitly enabled.
- =

- More details are here [[Hbase/DataModel| The HBase Data Model]]
- =

- <<Anchor(conceptual)>>
- =3D=3D Conceptual View =3D=3D
- =

- Conceptually a table may be thought of a collection of rows that are loca=
ted by a row key (and optional timestamp) and where any column
- may not have a value for a particular row key (sparse).
- =

- <<Anchor(datamodelexample)>>
- ||<:> '''Row Key''' ||<:> '''Time Stamp''' ||<:> '''Column''' ''"contents=
:"'' ||||<:> '''Column''' ''"anchor:"'' ||<:> '''Column''' ''"mime:"'' ||
- ||<^|5> "com.cnn.www" ||<:> t9 || ||<)> "anchor:cnnsi.com" ||<:> "CNN" ||=
 ||
- ||<:> t8 || ||<)> "anchor:my.look.ca" ||<:> "CNN.com" || ||
- ||<:> t6 ||<:> "<html>..." || || ||<:> "text/html" ||
- ||<:> t5 ||<:> "<html>..." || || || ||
- ||<:> t3 ||<:> "<html>..." || || || ||
- =

- <<Anchor(internal)>>
- =3D=3D Internal View =3D=3D
- =

- Although at a conceptual level, tables may be viewed as a sparse set of r=
ows, physically they are stored on a per-column family basis. This is an im=
portant consideration for schema and application designers to keep in mind.
- =

- Pictorially, the table shown in the [[#datamodelexample|conceptual view]]=
 above would be stored as follows:
- =

- ||<:> '''Row Key''' ||<:> '''Time Stamp''' ||<:> '''Column''' ''"contents=
:"'' ||
- ||<^|3> "com.cnn.www" ||<:> t6 ||<:> "<html>..." ||
- ||<:> t5 ||<:> "<html>..." ||
- ||<:> t3 ||<:> "<html>..." ||
- =

- <<BR>>
- =

- ||<:> '''Row Key''' ||<:> '''Time Stamp''' |||| '''Column''' ''"anchor:"'=
' ||
- ||<^|2> "com.cnn.www" ||<:> t9 ||<)> "anchor:cnnsi.com" ||<:> "CNN" ||
- ||<:> t8 ||<)> "anchor:my.look.ca" ||<:> "CNN.com" ||
- =

- <<BR>>
- =

- ||<:> '''Row Key''' ||<:> '''Time Stamp''' ||<:> '''Column''' ''"mime:"''=
 ||
- || "com.cnn.www" ||<:> t6 ||<:> "text/html" ||
- =

- <<BR>>
- =

- It is important to note in the diagram above that the empty cells shown i=
n the conceptual view are not stored since they need not be in a column-ori=
ented storage format. Thus a request for the value of the ''"contents:"'' c=
olumn at time stamp t8 would return no value. Similarly, a request for an '=
'"anchor:my.look.ca"'' value at time stamp t9 would return no value.
- =

- However, if no timestamp is supplied, the most recent value for a particu=
lar column would be returned and would also be the first one found since ti=
mestamps are stored in descending order. Thus a request for the values of a=
ll columns in the row "com.cnn.www" if no timestamp is specified would be: =
the value of ''"contents:"'' from time stamp t6, the value of ''"anchor:cnn=
si.com"'' from time stamp t9, the value of ''"anchor:my.look.ca"'' from tim=
e stamp t8 and the value of ''"mime:"'' from time stamp t6.
- =

- =3D=3D=3D Regions (Row Ranges) =3D=3D=3D
- =

- To an application, a table appears to be a list of tuples sorted by row k=
ey ascending, column name ascending and timestamp descending.  Physically, =
tables are broken up into row ranges called ''regions''. Each row range con=
tains rows from start-key (inclusive) to end-key (exclusive). A set of regi=
ons, sorted appropriately, forms an entire table. Row range identified by t=
he table name and start-key.
- =

- Each column family in a region is managed by an ''Store''. Each ''Store''=
 may have one or more ''!StoreFiles'' (a Hadoop HDFS file type). !StoreFile=
s are immutable once closed. !StoreFiles are stored in the Hadoop HDFS. Oth=
er details:
-  * !StoreFiles cannot currently be mapped into memory.
-  * !StoreFiles maintain the sparse index in a separate file
-  * HBase extends !StoreFiles so that a bloom filter can be employed to en=
hance negative lookup performance. The hash function employed is one develo=
ped by Bob Jenkins.
- =

- <<Anchor(api)>>
- =3D API =3D
- =

- =3D=3D Client API =3D=3D
- =

- See the Javadoc for [[http://hadoop.apache.org/hbase/docs/current/api/org=
/apache/hadoop/hbase/client/HTable.html|HTable]] and [[http://hadoop.apache=
.org/hbase/docs/current/api/org/apache/hadoop/hbase/client/HBaseAdmin.html|=
HBaseAdmin]]
- =

- =3D=3D Scanner API =3D=3D
- =

- To obtain a scanner, a Cursor-like row 'iterator' that must be closed, [[=
http://hadoop.apache.org/hbase/docs/current/api/org/apache/hadoop/hbase/cli=
ent/HTable.html#HTable(org.apache.hadoop.hbase.HBaseConfiguration,%20java.l=
ang.String)|instantiate an HTable]], and then invoke ''getScanner''.  This =
method returns an [[http://hadoop.apache.org/hbase/docs/current/api/org/apa=
che/hadoop/hbase/client/Scanner.html|Scanner]] against which you call [[htt=
p://hadoop.apache.org/hbase/docs/current/api/org/apache/hadoop/hbase/client=
/Scanner.html#next()|next]] and ultimately [[http://hadoop.apache.org/hbase=
/docs/current/api/org/apache/hadoop/hbase/client/Scanner.html#close()|close=
]].
- =

- <<Anchor(design)>>
- =3D Architecture Design =3D
- =

- HBase has Multiple Client - Multiple Server Client-Server architecture.
- =

- There are three major components of the HBase architecture:
-  1. The HMaster (HBase master server)
-  2. The H!RegionServer (HBase region server)
-  3. The HBase client, defined by org.apache.hadoop.hbase.client.HTable
- =

- Each will be discussed in the following sections.
- =

- <<Anchor(master)>>
- =3D=3D HMaster =3D=3D
- =

- There is only one HMaster for a single HBase deployment. To ensure that t=
here is always one active HMaster uses [[http://hadoop.apache.org/zookeeper=
/docs/current/recipes.html#sc_leaderElection|leader election algorithm]] an=
d it's address is stored in !ZooKeaper.
- =

- If HMaster dies, starts new competition between not active "hot ready" HM=
asters using [[http://hadoop.apache.org/zookeeper/docs/current/recipes.html=
#sc_leaderElection|leader election algorithm]].
- =

- HMaster duties:
- =

-  * Cluster initialization
-  * Assigning/unassigning regions to/from H!RegionServers (unassigning is =
for load balance)
-  * Monitor the health and load of each H!RegionServer
-  * Changes to the table schema and handling table administrative functions
-  * Data localization
- =

- =3D=3D Cluster initialization =3D=3D
- =

- While first start master tries to get root and root region directories fr=
om HDFS and after fail creates them and first meta region directory. In nex=
t start master will get information about cluster and it's regions.
- =

- =3D=3D=3D Assigning regions to HRegionServers =3D=3D=3D
- =

- Each region is assigned to only one H!RegionServer or not assigned yet. T=
he first region to be assigned is the ''ROOT region'' which locates all the=
 META regions to be assigned. Each ''META region'' maps a number of user re=
gions which comprise the multiple tables that a particular HBase instance s=
erves. Once all the META regions have been assigned, the master will then a=
ssign user regions to the H!RegionServers, attempting to balance the number=
 of regions served by each H!RegionServer.
- =

- =3D=3D=3D=3D Assigned region =3D=3D=3D=3D
- =

- If region is assigned to some H!RegionServer it means that this region se=
rved by this server. While serving region H!RegionServer handles read/write=
 requests to this region, caches last (not yet flushed) modifications in Me=
mcache and writes all changes to WAL but persistent reliable storage of reg=
ions is provided by HDFS.
- =

- =3D=3D=3D=3D The META Table =3D=3D=3D=3D
- =

- The META table stores information about every user region in HBase which =
includes a H!RegionInfo object containing information such as HRegion id, s=
tart and end keys, a reference to this HRegions' table descriptor, etc. and=
 the address of the H!RegionServer that is currently serving the region. Th=
e META table can grow as the number of user regions grows.
- =

- =3D=3D=3D=3D The ROOT Table =3D=3D=3D=3D
- =

- The ROOT table is confined to a single region and maps all the regions in=
 the META table. Like the META table, it contains a H!RegionInfo object for=
 each META region and the location of the H!RegionServer that is serving th=
at META region.
- =

- Each row in the ROOT and META tables is approximately 1KB in size. At the=
 default region size of 256MB, this means that the ROOT region can map 2.6 =
x 10^5^ META regions, which in turn map a total 6.9 x 10^10^ user regions, =
meaning that approximately 1.8 x 10^19^ (2^64^) bytes of user data.
- =

- Every server (master or region) can get ''ROOT region'' location from !Zo=
oKeeper. =

- =

- =3D=3D=3D Monitor the health of each HRegionServer =3D=3D=3D
- =

- If HMaster detects a H!RegionServer is no longer reachable, it will split=
 the H!RegionServer's write-ahead log so that there is now one write-ahead =
log for each region that the H!RegionServer was serving. After it has accom=
plished this, it will reassign the regions that were being served by the un=
reachable H!RegionServer.
- =

- If HMaster detects overloaded or low loaded H!RegionServer, it will unass=
ign (close) some regions from most loaded H!RegionServer. Unassigned region=
s will be assigned to low loaded servers.
- =

- =3D=3D=3D Changes to the table schema and handling table administrative f=
unctions =3D=3D=3D
- =

- Table schema is set of tables and it's column families. HMaster can add a=
nd remove column families, turn on/off tables.
- =

- =3D=3D Data localization =3D=3D
- =

- Clients can request location of regions to read data directly from region=
 servers.
- =

- <<Anchor(hregionserv)>>
- =3D=3D HRegionServer =3D=3D
- =

- H!RegionServer duties:
- =

-  * Serving HRegions assigned to H!RegionServer
-  * Handling client read and write requests
-  * Flushing cache to HDFS
-  * Keeping HLog
-  * Compactions
-  * Region Splits
- =

- =3D=3D=3D Serving HRegions assigned to HRegionServer =3D=3D=3D
- =

- Each HRegion is served by only one H!RegionServer. When H!RegionServer st=
arts serving HRegion, it reads HLog and all !StoreFiles from HDFS for this =
HRegion. While serving HRegions, H!RegionServer manage persistent storage o=
f all changes to HDFS.
- =

- =3D=3D=3D Handling client read and write requests =3D=3D=3D
- =

- Client communicates with the HMaster to get a list of HRegions and H!Regi=
onServers serving them. Then client sends write/read requests directly to H=
!RegionServers.
- =

- =3D=3D=3D=3D Write Requests =3D=3D=3D=3D
- =

- When a write request is received, it is first written to a write-ahead lo=
g called a ''HLog''. All write requests for every region the region server =
is serving are written to the same ''HLog''. Once the request has been writ=
ten to the ''HLog'', the result of changes is stored in an in-memory cache =
called the ''Memcache''. There is one Memcache for each Store.
- =

- =3D=3D=3D=3D Read Requests =3D=3D=3D=3D
- =

- Reads are handled by first checking the Memcache and if the requested dat=
a is not found, the !StoreFiles are searched for results.
- =

- =3D=3D=3D Cache Flushes =3D=3D=3D
- =

- When the Memcache reaches a configurable size, it is flushed to HDFS, cre=
ating a new !StoreFile and a marker is written to the HLog, so that when it=
 is replayed, log entries before the last flush can be skipped. A flush may=
 also be triggered to relieve memory pressure on the region server.
- =

- Cache flushes happen concurrently with the region server processing read =
and write requests. Just before the new !StoreFile is moved into place, rea=
ds and writes are suspended until the !StoreFile has been added to the list=
 of active !StoreFile for the HStore.
- =

- =3D=3D=3D Keeping HLog =3D=3D=3D
- =

- There is only one ''HLog'' per each H!RegionServer. It is write-ahead log=
 for all changes in serving HRegions for this server.
- =

- There are 2 processes that restricts ''HLog'' size:
-  * Rolling process: when ''HLog'' file reaches a configurable size, ''HLo=
g'' starts to write in new file and closes old one.
-  * Flushing process: when ''HLog'' reaches a configurable size, it is flu=
shed to HDFS.
- =

- =3D=3D=3D Compactions =3D=3D=3D
- =

- When the number of !StoreFiles exceeds a configurable threshold, a minor =
compaction is performed which consolidates the most recently written !Store=
Files. A major compaction is performed periodically which consolidates all =
the !StoreFiles into a single !StoreFile. The reason for not always perform=
ing a major compaction is that the oldest !StoreFile can be quite large and=
 reading and merging it with the latest !StoreFiles, which are much smaller=
, can be very time consuming due to the amount of I/O involved in reading m=
erging and writing the contents of the largest !StoreFile.
- =

- Compactions happen concurrently with the region server processing read an=
d write requests. Just before the new !StoreFile is moved into place, reads=
 and writes are suspended until the !StoreFile has been added to the list o=
f active !StoreFiles for the HStore and the !StoreFiles that were merged to=
 create the new !StoreFile have been removed.
- =

- =3D=3D=3D Region Splits =3D=3D=3D
- =

- When the aggregate size of the !MapFiles for an HStore reaches a configur=
able size (currently 256MB), a region split is requested. Region splits div=
ide the row range of the parent region in half and happen very quickly beca=
use the child regions read from the parent's !MapFile. =

- =

- The parent region is taken off-line, the region server records the new ch=
ild regions in the META region and the master is informed that a split has =
taken place so that it can assign the children to region servers. Should th=
e split message be lost, the master will discover the split has occurred si=
nce it periodically scans the META regions for unassigned regions.
- =

- Once the parent region is closed, read and write requests for the region =
are suspended. The client has a mechanism for detecting a region split and =
will wait and retry the request when the new children are on-line.
- =

- When a compaction is triggered in a child, the data from the parent is co=
pied to the child. When both children have performed a compaction, the pare=
nt region is garbage collected.
- =

- <<Anchor(client)>>
- =3D=3D HBase Client =3D=3D
- =

- HBase is a Heavy Client System. Each client manages its own connection to=
 appropriate server.
- =

- The HBase client is responsible for finding H!RegionServers that are serv=
ing the particular row range of interest. On instantiation, the HBase clien=
t communicates with the H!BaseMaster to find the location of the ROOT regio=
n. This is the only communication between the client and the master.
- =

- Once the ROOT region is located, the client contacts that region server a=
nd scans the ROOT region to find the META region that will contain the loca=
tion of the user region that contains the desired row range. It then contac=
ts the region server that is serving that META region and scans that META r=
egion to determine the location of the user region.
- =

- After locating the user region, the client contacts the region server ser=
ving that region and issues the read or write request.
- =

- This information is cached in the client so that subsequent requests need=
 not go through this process. =

- =

- Should a region be reassigned either by the master for load balancing or =
because a region server has died, the client will rescan the META table to =
determine the new location of the user region. If the META region has been =
reassigned, the client will rescan the ROOT region to determine the new loc=
ation of the META region. If the ROOT region has been reassigned, the clien=
t will contact the master to determine the new ROOT region location and wil=
l locate the user region by repeating the original process described above.
- =

- <<Anchor(impl)>>
- =3D Implementation =3D
- Here will be details of HBase implementation. =

-=20