Join-Idle-Queue：动态可扩展Web服务的新型负载均衡算法

144 浏览量更新于2024-07-14 收藏 372KB PDF 举报

"Join-Idle-Queue 是一种针对动态可扩展Web服务的新颖负载均衡算法，由Yi Lua、Qiaomin Xie、Gabriel Kliot、Alan Geller、James R. Larus和Albert Greenberg提出，分别来自伊利诺伊大学厄巴纳-香槟分校的电气与计算机工程系、微软研究的极端计算组和微软Azure团队。该算法旨在解决动态内容web服务（如搜索引擎和在线社交网络）日益增长的需求，以及云环境中的横向扩展问题。在云环境中，由于其弹性特性，横向扩展成为动态内容Web服务的首选解决方案。现有的分布式调度器通常采用集中式设计的算法，如Join-the-Shortest-Queue (JSQ)，这种算法在分布式调度时会产生高通信开销。 Join-Idle-Queue (JIQ)算法是为了解决这一问题而提出的，它属于一种分布式负载均衡算法。与Power-of-Two等算法不同，JIQ算法在任务到达时，调度器和处理器之间不产生任何通信开销。在大规模系统极限分析中，JIQ算法被发现能有效地减少系统的同步延迟，提高整体效率。通过让新到达的任务加入空闲队列，而不是选择最短队列，JIQ算法减少了调度器与处理器之间的通信交互，从而降低了系统的整体开销。这种策略可以降低系统的复杂性，同时确保服务质量和响应时间的提升。此外，JIQ算法还能帮助平衡工作负载，防止某些服务器过载，而其他服务器空闲。在论文中，作者们对JIQ算法进行了深入的理论分析，并可能提供了模拟或实证结果来证明其在实际应用中的性能优势。他们可能还讨论了与现有负载均衡策略的比较，以及如何在动态变化的工作负载条件下优化该算法的性能。此外，可能还探讨了JIQ算法在云服务提供商如Microsoft Azure等平台上的潜在实施和影响。 Join-Idle-Queue算法提供了一种创新的解决方案，解决了分布式系统中的负载均衡挑战，尤其适用于那些需要快速响应时间和高效率的动态Web服务。这项工作对于理解如何在大型云环境中实现更高效、更节省资源的负载分配具有重要意义，为未来的云服务设计和优化提供了新的思路。"

arrivals. In particular, reporting decisions are made locally by each processor, which can take into account

its heterogeneity. Note that data locality is not a problem in the front end where the servers are responsible

for gathering data from the back end and organizing them into pages. The general distribution of arrival

intervals does not change the analysis in the large system limit as the arrivals at an individual dispatcher

become Poisson. The evaluation of the performance of JIQ algorithm is based on simulation with a variety of

service time distributions, corresponding to diﬀerent application workloads. Since the JIQ algorithm exploits

the large scale of the system, a testbed capturing its behavior will need to contain at least hundreds, if not

thousands of servers, which is not available at the moment. We defer the implementation details of the JIQ

algorithm to future publications.

Section 2 describes the JIQ algorithm with distributed dispatchers. We analyze the algorithm in the

large system limit with general service time distributions in Section 3 and discuss design extensions and

implementation issues in Section 4. Section 5 compares the performance of the JIQ algorithm with the SQ(2)

algorithm via simulation.

2 The Join-Idle-Queue Algorithm

Consider a system of n parallel homogeneous processors interconnected with commo dity network components.

There are an array of m dispatchers, with m << n. Requests arrive at the system as a rate-nλ Poisson process.

Each request is directed to a randomly chosen dispatcher, which assigns it to a processor. The service time

of a request is assumed to be i.i.d. with a general service time distribution B(·) of mean 1. We consider both

PS and FIFO service disciplines.

The objective of the load balancing algorithm is to provide fast response time at each processor without

incurring excessive communication overhead. In particular, communication overhead on the critical path,

i.e., at the arrival of a request, is to be avoided as it adds to the overall response time. Communication

oﬀ the critical path is much less costly as it can ride on heartbeats sent from processors to job dispatchers

signalling the health of the nodes.

2.1 Preliminary

There are two ways to think about load balancing in a system of parallel processors. As an entire system,

the processors collaborate to adapt quickly to the randomness in the arrival process and service times. On

the other hand, when focusing on a single processor, eﬃcient load balancing changes the arrival rate to

the processor based on the number of jobs in its queue. In particular, it increases the arrival rate to idle

processors and decreases that to processors with a large queue size. This results in shorter busy cycles for

each processor and faster response time.

To illustrate the eﬀect of length of busy cycles on response times, compare the two busy cycle patterns

on a single processor illustrated in Fig. 2. The letter ’b’ denotes ’busy’ and the letter ’i’ denotes ’idle’. The

two patterns can result from diﬀerent load balancing schemes in the system. The load is the same for both

patterns, as they share the same mean idle time. However, pattern 2 indicates a much larger arrival rate

than pattern 1 when the processor is idle. This results in shorter busy cycles and a much shorter response

time.

i b i

i i i i

b

b b

b

Pattern 1:

Pattern 2:

Figure 2: Busy (b) / idle (i) patterns of a processor.

Motivated by the above, we compare the rate of arrival to an idle processor, λ

, for the following three

algorithms. With rate-nλ arrivals and n processors of service rate 1, the load on the system is λ. The Random

剩余17页未读，继续阅读

weixin_38553381

粉丝: 1
资源: 924

Join-Idle-Queue：动态可扩展Web服务的新型负载均衡算法

前端项目-ng-idle.zip

Python库 | django-session-idle-timeout-1.3.0.tar.gz

Invasive weed optimization algorithm for optimization no-idle flow shop scheduling problem

ng2-idle-example:ng2-idle的示例

A-Mazing-Idle

Idle102-idle

open-defi-idle-protocol-gr9

前端开源库-react-redux-idle-monitor

meteor-idle-watcher-ui

hd-idle-开源

最新资源