論文 / 著書情報
Article / Book Information
論題(和文)

Evaluation of Multiple Fat-Btrees on a Parallel Database

Title(English)

Evaluation of Multiple Fat-Btrees on a Parallel Database

著者(和文)

Min LUO, Takeshi Mishima, Haruo YOKOTA

Authors(English)

Min LUO, Takeshi Mishima, Haruo YOKOTA

出典(和文), , ,Citation(English), , ,発行日 / Pub. date2012, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2012 D10-3

Evaluation of Multiple Fat-Btrees on a Parallel Database
Min LUO†

Takeshi MISHIMA‡

Haruo YOKOTA††Dept. of Computer Science, Tokyo Institute of Technology 2-12-1 Ookayama, Meguro-ku, Tokyo, 152-8552 Japan‡NTT Information Sharing Platform Laboratories 3-9-11 Midori-cho, Musashino-shi, Tokyo, 180-8585 Japan
E-mail: †luomin@de. cs.titech.ac.jp, ‡mishima.takeshi@lab.ntt.co.jp, †yokota@cs.titech.ac.jp
Abstract Fat-Btree, as well as the following contribution work for its efficient concurrent control, load balancing and datareliability, has been proposed for the high-speed access in parallel database systems on shared-nothing environment. Because
these contributions are focus on the index accessing and maintenance efficiency only, a single Fat-Btree structure in a parallel
database system is sufficient for all the previous evaluations. However, databases with multiple relations require multiple
Fat-Btrees for the parallel accessing. In this work, we introduce the construction of a multiple Fat-Btree index system for
multiple relations, a study of the throughput in this system using PostgreSQL based DBMS cluster is provided.
Keyword Fat-Btree，Multiple Relation，Parallel Databasehigher

1. Introduction“Clustercomputing”

hasattracted

considerable

attentions in high performance and scalable distributed

scalability and

Map-Reduce

systemasless data loading
well,

which

are

time

than

different

observations from [9], especially for small file I/O.

systems research. In these systems, a large number of

Besides the scalable and efficient data accessing

low-end servers are lined up and work in parallel to act asperformance, the variant of Fat-Btree, a compounda smaller set of high-end servers. Many data accessing

Fat-Btree has been introduced for dynamical access-skew

methods and distributed execution frameworks have beenbalancing ability [1, 10]. It balances the skew without

proposed to coordinate the clusters [2, 3, 4, 5, 6, 7].

high-cost data migration or index reconstruction processes

In these frameworks, Map-Reduce [2] is one of the mostas in ordinary parallel DBMSs, but only modifies the data

famous one and there are numerous academic andaccessing paths to the replicas on other nodes bycommercial implementations of Map-Reduce frameworkswitching the flag identifier in the compound index.

because it offers a simple, functional interface that

The previous work [1, 7, 9 10] have verified the hightransparently executes the computations with a goodscalability and availability in the Fat-Btree, but thesesystem scalability. On the other hand, [5], [6], [7] provide

contributions are focus on the index accessing andmany data accessing methods in parallel databases for data

maintenance efficiency, and only one single Fat-Btree

processing on the “clusters”. Besides the contributions

structure is constructed in a parallel database system.

made over the past two decades, many ongoing academic

However, databases with multiple relations require

projects are also engaged to provide better performance,

multiple Fat-Btrees for the efficient parallel accessing.

scalability and failure tolerance parallel database systems

Furthermore, parallel join-operations could be optimized[11], [12], [13], [14].

by the multiple Fat-Btree parallel indices. Therefore, it is

Although the parallel database and Map-Reduce based
systems may seem to target different applications, it is infact possible to write the parallel processing tasks forimportant to provide a parallel database of multiple
Fat-Btree indices, and study the system performance.
In this paper, we introduce the construction of aalmost all the applications with Map-Reduce jobs or

multiple Fat-Btree indices system for multiple relations.

database queries with these two systems, individually [15].

