1. Trang Chủ
  2. Kĩ thuật Viễn thông
  3. Đ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

Đ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

Bài viết tập trung nghiên cứu 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. Mời các bạn cùng tham khảo! 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

Thể loại Tài liệu miễn phí Kĩ thuật Viễn thông

Số trang 6

Ngày tạo 4/8/2023 3:54:33 AM +00:00

Loại tệp PDF

Kích thước 1.65 M

Tên tệp

Tải Điều phối tác vụ trong hệ thống MAP-REDUCE dựa trê... (.pdf)

Xem mẫu

  1. 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 Bùi Xuân Lc Hc viên Khoa Công Ngh Thông Tin II Khoa K Thut Hc Vin Công Ngh Bưu Chính Vin Thông i Hc Tân To Email: dathuynhtan@gmail.com Email: locbui@ieee.org Abstract— Vn  d liu a phưng là mt vn  quan trng thêm  to ra kt qu cui cùng. Khi thc hin các tác v cn xem xét khi thit k thut toán iu phi công vic cho h “map”, mt trong nhng xem xét quan trng là vic phân b thng Map-Reduce. Gn ây, bài báo k thut [13] ã gii quyt 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 ưc vn  d liu a phưng bng vic  xut mt kin trúc ó; vn  này còn ưc gi là vn  d liu a phưng. 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 i vi mi tác v, chúng ta gi mt máy tính là mt máy vi chính sách MaxWeight. Tuy nhiên, bài báo [13] ch xem xét tính a phưng cho tác v nu on d liu liên quan n tác trưng hp  sao lưu d liu là mt giá tr c th bng 3. Trên v này ưc lưu tr ngay ti máy tính ó, và chúng ta gi tác thc t, tu thuc vào cu hình h thng,  sao lưu d liu có th v này là mt tác v a phưng trên máy tính. Trong trưng 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 hp còn li (ngha là d liu cn thit cho tác v không ưc các trưng hp  sao lưu d liu có giá tr khác nhau, t ó lưu tr ti máy tính), máy tính ó ưc gi là máy tính t xa giúp ngưi vn hành h thng Map-Reduce có thêm mt tiêu chí cho tác v, và tưng ng vi tác v này ưc gi là tác v t  chn các thông s h thng phù hp. 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 Keywords- in toán ám mây, Map-Reduce, d liu a ci thin tính a phưng có th gim thi gian x lý ca các phưng, Hadoop. 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 I. GII THIU v n các máy tính a phưng có th dn n mt s phân Ngày nay, chúng ta ang sng trong thi i thông tin, vi 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 tng trưng bùng n thông tin theo cp s nhân. Nhng s máy b tc nghn trong khi các máy khác nhàn ri. Vì vy công ty hàng u v công ngh thông tin như Google, Yahoo!, chúng ta cn phi cân bng gia các d liu a phưng và cân Amazon, Microsoft, Facebook, Twitter… ang i mt vi bng ti trong Map-Reduce. ây chính là ng lc thúc y mt khi lưng d liu khng l. S tng trưng này òi hi các nhà nghiên cu tìm hiu, ci tin,  xut các thut toán các chin lưc mi  x lý và phân tích d liu. in toán mi nhm nâng cao hiu qu s dng và hiu sut h thng. ám mây ưc phát trin và Map-Reduce/Hadoop ang là mt Mt s thut toán iu phi ưc  xut trưc ây trong h mô hình tính toán mnh m ưc ng dng trong in toán thng Map-Reduce/Hadoop  ci thin d liu a phưng. ám mây. Vic x lý các tp d liu quy mô ln ã tr thành Thut toán FIFO scheduler trong Hadoop [12] vi vic iu mt vn  ngày càng quan trng và y thách thc vi s phi mt máy sn sàng  phc v tác v “map” t công vic lưng d liu ưc to ra bi các mng xã hi trc tuyn, head-of-line vi d liu gn nht n máy tính. Mc dù mt vài nghiên cu khoa hc… Map-Reduce/Hadoop [9]-[15] là mt ti ưu hoá a phưng ã ưc thc hin, vn  head-of-line framework n gin nhưng mnh m  x lý các tp d liu blocking  a phưng vn tn ti và hiu sut thông lưng vn quy mô ln trong môi trưng phân tán và x lý song song, và b hn ch. Thut toán Fair Scheduler trong Hadoop [6] vi k ang ưc s dng rng rãi trong thc t. Mt cm máy tính thut iu phi chm tr ưc s dng  ci thin a phưng. Map-Reduce có th bao gm hàng chc ngàn máy tính [2]. Các 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 d liu ưc lưu tr thưng ưc t chc trên h thng phân iu phi tip  công bng không có tác v a phưng sn có phi tp tin (ví d h thng tp tin Google (GFS) [10], h thng cho máy tính này, thì công vic tm thi b qua và máy tính tp tin phân tán Hadoop (HDFS) [4]) trong ó phân chia mt kim tra các công vic tip theo trong danh sách. K t khi tp d liu ln thành nhiu on d liu và lưu tr thành nhiu máy tính ưc gii phóng nhanh, nhiu tác v a phưng ưc bn sao (mc nh là 3 bn sao) ca mi on d liu trên các phc v. Tuy nhiên, máy tính ang rnh s ưc gii thiu t máy tính khác khau. Mt yêu cu x lý d liu trong mt máy sn sàng có th b qua tt c các công vic khi nó framework Map-Reduce ưc gi là mt công vic (job) bao không th tìm mt tác v a phưng và vic cân bng gia gm hai loi tác v: “map” (“ánh x”) và “reduce” (“gim”). thi gian rnh và a phưng là không rõ ràng. Thut toán iu Mt tác v “map” c mt on d liu và x lý nó  to ra phi Quincy ưc thit k cho Dryad [7] vi mt mô hình phân kt qu trung gian (các cp khoá – giá tr). Sau ó tác v phi máy tính cho phép lưu d liu phc tp hn Map-Reduce. “reduce” ly kt qu trung gian và thc hin các tính toán Quincy s dng tng s d liu truyn như n v o a ISBN: 978-604-67-0635-9 24 24
  2. 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ã hoá nó vào trong mô hình giá. Sau ó, quyt cn ly d liu u tiên. Các tác v có th phân loi theo các nh iu phi ưc thc hin bng cách gii quyt vn  chi máy tính a phưng mà chúng liên kt vi nhau. i vi mi phí thp nht. Ngoài ra, còn có rt nhiu công trình nghiên cu tác v chúng tôi gán ch s ca K máy tính cc b theo mt ã  xut thut toán iu phi  gii quyt vn  ci thin trt t tng dn vào trong mt vector  hình thành các loi tác d liu a phưng trong Map-Reduce và ưc trin khai trong v: thc t. Tuy nhiên chưa có công trình nghiên cu nào ưa ra  ∈   ,  , … ,    ∈ 1,2, … ,  ,  <  < ⋯ thut toá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. Các ký hiu  ∈  ch rng máy tính m là mt máy tính a Vi tình hình ó, mt kin trúc hàng i mi và mt thut phưng cho kiu tác v . Chn ký hiu ℒ biu th cho tp toán iu phi tác v “map” ã ưc  xut gn ây trong bài hp các kiu công vic tn ti trong cm và  = ℒ. báo k thut [13]. Kin trúc và thut toán này gii quyt ưc A. Quá trình n và quá trình phc v 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 Cho   biu din tng s lưng kiu công vic  n h mt cm máy tính Map-Reduce. Kin trúc hàng i này gm thng cho n thi im bt u ca khe thi gian t. Chúng tôi mt hàng i a phưng tưng ng vi tng máy tính  lưu gi s rng quá trình n là hàm tng theo thi gian vi tc  tr các tác v a phưng cho các máy này và mt hàng i n  . Ti mi máy tính thi gian phc v công vic ưc gi chung cho tt c các máy tính. Da trên kin trúc hàng i này, s là tuân theo phân phi hình hc (geometric distribution). các tác gi nghiên cu mt thut toán iu phi tác v ánh x Tham s phân phi hình hc cho mt công vic ti mt máy (map) vi hai giai on: khi mt tác v mi n nó s ưc tính a phưng là  và ti máy tính t xa là . Quá trình phc chuyn n mt trong 3 hàng i tưng ng vi 3 máy tính a v ca mt công vic có th ưc xem như là mt chui các phưng hoc hàng i chung bng chính sách Join the Shortest s kin c lp vi xác sut thành công  (hoc ) và chui s Queue (JSQ) và khi mt máy tính rnh nó s chn mt tác v kin s dng mt khi chúng ta có mt s thành công tc là t hàng i a phưng tưng ng vi nó hoc hàng i chung mt công vic ã hoàn thành. Trong mô hình này chúng tôi gi bng cách s dng chính sách MaxWeight [14]. 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ú ý Có th d dàng thy rng các tác gi ca [13] ch xem xét rng các giá tr khác nhau ca  và  th hin hiu qu x lý trưng hp  sao lưu d liu bng 3 (ngha là mi on d khác nhau i vi d liu a phưng. 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ó B. Thut toán iu phi công vic (task scheduling algorithm) 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 iu phi công vic là vic gán các công vic n các máy hiu sut h thng trong các trưng hp  sao lưu d liu có tính  x lý. Vi vn  d liu a phưng, thut toán iu giá tr khác nhau. C th, chúng tôi chng minh lý thuyt và phi công vic có th nh hưng áng k n hiu qu ca h mô phng h thng dùng công c mô phng OMNeT++ cho thng. Trong bài báo này, chúng tôi xem xét mt thut toán trưng hp  sao lưu d liu K có giá tr tng quát; ng thi iu phi công vic bao gm hai phn, nh tuyn và iu so sánh hiu sut ca h thng vi các trưng hp dưi ti phi, ưc  xut trong bài báo k thut [13]. H thng iu (underload), gn ti (load), và quá ti (overload). Chúng tôi tin phi bao gm mt kin trúc hàng i ưc minh ho bi Hình rng nhng kt qu có ưc s giúp ngưi vn hành h thng 1. Máy Master duy trì mt hàng i các công vic cc b cho Map-Reduce có thêm mt tiêu chí  chn các thông s h mi máy tính m, ưc ký hiu là  và ưc gi là hàng i thng phù hp. 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 Phn còn li ca bài báo ưc t chc như sau. Trong phn gi là hàng i chung t xa (common remote queue). Chúng II, chúng tôi miêu t mô hình h thng. Trong phn III, chúng tôi dùng mt vector chiu dài hàng i  =   , … , tôi trình bày chng minh lý thuyt v ti ưu hoá thông lưng.  ,    ký hiu cho chiu dài các dàng i ti thi Phn IV cung cp các kt qu mô phng. Cui cùng, chúng tôi im bt u ca khe thi gian t. Khi mt công vic n, máy kt lun bài báo trong phn V. 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 II. MÔ HÌNH H THNG vic t hàng i a phưng tưng ng hoc hoc t hàng i Chúng tôi xem xét mt mô hình thi gian ri rc cho mt cm chung t xa  phc v. Hai bưc này ưc minh ho trong máy tính bao gm M máy tính, ưc ánh s th t 1, 2, …, Hình 1. Chúng ta gi bưc u tiên là nh tuyn (routing) và M. Chúng tôi gi nh rng mi công vic n yêu cu mt tác bưc th hai là iu phi (scheduling). Thut toán c th như v “map”, và mi tác v “map” yêu cu mt mu d liu u sau. vào. Chúng tôi cng gi s rng mi mt mu d liu ưc Bưc 1 - Join the Shortest Queue (JSQ) Routing: Khi mt sao lưu  K (K > 1) máy tính khác nhau. Vì vy mi tác v công vic n, máy tính Master s so sánh chiu dài hàng i liên quan n K máy tính a phưng. Phi mt mt thi gian ca K hàng i cc b và hàng i chung t xa và sau ó nh 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 tuyn n mt hàng i có chiu dài ngn nht. Cho ,  2525
  3. 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) và   biu din các công vic  ưc giao tưng ng vi nu máy tính m là idle tc là   = ,   là 1 hoc 2  và  . Các công vic ưc giao n cho mi hàng i có ưc quyt nh bi máy tính Master bng thut toán th ưc biu din bng vector n MaxWeight. Chúng tôi dùng vector iu phi  =  =  , … ,  ,  ưc nh ngha như sau:  ,  , … ,    biu din quyt nh iu phi cho tt c các máy tính.   =   , ,  = 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 toán iu phi        1,   =    Bưc 2 - MaxWeight Scheduling: Nu mt máy tính m va       = . hoàn thành mt công vic ti khe thi gian t-1, thì trng thái Hàng i t xa (Remote queue) 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 =           ,      = , 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 trong ó: 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 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t c các máy tính da trên  và . Các máy tính idle t hàng i t xa ti slot thi gian t. Chú ý rng có th có mt ưc iu phi bi thut toán MaxWeight: gi s máy tính m vài máy tính c gng phc v hàng i t xa nhưng tht bi do là idle ti slot thi gian t, thì nó phc v mt công vic a thiu công vic. phưng nu     và phc v mt công vic t Chúng ta có th vit li phưng trình ng hc hàng i như xa cho các trưng hp khác. Các máy tính khác tip tc thc sau: hin các công vic chưa hoà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   1 =       , (1) ca máy tính m ti slot thi gian t, thì nó là mt hàm ca  . vi  =  , … ,  ,  và   và Trong trưng hp thi gian phc v là xác nh, quá trình 1 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 2. do vn  d liu a phưng. Do ó chúng ta cn xem xét Lưu ý rng   cho bit hàng i máy tính m ã ưc iu thêm các vector trng thái làm vic ; c th,  cùng phi  phc v. Nó ch có giá tr 1 hoc 2 k t khi ưc iu vi  s to thành chui Markov , ,    . phi  phc v mt công vic a phưng hoc mt công vic Chúng ta gi nh trng thái ban u là ,  = t xa. Nu máy tính m không idle tc là   = 12 ,  ,   và không gian trng thái      chúng ta thit lp iu phi   bng vi  . Tuy nhiên, ,1,2 bao gm tt c các trng thái mà nó có th t ưc 26 26
  4. 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) t trng thái ban u, vi  là tp s nguyên không âm. D chn ngoài Ʌ. Do ó thut toán này là ti ưu thông lưng và Ʌ thy rng chui Markov này là ti gin (irreducible) và không cng là min dung lưng ca h thng. tun hoàn (aperiodic). Chng minh: III. TI U HOÁ THÔNG LNG 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 Trong phn này, chúng tôi s chng minh tính nng ti ưu hoá K=3. Vi trưng hp K tng quát, ta thy rng tp ℒ (tp hp thông lưng ca thut toán iu phi ưc trình bày  phn các kiu công vic) s thay i, và  = ℒ cng thay i. Tuy trưc. Chú ý rng tính nng này ã ưc chng minh trong bài nhiên, chng minh ca nh lý 1 trong [13] vn có th ưc báo k thut [13] vi trưng hp K=3; trong phn này chúng m rng cho trưng hp K tng quát. Vì lý do gii hn v  tôi m rng chng minh vi trưng hp K tng quát. dài bài báo, chúng tôi ch nêu ý tưng chng minh  ây và Ý tưng ca chng minh như sau: Trưc tiên chúng ta xác mi ngưi c tham kho bài báo [13] v chi tit. Ý tưng ca nh min chn ngoài (outer bound) ca min dung lưng ca chng minh như sau: Vì , ,    là mt chui h thng. Sau ó chúng ta chng minh rng thut toán iu Markov ti gin và không tun hoàn, s n nh ưc nh phi trên có th n nh hoá bt k vector tc  n nào ngha là s hi quy dưng (positive recurrence) ca chui thuc min chn ngoài này (n nh hoá theo ngha các hàng Markov này. Da theo nh lý Foster-Lyapunov m rng, ta i u n nh và không tng theo thi gian). iu ó có ch cn tìm mt s dưng T và mt hàm Lyapunov sao cho  ngha là thut toán iu phi trên là ti ưu thông lưng, và trôi ca hàm Lyapunov (Lyapunov drift) sau T khe thi gian b min dung lưng cng trùng vi min chn ngoài. 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 A. Min dung lng (capacity region) Lyapunov ưc chn có dng: 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     ,    ∈ℒ,,…, ưc gi là mt phân tích (decomposition) ca vector tc  Khi ó ta có th chng minh rng (tham kho chi tit trong  =   ,  , … ,  . Vi vector tc  n , xét mt máy [13])  trôi Lyapunov sau T khe thi gian t t0 ưc chn bi  ,    ≤ 2     vi hng s  > . nh 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 ngha tp ß = ,  ∈   ⋯    ≤    vi mt khe thi gian có th ưc phc v ht trong khe thi gian  >  bt k. Khi ó ß là mt tp con hu hn ca không ó, có ngha là: gian trng thái vi ,  ∈ ß , ,  ≤  và ,  ∈ , , ß, ,  ≤ . iu này tho mãn nh lý Foster-Lyapunov     ≤ 1, (2) m rng và hoàn thành chng minh.   ∈    ∉   IV. KT QU MÔ PHNG trong ó v trái là thi gian máy tính m cn có  phc v Trong phn trưc chúng tôi ã chng minh tính ti ưu hoá lưng tác v trung bình phân b cho nó trong mt khe thi thông lưng ca thut toán iu phi ưc  xut ngay c vi gian, vi tc  dch v  cho công vic a phưng và  cho  sao lưu d liu K tng quát. Tuy nhiên, câu hi ưc t ra công vic t xa. là hiu sut h thng ca thut toán iu phi thay i th nào Gi Ʌ là tp giá tr tc  n mà mi phn t phân tích ca nó vi các giá tr K khác nhau. Chúng tôi s tr li câu hi ó tho mãn (2). C th: trong phn này vi các kt qu mô phng. Ʌ =   =  ,  , … ,    Chúng tôi mô phng thut toán vi các giá tr  sao lưu  =   , , ∀ ∈ ℒ, (3) 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à  ,  , ∀ ∈ ℒ, ∀ = 1, … ,  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.     ≤ 1, ∀ = 1, … ,  .   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 D thy rngɅ chính là min chn ngoài ca min dung lưng trong s ó. Thi gian phc v cho tác v a phưng và tác ca h thng. 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 B. Tính ti u thông lng (throughput optimality) (tính theo s tác v n trong mt n v thi gian) bng  = nh lý 1: Thut toán iu phi ưc  xut  Phn II.B có 320 α + 80γ = 272. Tng thi gian chy ca h thng là 2000 th n nh h thng vi vector tc  n bt k thuc min n v thi gian. 27 27
  5. HộiHội Thảo Quốc Thảo GiaGia Quốc 2015 2015vềvềĐiện ĐiệnTử, Tử,Truyền TruyềnThông và Công Thông và CôngNghệ NghệThông ThôngTinTin (ECIT (ECIT 2015) 2015) Bng 1 cho thy kt qu trung bình theo thi gian ca tng A. Trng hp di ti (underload) s lưng tác v còn trong hàng i (tưng ng vi tng chiu Vi trưng hp này chúng ta cho h thng chy vi tc  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  = 100 (tác v trong mt n v thi gian). Chy  tác v n () và  sao lưu d liu (K). Kt qu này cng vi K = 2, 3, 4, 6, 8, 10 vi thi gian 2000 n v thi gian. ư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 Chúng ta theo dõi tng s lưng tác v tc thi trong h thay i ca tc  tác v n ng vi các trưng hp K = 2, thng  quan sát s n nh. Hình 3 cho thy con s i din 3, 4, 6, 8, 10. Ta có th thy rng khi tc  n nh (dưi ti này n nh theo thi gian, qua ó thy rõ s n nh ca h – underload), tng chiu dài trung bình hàng i tng dn khi thng. Vi kt qu như Hình 3 chúng ta thy rng hiu sut h K tng dn, ngha là giá tr K nh s có hiu sut cao hn trong thng vi  sao chép d liu K = 2, 3, 4, 6, 8, 10 luôn luôn n trưng hp này. Tuy nhiên, khi tc  n tng dn (ti tng nh theo thi gian. Tuy nhiên vi trưng hp này  sao chép dn), tng chiu dài trung bình hàng i ng vi giá tr K nh d liu K = 2 tt hn các trưng hp khác. 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. 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 Hình 2: Hiu sut thông lưng h thng thi gian. Bng 1: Kt qu s lưng công vic trung bình trong h thng Vi kt qu như Hình 4, Hình 5 chúng ta thy rng tng s CCCCCCSSCC K lưng tác v tc thi trong h thng vn n nh theo thi K=2 K=3 K=4 K=6 K=8 K=10  gian. Kt qu Hình 6, Hình 7 cho thy tng s lưng tác v 100 42 48 55 68 77 85 tc thi trong h thng có chiu hưng quá ti. Tuy nhiên vi 120 65 66 75 90 101 110 các trưng hp này  sao chép d liu K = 10 tt hn các 140 114 89 96 113 127 136 trưng hp khác. 160 371 122 122 138 153 163 180 503 330 159 166 180 191 200 596 445 347 203 211 220 220 713 530 444 344 270 258 230 798 584 490 390 349 316 240 937 663 555 444 398 371 250 1613 849 690 544 482 437 260 8277 7673 7608 7209 7280 6788 272 22941 22514 22456 22042 22205 21752 300 57792 57420 57438 57050 57246 56792 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
  6. 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] 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. [2] 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. [3] J. Dean and S. Ghemawat (2008), “MapReduce: simplified data processing on large clusters” ACM Commun, vol 51 (no. 1), pp. 107– 113. [4] 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. [5] 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. Hình 6: Kt qu trưng hp  = 260 [6] 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. [7] 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. [8] S. T. Maguluri and R. Srikant (2013), “Scheduling jobs with unknown duration in clouds” in Proc. IEEE Int. Conf. Computer Communications (INFOCOM), Turin, Italy. [9] 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. [10] S. Ghemawat, H. Gobioff, and S.-T. Leung (2003), “The google file system” in Proc. ACM Symp. Operating Systems Principles (SOSP), pp. Hình 7: Kt qu trưng hp  = 270 29–43. [11] S. Kavulya, J. Tan, R. Gandhi, and P. Narasimhan (2010), “An analysis C. Trng hp quá ti (overload) of traces from a production MapReduce cluster” in Proc. IEEE/ACM Int. Conf. Cluster, Cloud and Grid Computing (CCGRID), pp. 94–103. Vi trưng hp này chúng ta cho h thng chy vi tc  tác [12] T. White (2010), Hadoop: The definitive guide, Yahoo Press. v n ln lưt  = 272 (tác v trong mt n v thi gian),  [13] W. Wang, K. Zhu, L. Ying, J. Tan, and L. Zhang, (2013), “MapTask = 300 (tác v trong mt n v thi gian). Chy vi K = 2, 3, scheduling in MapReduce with data locality: Throughput and heavy- 4, 6, 8, 10 vi thi gian 2000 n v thi gian. traffic optimality”, in Proc. IEEE Int. Conf. Computer Communications (INFOCOM), Turin, Italy. Vi kt qu Bng 1 chúng ta thy rng ng vi c hai giá tr  [14] L. Tassiulas and A. Ephremides (1993), “Dynamic server allocation to trong trưng hp này tng s lưng tác v trung bình theo thi parallel queues with randomly varying connectivity” IEEE Trans. Inf. Theory, vol. 39, pp. 466–478. gian là tưng ưng nhau cho tt c các giá tr ca K, và h [15] http://hadoop.apache.org. thng luôn luôn quá ti. [16] https://omnetpp.org. 29 29
nguon tai.lieu . vn
Kiến trúc - Xây dựng Tự động hoá Điện - Điện tử Kĩ thuật Viễn thông Cơ khí - Chế tạo máy Năng lượng Hoá dầu Hoá học Sinh học