Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)

iu Phi Tác V Trong H Thng MAP-REDUCE
Da Trên Tính a Phưng Ca D Liu
Hunh Tn t
Hc viên Khoa Công Ngh Thông Tin II
Hc Vin Công Ngh Bưu Chính Vin Thơng
Email:

Bùi Xn Lc
Khoa K Thut
i Hc Tân To
Email:

Abstract— Vn  d liu a phưng là mt vn  quan trng
cn xem xét khi thit k thut tốn iu phi cơng vic cho h
thng Map-Reduce. Gn ây, bài báo k thut [13] ã gii quyt
ưc vn  d liu a phưng bng vic  xut mt kin trúc
hàng i mi và mt thut toán iu phi tác v ánh x (map
task) da trên chính sách JSQ (Join the Shortest Queue) kt hp
vi chính sách MaxWeight. Tuy nhiên, bài báo [13] ch xem xét
trưng hp  sao lưu d liu là mt giá tr c th bng 3. Trên
thc t, tu thuc vào cu hình h thng,  sao lưu d liu có th
ln hn hoc nh hn 3. Trong bài báo này, chúng tôi m rng
nghiên cu ca bài báo [13] và so sánh hiu sut h thng trong
các trưng hp  sao lưu d liu có giá tr khác nhau, t ó
giúp ngưi vn hành h thng Map-Reduce có thêm mt tiêu chí
 chn các thơng s h thng phù hp.

thêm  to ra kt qu cui cùng. Khi thc hin các tác v

“map”, mt trong nhng xem xét quan trng là vic phân b
tác v gn vi máy tính lưu tr khi d liu u vào cho tác v
ó; vn  này cịn ưc gi là vn  d liu a phưng.
i vi mi tác v, chúng ta gi mt máy tính là mt máy
tính a phưng cho tác v nu on d liu liên quan n tác
v này ưc lưu tr ngay ti máy tính ó, và chúng ta gi tác
v này là mt tác v a phưng trên máy tính. Trong trưng
hp cịn li (ngha là d liu cn thit cho tác v khơng ưc
lưu tr ti máy tính), máy tính ó ưc gi là máy tính t xa
cho tác v, và tưng ng vi tác v này ưc gi là tác v t
xa trên máy tính. Tính a phưng nên ưc xem xét n trong
vic phân b các tác v “map” chy trên các máy tính. Vic
ci thin tính a phưng có th gim thi gian x lý ca các
tác v “map” và lưu lưng ti t mng khi mt vài tác v
“map” cn ly d liu t xa. Tuy nhiên, vic gán tt c các tác
v n các máy tính a phưng có th dn n mt s phân
phi khơng ng u ca các tác v gia các máy, tc là mt
s máy b tc nghn trong khi các máy khác nhàn ri. Vì vy
chúng ta cn phi cân bng gia các d liu a phưng và cân
bng ti trong Map-Reduce. ây chính là ng lc thúc y
các nhà nghiên cu tìm hiu, ci tin,  xut các thut tốn
mi nhm nâng cao hiu qu s dng và hiu sut h thng.
Mt s thut toán iu phi ưc  xut trưc ây trong h
thng Map-Reduce/Hadoop  ci thin d liu a phưng.
Thut toán FIFO scheduler trong Hadoop [12] vi vic iu
phi mt máy sn sàng  phc v tác v “map” t công vic
head-of-line vi d liu gn nht n máy tính. Mc dù mt vài
ti ưu hố a phưng ã ưc thc hin, vn  head-of-line
blocking  a phưng vn tn ti và hiu sut thông lưng vn
b hn ch. Thut toán Fair Scheduler trong Hadoop [6] vi k

thut iu phi chm tr ưc s dng  ci thin a phưng.
Khi mt máy tính yêu cu mt tác v mi, nu công vic ưc
iu phi tip  công bng không có tác v a phưng sn có
cho máy tính này, thì cơng vic tm thi b qua và máy tính
kim tra các công vic tip theo trong danh sách. K t khi
máy tính ưc gii phóng nhanh, nhiu tác v a phưng ưc
phc v. Tuy nhiên, máy tính ang rnh s ưc gii thiu t
mt máy sn sàng có th b qua tt c các cơng vic khi nó
khơng th tìm mt tác v a phưng và vic cân bng gia
thi gian rnh và a phưng là không rõ ràng. Thut toán iu
phi Quincy ưc thit k cho Dryad [7] vi mt mơ hình phân
phi máy tính cho phép lưu d liu phc tp hn Map-Reduce.
Quincy s dng tng s d liu truyn như n v o a

