VLDB 2020-_Leaper A Learned Prefetcher for Cache Invalidation in LSM-tree based Storage Engines _Lei Yang.pdf

Solo

415

14页

4次

2022-01-27

免费下载

Leaper: A Learned Prefetcher for Cache Invalidation in

LSM-tree based Storage Engines

Lei Yang

∗

, Hong Wu

, Tieying Zhang

, Xuntao Cheng

, Feifei Li

, Lei Zou

Yujie Wang

, Rongyao Chen

, Jianying Wang

, and Gui Huang

{yang lei, zoulei}@pku.edu.cn

{hong.wu, tieying.zhang, xuntao.cxt, lifeifei, zhencheng.wyj, rongyao.cry, beilou.wjy,

qushan}@alibaba-inc.com

Peking University

Alibaba Group

ABSTRACT

Frequency-based cache replacement policies that work well

on page-based database storage engines are no longer suﬃ-

cient for the emerging LSM-tree (Log-Structure Merge-tree)

based storage engines. Due to the append-only and copy-

on-write techniques applied to accelerate writes, the state-

of-the-art LSM-tree adopts mutable record blocks and issues

frequent background operations (i.e., compaction, ﬂush) to

reorganize records in possibly every block. As a side-eﬀect,

such operations invalidate the corresponding entries in the

cache for each involved record, causing sudden drops on the

cache hit rates and spikes on access latency. Given the ob-

servation that existing methods cannot address this cache

invalidation problem, we propose Leaper, a machine learn-

ing method to predict hot records in an LSM-tree storage

engine and prefetch them into the cache without being dis-

turbed by background operations. We implement Leaper in

a state-of-the-art LSM-tree storage engine, X-Engine, as a

light-weight plug-in. Evaluation results show that Leaper

eliminates about 70% cache invalidations and 99% latency

spikes with at most 0.95% overheads as measured in real-

world workloads.

PVLDB Reference Format:

Lei Yang, Hong Wu, Tieying Zhang, Xuntao Cheng, Feifei Li,

Lei Zou, Yujie Wang, Rongyao Chen, Jianying Wang, and Gui

Huang. Leaper: A Learned Prefetcher for Cache Invalidation in

LSM-tree based Storage Engines. PVLDB, 13(11): 1976-1989,

2020.

DOI: https://doi.org/10.14778/3407790.3407803

1. INTRODUCTION

Caches are essential in many database storage engines

for buﬀering frequently accessed (i.e., hot) records in main

memory and accelerating their lookups. Recently, LSM-tree

(Log-Structure Merge-tree) based database storage engines

have been widely applied in industrial database systems

∗

Work performed while at Alibaba Group.

This work is licensed under the Creative Commons Attribution-

NonCommercial-NoDerivatives 4.0 International License. To view a copy

of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For

any use beyond those covered by this license, obtain permission by emailing

info@vldb.org. Copyright is held by the owner/author(s). Publication rights

licensed to the VLDB Endowment.

Proceedings of the VLDB Endowment, Vol. 13, No. 11

ISSN 2150-8097.

DOI: https://doi.org/10.14778/3407790.3407803

0 50 100 150 200

Time (s)

Normalized value

Hit ratio

QPS

Latency

Figure 1: Cache hit ratio and system performance churn (QPS

and latency of 95th percentile) caused by cache invalidations.

with notable examples including LevelDB [10], HBase [2],

RocksDB [7] and X-Engine [14] for its superior write perfor-

mance. These storage engines usually come with row-level

and block-level caches to buﬀer hot records in main mem-

ory. In this work, we ﬁnd that traditional page-based and

frequency-based cache replacement policies (e.g., Least Re-

cently Used (LRU) [28], Least Frequently Used (LFU) [33])

do not work well in such caches, despite their successes

on B-Trees and hash indexes. The key reason is that the

background operations in the LSM-tree (e.g., compactions,

ﬂushes) reorganize records within the storage periodically,

invalidating the tracked statistics for the cache and dis-

abling these replacement policies to eﬀectively identify the

hot blocks to be swapped into the cache.

The root causes come from append-only and copy-on-

write (CoW) techniques applied to accelerate inserts, up-

dates and deletes, in conjunction with the mutable blocks

in the storage layout of an LSM-tree. Although newly ar-

rived records and deltas on existing records are appended

into the main memory in the ﬁrst place, eventually they

need to be merged with existing record blocks in the durable

storage through the ﬂush and compaction operations in the

LSM-tree. Because of these operations, traditional cache

replacement policies that rely on tracking page/block level

access frequency are no longer eﬀective. Every time when

a ﬂush or compaction is executed in the LSM-tree, record

blocks are reorganized and moved both physically and logi-

cally to or within the durable storage, along with changing

key ranges for records and updated values and locations.

This invalidates their corresponding entries and statistics in

the cache and leads to cache miss for their lookups. Further-

more, compactions are usually executed multiple times for

the same record due to the hierarchical storage layout of the

1976

LSM-tree. In this work, we have identiﬁed that this problem

often causes latency spikes due to the decreased cache hit

rates. We refer to it as the cache invalidation problem.

Such cache invalidations happen frequently in workloads

with intensive writes and updates, such as order-placement

on hot merchandises in e-commerce workloads. Figure 1

shows an example where the cache misses caused by such

invalidations leads up to 10× latency spikes and 90% queries

per second (QPS) drops in X-Engine [14], a high-performance

