Resource allocation using distributed segment processing credits

Patent metadata

Field	Value
Publication number	US-11765099-B2
Application number	US-202217822534-A
Country	US
Kind code	B2
Filing date	Aug 26, 2022
Priority date	Oct 8, 2018
Publication date	Sep 19, 2023
Grant date	Sep 19, 2023

Abstract

Systems and methods for allocating resources are disclosed. Resources as processing time, writes or reads are allocated. Credits are issued to the clients in a manner that ensure the system is operating in a safe allocation state. The credits can be used not only to allocate resources but also to throttle clients where necessary. Credits can be granted fully, partially, and in a number greater than requested. Zero or negative credits can also be issued to throttle clients. Segment credits are associated with identifying unique fingerprints or segments and may be allocated by determining how many credits a CPU/cores can support. This maximum number may be divided amongst clients connected with the server.

First claim

What is claimed is:

1. A method for allocating resources of a cluster of servers to connected clients, the method comprising:
receiving a request for credits from a client, wherein each credit corresponds to resources of the cluster;
determining, by the cluster, whether the credits requested by the client result in a safe allocation state for all of the clients, wherein the cluster determines whether the allocation state is safe by finding a hypothetical credit request that allows at least one other client to request and use their maximum allowed credits, wherein the allocation state is safe when credit request is found and wherein the allocation state is not safe when the credit request is not found; and
issuing the credits requested by the client to the client such that the allocation state is safe.

2. The method of claim 1 , further comprising determining that the allocation state is safe when a set of credit requests allows each of the clients to request and use their maximum allowed credits.

3. The method of claim 2 , further comprising determining whether all of the other clients can request and use their maximum allowed credits individually, wherein the allocation state is safe when all of the other clients can request and use their maximum allowed credits.

4. The method of claim 3 , wherein the maximum allowed credits of each of the clients is evaluated independently of the maximum allowed credits of other clients by considering whether each of the clients can request and use their maximum allowed credits in succession.

5. The method of claim 1 , further comprising determining whether a first client can request and use their maximum allowed credits and then determining whether a second client can request and use their maximum allowed credits, wherein the determination for the first client does not impact the determination for the second client.

6. The method of claim 1 , wherein the cluster maintains matrices including a total availability matrix identifying a maximum number of credits available from each server in the cluster, a current availability matric identifying a number of credits available from each of the servers, a current demand matrix identifying the maximum allowed credits of each of the clients, and a current need matrix identifying credit needs for each of the clients, further comprising determining whether the allocation state is safe based on the matrices.

7. The method of claim 1 , further comprising determining that the allocation state is unsafe and issuing the credits in a number that is one of:
less than a number of the credits requested by the client;
zero; or
negative.

8. The method of claim 1 , wherein the credits are one of segment credits for segment processing operations, stream credits for streaming operations, credits for identifying unique fingerprints corresponding to segments that are not stored by the cluster, or restore credits for restoring operations.

9. The method of claim 1 , further comprising throttling the client when the number of credits issued is zero or negative.

10. The method of claim 1 , further comprising releasing credits by the client.

11. A non-transitory computer readable medium including computer executable instructions configured to be executed by a processor for performing a method, the method comprising:
receiving a request for credits from a client, wherein each credit corresponds to resources of the cluster;
determining, by the cluster, whether the credits requested by the client result in a safe allocation state for all of the clients, wherein the cluster determines whether the allocation state is safe by finding a hypothetical credit request that allows at least one other client to request and use their maximum allowed credits, wherein the allocation state is safe when credit request is found and wherein the allocation state is not safe when the credit request is not found; and
issuing the credits requested by the client to the client such that the allocation state is safe.

12. The non-transitory computer readable medium of claim 11 , further comprising determining that the allocation state is safe when a set of credit requests allows each of the clients to request and use their maximum allowed credits.

13. The non-transitory computer readable medium of claim 12 , further comprising determining whether all of the other clients can request and use their maximum allowed credits individually, wherein the allocation state is safe when all of the other clients can request and use their maximum allowed credits.

14. The non-transitory computer readable medium of claim 13 , wherein the maximum allowed credits of each of the clients is evaluated independently of the maximum allowed credits of other clients by considering whether each of the clients can request and use their maximum allowed credits in succession.

15. The non-transitory computer readable medium of claim 14 , further comprising determining whether a first client can request and use their maximum allowed credits and then determining whether a second client can request and use their maximum allowed credits, wherein the determination for the first client does not impact the determination for the second client.

16. The non-transitory computer readable medium of claim 11 , wherein the cluster maintains matrices including a total availability matrix identifying a maximum number of credits available from each server in the cluster, a current availability matric identifying a number of credits available from each of the servers, a current demand matrix identifying the maximum allowed credits of each of the clients, and a current need matrix identifying credit needs for each of the clients, further comprising determining whether the allocation state is safe based on the matrices.

17. The non-transitory computer readable medium of claim 11 , further comprising determining that the allocation state is unsafe and issuing the credits in a number that is one of:
less than a number of the credits requested by the client;
zero; or
negative.

18. The non-transitory computer readable medium of claim 11 , wherein the credits are one of segment credits for segment processing operations, stream credits for streaming operations, credits for identifying unique fingerprints corresponding to segments that are not stored by the cluster, or restore credits for restoring operations.

19. The non-transitory computer readable medium of claim 11 , further comprising throttling the client when the number of credits issued is zero or negative.

20. The non-transitory computer readable medium of claim 11 , further comprising releasing credits by the client.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Desai Keyur B

Classifications

• H04L47/783 Primary

  Distributed allocation of resources, e.g. bandwidth brokers · CPC title

• G06F9/5011 Primary

  the resources being hardware resources other than CPUs, Servers and Terminals · CPC title

• G06F3/0641

  De-duplication techniques · CPC title

• G06F2209/504

  Resource capping · CPC title

• G06F2209/5013

  Request control · CPC title