Keywords- in toán ám mây, Map-Reduce, d liu a
phưng, Hadoop.

I.

GII THIU

Ngày nay, chúng ta ang sng trong thi i thông tin, vi
s tng trưng bùng n thông tin theo cp s nhân. Nhng
công ty hàng u v công ngh thông tin như Google, Yahoo!,
Amazon, Microsoft, Facebook, Twitter… ang i mt vi
mt khi lưng d liu khng l. S tng trưng này òi hi
các chin lưc mi  x lý và phân tích d liu. in toán
ám mây ưc phát trin và Map-Reduce/Hadoop ang là mt
mơ hình tính tốn mnh m ưc ng dng trong in toán
ám mây. Vic x lý các tp d liu quy mô ln ã tr thành

mt vn  ngày càng quan trng và y thách thc vi s
lưng d liu ưc to ra bi các mng xã hi trc tuyn,
nghiên cu khoa hc… Map-Reduce/Hadoop [9]-[15] là mt
framework n gin nhưng mnh m  x lý các tp d liu
quy mô ln trong môi trưng phân tán và x lý song song, và
ang ưc s dng rng rãi trong thc t. Mt cm máy tính
Map-Reduce có th bao gm hàng chc ngàn máy tính [2]. Các
d liu ưc lưu tr thưng ưc t chc trên h thng phân
phi tp tin (ví d h thng tp tin Google (GFS) [10], h thng
tp tin phân tán Hadoop (HDFS) [4]) trong ó phân chia mt
tp d liu ln thành nhiu on d liu và lưu tr thành nhiu
bn sao (mc nh là 3 bn sao) ca mi on d liu trên các
máy tính khác khau. Mt yêu cu x lý d liu trong
framework Map-Reduce ưc gi là mt công vic (job) bao
gm hai loi tác v: “map” (“ánh x”) và “reduce” (“gim”).
Mt tác v “map” c mt on d liu và x lý nó  to ra
kt qu trung gian (các cp khố – giá tr). Sau ó tác v
“reduce” ly kt qu trung gian và thc hin các tính tốn

ISBN: 978-604-67-0635-9

24
24


Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)

phưng và mã hố nó vào trong mơ hình giá. Sau ó, quyt
nh iu phi ưc thc hin bng cách gii quyt vn  chi

phí thp nht. Ngồi ra, cịn có rt nhiu cơng trình nghiên cu
ã  xut thut toán iu phi  gii quyt vn  ci thin
d liu a phưng trong Map-Reduce và ưc trin khai trong
thc t. Tuy nhiên chưa có cơng trình nghiên cu nào ưa ra
thut tốn iu phi cơng vic có th t ưc min dung
lưng y  (full capacity region)  gim thiu thi gian ch
i và tc nghn trong mt cm máy tính Map-Reduce.
Vi tình hình ó, mt kin trúc hàng i mi và mt thut
toán iu phi tác v “map” ã ưc  xut gn ây trong bài
báo k thut [13]. Kin trúc và thut toán này gii quyt ưc
vn  d liu a phưng bng vic t ưc min dung lưng
y  nhm gim thiu thi gian ch i và tc nghn trong
mt cm máy tính Map-Reduce. Kin trúc hàng i này gm
mt hàng i a phưng tưng ng vi tng máy tính  lưu
tr các tác v a phưng cho các máy này và mt hàng i
chung cho tt c các máy tính. Da trên kin trúc hàng i này,
các tác gi nghiên cu mt thut toán iu phi tác v ánh x
(map) vi hai giai on: khi mt tác v mi n nó s ưc
chuyn n mt trong 3 hàng i tưng ng vi 3 máy tính a
phưng hoc hàng i chung bng chính sách Join the Shortest
Queue (JSQ) và khi mt máy tính rnh nó s chn mt tác v
t hàng i a phưng tưng ng vi nó hoc hàng i chung
bng cách s dng chính sách MaxWeight [14].
Có th d dàng thy rng các tác gi ca [13] ch xem xét
trưng hp  sao lưu d liu bng 3 (ngha là mi on d
liu có 3 bn sao ưc lưu tr  3 máy tính khác nhau). Trên
thc t, tu thuc vào cu hình h thng,  sao lưu d liu có
th ln hn hoc nh hn 3. Trong bài báo này, chúng tôi m
rng nghiên cu ca bài báo [13] bng vic xem xét và so sánh
hiu sut h thng trong các trưng hp  sao lưu d liu có

