ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

BÁO CÁO MÔN
CHỦ ĐỀ HIỆN ĐẠI VỀ HTTT

Đề tài: “Dominant Resource Fairness: Fair Allocation
of Multiple Resource Type”

Giảng viên: TS. Nguyễn Ngọc Hóa
Nhóm: 27
Họ và tên học viên: Nguyễn Bá Quân


Tóm tắt Tiểu luận
Tài nguyên của hệ thống (CPU, bộ nhớ, thiết bị ngoại vi,...) vốn rất giới hạn, nhưng
trong các hệ thống đa nhiệm, nhiều người sử dụng có thể đồng thời yêu cầu nhiều tài
nguyên. Để thỏa mãn yêu cầu sử dụng chỉ với tài nguyên hữu hạn và nâng cao hiệu quả sử
dụng tài nguyên, cần phải có cơ chế và chiến lược thích hợp để quản lý việc phân phối tài
nguyên.
Ngoài yêu cầu dùng chung tài nguyên để tiết kiệm chi phí, người sử dụng còn cần phải
chia sẻ thông tin (tài nguyên phần mềm) lẫn nhau, khi đó cần đảm bảo việc truy xuất đến
các tài nguyên này là hợp lệ, không xảy ra tranh chấp, mất đồng nhất,...
Tiểu luận tập trung tìm hiểu phương pháp phân bổ nguồn tài nguyên một cách công
bằng để mỗi người sử dụng đều có thể sử dụng tài nguyên một cách hợp lý.

2
2


1.Introduction

Trong một hệ thống có chứa các loại tài nguyên khác nhau mỗi người sử dụng có
thể có nhu cầu khác nhau cho mỗi tài nguyên. Đề có thể phần phối hợp lý tài nguyên này
người ta đề ra DRF( Phân phối công bằng tài nguyên). Một cách tổng quát đây chính là
cách đề phân phối công bằng cho tất cả các tài nguyên trong máy tính. Không giống như
chính sách khác DRF chia sẻ tài nguyên bằng cách đảm bảo rằng không có người dùng nào
được ưu tiên và người sử dụng không thể yêu cầu thêm tài nguyên cho mình nếu như đã đủ
số tài nguyên sử dụng cũng như không thể ưu tiên phân bổ cho người này và giảm sự phân
bổ cho người sử dụng khác.
Phân bổ tài nguyên là chìa khóa để xây dựng các khối quan trọng của bất kỳ sự
chia sẻ nào trong hệ thống máy tính. Đó là một trong những chính sách phân phối phổ
biến nhất đến này là phân phối công bằng Max- Min. đó chính là phân phối Max- Min
được bởi người dùng trong hệ thống. Giả sử mỗi người dùng có đủ nhu cầu chính, sách
này cung cấp cho mỗi người sử dụng một phần bằng nhau của tài nguyên. Max-min sự
công bằng đã được khái quát hóa để bao gồm các khái niệm về trọng lượng, trong đó mỗi
người dùng nhận được một phần của tài nguyên tỷ lệ thuận với trọng lượng của nó.
Quan trọng của công bằng max-min xuất phát từ tổng quát của nó và khả năng của
mình để cung cấp hiệu suất cách ly. Các mô hình công bằng max-min trọng có thể hỗ trợ
một loạt các chính sách phân bổ nguồn lực khác, trong đó ưu tiên, đặt phòng, và thời hạn
phân bổ dựa. Ngoài ra, trọng lượng sự công bằng max-min đảm bảo cô lập, trong đó một
người dùng được đảm bảo nhận được phần của mình không phụ thuộc vào nhu cầu của
người sử dụng khác.
Với những tính năng, nó sẽ đến như là không có gì ngạc nhiên khi một số lượng
lớn các thuật toán đã được đề xuất để thực hiện (trọng số) max-min công bằng với mức độ
khác nhau của độ chính xác, chẳng hạn như vòng tròn một lượt, chia sẻ tài nguyên theo tỷ
lệ, Và xếp hàng công bằng trọng lượng. Các thuật toán này đã được áp dụng cho một loạt
các tài nguyên, bao gồm băng thông liên kết Bộ xử lý trung tâm, bộ nhớ và lưu trữ.
Mặc dù số lượng lớn các công việc về phân bổ công bằng, sự tập trung cho đến
nay chủ yếu vào một loại tài nguyên duy nhất. Thậm chí trong nhiều tài nguyên môi
3
3



trường,nơi người dùng có nhu cầu nguồn lực không đồng nhất, phân bổ thường được thực
hiện bằng cách sử dụng một nguồn tài nguyên duy trừu tượng. Ví dụ, lập lịch công bằng
cho Hadoop và Dryad hai khung tính toán cluster được sử dụng rộng rãi, phân bổ nguồn
lực ở cấp độ phân vùng cố định kích thước của các nút, gọi là khe cắm Điều này bất chấp
thực tế rằng công việc khác nhau trong các cụm có thể có nhu cầu rất khác nhau cho CPU,
bộ nhớ, và I / O các nguồn lực
Quá trình thực hiện và đánh giá DRF trong Mesos một người quản lý tài nguyên
trong đó nhiều khung tính toán cluster, như Hadoop và MPI, có thể chạy. so sánh DRF với
công bằng chương trình chia sẻ khe dựa trên sử dụng trong Hadoop và Dryad và cho thấy
rằng khe dựa trên chia sẻ công bằng có thể dẫn đến hiệu suất kém hơn, khối lượng công
việc nhất định trừng phạt bất công, trong khi cung cấp sự bảo đảm cách ly yếu
Trong bài báo này tập trung vào việc phân bổ nguồn lực trong trung tâm dữ liệu, vì
vậy DRF là áp dụng chung cho các môi trường đa nguồn tài nguyên khác, nơi người dùng
có nhu cầu không đồng nhất, chẳng hạn như trong các máy đa nhân.

2. Motivation

Trong khi việc trước đây về quyền công bằng max-min đã tập trung vào các nguồn
tài nguyên duy nhất, sự ra đời của các bộ vi xử lý điện toán đám mây và đa lõi đã làm tăng
nhu cầu đối với chính sách phân bổ cho các môi trường nhiều nguồn lực và nhu cầu người
sử dụng không đồng nhất. Bởi nhiều nguồn lực chúng tôi có nghĩa là nguồn lực của các
loại khác nhau, thay vì nhiều trường hợp của các nguồn tài nguyên thay thế cho nhau cùng.
Để thúc đẩy nhu cầu đối với phân bổ đa tài nguyên, chúng ta vẽ các cấu hình sử
dụng tài nguyên của các nhiệm vụ trong năm 2000-nút Hadoop nhóm tại Facebook hơn
một tháng (tháng 10 2010) trong Hình 1. Các vị trí của một vòng tròn trong hình 1 cho biết
các bộ nhớ và tài nguyên CPU được tiêu thụ bởi các nhiệm vụ. Kích thước của một vòng
tròn là logarit với số nhiệm vụ trong khu vực của hình tròn Mặc dù phần lớn các nhiệm vụ
là CPU-nặng, có tồn tại những công việc mà bộ nhớ nặng là tốt, đặc biệt là đối với các hoạt

