US 10,884,823 B2Granted

Distributed semaphore with adjustable chunk sizes

AssigneeRubrik, Inc.

InventorNoel Moldvai

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods and systems for allocating disk space and other limited resources (e.g., network bandwidth) for a cluster of data storage nodes using distributed semaphores with atomic updates are described. The distributed semaphores may be built on top of a distributed key-value store and used to reserve disk space, global disk streams for writing data to disks, and per node network bandwidth settings. A distributed semaphore comprising two or more semaphores that are accessed with different keys may be used to reduce contention and allow a globally accessible semaphore to scale as the number of data storage nodes within the cluster increases over time. In some cases, the number of semaphores within the distributed semaphore may be dynamically adjusted over time and may be set based on the total amount of disk space within the cluster and/or the number of contention fails that have occurred to the distributed semaphore.

Claims20

Dependent claims

A method for operating a data management system, comprising:

determining a first amount of disk space for a cluster of data storage nodes at a first point in time;
determining a first number of semaphores corresponding with a distributed semaphore based on the first amount of disk space for the cluster at the first point in time;
determining a second amount of disk space for the cluster of data storage nodes at a second point in time subsequent to the first point in time;
detecting that the second amount of disk space for the cluster of data storage nodes at the second point in time is different from the first amount of disk space for the cluster of data storage nodes at the first point in time;
in response to detecting that the second amount of disk space for the cluster of data storage nodes at the second point in time is different from the first amount of disk space for the cluster of data storage nodes at the first point in time, determining a second number of semaphores different from the first number of semaphores corresponding with the distributed semaphore, the determining the second number of semaphores includes determining the second number of semaphores based on the second amount of disk space for the cluster at the second point in time;
generating a plurality of semaphores comprising the second number of semaphores;
reserving a portion of the second amount of disk space for a first job using the plurality of semaphores;
allocating the portion of the second amount of disk space to the first job:
running the first job using the cluster subsequent to allocating the portion of the second amount of disk space to the first job;
and
storing data generated by the first job within the portion of the second amount of disk space allocated to the first job.

8 more elements

A method for operating a data management system, comprising:

determining a total amount of disk space for a cluster of data storage nodes at a first point in time;
determining a first number of semaphores corresponding with a distributed semaphore based on the total amount of disk space for the cluster;
storing a first plurality of semaphores for the distributed semaphore comprising the first number of semaphores;
detecting that a number of contention fails associated with prior jobs that failed to access the distributed semaphore during a particular period of time subsequent to the first point in time has exceeded a threshold number of contention fails;
in response to detecting that the number of contention fails during the particular period of time has exceeded the threshold number of contention fails, determining a second number of semaphores greater than the first number of semaphores corresponding with the distributed semaphore subsequent to the first point in time;
storing a second plurality of semaphores for the distributed semaphore comprising the second number of semaphores;
reserving a portion of the total amount of disk space for a first job using the second plurality of semaphores;
allocating the portion of the total amount of disk space to the first job;
running the first job using the cluster subsequent to allocating the portion of the total amount of disk space to the first job;
and
storing data generated by the first job within the portion of the total amount of disk space allocated to the first job.

8 more elements

A data management system comprising:

a database;
and
one or more processors configured to perform operations in a method of data management, the operations comprising at least:
determining a first amount of disk space for a cluster of data storage nodes at a first point in time;
determining a first number of semaphores corresponding with a distributed semaphore based on the first amount of disk space for the cluster at the first point in time;
determining a second amount of disk space for the cluster of data storage nodes at a second point in time subsequent to the first point in time;
detecting that the second amount of disk space for the cluster of data storage nodes at the second point in time is different from the first amount of disk space for the cluster of data storage nodes at the first point in time;
in response to detecting that the second amount of disk space for the cluster of data storage nodes at the second point in time is different from the first amount of disk space for the cluster of data storage nodes at the first point in time;
determining a second number of semaphores different from the first number of semaphores corresponding with the distributed semaphore, the determining the second number of semaphores includes determining the second number of semaphores based on the second amount of disk space for the cluster at the second point in time;
generating a plurality of semaphores comprising the second number of semaphores;
reserving a portion of the second amount of disk space for a first job using the plurality of semaphores;
allocating the portion of the second amount of disk space to the first job;
running the first job using the cluster subsequent to allocating the portion of the second amount of disk space to the first job;
and
storing data generated by the first job within the portion of the second amount of disk space allocated to the first job.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/577,166Filed 20 Sep 2019 · continuation
Priority: 21 Feb 2018
Published: US 2020/0057683 A120 Feb 2020
Granted: 5 Jan 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification19 codes

G06F 9/5016
The resources being hardware resources other than CPUs, Servers and Terminals: the resource being the memory
G06F 9/52
Multiprogramming arrangements: program synchronisation; Mutual exclusion, e.g. by means of semaphores
G06F 8/71
Software maintenance or management: version control ; Configuration management
G06F 9/45533
Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines:…

Family

Application15/901,390Parent of this continuation · filed 21 Feb 2018
US 2020/0057683 A1Pre-grant publication · published 20 Feb 2020
US 10,423,465 B2Parent of this continuation
US 2019/0258530 A1Published application
US 10,884,823 B2This patent

From the US filing history. Foreign family members aren’t listed.