giá tr khác nhau. C th, chúng tôi chng minh lý thuyt và
mô phng h thng dùng công c mô phng OMNeT++ cho
trưng hp  sao lưu d liu K có giá tr tng quát; ng thi
so sánh hiu sut ca h thng vi các trưng hp dưi ti
(underload), gn ti (load), và q ti (overload). Chúng tơi tin
rng nhng kt qu có ưc s giúp ngưi vn hành h thng
Map-Reduce có thêm mt tiêu chí  chn các thơng s h
thng phù hp.
Phn còn li ca bài báo ưc t chc như sau. Trong phn
II, chúng tơi miêu t mơ hình h thng. Trong phn III, chúng
tơi trình bày chng minh lý thuyt v ti ưu hố thơng lưng.
Phn IV cung cp các kt qu mô phng. Cui cùng, chúng tôi
kt lun bài báo trong phn V.
II.

MƠ HÌNH H THNG

Chúng tơi xem xét mt mơ hình thi gian ri rc cho mt cm
máy tính bao gm M máy tính, ưc ánh s th t 1, 2, …,
M. Chúng tôi gi nh rng mi công vic n yêu cu mt tác
v “map”, và mi tác v “map” yêu cu mt mu d liu u
vào. Chúng tôi cng gi s rng mi mt mu d liu ưc
sao lưu  K (K > 1) máy tính khác nhau. Vì vy mi tác v
liên quan n K máy tính a phưng. Phi mt mt thi gian
dài hn cho mt máy tính  x lý mt tác v nu on d liu
cn thit không ưc lưu tr ti a phưng k t khi máy tính

cn ly d liu u tiên. Các tác v có th phân loi theo các
máy tính a phưng mà chúng liên kt vi nhau. i vi mi
tác v chúng tôi gán ch s ca K máy tính cc b theo mt

trt t tng dn vào trong mt vector  hình thành các loi tác
v:
 ∈   ,  , … ,    ∈ 1,2, … ,  ,  <  < ⋯
<  .

Các ký hiu  ∈  ch rng máy tính m là mt máy tính a
phưng cho kiu tác v . Chn ký hiu ℒ biu th cho tp
hp các kiu công vic tn ti trong cm và  = ℒ.

A. Quá trình n và quá trình phc v

Cho   biu din tng s lưng kiu công vic  n h
thng cho n thi im bt u ca khe thi gian t. Chúng tôi
gi s rng quá trình n là hàm tng theo thi gian vi tc 
n  . Ti mi máy tính thi gian phc v công vic ưc gi
s là tuân theo phân phi hình hc (geometric distribution).
Tham s phân phi hình hc cho mt cơng vic ti mt máy
tính a phưng là  và ti máy tính t xa là . Q trình phc
v ca mt cơng vic có th ưc xem như là mt chui các
s kin c lp vi xác sut thành công  (hoc ) và chui s
kin s dng mt khi chúng ta có mt s thành cơng tc là
mt cơng vic ã hồn thành. Trong mơ hình này chúng tơi gi
s  > , ngha là, thi gian phc v trung bình ca cơng vic
a phưng là ít hn thi gian phc v cơng vic t xa. Chú ý
rng các giá tr khác nhau ca  và  th hin hiu qu x lý
khác nhau i vi d liu a phưng.

B. Thut tốn iu phi cơng vic (task scheduling algorithm)

iu phi công vic là vic gán các cơng vic n các máy