We also compare and discuss the experimental results ofTherefore, lots of comparisons between these two systems

this system with that of the single Fat-Btree system.

have been carried out for the users’ information. For
instance, [8] showed that DBMSs on shared-nothing

2. Backgroundclusters outperform Map-Reduce by a large factor in a

We briefly review the existing technologies for highvariety of tasks. Additional comparisons in [9] showed

scalable and available parallel index and introduce athat the Fat-Btree [7] based parallel DBMSs possessshared-nothing parallel database based on Fat-Btree index.

2.1 Parallel Indexing Structures

Because of these redundant intermediate index nodes, a

There are two main methods of distributed data

parent node has pointers to their child nodes in theaccessing. DHT-based methods uniformly map nodes andneighbor PE. Thus, the root node has a point path to any

data objects into a single ID space, and each node isleaf node in any PE. Therefore, a client is able to retrieve

responsible for a specific range of the ID space. On the

any tuples from any PE in the system.

other hand, B-tree based parallel index is efficient in

Fig. 2 also shows a query processing flow in this system.

range-query, but skewed range access may lead to obvious

The sequence of the red arrow lines illustrates how to

performance degradation, unless the migration of thehandle a remote query. We assume all the queries are

skewed data and index structure.

querying the Fat-Btree indexed attribute. Their processing
sequences are shown as the red ordered arrows in Fig. 2.
a). Clients send query through a socket connection to
the Fat-Btree system.
b). A thread pool receives these queries and issues a“SQL Server” for processing each query.
c). “SQL Server” extracts the ‘key’ in the query andsend it to “FBT Mgr.” (Fat-Btree manager) through the“Comm. Mgr.” (communication manager).
d). Based on the information at local Fat-Btree, “FBTMgr.” forwards the query to a remote PE, where the target
data is located, through “Comm. Mgr.”.
e). The target PE receives the query, and its local “FBT

Fig.1 Fat-Btree

Mgr.” verifies the ‘key’ is contained by current PE.
f). Start query processing in the DBMS module.

The Fat-Btree [7] is introduced to reduce the update
maintenance and index migration cost, as a parallel B-treeindex. An example of a four-PE Fat-Btree is given in Fig.

f1). If the target page is already in the PGSQL buffer,
return the tuple in the page.
f2). If the target page is not in the PGSQL buffer,

1, where multiple copies of index nodes close to the root

load the target page from Page Server by using the ‘key’ ofnode with relatively low update frequency are replicatedtarget tuple.

on several PEs, while leaf nodes with relatively highupdate frequency are distributed across the PEs. Thus thef2.1). traverse Fat-Btree to find the leaf nodethat contains the ‘key’

index nodes that require synchronization in different PEsf2.2) get the data page No. in the index leaf

are greatly reduced and it also provides load indexf2.3) fetch the page in Page Server by the No.

migration methods [7] than other parallel Btree structures.

f2.4) load the page into PGSQL buffer.
f2.5) return the target tuple in the page

2.2 One Fat-Btree Based Systemf3). Increase the accessing account of the page

We introduce the architecture of a proposed one

If the above query is for a non-Fat-Btree indexed

Fat-Btree based parallel database system here. As shown

relation, DBMS module follows the query handlingin Fig. 2, each PE in this system contains two mainprocess in original PostgreSQL.

modules. The open-source PostgreSQL DBMS is chosen

Note that, in the step-d) above, remote queries have tofor the DBMS module and the Fat-Btree parallel index is

be transmitted between PEs by the “Comm. Mgr” throughimplemented inside the FBT module.

socket connections. This transmission overhead grows

For the relation with Fat-Btree, its tuples are sorted andwhen the number of PEs or clients increases.

every 60 tuples are put into one data-page which is stored
in the Page Server. To index these data-pages by Fat-Btree,

3. Multiple Fat-Btrees System Structure

the min_value of the tuple in a data-page is used as the

3.1 System Structure Discussion