LSM-tree based storage engine at Alibaba and Alibaba Cloud.

This level of performance instability introduces potential

risks for mission-critical applications. Meanwhile, oﬀ-peak

scheduling of compactions cannot maintain high performance

under high stress, because it accumulates a large number of

levels which lead to severe performance degradation in LSM-

tree (e.g., the accrued range deletion operations have fatal

performance reduction to range selection queries [35]). Be-

yond this, we aim to provide a general database service on

the cloud, so that we cannot ignore the cache invalidation

problem when users need high performance (i.e., under high

stress).

The cache invalidation problem has attracted some re-

search attention in the past [11, 1, 37]. They try to decrease

the frequency of compactions by relaxing the sorted data

layout of the LSM-tree [15], or maintain a mapping between

records before and after compactions [1, 40]. Furthermore,

they often require signiﬁcant changes to the LSM-tree im-

plementation. Hence, they either sacriﬁce the range query

performance, or the space eﬃciency, or introduce signiﬁ-

cant extra overhead. These are often unacceptable because

many industrial applications prefer general-purpose storage

engines oﬀering competitive performance for both point and

range queries with high memory and space eﬃciencies.

In this paper, we introduce machine learning techniques to

capture the data access trends during and after compactions

that cannot be captured by existing methods. Our proposal

introduces a small overhead without adding or altering any

data structures in the LSM-tree. More speciﬁcally, we pro-

pose a learned prefetcher, Leaper, to predict which records

would be accessed during and after compactions using ma-

chine learning models, and prefetch them into the cache ac-

cordingly. Our key insight is to capture data access trends

at the range level, and intersects hot ranges with record

block boundaries to identify record blocks for prefetching

into the cache. We are enabled by machine learning models

to ﬁnd such hot ranges from the workload, which cannot be

identiﬁed by conventional cache replacement policies. The

identiﬁed ranges are independent of background operations,

allowing Leaper to perform across multiple compactions or

ﬂushes continuously. And, our method naturally supports

both point and range queries.

We design and implement Leaper to minimize both of-

ﬂine training overhead and online inference overhead. To

this end, we have applied several optimizations in the imple-

mentation such as the locking mechanism and the two-phase

prefetcher. We have evaluated Leaper using both synthetic

and real-world workloads. Results show that Leaper is able

to reduce cache invalidations and latency spikes by 70% and

99%, respectively. The training and inference overheads of

Leaper are constrained to 6 seconds and 5 milliseconds, re-

spectively. Our main contributions are as follows:

• We formulate the cache invalidation problem, and iden-

tify its root causes in the modern LSM-tree storage

engines, which existing methods cannot address. We

have proposed a machine learning-based approach, Le-

aper, to predict future hot records and prefetch them

into the cache, without being disturbed by background

LSM-tree operations that cause the cache invalidation

problem.

• We have achieved a low training and inference over-

head in our machine learning-based proposal by care-

fully formulating the solution, selecting light-weight

models for predictions and optimizing the implemen-

tation. The overall overhead is often as small as 0.95%

(compared to the cost of other normal execution op-

erations excluding Leaper) as observed in real-world

workloads. We have extracted eﬀective features, achie-

ving a high level of accuracy: 0.99 and 0.95 recall

scores for synthetic and real-world workloads, respec-

tively.

• We have evaluated our proposal by comparing it with

the state-of-the-art baselines using both synthetic and

real-world workloads. Experimental results show that

Leaper improves the QPS by more than 50% in average

and eliminates about 70% cache invalidations and 99%

of latency spikes, signiﬁcantly outperforming others.

The remainder of this paper is organized as follows. Sec-

tion 2 introduces the background and formulates the cache

invalidation problem. Section 3 presents our design overview

of Leaper. We introduce details of Leaper’s components in

Sections 4, 5 and 6. We evaluate our proposal in Section 7

and discuss related works in Section 8. At last, we conclude

in Section 9.

2. BACKGROUND AND PRELIMINARY

2.1 LSM-tree based Storage Engines

LSM-tree based storage engines have acquired signiﬁcant

popularity in recent years. Notable examples include Lev-

elDB [10] from Google, RocksDB [7] from Facebook and X-

Engine [14] from Alibaba, supporting applications such as

Chrome [17], LinkedIn [8], and DingTalk [14]. This popu-

larity is driven by the trend that there are increasingly more

writes (e.g., inserts, updates) in database workloads, where

the traditional B-tree based storages struggle to oﬀer the

expected performance at a reasonable space cost.

LSM-tree is designed to achieve a high write through-

put. Figure 2 illustrates the generic architecture of a LSM-

tree, consisting of a memory-resident component and a disk-

resident component. Incoming records are inserted into ac-

tive memtables in the main memory, which are implemented

as skiplists in many systems [31, 14]. To update an existing

record, the corresponding delta is inserted into this active

memtable in the same way. This append-only design ensures

that all writes other than logging are completed in the main

memory without going into the durable storage where the

access latency is much higher. When an active memtable

is ﬁlled, it is switched to be an immutable memtable. As

memtables accumulate in the main memory, approaching

the main memory capacity, ﬂush operations are triggered

to ﬂush some immutable memtables into the durable storage

where incoming records are merged with existing ones. Such

a merge may incur a lot of disk I/Os. And, the same record

may be merged multiple times, causing write ampliﬁcations.

To bound such write ampliﬁcations and to facilitate fast

lookups over recently ﬂushed records which are still very

1977

of 14

免费下载

关注

评论