tính  x lý. Vi vn  d liu a phưng, thut tốn iu
phi cơng vic có th nh hưng áng k n hiu qu ca h
thng. Trong bài báo này, chúng tôi xem xét mt thut tốn
iu phi cơng vic bao gm hai phn, nh tuyn và iu
phi, ưc  xut trong bài báo k thut [13]. H thng iu
phi bao gm mt kin trúc hàng i ưc minh ho bi Hình
1. Máy Master duy trì mt hàng i các cơng vic cc b cho
mi máy tính m, ưc ký hiu là  và ưc gi là hàng i
cc b. Có mt hàng i chung cho tt c các máy tính ưc
ký hiu là  (hoc ôi khi ngưi ta ký hiu  ) và ưc
gi là hàng i chung t xa (common remote queue). Chúng
tôi dùng mt vector chiu dài hàng i  =   , … ,
 ,    ký hiu cho chiu dài các dàng i ti thi
im bt u ca khe thi gian t. Khi mt công vic n, máy
Master nh tuyn công vic này n mt hàng i trong h
thng hàng i. Khi mt máy tính là idle, nó chn mt cơng
vic t hàng i a phưng tưng ng hoc hoc t hàng i
chung t xa  phc v. Hai bưc này ưc minh ho trong
Hình 1. Chúng ta gi bưc u tiên là nh tuyn (routing) và
bưc th hai là iu phi (scheduling). Thut toán c th như
sau.
Bưc 1 - Join the Shortest Queue (JSQ) Routing: Khi mt
cơng vic n, máy tính Master s so sánh chiu dài hàng i
ca K hàng i cc b và hàng i chung t xa và sau ó nh
tuyn n mt hàng i có chiu dài ngn nht. Cho , 

2525


Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)

Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)

nu máy tính m là idle tc là   = ,   là 1 hoc 2
ưc quyt nh bi máy tính Master bng thut tốn
MaxWeight. Chúng tôi dùng vector iu phi  =
 ,  , … ,    biu din quyt nh iu phi cho
tt c các máy tính.

và   biu din các công vic  ưc giao tưng ng vi
 và  . Các công vic ưc giao n cho mi hàng i có
th
ưc
biu
din
bng
vector
n
 =  , … ,  ,  ưc nh ngha như sau:
  =  

 ∈


, ,  = 1,2, … , ,

C. ng hc hàng i (queue dynamics)

Trong khe thi gian t, u tiên máy tính Master kim tra thơng
tin trng thái làm vic  và chiu dài hàng i . Sau ó
các cơng vic n ti máy tính Master và máy tính Master

thc hin nh tuyn và iu phi, cho ta thông tin
. Chúng tôi nh ngha:

 =    .



 
=   = 1,
   = , 
 
 
 
= , 
=   = 2.


Vi nh ngha trên, dch v t máy tính m cho hàng i a
phưng  và hàng i t xa  là hai bin Bernoulli


 và  
 . Do ó, các
 
dch v ưc áp dng cho mi hàng i có th ưc biu din
 , 

 
bng vector dch v  =  , … , 
 vi

tc  dch v  hoc . Khi ó chiu dài các hàng i tho
mãn các phưng trình sau:
Hàng i a phưng (Local queues): vi m=1,2, …, M,
 
   ,
   1 =        

trong ó:

Hình 1: Kin trúc hàng i và thut tốn iu phi

       1,
  =   
      = .

Bưc 2 - MaxWeight Scheduling: Nu mt máy tính m va
hồn thành mt cơng vic ti khe thi gian t-1, thì trng thái
làm vic ca nó là idle. Nu khơng, máy tính phi thc hin
mt cơng vic a phưng hoc mt công vic t xa. Cho
  = , 1, 2 biu din tưng ng cho 3 trng thái: idle,
ang thc hin mt công vic a phưng, và ang thc hin
mt công vic t xa. Vector trng thái làm vic   =
 ,  , … ,   và vector chiu dài hàng i 
ưc báo cáo v cho máy tính Master ti thi im bt u ca
khe thi gian t và máy tính Master quyt nh iu phi cho
tt c các máy tính da trên  và . Các máy tính idle
ưc iu phi bi thut tốn MaxWeight: gi s máy tính m
là idle ti slot thi gian t, thì nó phc v mt cơng vic a
phưng nu     và phc v mt công vic t
xa cho các trưng hp khác. Các máy tính khác tip tc thc