động giảm

4
4


Hiện lập lịch công bằng cho các cụm, như Quincy và Hadoop Fair Scheduler ,bỏ
qua tính không đồng nhất của nhu cầu người sử dụng, và phân bổ nguồn lực ở mức chi tiết
của khe, nơi một khe cắm là một phần cố định của một nút. Điều này dẫn đến việc phân bổ
không hiệu quả như một khe cắm là thường xuyên hơn không phải là một trận đấu nghèo
cho các nhu cầu công việc.
Hình 2 định lượng mức độ công bằng và sự biệt lập của các Hadoop MapReduce
công bằng lịch [2, 34]. Con số này cho thấy CDF của tỷ lệ giữa nhu cầu công việc CPU và
CPU khe chia sẻ, và các tỷ lệ giữa nhu cầu bộ nhớ nhiệm vụ và chia sẻ bộ nhớ khe. Chúng
tôi tính toán bộ nhớ khe và cổ phiếu CPU bằng cách chia đôi tổng số lượng bộ nhớ và CPU
do số lượng các khe. Một tỷ lệ 1 tương ứng với một kết hợp hoàn hảo giữa nhu cầu công
việc và nguồn lực khe, một tỷ lệ dưới 1 tương ứng với nhiệm vụ underutilizing nguồn khe
của họ, và một tỷ lệ trên 1 tương ứng với nhiệm vụ trên, khi sử dụng nguồn khe của họ,
trong đó có thể dẫn đến trận đòn. Hình 2 cho thấy rằng hầu hết các nhiệm vụ hoặc
underutilize hoặc overutilize một số tài nguyên khe của họ. Thay đổi số lượng các khe trên
mỗi máy sẽ không giải quyết vấn đề như thế này có thể dẫn đến một trong hai trong một sử
dụng tổng thể thấp hơn hoặc nhiều nhiệm vụ experiencingpoor hiệu suất do việc sử dụng
quá (Phần ee s 7).

5
5


3 Allocation Properties
Bây giờ chúng ta chuyển sự chú ý của chúng tôi để thiết kế một chính sách phân bổ

công bằng max-min cho nhiều tài nguyên và yêu cầu không đồng nhất. Để minh họa vấn
đề, xem xét một hệ thống bao gồm 9 CPU và 18 GB RAM, và hai người sử dụng: Một
người sử dụng chạy các tác vụ đòi hỏi CPU h1, 4 GBI nhau, và người sử dụng B chạy tác
vụ yêu cầu CPU h3, 1 GBI mỗi. Tạo nên cái mà một chính sách phân bổ công bằng đối với
trường hợp này?
Một khả năng có thể để phân bổ cho mỗi hiệp của người sử dụng mọi nguồn lực.
Một khả năng khác là để cân bằng tổng hợp (ví dụ, CPU với bộ nhớ) phân bổ cho mỗi
người dùng. Trong khi nó là tương đối dễ dàng để đến với một loạt các khả năng phân bổ
"công bằng", nó là không rõ ràng như thế nào để đánh giá và so sánh các phân bổ.
Để giải quyết thách thức này, chúng ta bắt đầu với một tập hợp các tính chất mong
muốn rằng chúng tôi tin rằng bất kỳ chính sách phân bổ nguồn lực cho nhiều tài nguyên và
nhu cầu không đồng nhất nên đáp ứng. Sau đó chúng tôi mời những đặc tính hướng dẫn sự
phát triển của một chính sách phân bổ công bằng. Chúng tôi đã tìm thấy bốn thuộc tính sau
đây là quan trọng:
6
6


1. Chia sẻ khuyến khích: Mỗi người sử dụng nên được tốt hơn off chia sẻ các cluster,

hơn độc quyền sử dụng phân vùng riêng của mình của cluster. Hãy xem xét một
cluster với các nút và n người dùng giống nhau. Sau đó, người dùng không nên có
thể phân bổ nhiệm vụ nhiều hơn trong một phân vùng cụm gồm 1 / n của tất cả các
nguồn lực.
2.

Chiến lược-proofness: Người dùng không nên có thể hưởng lợi bằng cách nói dối
về nhu cầu tài nguyên của họ. Điều này cung cấp khả năng tương thích khuyến
khích, như một người sử dụng không thể cải thiện việc phân bổ của mình bằng cách
nói dối


3. Envy-freeness: Một người sử dụng không nên thích việc phân bổ của người dùng

khác. Khách sạn này là hiện thân của ý niệm về sự công bằng [13, 30].
4. hiệu quả Pareto: Nó không phải là có thể làm tăng sự phân bổ của một người sử

dụng mà không làm giảm sự phân bổ ít nhất một người dùng khác. Khách sạn này là
quan trọng vì nó dẫn đến việc tối đa hóa đối tượng sử dụng hệ thống để đáp ứng các
thuộc tính khác
Chúng tôi cũng đã bình luận về chiến lược proofness và chia sẻ khích lệ tài sản, mà
chúng tôi cho là có tầm quan trọng đặc biệt trong môi trường trung tâm dữ liệu. Bằng
chứng từ các nhà khai thác điện toán đám mây mà chúng tôi đã nói chuyện với chỉ ra rằng
chiến lược proofness là quan trọng, vì nó là phổ biến đối với người dùng cố gắng để thao
tác lập lịch. Ví dụ, một trong những trung tâm dữ liệu Hadoop MapReduce của Yahoo! có
các số khác nhau của khe cho bản đồ và giảm nhiệm vụ. Một người sử dụng phát hiện ra
rằng các khe bản đồ đã được tranh luận, và do đó đưa ra tất cả các công việc của mình như
giảm dài giai đoạn, trong đó sẽ tự làm những công việc mà MapReduce hiện trong giai
đoạn bản đồ của nó. Một công ty cung cấp máy tìm kiếm lớn dành riêng cho công việc chỉ
nếu người sử dụng có thể đảm bảo sử dụng cao. Công ty này sớm phát hiện ra rằng người
dùng sẽ rắc mã của họ với các vòng trong hữu hạn nhân tạo thổi phồng mức độ sử dụng.
Hơn nữa, bất kỳ chính sách đáp ứng các bất động sản khuyến khích chia sẻ cũng cung
cấp hiệu năng cô lập, vì nó bảo đảm việc phân bổ tối thiểu cho mỗi người dùng (ví dụ, một
người sử dụng có thể không làm tồi tệ hơn việc sở hữu 1 / n của cluster) mà không tính đến
nhu cầu của người sử dụng khác.
7
7


Nó có thể dễ dàng thấy rằng trong trường hợp của một tài nguyên duy nhất, đáp ứng sự
công bằng max-min tất cả các properties.However trên, đạt được những tài sản trong

