# US 11,442,902 B2 · Shard-level synchronization of cloud-based data store and local file system with dynamic sharding

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

- Number: US 11,442,902 B2
- Document ID: US11442902B2
- Status: Granted
- Kind: B2
- Application number: 16/014,518
- Filed: 2018-06-21
- Published: 2019-12-26
- Granted: 2022-09-13
- Earliest claimed: 2018-06-21
- Assignees: Nasuni Corporation
- Applicants: Nasuni Corporation
- Inventors: Georgi Damyanov; Yuyan Zhang
- Web page: https://patentgrep.com/patent/US11442902B2

## CPC

- G06F 16/178: Techniques for file synchronisation in file systems
- G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)}
- G06F 16/182: Distributed file systems
- G06F 16/1873: {Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An operations server synchronizes updates to a cloud-based shared versioned file system. The shared versioned file system includes directories and sub-directories that are divided into shards. The operations server coordinates requests from local filer servers, each running a respective local version of the shared versioned file system, to update a shard in the cloud-based shared versioned file system. The operations server can provide a global lock on the shard to a local filer server before it updates the shard in the cloud-based shared versioned file system. Preferably, shards are sized dynamically based on the number of entries in the directories associated therewith.

## Claims

### Claim 1

A method of synchronizing updates to a shared versioned file system from a local filer server, the local filer server running a local version of the shared versioned file system, comprising:
partitioning contents of a directory into a dynamic number of shards by applying an extendible hashing function that generates a maximally-extended radix tree per a configurable maximum depth, wherein a shard is a portion of a sub-directory of the directory, the portion being less than the sub-directory as a whole, the maximally-extended radix tree having a set of leaves, wherein the shards are of predefined size based on a number of entries in the directory, wherein information about the shards is represented by shard counters corresponding to leaves of the maximally-extended radix tree, and wherein a structure of the radix tree is adjusting by tracking the shard counters and selectively applying a list of shard counter differentials;
receiving one or more requests from the local file server to update one of more of the shards in a cloud data store; and
updating one or more shards in the cloud data store in response to receipt of the requests.

### Claim 2 (depends on 1)

The method as described in claim 1 further including selectively using the shard counters to construct a variable depth prefix tree in response to a given occurrence at the local filer server.

### Claim 3 (depends on 2)

The method as described in claim 2 wherein the given occurrence is a local file server operation.

### Claim 4 (depends on 3)

The method as described in claim 3 wherein the structure of the radix tree is adjusted in response to the local file server operation.

### Claim 5 (depends on 4)

The method as described in claim 4 wherein the structure of the radix tree is adjusted by merging two or more leaves.

### Claim 6 (depends on 5)

The method as described in claim 5 wherein the two or more leaves are merged without requiring a split operation.

### Claim 7 (depends on 1)

The method as described in claim 1 wherein a shard counter is maintained in a directory manifest.

### Claim 8 (depends on 1)

The method as described in claim 1 wherein a request is associated with a snapshot operation.

### Claim 9 (depends on 1)

The method as described in claim 1 further including compacting the radix tree to produce an updated radix tree.