hin các cơng vic chưa hồn thành tc là thc hin các công
vic không ưu tiên. Cho   biu din quyt nh iu phi
ca máy tính m ti slot thi gian t, thì nó là mt hàm ca 
và   và

Hàng i t xa (Remote queue)



  1 =       

trong ó:





 =  





  


 
,

 


,


∈

vi là tp các máy tính mà nó phc v mt vài cơng vic
t hàng i t xa ti slot thi gian t. Chú ý rng có th có mt
vài máy tính c gng phc v hàng i t xa nhưng tht bi do
thiu cơng vic.
Chúng ta có th vit li phưng trình ng hc hàng i như
sau:
  1 =       ,

.
vi  =  , … ,  , 

(1)

Trong trưng hp thi gian phc v là xác nh, quá trình
hàng i ,    là chui Markov. Tuy nhiên thi gian
phc v trong mô hình này là ngu nhiên và khơng ng nht
do vn  d liu a phưng. Do ó chúng ta cn xem xét
thêm các vector trng thái làm vic ; c th,  cùng
vi  s to thành chui Markov , ,    .
Chúng ta gi nh trng thái ban u là ,  =
 ,   và không gian trng thái     
,1,2 bao gm tt c các trng thái mà nó có th t ưc

1

,
  =  
2.

Lưu ý rng   cho bit hàng i máy tính m ã ưc iu
phi  phc v. Nó ch có giá tr 1 hoc 2 k t khi ưc iu
phi  phc v mt công vic a phưng hoc mt công vic
t xa. Nu máy tính m khơng idle tc là   = 12 ,
chúng ta thit lp iu phi   bng vi  . Tuy nhiên,

26

26


Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)

chn ngồi Ʌ. Do ó thut tốn này là ti ưu thông lưng và Ʌ
cng là min dung lưng ca h thng.

t trng thái ban u, vi  là tp s nguyên không âm. D
thy rng chui Markov này là ti gin (irreducible) và khơng
tun hồn (aperiodic).

Chng minh:
Chng minh này tưng t như chng minh ca nh lý 1
trong bài báo k thut [13], tuy nhiên, [13] ch xét trưng hp
K=3. Vi trưng hp K tng quát, ta thy rng tp ℒ (tp hp
các kiu công vic) s thay i, và  = ℒ cng thay i. Tuy

nhiên, chng minh ca nh lý 1 trong [13] vn có th ưc
m rng cho trưng hp K tng quát. Vì lý do gii hn v 
dài bài báo, chúng tôi ch nêu ý tưng chng minh  ây và
mi ngưi c tham kho bài báo [13] v chi tit. Ý tưng ca
chng minh như sau: Vì , ,    là mt chui
Markov ti gin và khơng tun hồn, s n nh ưc nh
ngha là s hi quy dưng (positive recurrence) ca chui
Markov này. Da theo nh lý Foster-Lyapunov m rng, ta
ch cn tìm mt s dưng T và mt hàm Lyapunov sao cho 
trôi ca hàm Lyapunov (Lyapunov drift) sau T khe thi gian b
chn nu  bên trong mt tp con hu hn ca không gian
trng thái và là âm nu  bên ngoài tp con này. C th hàm
Lyapunov ưc chn có dng:

TI U HỐ THƠNG LNG

III.

Trong phn này, chúng tơi s chng minh tính nng ti ưu hố
thơng lưng ca thut tốn iu phi ưc trình bày  phn
trưc. Chú ý rng tính nng này ã ưc chng minh trong bài
báo k thut [13] vi trưng hp K=3; trong phn này chúng
tôi m rng chng minh vi trưng hp K tng quát.
Ý tưng ca chng minh như sau: Trưc tiên chúng ta xác
nh min chn ngoài (outer bound) ca min dung lưng ca
h thng. Sau ó chúng ta chng minh rng thut tốn iu
phi trên có th n nh hố bt k vector tc  n nào
thuc min chn ngồi này (n nh hố theo ngha các hàng
i u n nh và không tng theo thi gian). iu ó có
ngha là thut tốn iu phi trên là ti ưu thông lưng, và

