סמינר: ceClub: The Technion Computer Engineering Club

קהילת נשות הנדסת חשמל ומחשבים

Quantized Consistent Hashing

Date: March,29,2023 Start Time: 11:30 - 12:30
Location: חדר 861, בניין מאייר, הפקולטה להנדסת חשמל ומחשבים
Add to:
Lecturer: Yoav Levi

Consistent hashing (CH) is a crucial building block for load-balancers. It enables packets of the same flow to keep being mapped to the same server whenever possible. However, papers from the literature and leading load-balancers rely on heuristic algorithms to implement heterogeneous CH, without any ability to provide stability guarantees.

In this talk, I present a new framework for heterogeneous CH. The framework relies on quantization using virtual servers, and on a min-max fairness-based mapping algorithm.  The main result is the establishment of the necessary and sufficient conditions for guaranteeing stability for any arbitrary heterogeneous server service rate. I further demonstrate how limiting the set of allowed service rates enables attaining the maximal stability region for heterogeneous CH. Practical evaluations show that existing solutions suffer from significant stability issues, while the offered solution can leverage its stability guarantees. Finally, I show that the offered solution has better scalability properties, including a faster key lookup rate and a lower memory footprint.

M.Sc. student under the supervision of Prof. Isaac Keslassy.

 

כל הסמינרים
דילוג לתוכן