trường hợp nhiều nguồn lực và nhu cầu người sử dụng không đồng nhất là không nhỏ. Ví
dụ, các cơ chế ưu đãi công bằng phân chia trong lý thuyết kinh tế vi mô, cân bằng cạnh
tranh từ Thu nhập bình đẳng [22, 30, 33], không strategyproof
Ngoài các đặc tính trên, chúng tôi xem xét đặc tính khác
• Độc tính công bằng tài nguyên: Đối với một nguồn duy nhất, các giải pháp cần giảm
để công bằng max-min.
• sự công bằng nút cổ chai: Nếu có một nguồn tài nguyên đó là phần trăm-khôn ngoan
đòi hầu hết bởi mỗi người dùng, sau đó các giải pháp để giảm nên công bằng max-min cho
tài nguyên đó.
• Dân số đơn điệu: Khi một người sử dụng rời khỏi hệ thống và tuyên bố từ bỏ các
nguồn lực của mình, không ai trong số các phân bổ của người sử dụng còn lại sẽ giảm.
• đơn điệu Resource: Nếu có nhiều nguồn tài nguyên được bổ sung vào hệ thống, không
có sự phân bổ của người dùng hiện tại sẽ giảm.

4. Dominant Resource Fairness (DRF).
Chúng tôi đề xuất Dominant Resource Công bằng (DRF), một chính sách phân bổ mới
cho nhiều tài nguyên đáp ứng tất cả bốn của các thuộc tính cần thiết trong các phần trước.
Đối với mỗi người sử dụng, DRF tính thị phần của mỗi tài nguyên được phân bổ cho người
đó. Tối đa trong tất cả các cổ phiếu của một người dùng được gọi là cổ phần chi phối của
người dùng, và các nguồn tài nguyên tương ứng với phần chi phối được gọi là tài nguyên
thống trị. Người sử dụng khác nhau có thể có các nguồn tài nguyên khác nhau chi phối. Ví
dụ, các tài nguyên thống trị của một người dùng chạy một công việc tính toán bị ràng buộc
là CPU, trong khi các nguồn tài nguyên thống trị của một người dùng chạy một I / O công
việc bị ràng buộc là bandwidth.1 DRF đơn giản chỉ áp công bằng maxmin qua cổ phần chi
phối của người sử dụng. Đó là, DRF tìm cách tối đa hóa thị phần chiếm ưu thế nhỏ nhất
trong hệ thống, sau đó thứ hai nhỏ nhất, và như vậy.

8
8



Chúng

tôi

bắt đầu bằng cách

minh họa DRF với một ví dụ (§4.1), sau đó trình bày một thuật toán cho (§4.2) DRF và
một định nghĩa về trọng (§4.3) DRF. Trong phần 5, chúng tôi trình bày hai chính sách phân
bổ khác: công bằng tài sản, một chính sách đơn giản nhằm mục đích cân bằng tổng hợp
nguồn lực được phân bổ cho mỗi người dùng, và cân bằng cạnh tranh từ thu nhập ngang
nhau (CEEI), một phổ biến chính sách phân bổ công bằng ưa thích trong kinh tế vi mô
miền
Trong phần này, chúng ta xem xét một mô hình tính toán với n người dùng và tài
nguyên m. Mỗi người sử dụng chạy các nhiệm vụ cá nhân, và mỗi công việc được đặc
trưng bởi một vector nhu cầu, xác định số lượng tài nguyên theo yêu cầu của công việc, ví
dụ như, CPU h1, 4 GBI. Nói chung, công việc (thậm chí những người thuộc cùng một
người dùng) có thể có nhu cầu khác nhau.

4.1 An Example.
Hãy xem xét một hệ thống với 9 CPU, 18 GB RAM, và hai người sử dụng, người
dùng A chạy nhiệm vụ với h1 CPU vector nhu cầu, 4 GBI, và người sử dụng B chạy nhiệm
vụ với CPU h3 vector cầu, 1 GBI mỗi
Trong trường hợp trên, mỗi công việc từ người sử dụng A tiêu thụ 1/9 tổng số CPU
và 2/9 của tổng số bộ nhớ, vì vậy người dùng của một tài nguyên thống trị là bộ nhớ. Mỗi
nhiệm vụ từ người dùng B tiêu thụ 1/3 tổng số CPU và 1/18 của tổng bộ nhớ, vì vậy người
sử dụng tài nguyên ominant B là CPU. DRF sẽ bằng cổ phần chi phối của người sử dụng,
cho việc phân bổ trong hình 3: ba nhiệm vụ cho người sử dụng A, với tổng số CPU h3, 12
GBI, và hai nhiệm vụ cho người sử dụng B, với tổng số CPU h6, 2 GBI. Với việc phân bổ


9
9


này, mỗi người sử dụng kết thúc với phần vượt trội cùng, tức là, người dùng A được 2/3 bộ
nhớ RAM, trong khi người dùng B được 2/3 của CPU.
Sự phân bổ này có thể được tính toán học như sau. Cho x và y là số các nhiệm vụ
được phân bổ bởi DRF cho người dùng A và B, tương ứng. Sau đó, người dùng A nhận
CPU hx, 4x GBI, trong khi người dùng B được CPU h3y, y GBI. Tổng số lượng tài nguyên
được phân bổ cho cả người dùng là (x + 3Y) CPU và (4x + y) GB. Ngoài ra, các cổ phần
chi phối của người dùng A và B là 4x / 18 = 2x / 9 và 3Y / 9 = y / 3, tương ứng (cổ phiếu
tương ứng của họ về bộ nhớ và CPU). Sau đó phân bổ DRF được đưa ra bởi các giải pháp
cho các vấn đề tối ưu hóa sau đây:

Giải quyết vấn đề này yields2 x = 3 và y = 2. Do đó, người dùng A được CPU h3,
12 GBI và B được CPU h6, 2 GBI.
Lưu ý rằng DRF không cần luôn cân bằng cổ phần chi phối của người sử dụng. Khi
tổng nhu cầu của người dùng được đáp ứng, người dùng sẽ không cần nhiều nhiệm vụ hơn,
vì vậy các nguồn lực dư thừa sẽ được chia đều cho những người sử dụng khác, giống như
trong sự công bằng max-min. Ngoài ra, nếu một nguồn tài nguyên bị cạn kiệt, người dùng
không cần tài nguyên có thể vẫn tiếp tục nhận cổ phiếu cao hơn các nguồn tài nguyên khác.
Chúng tôi trình bày một thuật toán để phân bổ DRF trong phần tiếp theo.

10
10


4.2 DRF thuật toán lập lịch.

Thuật

toán 1 lãm
pseudo-code
cho các thuật
toán

DRF

