# US 11,030,185 B2 · Schema-agnostic indexing of distributed databases

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,030,185 B2
- Document ID: US11030185B2
- Status: Granted
- Kind: B2
- Application number: 15/991,786
- Filed: 2018-05-29
- Published: 2019-11-07
- Granted: 2021-06-08
- Earliest claimed: 2018-05-07
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Karthik Raman; Momin Mahmoud Al-Ghosien; Samer Boshra; Brandon Chong; Madhan Gajendran; Mikhail Mikhailovich Koltachev; Aravind Ramachandran Krishna; Emily Lawton; Liang Li; Karan Vishwanath Popali; Adrian Ilcu Predescu; Ankur Savailal Shah; Pankaj Sharma; Dharma Shukla; Hari Sudan Sundar; Krishnan Sundaram; Shireesh Kumar Thota
- Web page: https://patentgrep.com/patent/US11030185B2

## CPC

- G06F 9/5061: {Partitioning or combining of resources}
- G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)}
- G06F 11/2007: {using redundant communication media}
- G06F 11/2023: {Failover techniques}
- G06F 11/2056: {by mirroring}
- G06F 16/184: {implemented as replicated file system}
- G06F 16/211: {Schema design and management}
- G06F 16/219: {Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477)}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/2255: {Hash tables}
- G06F 16/2272: {Management thereof}
- G06F 16/2315: {Optimistic concurrency control}
- G06F 16/2322: {using timestamps}
- G06F 16/2329: {using versioning}
- G06F 16/2336: {Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/2452: Query translation
- G06F 16/252: {between a Database Management System and a front-end application}
- G06F 16/258: {Data format conversion from or to a database}
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 16/273: {Asynchronous replication or reconciliation}
- G06F 16/28: Databases characterised by their database models, e.g. relational or object models
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/9027: {Trees}
- G06F 16/903: Querying (for retrieval from the web G06F16/953)
- H04L 41/0803: Configuration setting
- H04L 41/0896: Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities (flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76)
- H04L 41/5009: Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
- H04L 41/5019: Ensuring fulfilment of SLA
- H04L 41/5022: by giving priorities, e.g. assigning classes of service
- H04L 41/5032: {Generating service level reports}
- H04L 47/72: using reservation actions during connection setup
- H04L 47/762: triggered by the network
- H04L 47/83: based on usage prediction
- H04L 67/1008: based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30)
- H04L 67/1012: based on compliance of requirements or conditions with available server resources
- H04L 67/1034: Reaction to server failures by a load balancer
- H04L 67/565: Conversion or adaptation of application format or content (adding application control or application functional data H04L67/561)
- H04L 69/24: Negotiation of communication capabilities
- G06F 9/468: {Specific access rights for resources, e.g. using capability register}
- G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F 2201/80: Database-specific techniques
- G06F 2209/505: Clust
- H04L 67/1029: using data related to the state of servers by a load balancer
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Data sets such as databases are often distributed over a number of servers, where each server stores a subset of records and an index that enables the server to locate the records in response to queries. However, tight coupling of indexing and storage may limit load-balancing, fault recovery, and distribution. Instead, the set of servers may be partitioned into a set of storage servers that store the records and a set of index servers of the index over the records. In a set that is decoupled in this manner, load-balancing may involve provisioning and locating index servers independently of the provisioning and locating of the storage servers in view of the particular sensitivities and tolerances of various applications. Additionally, the index servers may also utilize a data layout that is selected and adapted independent of the data layout of the storage servers and/or the schema of the data stored thereby.

## Claims

### Claim 1

A method of storing a data set on a set of servers, wherein the set of servers comprises at least one storage server that stores at least a portion of the data set, the method comprising:
configuring an index server of the set to:
store a data set index comprising:
a first index in a first index format that fulfills queries of a first query type, and
a second index in a second index format that fulfills queries of a second query type;
receive a record to be stored by a storage server of the set;
add the record to both the first index and the second index of the index server including an indication of the storage server that stores the record, wherein the data set further comprises:
a first subset of records that are stored by a first storage server according to a first data set schema, and
a second subset of records that are stored by a second storage server according to a second data set schema that is different than the first data set schema, the data set index employing a single indexing schema for the first and second subsets of records, the indexing schema decoupled from the first and second data set schemas; and
evaluate a query over the data set that involves the record by:
from the data set index, choosing a selected index that fulfills queries of a query type that matches the query;
using the selected index, identifying the storage server that stores the record; and
initiating a fulfillment of the query by the storage server.

### Claim 2 (depends on 1)

The method of claim 1, wherein:
the data set is organized by the storage server according to a data set layout; and
the data set index is organized by the index server according to an index data layout that is independent of the data set layout.

### Claim 3