min dung lưng cng trùng vi min chn ngoài.
A. Min dung lng (capacity region)
i vi bt k kiu công vic  ∈ ℒ, chúng ta gi nh rng s
lưng kiu công vic  n ưc phân b n máy m có tc 
, , vi  =  
, 
, . Tp tc  
 



 
   
,  =   =  


 ∈ℒ,,…,

Khi ó ta có th chng minh rng (tham kho chi tit trong
[13])  trôi Lyapunov sau T khe thi gian t t0 ưc chn bi
 ,    ≤ 2     vi hng s  > . nh

ưc gi là mt phân tích (decomposition) ca vector tc 
 =   ,  , … ,  . Vi vector tc  n , xét mt máy
tính m bt k, iu kin cn  h thng ưc n nh là khi
lưng tác v trung bình ưc phân b cho máy tính m trong
mt khe thi gian có th ưc phc v ht trong khe thi gian
ó, có ngha là:



∈



,
,
 
 ≤ 1,





ngha tp ß = ,  ∈   ⋯    ≤    vi
 >  bt k. Khi ó ß là mt tp con hu hn ca khơng
gian trng thái vi ,  ∈ ß , ,  ≤  và ,  ∈
ß, ,  ≤ . iu này tho mãn nh lý Foster-Lyapunov
m rng và hồn thành chng minh.

(2)

 ∉



IV.

trong ó v trái là thi gian máy tính m cn có  phc v
lưng tác v trung bình phân b cho nó trong mt khe thi
gian, vi tc  dch v  cho công vic a phưng và  cho

công vic t xa.
Gi Ʌ là tp giá tr tc  n mà mi phn t phân tích ca nó
tho mãn (2). C th:
Ʌ =   =  ,  , … ,  


 =   , , ∀ ∈ ℒ,

Trong phn trưc chúng tơi ã chng minh tính ti ưu hố
thơng lưng ca thut toán iu phi ưc  xut ngay c vi
 sao lưu d liu K tng quát. Tuy nhiên, câu hi ưc t ra
là hiu sut h thng ca thut toán iu phi thay i th nào
vi các giá tr K khác nhau. Chúng tôi s tr li câu hi ó
trong phn này vi các kt qu mơ phng.
Chúng tơi mơ phng thut tốn vi các giá tr  sao lưu
d liu: K = 2, 3, 4, 6, 8, 10, và so sánh hiu sut ca h thng
vi các trưng hp dưi ti (underload), trong ti (load) và
quá ti (overload). Tiêu chun ánh giá da vào tng s lưng
các tác v còn tn ti trong các hàng i a phưng và hàng
i t xa sau mi khe thi gian.

(3)



,  , ∀ ∈ ℒ, ∀ = 1, … , 


 ∈




,


 

∉



,


 ≤ 1, ∀ = 1, … , 

KT QU MƠ PHNG

.

Chúng tơi thc hin mơ phng trên h thng vi 400 máy
tính và mt tp d liu ưc phân b ng u trên 320 máy
trong s ó. Thi gian phc v cho tác v a phưng và tác
v t xa tuân theo phân phi hình hc vi tham s tưng ng
là  = .8 và  = .2. Vì vy tng dung lưng ca h thng
(tính theo s tác v n trong mt n v thi gian) bng  =
320 α + 80γ = 272. Tng thi gian chy ca h thng là 2000
n v thi gian.

D thy rngɅ chính là min chn ngồi ca min dung lưng

ca h thng.
B. Tính ti u thơng lng (throughput optimality)
nh lý 1: Thut toán iu phi ưc  xut  Phn II.B có
th n nh h thng vi vector tc  n bt k thuc min

27

27


HộiHội
Thảo
Quốc
GiaGia
2015
và Cơng
CơngNghệ
NghệThơng
Thơng
(ECIT
2015)
Thảo
Quốc
2015vềvềĐiện
ĐiệnTử,
Tử,Truyền
TruyềnThơng
Thơng và
TinTin
(ECIT

2015)
Bng 1 cho thy kt qu trung bình theo thi gian ca tng
s lưng tác v còn trong hàng i (tưng ng vi tng chiu
dài ca tt c các hàng i) vi các giá tr khác nhau ca tc
 tác v n () và  sao lưu d liu (K). Kt qu này cng