scheduling.The dõi tổng nguồn lực phân bổ cho từng người sử dụng cũng như phần chi
phối của người dùng, si. Tại eachstep, DRF kén người dùng với phần chi phối thấp nhất
trong số những người có nhiệm vụ sẵn sàng để chạy. Nếu nhu cầu công việc của người
dùng có thể hài lòng, tức là, có đủ nguồn lực sẵn có trong hệ thống, một trong những
nhiệm vụ của cô được tung ra. Chúng tôi xem xét trường hợp tổng quát trong đó người
dùng có thể có nhiệm vụ với vectơ nhu cầu khác nhau, và chúng tôi sử dụng biến Di để
biểu thị vector nhu cầu của người sử dụng nhiệm vụ tiếp theo tôi muốn khởi động. Để đơn
giản, giả mã không nắm bắt được sự kiện của một kết thúc nhiệm vụ. Trong trường hợp
này, người sử dụng phát hành các nguồn lực của công việc và DRF lại lựa chọn cho người
sử dụng với các phần chi phối nhỏ nhất để chạy công việc của mình.
Hãy xem xét ví dụ hai người dùng trong phần 4.1. Bảng 1 mô tả các quá trình giao
DRF ví dụ này. DRF đầu tiên chọn B để chạy một nhiệm vụ. Kết quả là, các cổ phiếu của
B trở h3 / 9, 1 / 18i, và cổ phần chi phối trở nên max (3/9, 1/18) = 1/3. Tiếp theo, DRF
chọn A, như phần chi phối mình là 0. Quá trình này tiếp tục cho đến khi nó không còn có
thể để chạy các nhiệm vụ mới. Trong trường hợp này, điều này xảy ra ngay sau khi CPU
đã bị bão hòa.
Vào cuối của việc phân bổ ở trên, người dùng A được CPU h3, 12 GBI, trong khi
người dùng B được CPU h6, 2 GBI, tức là, mỗi người sử dụng được 2/3 tài nguyên thống
trị của mình.
Lưu ý rằng trong ví dụ này, phân bổ dừng lại ngay khi bất kỳ tài nguyên được bão
hòa. Tuy nhiên, trong trường hợp chung, nó có thể là có thể tiếp tục giao nhiệm vụ thậm
11
11



chí sau khi một số tài nguyên đã được bão hòa, như một số nhiệm vụ có thể không có bất
kỳ nhu cầu về tài nguyên bão hòa.
Các thuật toán trên có thể được thực hiện bằng cách sử dụng một đống nhị phân mà
các cửa hàng cổ phần chi phối của mỗi người dùng. Mỗi quyết định lập kế hoạch sau đó
phải mất O (log n) thời gian cho n người dùng.

4.3 weighted DRF.
Trong thực tế, có rất nhiều trường hợp trong đó phân bổ nguồn lực đều trên tất cả
người sử dụng không phải là policy.Instead mong muốn, chúng ta có thể phân bố nhiều tài
nguyên hơn cho người sử dụng chạy các công việc quan trọng hơn, hoặc cho người dùng
đã đóng góp thêm nguồn lực để các cluster. Để đạt được mục tiêu này, chúng tôi đề xuất
trọng DRF, một sự tổng quát của cả DRF và trọng sự công bằng max-min.
Với trọng DRF, mỗi i dùng có liên quan đến một vector trọng lượng Wi = (wi, 1,...,
Wi, mi), nơi wi, j đại diện cho trọng lượng của người dùng i cho tài nguyên j. Các định
nghĩa của một cổ phần chi phối cho người dùng i thay đổi si = maxj {ui, j / wi, j}, nơi ui, j
là người sử dụng tôi chia sẻ của tài nguyên j. Một trường hợp đặc biệt quan tâm là khi tất
cả các trọng số của người sử dụng tôi đều bình đẳng, tức là, wi, j = wi (1 ≤ j ≤ m). Trong
trường hợp này, tỷ lệ giữa các cổ phần chi phối của người dùng i và j sẽ chỉ đơn giản là
wi / wj. Nếu trọng lượng của tất cả người dùng được thiết lập để 1, trọng DRF giảm
trivially để DRF.

5. Alternative Fair Allocation Policies.
Xác định phân bổ công bằng trong một hệ thống đa nguồn tài nguyên không phải là
một câu hỏi dễ dàng, như khái niệm "công bằng" là tự mở để thảo luận. Trong những nỗ
lực của chúng tôi, chúng tôi xem xét nhiều chính sách phân bổ trước khi quyết định DRF
như là chỉ thỏa mãn tất cả bốn của các thuộc tính cần thiết tại mục 3: chia sẻ khích lệ, chiến
lược proofness, hiệu quả Pareto, và ghen tị-freeness. Trong phần này, chúng ta xem xét hai
trong số những lựa chọn thay thế, chúng tôi đã điều tra: Công bằng tài sản, một chính sách

đơn giản và trực quan mà nhằm mục đích cân bằng tổng hợp nguồn lực được phân bổ cho
mỗi người dùng, và cân bằng cạnh tranh từ Thu nhập bình đẳng (CEEI), các chính sách và
lựa chọn khá phân bổ nguồn lực trong lĩnh vực kinh tế vi mô.
12
12


5.1 Công bằng tài sản.
Ý tưởng đằng sau tài sản Công bằng là những phần bằng nhau của các nguồn tài
nguyên khác nhau có giá trị như nhau, tức là 1% của tất cả các CPU có giá trị là giống như
1% bộ nhớ và 1% / O băng thông I. Công bằng tài sản sau đó cố gắng để cân bằng các giá
trị tài nguyên tổng hợp phân bổ cho mỗi người dùng. Đặc biệt, Công bằng tài sản tính cho
mỗi người dùng i phần theaggregate xi = Pj si, j, nơi si, j là chia sẻ tài nguyên j cho người
dùng i. Sau đó nó được áp dụng max-min trên cổ phiếu tổng hợp của người sử dụng, ví dụ,
nó liên tục tung ra các nhiệm vụ cho người sử dụng với các phần tổng hợp tối thiểu.
Hãy xem xét các ví dụ trong phần 4.1. Vì có hai lần như nhiều GB của RAM như
CPU (tức là, 9 CPU và 18 GB RAM), một CPU có giá trị gấp đôi so với một GB bộ nhớ
RAM. Giả sử rằng một trong GB trị giá $ 1 và một CPU là giá trị $ 2, sau đó người dùng A
dành 6 $ cho mỗi công việc, trong khi người dùng B dành $ 7. Cho x và y là các số nhiệm
vụ giao tài sản Công bằng cho người sử dụng A và B, tương ứng. Sau đó, việc phân bổ tài
sản hợp lý được đưa ra bởi các giải pháp cho các vấn đề tối ưu hóa sau đây:

Giải quyết các vấn đề trên sản lượng x = 2,52 và y = 2,16. Vì vậy, người dùng A
được CPU h2.5, 10.1 GBI, trong khi người dùng B được CPU h6.5, 2.2 GBI, tương ứng.
Trong khi chính sách phân bổ này có vẻ hấp dẫn trong sự đơn giản của nó, nó có
một nhược điểm quan trọng: nó vi phạm sở hữu chia sẻ khích lệ. Như chúng ta thấy trong
Phần 6.1.1, công bằng tài sản có thể dẫn đến một người sử dụng nhận được ít hơn 1 / n của
tất cả các nguồn lực, trong đó n là tổng số người dùng.

5.2 Cân bằng cạnh tranh từ Thu nhập bình đẳng.