A method of configuring a set of servers to provide access to a data set, wherein the set of servers comprises at least one storage server that stores at least a portion of the data set, the method comprising:
selecting, from the set, a storage server of the data set, wherein the data set further comprises:
a first subset of records that are stored by a first storage server according to a first data set schema,
a second subset of records that are stored by a second storage server according to a second data set schema that is different than the first data set schema, and;
selecting, from the set, an index server subset of index servers comprising a first index server and a second index server of the data set, wherein the index server subset excludes the storage server; and
configuring the first index server to:
receive a record to be stored by a storage server of the set;
add the record to a data set index of the index server including an indication of a location of the record in the set the data set index employing a single indexing schema for the first and second subsets of records, the indexing schema decoupled from the first and second data set schemas;
synchronize the data set index with the second index server; and
route queries over the data set to the storage server of the set that stores records of the data set that are involved in the query.

### Claim 4 (depends on 3)

The method of claim 3, wherein:
the storage server is closer to the second index server than the first index server; and
the first index server synchronizes the data set index with the second index server using a synchronization schedule that is proportional to a predicted demand of the record from the storage server.

### Claim 5 (depends on 3)

The method of claim 3, wherein:
the first index server is located in a first region; and
the index server subset further comprises:
a local index replica that is collocated with the first index server;
a first regional index replica that is not collocated with the first index server, and that is located within the first region; and
a second regional index replica that is located within a second region that is different than the first region.

### Claim 6 (depends on 5)

The method of claim 5, wherein the first index server is configured to synchronize the data set index by:
synchronizing the data set index with the local index replica according to a first synchronization schedule; and
synchronizing the data set index with the first regional index replica according to a second synchronization schedule that is different than the first synchronization schedule.

### Claim 7 (depends on 3)

The method of claim 3, wherein:
the first index server is located in a fault domain of the set; and
the index server subset further comprises at least one index replica that is located in a different fault domain than the fault domain of the first index server.

### Claim 8 (depends on 3)

The method of claim 3, wherein selecting the index server subset further comprises:
identifying a performance characteristic of an application utilizing the data set; and
selecting the index server subset based on the performance characteristic.

### Claim 9 (depends on 8)

The method of claim 8, wherein:
the performance characteristic further comprises an update latency of updates to the data set; and
selecting the index server subset further comprises: reducing an index replica count of index replicas of the index server subset to reduce the update latency.

### Claim 10 (depends on 8)

The method of claim 8, wherein:
the performance characteristic further comprises at least one of:
a concurrency of read accesses of the data set, and
a resiliency of the data set to faults; and
selecting the index server subset further comprises:
increasing an index replica count of index replicas of the index server subset to increase at least one of the concurrency and the resiliency of the data set.

### Claim 11 (depends on 8)

The method claim 8, further comprising:
generating an estimate of the performance characteristic for the index server subset; and
offering to host the data set for the application with a guarantee of the estimate of the performance characteristic.

### Claim 12 (depends on 8)

The method of claim 8, further comprising:
while the application utilizes the data set indexed by the index server subset, capturing a measurement of the performance characteristic for the index server subset;
performing a comparison of the measurement of the performance characteristic with a guarantee for the application; and
adjusting the index server subset based on the comparison.

### Claim 13 (depends on 12)

The method of claim 12, wherein:
the comparison indicates a deficiency between the guarantee and the measurement of the performance characteristic; and
adjusting the index server subset further comprises: adding, to the index server subset, a new index replica that is collocated with at least one storage server of the set to raise the performance characteristic toward the guarantee.

### Claim 14 (depends on 12)

The method of claim 12, wherein:
the comparison indicates that the measurement of the performance characteristic exceeds the guarantee by a measurement margin; and
adjusting the index server subset further comprises:
for a selected index replica of the index server subset, substituting a distant index replica that is further from the storage server than the selected index replica, and wherein the substituting reduces a resource cost of the application while maintaining the performance characteristic within the measurement margin of the guarantee.

### Claim 15

An index server that provides access to a data set accessible through a set of servers, wherein the set of servers comprises at least one storage server that stores at least a portion of the data set, the index server comprising:
a processor; and
a memory storing:
a data set index, comprising:
a first index in a first index format that fulfills queries of a first query type, and
a second index in a second index format that fulfills queries of a second query type;
a first subset of records that are stored by a first storage server according to a first data set schema, and
a second subset of records that are stored by a second storage server according to a second data set schema that is different than the first data set schema, the data set index employing a single indexing schema for the first and second subsets of records, the indexing schema decoupled from the first and second data set schemas; and
instructions that, when executed by the processor, cause the index server to:
receive a record to be stored by a storage server of the data set;
add the record to both the first index and the second index, the record including an indication of the storage server that stores the record; and
evaluate a query over the data set that involves the record by:
choosing, from the data set index, a selected index that fulfills queries of a query type that matches the query;
using the selected index to identify the storage server that stores the record; and
initiating a fulfillment of the query by the identified storage server.

### Claim 16 (depends on 15)

The index server of claim 15, wherein at least a portion of the memory storing the data set index further comprises a solid-state storage device.

### Claim 17 (depends on 15)

The index server of claim 15, wherein the index server:
initially receives updates to be applied to the data set; and
the index server adds the updates of the data set to the data set index.

### Claim 18 (depends on 15)

The index server of claim 15, wherein initiating the fulfillment of the query further comprises at least one of:
forwarding the query to the identified storage server; and
informing a client that submitted the query of the identified storage server that stores the record.