key_id. As described in Sec. 2.1, the root index node isAs described in Sec. 2.2, in the Fat-Btree index module,

replicated on all the PEs, and there are redundantthe independent thread pool handles query issuing, theintermediate index nodes between any neighbor PEs.

Comm. Mgr. handles the remote query transmission, theFBT Mgr. handles Fat-Btree traversing, and the Page

system, when there are multiple threads processing client

Server stores the Fat-Btree indexed data pages. Thesequeries concurrently. Therefore, we duplicated them whenresources are competitive even within the one Fat-Btree

constructing multiple Fat-Btrees.

Fig.2 One Fat-Btree System Structure
Because it requires data I/O between PGSQL buffer andIn the DBMS module, the PostgreSQL source code ishard disk when retrieve a non-Fat-Btree indexed relation.

modified. The index_ids and relation_ids of the Fat-Btrees

While indexing the relation by a Fat-Btree in theandMulti-FBT system will load the relation into the Page

PostgreSQL. A Postgre instance searches the local buffer

Server in memory. Therefore, the Multi-FBT system

based on the relation_id first. If the target data page is in

improves the data retrieving efficiency by avoiding thethe PGSQL buffer, the Postgre returns the target tuple indisk I/Os. In addition, Fat-Btree index will also provide

this buffered page. Otherwise, Postgre starts to load theefficient access to its data pages stored in the Page Server.

page from the corresponding Page Server. The correct FBTFat-Btreeindexedrelationsarerecordedin

Module is chosen by mapping the relation_id to the

3.2 Multiple Fat-Btrees System Structure

corresponding index_id. And the data page is retrieved

In this multiple Fat-Btree system structure, relations arefrom the target Fat-Btree’s Page Server, through therange partitioned across the PEs, and they have their own

correct socket connection to the FBT Module..

FBT modules on every PE to manage their data tuples.
Fig. 3 gives an image of two PEs in our system structure.

4. Experimental Comparison

The Page Servers ‘m’ on each PE stores the data ofIn this section, we provide the evaluations of therelation ‘m’ that is partitioned on its PE. The Fat-Btree for

proposed multiple Fat-Btree parallel database. We check

relation ‘m’ is constructed to index the data pages stored

its throughput scalability when the number of clients inon all these Page Servers ‘m’.

the cluster scales. Then we examine the efficiency of asingle Fat-Btree in the Multi-FBT system by comparing it

generated randomly within the data range. For instance, inwithoriginal

a four-PEs configuration, these queries are: key = randomSingle-FBT system. At last, we check the Multi-FBT

that

of

the

singleFat-Btreeinthe(1, 40000); select* from table X where id = key; update

system scalability when the number of PEs scales.

table X set value += 1 where id = key. In addition, in one
testing course, each client sent 20 queries in series. The

4.1 Environmental Setup

tps (throughput per second) value in our experimental

We initialize two FBT relations in the multiple FBTs

result is the average tps result of 20 testing courses.

system and one FBT relation in the original single FBTIn addition, on every PE, the number of SQL Server

system. Each relation has a 10,000 tuples on each PE, andthreads is set to the same number of clients per PE, thus

each tuple has 134 bytes. Each PE receives simultaneous

all the client threads are processed in parallel, and therequests from its client nodes; the key in each request isrequests in one client thread are processed in serial.

Fig.3 Multiple Fat-Btrees System Structure

TABLE 1
EXPERIMENTAL ENVIRONMENT 1
Process Type:Intel Xeon E5620
Cores:
4*2
Core Frequency
2..4GHz

Hard Drives:
Memory:OS:Java VM:
Network:

1TB, (Model:MB1000EBNCF)
24GB (4GB DDR3 * 6)
Ubuntu11.10
Sun J2SE SDK 1.6.018 Server VM
1000BASE-T

4.1 Evaluation Results

original single-FBT system. We run the experiments on