Theo lý thuyết kinh tế vi mô, phương pháp ưa thích để phân chia các nguồn lực là
khá cân bằng cạnh tranh từ Thu nhập bình đẳng (CEEI) [22, 30, 33]. Với CEEI, mỗi người
sử dụng nhận ban đầu 1 / n của mỗi tài nguyên, và sau đó, mỗi người sử dụng tài nguyên
nghề của mình với những người dùng khác trong một market.3 cạnh tranh hoàn hảo Kết
quả của CEEI là cả ghen tị miễn phí và hiệu quả Pareto.
13
13


Chính xác hơn, việc phân bổ CEEI được đưa ra bởi các thương lượng Nash
solution4 [22, 23]. Các giải pháp thương lượng Nash chọn phân bổ khả thi nhằm tối đa hóa
Qi ui (ai), nơi ui (ai) là tiện ích cho người sử dụng tôi nhận được từ việc giao cô ai. Để đơn
giản hóa việc so sánh, chúng tôi giả định rằng các tiện ích mà người dùng nhận được từ
việc giao cô chỉ đơn giản là phần chi phối, si của mình.
Xem xét lại các ví dụ hai người dùng trong phần 4.1. Nhớ lại rằng cổ phần chi phối
của người A 4x / 18 = 2x / 9, trong khi các cổ phần chi phối của người dùng B là 3Y / 9 = y
/ 3, trong đó x là số lượng nhiệm vụ được giao để A và y là số nhiệm vụ được giao B. Tối
đa hoá các sản phẩm của các cổ phần chi phối là tương đương với tối đa hóa các sản phẩm
x · y. Như vậy, CEEI nhằm giải quyết các vấn đề tối ưu hóa sau đây.

Giải
lượng x =
vậy,
người
16,4
GBI,
được
CPU

quyết các vấn đề trên sản

45/11 và y = 18/11. Vì
dùng A được CPU h4.1,
trong khi người dùng B
h4.9, 1.6 GBI.

Thật không may, trong khi CEEI là ghen tị miễn phí và Pareto cách hiệu ficient, nó
chỉ ra rằng nó không phải là chiến lược bằng chứng, như chúng ta sẽ thấy trong phần 6.1.2.
Do đó, người dùng có thể tăng phân bổ của họ bằng cách nói dối về nhu cầu tài nguyên của
họ.

5.3 So sánh với DRF.
Để cung cấp cho người đọc một sự hiểu biết trực quan của tài sản Công bằng và
CEEI, chúng ta so sánh phân bổ của họ ví dụ trong phần 4.1 để mà của DRF trong hình 4.
14
14


Chúng tôi thấy rằng DRF equalizes cổ phần chi phối của người sử dụng, ví dụ,
người sử dụng của một phần bộ nhớ và sử dụng CPU phần B của. Ngược lại, tài sản Công
bằng equalizes tổng phần nhỏ tài nguyên được phân bổ cho mỗi người dùng, ví dụ, các khu
vực của hình chữ nhật cho mỗi người dùng trong hình. Cuối cùng, vì CEEI giả định một thị
trường cạnh tranh hoàn hảo, nó tìm thấy một giải phóng mặt bằng giải pháp thị trường đáp
ứng, nơi mọi nguồn lực đã được phân bổ. Thật không may, bất động sản chính xác điều
này làm cho nó có thể để lừa CEEI: người dùng có thể yêu cầu cô ấy cần thêm một số tài
nguyên sử dụng đúng mức, ngay cả khi cô ấy không, dẫn CEEI để cung cấp cho nhiều
nhiệm vụ tổng thể cho người dùng này để đạt được giải phóng mặt bằng thị trường.

6 Analysis.
Trong phần này, chúng tôi thảo luận mà các thuộc tính trình bày trong phần 3 được
hài lòng bởi Asset Công bằng, CEEI, và DRF. Chúng tôi cũng đánh giá tính chính xác của

DRF khi kích thước công việc không phù hợp với các nguồn lực sẵn có chính xác.

6.1 Fairness Properties.

Bảng 2 tóm tắt các thuộc tính công bằng được hài lòng bởi Asset Công bằng, CEEI,
và DRF. Phần phụ lục có chứa các bằng chứng của các thuộc tính chính của DRF, trong
khi báo cáo kỹ thuật của chúng tôi [14] chứa một danh sách đầy đủ hơn về kết quả cho
DRF và CEEI. Trong phần còn lại của phần này, chúng tôi thảo luận về một số các mục
mất tích thú vị trong bảng, ví dụ, tính chất vi phạm của từng môn học. Đặc biệt, chúng tôi
hiển thị thông qua các ví dụ tại sao tài sản Công bằng và CEEI thiếu các tài sản mà họ làm,
và chúng tôi chứng minh rằng không có chính sách có thể cung cấp tài nguyên mà không
đơn điệu iolating hoặc chia sẻ khuyến khích hoặc hiệu quả Pareto để giải thích lý do tại sao
DRF thiếu đơn điệu tài nguyên.

15
15


1.1.1.1. 6.1.1 Properties Violated by Asset Fairness.
Trong khi được các chính sách đơn giản, tài sản Công bằng là vi phạm một số thuộc
tính quan trọng: sự khuyến khích chia sẻ, công bằng nút cổ chai, và đơn điệu tài nguyên.
Tiếp theo, chúng tôi sử dụng ví dụ cho thấy các vi phạm của các đặc tính này.
Định lý 1 tài sản vi phạm Công bằng tài sản chia sẻ khích lệ.
Proof xem xét ví dụ sau đây, minh họa trong Hình 5: hai người sử dụng trong một
hệ thống với h30, tổng nguồn 30I có nhu cầu vectơ D1 = h1, 3i, và D2 = h1, 1i. Công bằng
tài sản sẽ phân bổ sử dụng đầu tiên 6 nhiệm vụ và người dùng thứ hai 12 nhiệm vụ. Người
dùng đầu tiên sẽ nhận được h6, nguồn 18i, trong khi thứ hai sẽ sử dụng H12, 12i.While với
mỗi người dùng một phần tổng hợp bằng nhau của 24 60, người dùng thứ hai được ít hơn
một nửa (15) của cả hai nguồn lực. Điều này vi phạm tài sản chia sẻ khích lệ, là người
dùng thứ hai sẽ được tốt hơn để phân vùng tĩnh cluster và một nửa của riêng của các nút.

Định lý 2 tài sản Công bằng là vi phạm sở hữu công bằng nút cổ chai.
Proof xem xét một kịch bản với một vector nguồn tổng số H21, 21i và hai người
dùng với nhu cầu vectơ D1 = h3, 2i và D2 = h4, 1i, làm cho tài nguyên 1 sự công bằng nút
cổ chai resource.Asset sẽ cung cấp cho mỗi người dùng 3 nhiệm vụ, cân bằng tổng của
chúng sử dụng đến 15. Tuy nhiên, điều này chỉ cung cấp cho người sử dụng đầu tiên 3 /
7of nguồn 1 (các tài nguyên nút cổ chai tranh), vi phạm công bằng nút cổ chai.

16
16


