Shard-level synchronization of cloud-based data store and local file system with dynamic sharding
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.
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.
2. 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.
3. The method as described in claim 2 wherein the given occurrence is a local file server operation.
4. The method as described in claim 3 wherein the structure of the radix tree is adjusted in response to the local file server operation.
5. The method as described in claim 4 wherein the structure of the radix tree is adjusted by merging two or more leaves.
6. The method as described in claim 5 wherein the two or more leaves are merged without requiring a split operation.
7. The method as described in claim 1 wherein a shard counter is maintained in a directory manifest.
8. The method as described in claim 1 wherein a request is associated with a snapshot operation.
9. The method as described in claim 1 further including compacting the radix tree to produce an updated radix tree.