ưc th hin trong  th Hình 2. C th, Hình 2 biu din
s bin thiên ca tng chiu dài trung bình hàng i theo s
thay i ca tc  tác v n ng vi các trưng hp K = 2,
3, 4, 6, 8, 10. Ta có th thy rng khi tc  n nh (dưi ti
– underload), tng chiu dài trung bình hàng i tng dn khi
K tng dn, ngha là giá tr K nh s có hiu sut cao hn trong
trưng hp này. Tuy nhiên, khi tc  n tng dn (ti tng
dn), tng chiu dài trung bình hàng i ng vi giá tr K nh
tng nhanh hn tng chiu dài trung bình hàng i ng vi giá
tr K ln. c bit, khi tc  n gn ti (gn dung lưng h
thng), tng chiu dài trung bình hàng i gim dn khi K
tng dn, ngha là giá tr K ln s cho hiu sut cao hn.

A. Trng hp di ti (underload)
Vi trưng hp này chúng ta cho h thng chy vi tc 
tác v n  = 100 (tác v trong mt n v thi gian). Chy
vi K = 2, 3, 4, 6, 8, 10 vi thi gian 2000 n v thi gian.

Chúng ta theo dõi tng s lưng tác v tc thi trong h
thng  quan sát s n nh. Hình 3 cho thy con s i din
này n nh theo thi gian, qua ó thy rõ s n nh ca h
thng. Vi kt qu như Hình 3 chúng ta thy rng hiu sut h
thng vi  sao chép d liu K = 2, 3, 4, 6, 8, 10 luôn luôn n
nh theo thi gian. Tuy nhiên vi trưng hp này  sao chép
d liu K = 2 tt hn các trưng hp khác.


Hình 3: Kt qu trưng hp  = 100

B. Trng hp gn ti (load)

Vi trưng hp này chúng ta cho h thng chy vi tc  tác
v n ln lưt là  = 200 (tác v trong mt n v thi gian),
 = 250 (tác v trong mt n v thi gian),  = 260 (tác v
trong mt n v thi gian), và  = 270 (trong mt n v thi
gian). Chy vi K = 2, 3, 4, 6, 8, 10 vi thi gian 2000 n v
thi gian.

Hình 2: Hiu sut thông lưng h thng
Bng 1: Kt qu s lưng cơng vic trung bình trong h thng
CCCCCCSSCC
K



100
120
140
160
180
200
220
230
240
250
260

272
300

K=2

K=3

K=4

K=6

K=8

K=10

42
65
114
371
503
596
713
798
937
1613
8277
22941
57792

48

66
89
122
330
445
530
584
663
849
7673
22514
57420

55
75
96
122
159
347
444
490
555
690
7608
22456
57438

68
90
113

138
166
203
344
390
444
544
7209
22042
57050

77
101
127
153
180
211
270
349
398
482
7280
22205
57246

85
110
136
163
191

220
258
316
371
437
6788
21752
56792

Vi kt qu như Hình 4, Hình 5 chúng ta thy rng tng s
lưng tác v tc thi trong h thng vn n nh theo thi
gian. Kt qu Hình 6, Hình 7 cho thy tng s lưng tác v
tc thi trong h thng có chiu hưng quá ti. Tuy nhiên vi
các trưng hp này  sao chép d liu K = 10 tt hn các
trưng hp khác.

K tip, chúng tôi xem xét quá trình thay i ca tng chiu
dài hàng i theo thi gian ng vi các giá tr khác nhau ca 
và K.

Hình 4: Kt qu trưng hp  = 200

28

28


HộiHội
Thảo
Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)

Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
V.

KT LUN

Trong bài báo này chúng tôi ã k tha và m rng kt qu
nghiên cu ca các tác gi W. Wang, K. Zhu, L. Ying, J. Tan,
và L. Zhang trong bài báo k thut [13] cho trưng hp  sao
lưu d liu có giá tr tng quát. Trong h thng Map-Reduce
thc t,  sao lưu d liu là mt thông s quan trng và
chúng tôi tin rng nhng kt qu có ưc trong bài báo này s
giúp ngưi vn hành h thng Map-Reduce có thêm mt tiêu
chí  chn các thơng s h thng phù hp.
TÀI LIU THAM KHO
Hình 5: Kt qu trưng hp  = 250