Proof Xét hai người A và B với nhu cầu h4, 2i và h1, 1i và 77 đơn vị của hai nguồn
tài nguyên. Công bằng tài sản phân bổ A tổng cộng h44, 22i và B H33, 33i vạchtổng của
các cổ phiếu 66/77. Nếu tài nguyên hai là tăng gấp đôi, chia sẻ các nguồn tài nguyên thứ
hai cả hai người sử dụng giảm đi một nửa, trong khi tài nguyên đầu tiên được bão hòa.
Công bằng tài sản doanh nghiệp giảm phân bổ A tới h42, 21i và tăng của B để h35, 35I,
cân bằng tỉ số cổ phần của mình để 42/77 +21/154 = 35/77 +35/154 = 105/154 Như vậy tài
nguyên đơn điệu được vi phạm.
1.1.1.2. 6.1.2 Thuộc tính Vi phạm bởi CEEI.
Trong khi CEEI là ghen tị miễn phí và hiệu quả Pareto, nó chỉ ra rằng nó không phải
là bằng chứng chiến lược. Bằng trực giác, điều này là bởi vì CEEI giả định một thị trường
cạnh tranh hoàn hảo mà chieves giải phóng mặt bằng thị trường, tức là, phù hợp với cung
cầu và phân bổ của tất cả các nguồn lực sẵn có. Điều này có thể dẫn đến CEEI cho cổ
phiếu cao hơn nhiều cho người dùng sử dụng nhiều hơn một ít tài nguyên-tranh để sử dụng
đầy đủ các nguồn tài nguyên đó. Do đó, người dùng có thể khẳng định rằng cô ấy cần
nhiều hơn của một số tài nguyên sử dụng đúng mức để tăng thị phần tổng thể của mình về
tài nguyên. Chúng tôi minh họa dưới đây
Định lý 4 CEEI không phải là chiến lược chống.

17

17


Proof xem xét ví dụ sau đây, thể hiện trong hình 6. Giả sử một vector nguồn tổng số
H100, 100i, và hai người dùng có nhu cầu H16, 1i và h1, 2i. Trong trường hợp này, CEEI
giao 100/31 và 1500-1531 nhiệm vụ cho từng người sử dụng tương ứng (khoảng 3,2 và
48,8 nhiệm vụ). Nếu người sử dụng thay đổi 1 vector nhu cầu của mình để H16, 8I, đòi hỏi
nhiều hơn các nguồn tài nguyên 2 hơn cô thực sự cần, CEEI cung cấp cho các người dùng
và 25/6 100/3 nhiệm vụ tương ứng (khoảng 4,2 và 33,3 nhiệm vụ). Vì vậy, người sử dụng
cải thiện 1 số nhiệm vụ 3,2-4,2 cô nói dối về vector nhu cầu của mình. User 2 bị vì điều
này, như phân công nhiệm vụ của mình giảm đi.
Ngoài ra, với lý do cùng trực quan (giải phóng mặt bằng thị trường), chúng ta có các
kết quả sau:
Định lý 5 CEEI vi phạm đơn điệu dân.
Proof Xem xét tổng H100 vector nguồn, 100i và ba người dùng với các vectơ cầu
sau D1 = h4, 1i, D2 = h1, 16I, và D3 = H16, 1i (xem hình 7) .CEEI sẽ mang lại việc phân
bổ A1 = h11. 3, 5.4, 3.1i, nơi các con số trong ngoặc đơn đại diện cho số của nhiệm vụ
được phân bổ cho mỗi người dùng. Nếu người sử dụng 3 rời khỏi hệ thống và tuyên bố từ
bỏ tài nguyên của mình, cung cấp cho các CEEI mới phân bổ A2 = h23.8, 4.8i, mà đã làm
cho người sử dụng 2 tồi tệ hơn trong A1.
1.1.1.3. 6.1.3 Resource đơn điệu so với ưu đãi Chia sẻ và hiệu quả Pareto
Như thể hiện trong Bảng 2, DRF đạt được tất cả các thuộc tính trừ đơn điệu tài
nguyên. Thay vì là một hạn chế của DRF, đây là một hệ quả của thực tế là khuyến khích
chia sẻ, hiệu quả Pareto, và đơn điệu tài nguyên không thể đạt được cùng một lúc. Kể từ
khi chúng tôi xem xét hai đầu tiên của những tài sản này là quan trọng hơn (xem phần 3)
và từ khi bổ sung nguồn lực mới cho một hệ thống là một sự kiện tương đối hiếm, chúng
tôi đã chọn để chia sẻ khích lệ đáp ứng và hiệu quả Pareto, và bỏ đơn điệu tài nguyên. Đặc
biệt, chúng tôi có các kết quả sau.
18
18



Định lý 6 Không có chính sách giao đáp ứng các khuyến khích chia sẻ và tính hiệu
quả Pareto cũng có thể đáp ứng đơn điệu tài nguyên.
Proof Chúng tôi sử dụng một ví dụ đơn giản để chứng minh property.Consider này
hai người A và B đối xứng với nhu cầu h2, 1i, và h1, 2i, tương ứng, và giả định bằng lượng
của cả hai nguồn lực. Chia sẻ khuyến khích yêu cầu người dùng A được ít nhất một nửa tài
nguyên 1 và sử dụng B được một nửa nguồn 2. By hiệu quả Pareto, chúng ta biết rằng ít
nhất một trong hai người phải được phân bổ thêm nguồn lực. Không mất tính tổng quát,
giả sử rằng người dùng A được đưa ra hơn một nửa nguồn 1 (một đối số đối xứng giữ nếu
sử dụng B được đưa ra hơn một nửa tài nguyên 2). Nếu tổng lượng tài nguyên 2 bây giờ đã
tăng theo hệ số 4, người B không còn nhận được phần uaranteed của một nửa số tài nguyên
2. Bây giờ, việc phân bổ chỉ khả thi đáp ứng các khuyến khích chia sẻ là để cho cả người
sử dụng một nửa số tài nguyên 1, mà sẽ yêu cầu giảm ser 1 chia sẻ của tài nguyên 1, do đó
vi phạm tài nguyên đơn điệu.
Định lý này giải thích tại sao cả DRF và đơn điệu CEEI vi phạm tài nguyên.

6.2 Discrete Resource Allocation.
Cho đến nay, chúng ta đã mặc nhiên thừa nhận một hồ bơi tài nguyên lớn có nguồn
tài nguyên có thể được phân bổ một lượng nhỏ tùy ý. Tất nhiên, điều này thường không
phải là trường hợp trong practice.For dụ, cụm gồm nhiều máy nhỏ, nơi các nguồn lực được
phân bổ cho các nhiệm vụ với số lượng rời rạc. Trong lời nhắc nhở của phần này, chúng tôi
đề cập đến hai kịch bản này là liên tục, và kịch bản rời rạc, tương ứng. Bây giờ chúng ta
chuyển sự chú ý của chúng tôi như thế nào để công bằng được ảnh hưởng trong kịch bản
rời rạc.
Giả sử một cụm gồm máy K. Hãy tối đa tác vụ biểu thị vector tối đa nhu cầu trên tất
cả các vectơ nhu cầu, tức là, max-task = {hmaxi di, 1}, {maxi di, 2}, · · ·, maxi {di, m} i.
Giả sử thêm rằng bất kỳ nhiệm vụ có thể được dự kiến trên mỗi máy, tức là, tổng số lượng
tài nguyên trên mỗi máy tính là ít nhất tối đa tác vụ. Chúng tôi chỉ xem xét các trường hợp
khi mỗi người dùng có nhu cầu nghiêm ngặt tích cực. Với những giả định, chúng ta có kết

