Enhancing Memcached Traffic Load Balancing using SDN
Load Balancing Memcached Traffic
Using SDN
Supported by the European Research Council under the European Union's Seventh
Framework Programme
Idan Moyal
Interdisciplinary Center Herzliya, Israel
Joint work with:
Memcach
ed
•
Memcached is
a widely-used
in-memory
key value based distributed caching system
Memcached
•
Memcached is
a widely-used
in-memory
key value based distributed caching system
Application Server
Application Server
Application Server
L
o
a
d
B
a
l
a
n
c
e
r
DBMS
Get movie
review
Get movie
review
Movie
review
Movie
review
Read
review from
DB
Movie Review
Slow Response
Movie Reviews Web Application
Architecture
Memcached
•
Memcached is
a widely-used
in-memory
key value based distributed caching system
Application Server
Application Server
Application Server
L
o
a
d
B
a
l
a
n
c
e
r
DBMS
Get movie
review
Get movie
review
Get cache review
Movie
review
Movie
review
Cache Movie Review
Movie Reviews Web Application
Architecture
Memcached server
is picked by
applying a hash
function on the
requested key
C
A
C
H
E
H
I
T
Memcached
•
Memcached is
a widely-used
in-memory
key value based distributed caching system
Application Server
Application Server
Application Server
L
o
a
d
B
a
l
a
n
c
e
r
DBMS
Get movie
review
Get movie
review
Get cached review
Movie
review
Movie
review
C
A
C
H
E
M
I
S
S
Read
review from
DB
Movie Review
Slow Response
Cache review
Movie Reviews Web Application
Architecture
Memcached server
is picked by
applying a hash
function on the
requested key
The Hot Keys Problem
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
Application Server
Memcached
Client
Application Server
Memcached
Client
Application Server
Memcached
Client
Memcached
Server
L
o
a
d
B
a
l
a
n
c
e
r
DBMS
m
e
m
c
a
c
h
e
d
g
e
t
“
g
u
a
r
d
i
a
n
s
-
o
f
-
t
h
e
-
g
a
l
a
x
y
-
r
e
v
i
e
w
”
Memcached
Server
H
i
g
h
R
e
s
p
o
n
s
e
T
i
m
e
M
e
m
c
a
c
h
e
d
i
g
n
o
r
e
s
k
e
y
p
o
p
u
l
a
r
i
t
y
w
h
e
n
a
s
s
i
g
n
i
n
g
k
e
y
s
t
o
s
e
r
v
e
r
s
Key Popularity Follows Zipf
Distribution
M
o
s
t
p
o
p
u
l
a
r
k
e
y
Our Solution: MBalancer
Our Solution: MBalancer
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
Application Server
Memcached
Client
Application Server
Memcached
Client
Application Server
Memcached
Client
Memcached
Server
L
o
a
d
B
a
l
a
n
c
e
r
DBMS
m
e
m
c
a
c
h
e
d
g
e
t
“
g
u
a
r
d
i
a
n
s
-
o
f
-
t
h
e
-
g
a
l
a
x
y
-
r
e
v
i
e
w
”
Memcached
Server
m
e
m
c
a
c
h
e
d
g
e
t
“
g
u
a
r
d
i
a
n
s
-
o
f
-
t
h
e
-
g
a
l
a
x
y
-
r
e
v
i
e
w
”
G
o
o
d
R
e
s
p
o
n
s
e
T
i
m
e
Our Solution: MBalancer
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
L
o
a
d
B
a
l
a
n
c
e
r
DBMS
Memcached
Server
G
o
o
d
R
e
s
p
o
n
s
e
T
i
m
e
m
e
m
c
a
c
h
e
d
g
e
t
“
g
u
a
r
d
i
a
n
s
-
o
f
-
t
h
e
-
g
a
l
a
x
y
-
r
e
v
i
e
w
”
Application Server
Application Server
Application Server
m
e
m
c
a
c
h
e
d
g
e
t
“
g
u
a
r
d
i
a
n
s
-
o
f
-
t
h
e
-
g
a
l
a
x
y
-
r
e
v
i
e
w
”
Memcached
Client
Memcached
Client
Memcached
Client
S
a
m
e
r
e
q
u
e
s
t
,
d
i
f
f
e
r
e
n
t
d
e
s
t
i
n
a
t
i
o
n
s
?
Our Solution: MBalancer
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
L
o
a
d
B
a
l
a
n
c
e
r
Memcached
Server
G
o
o
d
R
e
s
p
o
n
s
e
T
i
m
e
Application Server
Application Server
Application Server
Memcached
Client
Memcached
Client
Memcached
Client
Memcached
statistics
SDN Switch
Using Software Defined Networking (SDN),
which separates control plane and data plane:
•
Data plane – match action rules
•
Control plane – insert/delete rules
Our Solution: MBalancer
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
L
o
a
d
B
a
l
a
n
c
e
r
Memcached
Server
G
o
o
d
R
e
s
p
o
n
s
e
T
i
m
e
Application Server
Application Server
Application Server
Memcached
Client
Memcached
Client
Memcached
Client
Memcached
statistics
SDN Switch
m
e
m
c
a
c
h
e
d
g
e
t
“
g
u
a
r
d
i
a
n
s
-
o
f
-
t
h
e
-
g
a
l
a
x
y
-
r
e
v
i
e
w
”
•
Payload matching
capabilities of exact
location.
•
Common in many SDN
switches.
Why duplication works?
•
If we look at very few
highly-loaded keys:
–
Most of the system’s load is
concentrated there
–
Very modest memory
overhead to duplicate these
keys’ values
–
Only a few switching rules
suffices to support load
balancing
Why duplication works?
•
Imbalance factor = average load / max load
•
The closer the imbalance factor is to 1, the
higher the throughput is.
•
Assume only 10 hot keys are duplicated
40-60% improvement
Worsen with the
size of the system
MBalancer
Tasks
1.
Hot keys
identification
2.
L
oad-balanc
e request
in the switch.
3.
Hot Keys <Key,Value> updating and
duplication to
additional
/all
Memcached
servers
Task 1: Hot Keys Identification
•
Identification using off
–
the-shelf
techniques (not part of MBalancer)
–
Tumblr’s, Etsy’s
–
Can also use sFlow, OpenFlow counters
Task 2:Load Balancing in the Switch
Using OpenFlow
G
r
o
u
p
2
.
T
y
p
e
:
S
e
l
e
c
t
F
l
o
w
T
a
b
l
e
G
r
o
u
p
T
y
p
e
S
e
l
e
c
t
(
S
i
n
c
e
O
p
e
n
F
l
o
w
1
.
3
)
:
P
a
c
k
e
t
s
a
r
e
p
r
o
c
e
s
s
e
d
b
y
a
s
i
n
g
l
e
b
u
c
k
e
t
i
n
t
h
e
g
r
o
u
p
.
B
u
c
k
e
t
s
e
l
e
c
t
i
o
n
p
r
o
v
i
d
e
s
e
q
u
a
l
l
o
a
d
s
h
a
r
i
n
g
(
e
.
g
.
,
s
i
m
l
p
l
e
r
o
u
n
d
r
o
b
i
n
)
P
a
y
l
o
a
d
m
a
t
c
h
i
n
g
E
n
t
r
y
p
e
r
h
o
t
k
e
y
g
e
t
r
e
q
u
e
s
t
S
e
r
v
e
r
s
c
o
n
t
a
i
n
i
n
g
t
h
e
h
o
t
k
e
y
s
(
e
.
g
.
a
l
l
s
e
r
v
e
r
s
)
E
n
t
r
y
p
e
r
h
o
t
k
e
y
s
e
t
w
i
l
l
b
e
u
s
e
d
l
a
t
e
r
Load Balancing in the Switch
Using OpenFlow
F
l
o
w
T
a
b
l
e
H
o
t
k
e
y
r
e
q
u
e
s
t
H
o
t
k
e
y
r
e
q
u
e
s
t
r
e
d
i
r
e
c
t
e
d
(
w
o
r
k
s
o
n
l
y
f
o
r
U
D
P
r
e
q
u
e
s
t
s
)
G
r
o
u
p
2
.
T
y
p
e
:
S
e
l
e
c
t
P
a
y
l
o
a
d
m
a
t
c
h
i
n
g
L
o
a
d
B
a
l
a
n
c
i
n
g
Total number of rules:
•
Per hot key: 1 get rule, 1 set rule
•
Plus # of groups multiple by group rule size
•
Group rule size is bounded by the number of
servers
Task 3: Key Updating and Duplication
(
OpenFlow
Implementation)
G
r
o
u
p
2
.
T
y
p
e
:
S
e
l
e
c
t
F
l
o
w
T
a
b
l
e
K
e
y
s
a
r
e
i
n
s
t
a
l
l
e
d
a
n
d
u
p
d
a
t
e
d
w
i
t
h
s
e
t
o
p
e
r
a
t
i
o
n
s
H
o
t
K
e
y
s
u
p
d
a
t
e
s
a
r
e
c
a
p
t
u
r
e
d
a
n
d
s
e
n
t
t
o
t
h
e
c
o
n
t
r
o
l
l
e
r
S
D
N
C
o
n
t
r
o
l
l
e
r
•
MBalancer application contains a memcached client
•
Re-duplicate hot keys on update
Key Updating and Duplication
Memcached
Server
Memcached
Server
Memcached
Server
Memcached
Server
Application Server
Memcached
Client
Application Server
Memcached
Client
Application Server
Memcached
Client
Memcached
Server
L
o
a
d
B
a
l
a
n
c
e
r
User performs a
request which requires
updating a hot key
Memcached set
“
best-seller
”
T
h
e
s
w
i
t
c
h
i
s
c
o
n
f
i
g
u
r
e
d
t
o
m
a
t
c
h
“
s
e
t
”
h
o
t
k
e
y
s
p
a
c
k
e
t
s
a
n
d
s
e
n
d
a
l
s
o
t
o
t
h
e
c
o
n
t
r
o
l
l
e
r
Memcached get
“
best-seller
”
Memcached set
“
best-seller
”
SDN Switch
D
a
t
a
P
l
a
n
e
C
o
n
t
r
o
l
P
l
a
n
e
M
B
a
l
a
n
c
e
r
A
p
p
l
i
c
a
t
i
o
n
Memcached
Client
Experimental Results
•
Setting:
–
NoviKit 250 SDN switch (1Gbit/s network).
–
RYU SDN controller.
–
64 memcached clients, 2 memcached servers.
–
1000 keys, 100KB values.
–
H=10, Hot Keys are copied to all servers
Experimental results
Z
i
p
f
6
0
/
4
0
7
0
/
3
0
8
0
/
2
0
9
0
/
1
0
Z
i
p
f
6
0
/
4
0
7
0
/
3
0
8
0
/
2
0
9
0
/
1
0
T
h
r
o
u
g
h
p
u
t
L
a
t
e
n
c
y
Comparing with Proxy-Based
Solutions
•
Additional servers
dedicated for hot
keys
–
Hot Keys arrive at the
proxy and sent to one
of the servers behind
it
–
MBalancer does not
require additional
servers and
architecture changes
•
Used by Facebook
The number of extra servers
required to achieve the same
imbalance factor of MBalancer
MBalancer: Limitation
s
•
MBalancer performs load balancing for
Memcached UDP get requests.
–
UDP is usually preferred when the goal is
better performance (Facebook’s solution)
•
SDN switch with payload matching
capabilities is required.
–
Memcached key length is limited (NoviKit250
limitation is 46 bytes).
Conclusions
•
MBalancer
solves an higher level application
issue, the hot keys problem in Memcached
,
using SDN.
–
Solution
does not require a
change
in
the
application’s architecture.
–
Low overhead in the
SDN
switch and memory
footprint.
–
An innovative way
to
perform L7 load balancing
•
Many extensions in the paper, including P4
implementation.
Thank You!
Questions?
Lorelyn Medina 123RF.com
Related Work
SwitchKV
•
Deals with general performance issues in
key value storage systems.
•
Keys are encoded in destination MAC
address UDP packet header.
•
Requires changing client
implementation.
BlowFish (based on Succinct)
•
An optimized distributed storage system
which can serve as a general purpose
database.
•
According to monitoring data, performs
in-memory caching, load-balancing and
scheduling.
•
Outperforms selective caching when
handling zipf workloads.
•
Is not built for handling the use cases
Memcached does.
Hot keys updating
•
Memcached set requests are captured by
MBalancer.
•
For each set request, MBalancer reads the
updated value from the destination server
(when it gets there).
•
MBalancer writes the updated value to all
relevant Memcached servers.
The limitation of this solution is that in some
cases, the servers containing the
duplicated hot keys, may serve stale data
for a short time.
Explore the joint research work on Load Balancing Memcached Traffic utilizing Software-Defined Networking (SDN) by Idan Moyal and team from Herzliya, Israel. The study delves into the efficient management of Memcached servers, addressing the Hot Keys Problem and optimizing key assignment to servers based on key popularity. Memcached, a prevalent distributed caching system, plays a crucial role in improving performance in memory-based key-value storage systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Load Balancing Memcached Traffic Using SDN Idan Moyal Interdisciplinary Center Herzliya, Israel Joint work with: Anat Bremler-Barr IDC Herzliya David Hay Hebrew University Liron Schiff Tel-Aviv University Supported by the European Research Council under the European Union's Seventh Framework Programme
Memcached Memcached is a widely-used in-memory key value based distributed caching system
Memcached Memcached is a widely-used in-memory key value based distributed caching system Movie Reviews Web Application Architecture DBMS Application Server Get movie review Application Server Load Balancer Movie review Application Server
Memcached Memcached is a widely-used in-memory key value based distributed caching system Memcached server is picked by applying a hash function on the requested key Movie Reviews Web Application Architecture DBMS CACHE HIT Application Server Memcached Server Memcached Client Memcached Server Get movie review Application Server Memcached Server Load Balancer Memcached Client Movie review Memcached Server Application Server Memcached Server Memcached Client
Memcached Memcached is a widely-used in-memory key value based distributed caching system Memcached server is picked by applying a hash function on the requested key Movie Reviews Web Application Architecture DBMS CACHE MISS Application Server Memcached Server Memcached Client Memcached Server Get movie review Application Server Memcached Server Load Balancer Memcached Client Movie review Memcached Server Application Server Memcached Server Memcached Client
The Hot Keys Problem Memcached ignores key popularity when assigning keys to servers DBMS Application Server Memcached Server Memcached Client Memcached Server Server Memcached Application Server Memcached Server Load Balancer Memcached Client Memcached Server Application Server Memcached Server High Response Time Memcached Client memcached get guardians-of- the-galaxy-review
Key Popularity Follows Zipf Distribution Most popular key
Our Solution: MBalancer Our Solution: Duplicate hot keys across many servers Objectives: Balance the load between servers (e.g., minimize average load/max load) Seamless to both memcached client and memcached server Let the network handle the load balancing
Our Solution: MBalancer DBMS Application Server Memcached Server Memcached Client Memcached Server Server Memcached Application Server Memcached Server Load Balancer Memcached Client Memcached Server Application Server Memcached Server Memcached Client Good Response Time memcached get guardians-of- memcached get guardians-of- the-galaxy-review the-galaxy-review
Our Solution: MBalancer DBMS Same request, different destinations? Application Server Memcached Server Memcached Client Memcached Memcached Server Server Application Server Memcached Server Load Balancer Memcached Client Memcached Server Application Server Memcached Server Memcached Client Good Response Time memcached get guardians-of- the-galaxy-review the-galaxy-review memcached get guardians-of-
Our Solution: MBalancer Memcached statistics Using Software Defined Networking (SDN), which separates control plane and data plane: MBalancer Application SDN Controller Data plane match action rules Control plane insert/delete rules Control Plane Data Plane Application Server Memcached Server Memcached Client Memcached Server Server Memcached Application Server Memcached Server Load Balancer Memcached Client Memcached Server SDN Switch Application Server Memcached Server Memcached Client Good Response Time
Our Solution: MBalancer Memcached statistics MBalancer Application SDN Controller Control Plane Data Plane Payload matching capabilities of exact location. Common in many SDN Application Server Memcached Server Memcached Client Memcached Server Server Memcached Application Server Load Balancer switches. Memcached Server Memcached Client Memcached Server SDN Switch Application Server Memcached Server Memcached Client Good Response Time memcached get guardians-of- the-galaxy-review
Why duplication works? If we look at very few highly-loaded keys: Most of the system s load is concentrated there Very modest memory overhead to duplicate these keys values Only a few switching rules suffices to support load balancing
Why duplication works? Imbalance factor = average load / max load The closer the imbalance factor is to 1, the higher the throughput is. Assume only 10 hot keys are duplicated 40-60% improvement Worsen with the size of the system
MBalancer Tasks 1. Hot keys identification 2. Load-balance request in the switch. 3. Hot Keys <Key,Value> updating and duplication to additional/all Memcached servers
Task 1: Hot Keys Identification Identification using off the-shelf techniques (not part of MBalancer) Tumblr s, Etsy s Can also use sFlow, OpenFlow counters
Task 2:Load Balancing in the Switch Using OpenFlow Payload matching Flow Table Entry per hot key get request Entry per hot key set will be used later Group 2. Type: Select Servers containing the hot keys (e.g. all servers) Group Type Select (Since OpenFlow 1.3): Packets are processed by a single bucket in the group. Bucket selection provides equal load sharing (e.g., simlple round robin)
Load Balancing in the Switch Using OpenFlow Hot key request Per hot key: 1 get rule, 1 set rule Plus # of groups multiple by group rule size Group rule size is bounded by the number of servers Total number of rules: Payload matching Flow Table Group 2. Type: Select Hot key request redirected (works only for UDP requests) Load Balancing
Task 3: Key Updating and Duplication (OpenFlow Implementation) Flow Table Keys are installed and updated with set operations Group 2. Type: Select Hot Keys updates are captured and sent to the controller
Key Updating and Duplication MBalancer application contains a memcached client Re-duplicate hot keys on update The switch is configured to match set hot keys packets and send also to the controller MBalancer Application Memcached Client User performs a request which requires updating a hot key SDN Memcached set best-seller Control Plane Controller Memcached get best-seller Data Plane Application Server Memcached Server Memcached Client Memcached Server Application Server Memcached Server Load Balancer Memcached Client SDN Switch Memcached Server Memcached set best-seller Application Server Memcached Server Memcached Client
Experimental Results Setting: NoviKit 250 SDN switch (1Gbit/s network). RYU SDN controller. 64 memcached clients, 2 memcached servers. 1000 keys, 100KB values. H=10, Hot Keys are copied to all servers
Experimental results Throughput Latency Zipf Zipf 60/40 70/30 80/20 90/10 60/40 70/30 80/20 90/10
Comparing with Proxy-Based Solutions Additional servers dedicated for hot keys Hot Keys arrive at the proxy and sent to one of the servers behind it MBalancer does not require additional servers and architecture changes Used by Facebook The number of extra servers required to achieve the same imbalance factor of MBalancer
MBalancer: Limitations MBalancer performs load balancing for Memcached UDP get requests. UDP is usually preferred when the goal is better performance (Facebook s solution) SDN switch with payload matching capabilities is required. Memcached key length is limited (NoviKit250 limitation is 46 bytes).
Conclusions MBalancer solves an higher level application issue, the hot keys problem in Memcached, using SDN. Solution does not require a change in the application s architecture. Low overhead in the SDN switch and memory footprint. An innovative way to perform L7 load balancing Many extensions in the paper, including P4 implementation.
Thank You! Questions?
Lorelyn Medina 123RF.com
