System and method for balance localization and priority of pages to flush in a sequential log

Patent metadata

Field	Value
Publication number	US-11068396-B2
Application number	US-201916528836-A
Country	US
Kind code	B2
Filing date	Aug 1, 2019
Priority date	Aug 1, 2019
Publication date	Jul 20, 2021
Grant date	Jul 20, 2021

Abstract

A method, computer program product, and computer system for staging writes into a log in chronological order, wherein each write may have a log record of a plurality of log records describing data of the write. The log record may be organized into a bucket of a plurality of buckets associated with a range of a plurality of ranges within a backing store, wherein each bucket of the plurality of buckets may include two keys respectively. The log record of the plurality of log records may be flushed from the bucket of the plurality of buckets to the backing store at a location and in an order determined based upon, at least in part, the two keys included with the bucket.

First claim

What is claimed is:

1. A computer-implemented method comprising:
staging writes into a log in chronological order, wherein each write has a log record of a plurality of log records describing data of the write;
organizing each of the log records of the plurality of log records into a bucket of a plurality of buckets associated with a range of a plurality of ranges within a backing store, wherein each bucket of the plurality of buckets includes a first key and a second key respectively;
creating a tree, wherein the tree is based upon, at least in part, the second key, wherein the second key includes a lowest log sequence number (LSN) of one or more log records of the plurality of log records, wherein the tree includes one or more LSNs of the one or more log records; and
flushing one or more log records of the plurality of log records from one or more buckets of the plurality of buckets to the backing store at a location and in an order determined based upon, at least in part, the first key, the second key, and one or more lowest LSNs from the tree.

2. The computer-implemented method of claim 1 wherein the log record includes a destination logical block address (LBA) of the backing store associated with the range within the backing store.

3. The computer-implemented method of claim 1 wherein the log record includes a log sequence number (LSN).

4. The computer-implemented method of claim 1 wherein a first key of the two keys includes a starting LBA of the range within the backing store.

5. The computer-implemented method of claim 4 wherein the first key of the two keys is used to one of reference the bucket and create a new bucket if the bucket does not exist.

6. A computer program product residing on a non-transitory computer readable storage medium having a plurality of instructions stored thereon which, when executed across one or more processors, causes at least a portion of the one or more processors to perform operations comprising:
staging writes into a log in chronological order, wherein each write has a log record of a plurality of log records describing data of the write;
organizing each of the log records of the plurality of log records into a bucket of a plurality of buckets associated with a range of a plurality of ranges within a backing store, wherein each bucket of the plurality of buckets includes a first key and a second key respectively;
creating a tree, wherein the tree is based upon, at least in part, the second key, wherein the second key includes a lowest log sequence number (LSN) of one or more log records of the plurality of log records, wherein the tree includes one or more LSNs of the one or more log records; and
flushing one or more log records of the plurality of log records from one or more buckets of the plurality of buckets to the backing store at a location and in an order determined based upon, at least in part, the first key, the second key, and one or more lowest LSNs from the tree.

7. The computer program product of claim 6 wherein the log record includes a destination logical block address (LBA) of the backing store associated with the range within the backing store.

8. The computer program product of claim 6 wherein the log record includes a log sequence number (LSN).

9. The computer program product of claim 6 wherein a first key of the two keys includes a starting LBA of the range within the backing store.

10. The computer program product of claim 9 wherein the first key of the two keys is used to one of reference the bucket and create a new bucket if the bucket does not exist.

11. A computing system including one or more processors and one or more memories configured to perform operations comprising:
staging writes into a log in chronological order, wherein each write has a log record of a plurality of log records describing data of the write;
organizing each of the log records of the plurality of log records into a bucket of a plurality of buckets associated with a range of a plurality of ranges within a backing store, wherein each bucket of the plurality of buckets includes a first key and a second key respectively;
creating a tree, wherein the tree is based upon, at least in part, the second key, wherein the second key includes a lowest log sequence number (LSN) of one or more log records of the plurality of log records, wherein the tree includes one or more LSNs of the one or more log records; and
flushing one or more log records of the plurality of log records from one or more buckets of the plurality of buckets to the backing store at a location and in an order determined based upon, at least in part, the first key, the second key, and one or more lowest LSNs from the tree.

12. The computing system of claim 11 wherein the log record includes a destination logical block address (LBA) of the backing store associated with the range within the backing store, and wherein the log record includes a log sequence number (LSN).

13. The computing system of claim 11 wherein a first key of the two keys includes a starting LBA of the range within the backing store.

14. The computing system of claim 13 wherein the first key of the two keys is used to one of reference the bucket and create a new bucket if the bucket does not exist.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Heng Socheavy D
• Davenport William C
• Wils Joris Johannes

Classifications

• G06F2212/313

  In storage device · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/154

  Networked environment · CPC title