[1]

[2]

[3]

[4]

[5]

Hình 6: Kt qu trưng hp  = 260

[6]


[7]

[8]

[9]

[10]

Hình 7: Kt qu trưng hp  = 270

[11]

C. Trng hp quá ti (overload)

Vi trưng hp này chúng ta cho h thng chy vi tc  tác
v n ln lưt  = 272 (tác v trong mt n v thi gian), 
= 300 (tác v trong mt n v thi gian). Chy vi K = 2, 3,
4, 6, 8, 10 vi thi gian 2000 n v thi gian.

[12]
[13]

Vi kt qu Bng 1 chúng ta thy rng ng vi c hai giá tr 
trong trưng hp này tng s lưng tác v trung bình theo thi
gian là tưng ưng nhau cho tt c các giá tr ca K, và h
thng luôn luôn quá ti.

[14]

[15]

[16]

29

29

C. Abad, Y. Lu, and R. Campbell (2011), “DARE: Adaptive data
replication for efficient cluster scheduling” in IEEE Int. Conf. Cluster
Computing (CLUSTER), pp. 159–168.
G. Ananthanarayanan, S. Agarwal, S. Kandula, A. Greenberg, I. Stoica,
D. Harlan, and E. Harris (2011), “Scarlett: coping with skewed content
popular in MapReduce clusters” in Proc. European Conf. Computer
Systems (EuroSys), pp. 287–300.
J. Dean and S. Ghemawat (2008), “MapReduce: simplified data
processing on large clusters” ACM Commun, vol 51 (no. 1), pp. 107–
113.
K. Shvachko, H. Kuang, S. Radia, and R. Chansler (2010), “The hadoop
distributed file system” in IEEE Symp. Mass Storage Systems and
Technologies (MSST), pp. 1–10.
L. Tassiulas and A. Ephremides (1992), “Stability properties of
constrained queueing systems and scheduling policies for maximum
throughput in multihop radio networks” IEEE Trans. Autom. Control,
vol 4, pp. 1936–1948.
M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker, and
I. Stoica (2010), “Delay scheduling: a simple technique for achieving
locality and fairness in cluster scheduling” in Proc. European Conf.
Computer Systems (EuroSys), pp. 265–278.
M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, and A.
Goldberg (2009), “Quincy: fair scheduling for distributed computing
clusters” in Proc. ACM Symp. Operating Systems Principles (SOSP),

Big Sky, MT, pp. 261-276.
S. T. Maguluri and R. Srikant (2013), “Scheduling jobs with unknown
duration in clouds” in Proc. IEEE Int. Conf. Computer Communications
(INFOCOM), Turin, Italy.
S. T. Maguluri, R. Srikant, and L. Ying (2012), “Heavy traffic optimal
resource allocation algorithms for cloud computing clusters” in Int.
Teletraffic Congr. (ITC), Krakow, Poland.
S. Ghemawat, H. Gobioff, and S.-T. Leung (2003), “The google file
system” in Proc. ACM Symp. Operating Systems Principles (SOSP), pp.
29–43.
S. Kavulya, J. Tan, R. Gandhi, and P. Narasimhan (2010), “An analysis
of traces from a production MapReduce cluster” in Proc. IEEE/ACM Int.
Conf. Cluster, Cloud and Grid Computing (CCGRID), pp. 94–103.
T. White (2010), Hadoop: The definitive guide, Yahoo Press.
W. Wang, K. Zhu, L. Ying, J. Tan, and L. Zhang, (2013), “MapTask
scheduling in MapReduce with data locality: Throughput and heavytraffic optimality”, in Proc. IEEE Int. Conf. Computer Communications
(INFOCOM), Turin, Italy.
L. Tassiulas and A. Ephremides (1993), “Dynamic server allocation to
parallel queues with randomly varying connectivity” IEEE Trans. Inf.
Theory, vol. 39, pp. 466–478.
.
.