Alibaba Singapore Holding Private Limited

Alibaba Group Holding Limited

Zhu Pang

Jiesheng Wu

Qingda Lu

Shuo Chen

Rui Wang

Jun Song

Yuanjiang Ni

Zhixing Ren

A key-value engine may perform garbage collection for a tree or hierarchical data structure on an append-only storage device with page mappings. The key-value engine may separate hot and cold data to reduce write amplification, track extent usage using a restricted or limited amount of memory, efficiently answer queries of valid extent usage, and adaptively or selectively defragment pages in snapshots in rounds of garbage collection.

Garbage collection of tree structure with page mappings

A key-value engine of a storage system may perform a restart recovery after a system failure. The key-value engine may read a metadata log to locate a latest system checkpoint, and load a page mapping table from the latest system checkpoint. The key-value engine may replay to apply changes to the page mapping table from a system transaction log starting from a system transaction replay starting point. The key-value engine may further form one or more read-only replicas using an underlying file stream opened in a read-only mode during the recovery after the system failure to further facilitate fast recovery and provide fast response to user transactions that conduct read only transactions after the system failure.

Fast recovery and replication of key-value stores

Systems and methods discussed herein, based on a key-value data store including multiple-tiered sorted data structures in memory and storage, implement granularly timestamped concurrency control. The multiple-tiering of the key-value data store enables resolving the snapshot queries by returning data record(s) according to granularly timestamped snapshot lookup instead of singularly indexed snapshot lookup. Queries return a merged collection of records including updates from data structures in memory and in storage, such that a persistent storage transaction may refer to non-committed updates up to a timeframe defined by the snapshot read timestamp. This way, inconsistency is avoided that would result from merely reading data records committed in storage, without regard as to pending, non-committed updates thereto. The global timestamp further modifies the generation of the local transaction commit timestamp and the local snapshot read timestamp, so as to establish a granularly timestamped concurrency control scheme (over three levels of granularity).

Granularly timestamped concurrency control for key-value store

A power management system may provide power management recommendations to a computer system including a plurality of computing nodes (which may include processors, etc.), to cause the computing nodes to individually or collectively adjust power states or modes of respective processors to achieve power management of the computer system. The power management system may be provided with a power management framework that continuously utilizes direct and indirect service-level feedbacks to guide power management decisions. The power management system may employ a reinforcement learning algorithm to make power management decisions at a user level, and provide a fast decision overriding mechanism for platform events or service-requested performance boosts.

Service-level feedback-driven power management framework

A mapping correspondence between memory addresses and request counts and a cache line flusher are provided, enabling selective cache flushing for persistent memory in a computing system to optimize write performance thereof. Random writes from cache memory to persistent memory are prevented from magnifying inherent phenomena of write amplification, enabling computing systems to implement persistent memory as random-access memory, at least in part. Conventional cache replacement policies may remain implemented in a computing system, but may be effectively overridden by operations of a cache line flusher according to example embodiments of the present disclosure preventing conventional cache replacement policies from being triggered. Implementations of the present disclosure may avoid becoming part of the critical path of a set of computer-executable instructions being executed by a client of cache memory, minimizing additional computation overhead in the critical path.

Growing community of inventors

Bellvue, WA, United States of America

Zhu Pang