High throughput data modifications using blind update operations

Patent metadata

Field	Value
Publication number	US-2016019279-A1
Application number	US-201414335927-A
Country	US
Kind code	A1
Filing date	Jul 20, 2014
Priority date	Jul 20, 2014
Publication date	Jan 21, 2016
Grant date	—

Abstract

Update requests that specify updates to a logical page associated with a key-value store are obtained. Updates to the logical page are posted using the obtained plurality of update requests, without accessing the logical page via a read operation.

First claim

What is claimed is:

1 . A system comprising:
at least one processor; a computer-readable storage medium that stores executable instructions that are executable by the at least one processor, the executable instructions including a page update manager that includes:
an update acquisition module that obtains a plurality of update requests that specify updates for a logical page associated with a key-value store; and
an update posting engine that posts the updates using the obtained plurality of update requests, without accessing the logical page via a read operation.

2 . The system of claim 1 , further comprising:
a page stub manager that initiates a prepending of a page stub to a current state of the logical page via a page stub delta record representing the page stub, the page stub including an indication of an address of a current state of the logical page and metadata specifying attributes of the logical page, the prepending of the page stub to the current state initiated by installing an address of the page stub delta record representing the page stub in a mapping table, via an atomic operation.

3 . The system of claim 2 , wherein:
the update acquisition module obtains a plurality of update requests that specify record updates to the logical page; and the update posting engine posts the obtained record updates using the obtained plurality of update requests, without accessing the logical page via a read operation.

4 . The system of claim 3 , wherein:
the update posting engine posts the obtained record updates by prepending a plurality of respective delta records to the page stub, wherein the plurality of respective delta records include record update information that specifies the respective updates to the logical page that are specified in the respective plurality of update requests.

5 . The system of claim 4 , further comprising:
a consolidation engine that consolidates the obtained record updates via a predefined consolidation function, using the plurality of respective delta records that are prepended to the page stub.

6 . The system of claim 2 , wherein:
the update acquisition module obtains a plurality of update requests that specify incremental updates to a record in the logical page; and the update posting engine incrementally posts the obtained specified incremental updates using the obtained plurality of update requests, without accessing the logical page via a read operation.

7 . The system of claim 6 , wherein:
the update posting engine incrementally posts the obtained specified incremental updates by incrementally prepending a plurality of respective delta records to the page stub, wherein the plurality of respective delta records include key update information that specifies the respective updates to the record.

8 . The system of claim 7 , further comprising:
a data retrieval engine that initiates a lookup of a key in the key-value store, to obtain a representation of at least a portion of the logical page, in a current state of the logical page, via a read operation from storage into memory; and a merge engine that merges the obtained specified incremental updates via a predefined merge function, using the plurality of respective delta records that are prepended to the page stub.

9 . The system of claim 8 , wherein:
the predefined merge function includes a user-defined merge function.

10 . The system of claim 2 , further comprising:
an incremental flush engine that incrementally flushes contents of the logical page, with the plurality of respective delta records that are prepended to the page stub, to a flush buffer storage area that is appended to storage using a single write operation.

11 . The system of claim 1 , wherein:
the key-value store includes keys that represent terms associated with respective documents, and respective values that represent respective document identifiers.

12 . The system of claim 1 , wherein:
the logical page is stored on secondary storage.

13 . A method comprising:
obtaining a plurality of update requests that specify incremental updates to a key in a key-value store that is associated with a logical page; and incrementally updating the key using the obtained plurality of update requests, without accessing the logical page via a read operation.

14 . The method of claim 13 , further comprising:
initiating a prepending of a page stub to a current state of the logical page via a page stub delta record representing the page stub, the page stub including an indication of an address of a current state of the logical page, the prepending of the page stub to the current state initiated by installing an address of the update delta record representing the page stub in a mapping table, via an atomic operation.

15 . The method of claim 14 , wherein:
incrementally updating the key includes incrementally prepending a plurality of respective delta records to the page stub delta record representing the page stub, wherein the plurality of respective delta records include key update information that specifies the respective updates to the key that is specified in the respective plurality of update requests.

16 . The method of claim 15 , wherein:
the prepending of the plurality of respective delta records is initiated by installing an address of a current respective incremental delta record in a mapping table, via an atomic operation.

17 . The method of claim 16 , further comprising:
initiating a lookup of the key, to obtain a representation of at least a portion of the logical page, in a current state of the logical page, via a read operation from storage into memory; and initiating a merge of the obtained incremental updates via a predefined merge function, using the plurality of respective delta records that are prepended to the page stub.

18 . The method of claim 13 , wherein:
incrementally updating the key includes incrementally updating the key using the obtained plurality of update requests, by writing out delta update records to secondary storage incrementally, without accessing the logical page via a read operation.

19 . The method of claim 13 , wherein:
the page stub includes values of key boundaries associated with the logical page.

20 . A computer program product comprising a computer-readable storage medium storing executable instructions that cause at least one data processing apparatus to:
obtain a plurality of update requests that specify updates to a logical page associated with a key-value store; and post the updates using the obtained plurality of update requests, without accessing the logical page via a read operation as part of the posting of the obtained updates to the key.

Assignees

• Microsoft Corp

Inventors

• Sengupta Sudipta
• Lomet David Bruce
• Levandoski Justin Jon

Classifications

• G06F16/275 Primary

  Synchronous replication · CPC title

• G06F16/2308 Primary

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/2329

  using versioning · CPC title

• G06F17/30339

  Physics · mapped topic