We provide the experimental results to examine the4-PEs and 8-PEs scales in our cluster. The ‘x’-axis shows

Multi-FBT system efficiency and scalability by evaluating

the number of clients on each PE. For example, value ‘16’

its throughputs. There are up to 8 PEs in our cluster, eachmeans there are 16 clients on one PE querying all the

PE is consisted of the same environment in Table 1.

relations evenly in the system. Thus, for the Multi-FBT

Fig. 4 shows the experiment results of all-select &all-update throughput in the Multi-FBT system andsystem of this experiment (two Fat-Btree relations), eachrelation has 8 clients on each PE.

Fig. 4 Comparison of Multiple-FBT vs. Single-FBT system
In the 4-PEs scale test, the throughput of both systems

Because the cluster used in these experiments has onlyis almost the same, which verifies the extension of another

8-PEs. We used another low-end cluster in our lab to

Fat-Btree index does not introduce obvious overhead into

examine the system scalability when system scales up to

the original single-FBT system. We note the throughput of

16 PEs. Its environment is shown in Table 2.

all-selectsaturatedandreachedplateau

while

the

scalability of all-update also declined in both systems,
when increasing the number of clients. This is because themore number of clients is being served in parallel; themore query transfer messages have to be transmitted andprocessed between PEs in one parallel index.
In the 8-PEs scale test, the Multi-FBT has higher
throughput. Because when the system scales, the numberof remote queries also increases. Compared with thesingle-FBT system, there are two Fat-Btree modules in theMulti-FBT

system

to

share

these

remotequeriestransmission. In addition, because the number of clients
per each relation in Multi-FBT system is times less thanFig. 5 Comparison of the extended indicesthat in Single-FBT system, there are much less conflict
update in index nodes modification. Therefore, theMulti-FBT has better performance when system scales up.
In addition, we compare the extended Fat-Btree
indices in the Multi-FBT system to examine their same
efficiency. Fig. 5 shows the results on our 8-PEs cluster.
In this experiment, all the clients in the Multi-FBT system
query only one of the relations in the same testing. The
results illustrate that the different FBT modules inMulti-FBT system has no obvious difference in theirefficiency.

TABLE 2
EXPERIMENTAL ENVIRONMENT 2
Blade server:
Sun Fire B200x Blade Server
CPU:
AMD Athlon XP-M 1800+ (1.53 GHz)
Network:
1000BASE-T
Gigabit Ethernet
Catalyst 6505 (720GB/s backbone)
Switch:Hard Drives:
TOSHIBA MK3019GAX(30 GB, 5400
rpm, 2.5 inch)
OS:Linux 2.4.20
Java VM:
Sun J2SE SDK 1.6.018 Server VM

In this experiment, we simulate 16 clients on each PE,
and each of the two Fat-Btree indexed relations will be
queried simultaneously by 8 of them. Experimental resultgraph in Figure 6 illustrates that the multiple Fat-Btree
system has over 90% scalability when the number of PEs
is doubled from 4 to 16 in both all-read & all-update
transactions.

Fig. 6 Scalability Evaluation
In conclusion, we have verified the better throughput
and high scalability of the proposed Multi-FBT system byscaling both the number of PEs and clients in theexperiments. The multiple Fat-Btrees provides higher
performance and scalability than that of the previous
single Fat-Btree index system.

5. Future WorkIn this paper, we have introduced the architecture of amultiple Fat-Btree based parallel database system. Ourevaluation results have shown the proposed Multi-FBT
system has higher salability than the single-FBT system
when the number of PEs or clients scales up.
With the multiple Fat-Btree parallel indices, paralleljoin-operation is able to be optimized in the Multi-FBT
system. [16, 17] have shown the parallel B-tree index isable to provide the best parallel join performance thanother well-known non-parallel-Btree based join algorithms.
Because the Fat-Btree has better efficiency than the
traditional parallel Btree used in [17], we believe thisMulti-FBT system is able to provide high join efficiency.
We tend to provide the parallel-join comparisons withother parallel databases in our future work.