quả sau.

19
19


Định lý 7 Trong kịch bản rời rạc, có thể để phân bổ các nguồn lực như vậy mà sự
khác biệt giữa các phân bổ của hai người được bao bọc bởi một max-nhiệm vụ so với kịch
bản phân bổ liên tục.
Proof Giả sử chúng ta bắt đầu phân bổ nguồn lực vào một máy tại một thời gian, và
rằng chúng tôi luôn dành một nhiệm vụ cho người sử dụng với các phần chi phối thấp nhất.
Miễn là có ít nhất một tối đa tác vụ có sẵn trên máy tính đầu tiên, chúng tôi tiếp tục giao
nhiệm vụ cho người sử dụng tiếp theo với phần vượt trội nhất. Một khi các nguồn lực sẵn
có trên máy tính đầu tiên trở nên ít hơn một kích thước tối đa tác vụ, chúng tôi di chuyển
đến các máy tiếp theo và lặp lại quá trình này. Khi hoàn thành việc phân bổ, sự khác biệt
giữa hai phân bổ của người sử dụng tài nguyên thống trị của họ so với các kịch bản liên tục
nhiều nhất là tối đa tác vụ. Nếu đây không phải là trường hợp, sau đó một số người dùng A
sẽ có nhiều hơn max-nhiệm vụ khác biệt wrt cho một người dùng B. Tuy nhiên, điều này
không thể là trường hợp, vì thời gian qua A đã được giao một nhiệm vụ, B nên đã được
giao một nhiệm vụ thay thế.

20
20


7. Kết quả thực nghiệm.
Phần này đánh giá DRF qua vi và macrobenchmarks. Các cựu được thực hiện thông
qua các thí nghiệm chạy một thực thi của DRF trong quản lý tài nguyên cụm Mesos [16].
Sau này được thực hiện bằng cách sử dụng mô phỏng tracedriven.
Chúng tôi bắt đầu bằng cách hiển thị DRF động điều chỉnh các cổ phiếu của các

công việc có nhu cầu nguồn lực khác nhau tại mục 7.1. Trong phần 7.2, chúng ta so sánh
với khe DRF cấp chia sẻ công bằng (như thực hiện bởi Hadoop Fair Scheduler [34] và
Quincy [18]), và CPU chỉ chia sẻ công bằng. Cuối cùng, tại mục 7.3, chúng ta sử dụng
Facebook để so sánh dấu vết DFT và Fair Scheduler của Hadoop về sử dụng và thời gian
hoàn thành công việc.

7.1 Dynamic Resource Sharing.
Trong thí nghiệm đầu tiên của chúng tôi, chúng tôi hiển thị như thế nào DRF động
chia sẻ tài nguyên giữa các công việc có yêu cầu khác nhau. Chúng tôi đã gặp hai công
việc trên 48-nút Mesos cluster trên Amazon EC2, sử dụng "cực lớn" hợp với 4 lõi CPU và
15 GB bộ nhớ RAM. Chúng tôi cấu hình mesos để phân bổ lên đến 4 CPU và 14 GB bộ
nhớ RAM trên mỗi nút, để lại 1 GB cho hệ điều hành. Chúng tôi gửi hai công việc mà đưa
ra các nhiệm vụ với nhu cầu nguồn lực khác nhau vào những thời điểm khác nhau trong
một khoảng thời gian 6 phút.
Con số 8 (a) và 8 (b) cho thấy CPU và bộ nhớ phân bổ cho từng công việc như là
một hàm của thời gian, trong khi hình 8 (c) cho thấy cổ phần chi phối của họ. Trong 2 phút
đầu tiên, việc sử dụng 1 CPU h1, 10 GB Rami mỗi nhiệm vụ và công việc của 2 sử dụng
CPU h1, 1 GB Rami mỗi nhiệm vụ. Nguồn lực chi phối công việc của 1 là RAM, trong khi
tài nguyên thống trị công việc của 2 là CPU. Lưu ý rằng DRF equalizes cổ phiếu của các
công việc của các nguồn tài nguyên thống trị của họ. Ngoài ra, vì công việc có nguồn lực
21
21


chi phối khác nhau, cổ phần chi phối của họ vượt quá 50%, tức là, việc sử dụng 1 khoảng
70% của RAM trong khi việc sử dụng 2 khoảng 75% của CPU. Vì vậy, các công việc được
hưởng lợi từ chạy trong một cụm chia sẻ chứ không phải dùng một nửa các nút từng. Điều
này nắm bắt được bản chất của tài sản chia sẻ ưu đãi.
Sau 2 phút, các kích cỡ nhiệm vụ của cả hai công việc thay đổi, để CPU h2, 4 GBI
cho công việc và 1 CPU h1, 3 GBI cho công việc 2. Bây giờ, tài nguyên thống trị cả hai

công việc "là CPU, vì vậy DRF equalizes cổ phần CPU của họ. Lưu ý rằng DRF tắc phân
bổ tự động bởi có Mesos phục vụ nguồn lực cho công việc với các phần chi phối nhỏ nhất
là nhiệm vụ hoàn thành.
Cuối cùng, sau hơn 2 phút, các kích cỡ nhiệm vụ của cả hai công việc thay đổi một
lần nữa: CPU h1, 7 GBI cho công việc và 1 CPU h1, 4 GBI cho công việc 2. tài nguyên
thống trị của cả hai việc làm bây giờ là bộ nhớ, do DRF cố gắng để cân bằng trí nhớ của họ
cổ phiếu. Lý do các cổ phiếu không chính xác bằng nhau là do sự phân mảnh tài nguyên
(xem mục 6.2).

7.2 DRF vs. Alternative Allocation Policies.
Tiếp theo chúng tôi đánh giá DRF đối với hai phương án thay thế với: lập lịch công
bằng khe dựa trên (một chính sách chung trong các hệ thống hiện tại, chẳng hạn như
Hadoop Fair Scheduler [34] và Quincy [18]) và (max-min) chia sẻ công bằng chỉ áp dụng
cho một nguồn duy nhất (CPU). Với thử nghiệm, chúng tôi chạy một 48-nút Mesos cluster
trên EC2 với 8 lõi CPU và 7 GB RAM mỗi. Chúng tôi cấu hình mesos để phân bổ 8 CPU
và RAM 6 GB trên mỗi nút, để lại 1 GB miễn phí cho hệ điều hành. Chúng tôi thực hiện
các chính sách lập lịch trình ba là module phân bổ Mesos.
Chúng tôi chạy một khối lượng công việc với hai lớp người dùng, đại diện cho hai
đơn vị tổ chức với workloads.One khác nhau của các đối tượng đã bốn người dùng gửi các
công việc nhỏ với nhiệm vụ đòi hỏi CPU h1, 0,5 GBI. Các khác en-tity có bốn người dùng
gửi các công việc lớn với CPU nhiệm vụ demandsh2, 2 GBI. Mỗi công việc bao gồm 80
tasks.As ngay sau khi hoàn thành một công việc, người sử dụng sẽ khởi động một công
việc khác có nhu cầu tương tự. Mỗi thí nghiệm chạy cho mười phút. Cuối cùng, chúng tôi
tính toán số lượng công việc hoàn thành của từng loại, cũng như thời gian phản ứng của
họ.
22
22