Reference[1] M. Luo, A. Watanabe, and H. Yokota, “Compound
treatment of chained declustered replicas using aparallel btree for high scalability and availability”, in
Proc. of the 21st international conference on

Database and expert systems applications (DEXA2010), Vol.6262, pp. 49-63 of LNCS. Springer, 2010[2] Dean and S. Ghemawat. “MapReduce: Simplified
Data Processing on Large Clusters”, In OSDI ’04,．
[3] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A.
Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E.
Gruber. “Bigtable: A distributed storage system forstructured data”, In OSDI, 2006.
[4] S. Ghemawat, H. Gobioff, , and S.-T. Leung. “The
Google file system”, In SOSP, 2003．
[5] H. Boral, W. Alexander, L. Clay, G. Copeland, S.
Danforth, M. Franklin, B. Hart, M. Smith, and P.
Valduriez, “Prototyping Bubba, a highly parallel
database system”, IEEE TKDE, vol. 2, no. 1, pp. 4–
24, 1990．
[6] D. J. Dewitt, S. Ghandeharizadeh, D. A. Schneider, A.
Bricker, H. I. Hsiao, and R. Rasmussen, “The Gamma
database machine project”, IEEE TKDE, vol. 2, no. 1,
pp. 44–62, 1990.
[7] H. Yokota, Y. Kanemasa, and J. Miyazaki,“Fat-Btree: An update conscious parallel directory
structure”, in ICDE '99. IEEE Computer Society, Mar.
1999, pp. 448.457．
[8] A. Pavlo, E. Paulson, A. Rasin, D. J. Abadi, D. J.
DeWitt, S. Madden, and M. Stonebraker. “A
comparison of approaches to large-scale data
analysis”, In SIGMOD, 2009.
[9] M. Luo and H. Yokota, “Comparing hadoop andfat-btree based access method for small file i/oapplications,” in WAIM ’10: Proc. of the 11th
Web-Age Information Management Int’l Conference,
July, ser. LNCS, vol. 6184. Springer, 2010.
[10] M. Luo, and H. Yokota, “An Evaluation on Dynamic
Access-Skew Balancing Performance of Compound
Parallel Btree for Chained Declustering Parallel
Systems”, in Proc. of the 3rd Forum on Data
Engineering and Information Management (DEIM),
Feb. 2011[11] http://dev.mysql.com/doc/refman/5.1/en/overview.ht
ml[12] Wu, S. and Kemme, B. 2005. “Postgres-R(SI):
Combining Replica Control with Concurrency
Control Based on Snapshot Isolation”, in Proc. of the
21st Int’l Conf. on Data Engineering, ICDE ’2005,
April 05 – 08 Washington, DC. pp. 422-433[13] E. Pacitti, M. T. Ozsu, and C. Coulon, “Preventive
multi-master replication in a cluster of autonomous
databases”, in In Euro-Par, 2003, pp. 318-327.
[14] http://slony.info/documentation/failover.html[15] A. Gupta, D. Agrawal, and A. El Abbadi,“Approximate
range
selection
queriesinpeer-to-peer”, in Proc. Conf. Innovative Data
Systems Research (CIDR), 2002.
[16] Jianzhong Li, Hong Gao, Jizhou Luo, Shengfei Shi,and Wei Zhang. “InfiniteDB: a pc-cluster based
parallel massive database management system”, in
Proc. of the 2007 ACM SIGMOD Int’l Conf. on
Management of data (SIGMOD '07). ACM, New York,NY, USA, 899-909.
[17] Jianzhong Li, Wenjun Sun, and Yingshu Li. “Parallel
Join Algorithm based on Parallel B+-trees”, in Proc.
of the 3rd Int’l Symposium on Cooperative Database
Systems for Advanced Applications (CODAS '01).
IEEE Comp. Society, Washington DC, USA, 178-.,.