Đối với các đề án phân bổ khe-based, chúng tôi thay đổi số lượng các khe trên mỗi

máy 3-6 để xem làm thế nào nó ảnh hưởng đến hiệu suất. Hình 9 đến 12 cho thấy kết quả
của chúng tôi. Trong hình 9 và 10, chúng ta so sánh số lượng việc làm của mỗi loại hoàn
thành cho mỗi chương trình lập kế hoạch trong mười phút. Trong hình 11 và 12, chúng ta
so sánh thời gian đáp ứng trung bình.
Một số xu hướng này là rõ ràng từ dữ liệu. Đầu tiên, với lịch khe dựa trên, cả hai
thông lượng và đáp ứng công việc thời gian được tồi tệ hơn với DRF, không phụ thuộc vào
số lượng các khe. Điều này là bởi vì với một số khe thấp, chức năng lịch có thể
undersubscribe nút (ví dụ,, khởi động chỉ có 3 nhiệm vụ nhỏ trên một nút), trong khi với
một số khe lớn, nó có thể oversubscribe chúng (ví dụ, chạy 4 nhiệm vụ lớn vào một nút và
gây ra trao đổi bởi vì mỗi công việc cần 2 GB và các nút chỉ có 6 GB). , Với thứ hai chia sẻ
công bằng ở cấp độ của CPU, số lượng việc làm nhỏ thực hiện tương tự như DRF, nhưng
có rất ít việc làm lớn thực hiện, bởi vì bộ nhớ hơn cam kết trên một số máy móc và dẫn đến
hoạt động kém hiệu cho tất cả các nhiệm vụ bộ nhớ cao chạy đó. Nhìn chung, việc lập lịch
DRFbased đó là nhận thức của cả nguồn lực có thời gian đáp ứng thấp nhất và thông lượng
tổng thể cao nhất.

7.3 Simulations using Facebook Traces.
Tiếp theo chúng ta sử dụng dấu vết đăng nhập từ một cụm nút 2000 tại Facebook,
chứa dữ liệu cho một khoảng thời gian một tuần (tháng 10 năm 2010). Các dữ liệu bao
gồm việc làm Hadoop MapReduce. Chúng tôi giả định thời gian công tác, sử dụng CPU và
23
23


bộ nhớ tiêu thụ là giống hệt như trong các dấu vết ban đầu. Các dấu vết được mô phỏng
trên một cụm nhỏ hơn 400 nút để đạt được mức sử dụng cao hơn, như vậy là công bằng trở
thành có liên quan. Mỗi nút trong cluster gồm 12 khe cắm, 16 lõi, và bộ nhớ 32 GB. Hình
13 cho thấy một đoạn ngắn 300 thứ hai phụ mẫu để hình dung như thế nào CPU và bộ nhớ
sử dụng tìm kiếm các khối lượng công việc tương tự khi sử dụng DRF so với lịch công
bằng Hadoop của (slot). Như thể hiện trong hình, DRF cung cấp sử dụng cao hơn, vì nó có

thể
Hình 14 cho thấy việc giảm trung bình thời gian hoàn thành công việc cho DRF so
với lịch công bằng Hadoop. Khối lượng công việc khá nặng về việc làm nhỏ,mà không có
kinh nghiệm cải tiến (ví dụ, -3%). Điều này là bởi vì các công việc nhỏ thường bao gồm
một giai đoạn thực thi duy nhất, và thời gian hoàn thành được chi phối bởi các nhiệm vụ
dài nhất. Như vậy thời gian hoàn thành là khó để cải thiện cho các công việc nhỏ như vậy.
Ngược lại, thời gian hoàn thành các công việc lớn giảm của nhiều như 66%. Đây là việc
làm becausethese bao gồm nhiều giai đoạn, và do đó họ có thể được hưởng lợi từ việc sử
dụng cao hơn đạt được bằng DRF.

8. Related Work.
Chúng tôi cũng đã xem xét các công việc liên quan trong khoa học máy tính và kinh
tế.
Trong khi

nhiều bài báo về khoa

học máy tính tập

trung vào sự công bằng

nhiều

chúng ta chỉ xem xét

nguồn,

nhiều trường hợp

của


nguyên thay thế

cho nhau cùng, ví dụ,

CPU [6, 7, 35],

và băng thông [10, 20,

21].

Không

giống như các phương

pháp này, chúng

tôi tập trung vào việc

phân

nguồn lực của các loại

bổ

các

khác nhau.

24

24

các

nguồn

tài


Quincy [18] là một lịch trình phát triển trong bối cảnh khuôn khổ Dryad tính toán
cluster [17]. Quincy đạt được sự công bằng bằng cách mô phỏng vấn đề công bằng lịch
trình như một vấn đề dòng min-chi phí. Quincy hiện không hỗ trợ công bằng nhiều nguồn
lực. trong thực tế, như đã đề cập trong phần thảo luận của bài báo [18, tr. 17], nó xuất hiện
khó khăn để kết hợp các yêu cầu đa tài nguyên vào việc xây dựng dòng chảy min-chi phí.
Hadoop hiện đang cung cấp hai bộ kế hoạch chia sẻ công bằng [1, 2, 34]. Cả hai bộ
kế hoạch phân bổ nguồn lực tại granularity khe, nơi một khe cắm là một phần cố định của
các nguồn tài nguyên trên một máy. Kết quả là, các bộ kế hoạch có thể không phải
lúc nào cũng phù hợp với việc phân bổ tài nguyên với nhu cầu của công việc, đặc biệt là
khi những nhu cầu là không đồng nhất rộng rãi. Như chúng tôi đã trình bày trong phần 7,
không phù hợp này có thể dẫn đến việc sử dụng một trong hai cụm thấp hoặc hiệu suất
kém do tài nguyên trên thuê bao.
Trong các tài liệu kinh tế vi mô, các vấn đề của equityhas được nghiên cứu trong và
ngoài khuôn khổ của lý thuyết trò chơi. Những cuốn sách của trẻ [33] và Moulin [22]
là hoàn toàn dành riêng cho các chủ đề và cung cấp giới thiệu tốt. Các phương pháp
ưa thích của bộ phận công bằng trong kinh tế vi mô là CEEI [3, 33, 22], như đã giới thiệu
25
25