Systems and methods of providing possible value ranges

• US 20080256103A1
• Filed: 04/13/2007
• Published: 10/16/2008
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Husted, Justin M., Passey, Aaron J., Godman, Peter J., Fachan, Neal T.
• Granted Patent: US 7,779,048 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

Embodiments of the invention relate generally to incremental computing. Specifically, embodiments of the invention include systems and methods that provide for the concurrent processing of multiple, incremental changes to a data value while at the same time monitoring and/or enforcing threshold values for that data value. For example, a method is provided that determines whether multiple incremental changes to a data field could pass a threshold based on keeping track of a possible value range for the data field.

Claims

1. A method of determining whether multiple incremental changes to a data field could pass a threshold, comprising:

receiving at least one threshold related to a data field;

receiving a request to incrementally modify a data value of the data field; and

determining whether the request, in combination with a subset of other pending requests to incrementally modify the data value, could pass the at least one threshold.

2. The method of claim 1, wherein the at least one threshold is a threshold for a maximum or minimum data value of the data field.

3. The method of claim 1, wherein the determining comprises computing a possible data value for the data field based on the request and a bound of possible values of the data field, the bound derived from the other pending requests, and comparing the possible data value with the at least one threshold.

4. The method of claim 1, wherein the request is a request either to increment or to decrement the data value, and wherein the other pending requests are requests, respectively, either to increment or to decrement the data value.

5. The method of claim 1, wherein the data field is associated with at least one of the following:

a data storage system, a distributed storage system, a file system, and a distributed file system.

6. The method of claim 1, wherein the request and the other pending requests are associated with uncommitted, concurrent transactions to write to a storage location associated with the data field.

7. The method of claim 1, wherein the at least one threshold is specific to at least one of the following:

an operation type associated with the request, the data field, and a subset of a combination of the request and the other pending requests.

8. The method of claim 1, if it is determined that the request could pass the at least one threshold, further comprising permitting or denying the request.

9. The method of claim 8, if permitting the request causes the at least one threshold to be passed, further comprising performing at least one of the following:

sending an advisory notice that the at least one threshold has been passed and permitting data values of the data field to be past the at least one threshold until a condition is met.

10. The method of claim 9, wherein the condition is associated with an amount of time.

11. A computer-readable medium having instructions stored thereon for determining, when the instructions are executed, whether multiple incremental changes to a data field could pass a threshold, the instructions comprising:

receiving at least one threshold related to a data field;

receiving a request to incrementally modify a data value stored in the data field; and

determining whether the request could cause an incremented data value to pass the at least one threshold in combination with any subset of other pending incremental requests.

12. The computer-readable medium of claim 11, wherein the data field is associated with at least one of the following:

a data storage system, a distributed storage system, a file system, and a distributed file system.

13. The computer-readable medium of claim 11, wherein the determining comprises computing the incremented data value of the data field based on the request and a bound of possible values of the data field, the bound derived from the other pending incremental requests, and comparing the incremented data value with the at least one threshold.

14. A system that determines whether a subset of pending transactions could pass a threshold, comprising:

a module configured to receive at least one threshold related to a data field;

to receive an incremental transaction on the data field; and

to determine whether the incremental transaction could cause the data field to pass the at least one threshold in combination with any subset of other pending incremental transactions.

15. The system of claim 14, if the incremental transaction could cause the data field to pass the at least one threshold, the module further configured to disallow the incremental transaction until the other pending incremental transactions have resolved, and then to permit the incremental transaction as a serial operation while postponing additional incremental transactions.

16. The system of claim 15, when the incremental transaction is permitted as a serial operation, the module further configured to perform at least one of the following:

send an advisory notice that the at least one threshold has been passed and permit the data field to be past the at least one threshold until a condition is met.

17. The system of claim 16, wherein the condition is associated with an amount of time.

18. The system of claim 14, wherein the system is at least one of the following:

a data storage system, a distributed storage system, a file system, and a distributed file system.

19. The system of claim 14, further comprising a persistent memory and a journal module, the journal module configured to store in the persistent memory the incremental transaction after determining that the incremental transaction could not cause the data field to pass the at least one threshold in combination with any subset of other pending incremental transactions.

20. The system of claim 14, wherein configured to determine comprises configured to compute an incremented data value of the data field based on the incremental transaction and a bound of possible values of the data field, the bound derived from the other pending incremental transactions, and to compare the incremented data value with the at least one threshold.

21. A method of tracking a boundary for a field stored in a computer system, comprising:

receiving a delta request associated with a field stored in a computer system; and

computing an updated boundary value of a possible value for the field, wherein the possible value is based on the delta request and a previous boundary value, the previous boundary value derived from a subset of other pending delta requests for the field.

22. The method of claim 21, wherein the delta request comprises an incremental value and an operation type that indicates either increment or decrement, wherein the operation type indicates whether the delta request increments or decrements the possible values for the field.

23. The method of claim 21, wherein the updated boundary value is an updated upper boundary value and the previous boundary value is a previous upper boundary value.

24. The method of claim 23, wherein, if the data request is a request to increment the field by an incremental value, computing the updated boundary value comprises incrementing the previous upper boundary value by the incremental value.

25. The method of claim 23, wherein, if the delta request commits and if the delta request is a request to decrement the field by an incremental value, further comprising computing a readjusted upper boundary value by decrementing the updated upper boundary value by the incremental value.

26. The method of claim 23, wherein, if the delta request aborts and if the delta request is a request to increment the field by an incremental value, further comprising computing a readjusted upper boundary value by decrementing the updated upper boundary value by the incremental value.

27. The method of claim 21, wherein the updated boundary value is an updated lower boundary value and the previous boundary value is a previous lower boundary value.

28. The method of claim 27, wherein, if the data request is a request to decrement the field by an incremental value, computing the updated boundary value comprises decrementing the previous lower boundary value by the incremental value.

29. The method of claim 27, wherein, if the delta request commits and if the delta request is a request to increment the field by an incremental value, further comprising computing a readjusted lower boundary value by incrementing the updated lower boundary value by the incremental value.

30. The method of claim 27, wherein, if the delta request aborts and if the delta request is a request to decrement the field by an incremental value, further comprising computing a readjusted lower boundary value by incrementing the updated lower boundary value by the incremental value.

31. The method of claim 21, wherein the field is associated with at least one of the following:

a data storage system, a distributed storage system, a file system, and a distributed file system.

32. A system for tracking a boundary of a field stored in a computer system, comprising:

a boundary module configured to receive a delta transaction associated with a field stored in a computer system; and

to compute an updated boundary value based on possible values for the field, wherein the possible values are based on the delta transaction and a previous boundary value, the previous boundary value derived from a subset of other pending delta transactions for the field.

33. The system of claim 32, wherein the system is at least one of the following:

a data storage system, a distributed storage system, a file system, and a distributed file system.

34. The system of claim 32, wherein the delta transaction comprises an incremental value and an operation type that indicates either increment or decrement, wherein the operation type indicates whether the delta request increments or decrements the possible values for the field.

35. The system of claim 34, further comprising a persistent memory and a journal module, the journal module configured to store in the persistent memory the delta transaction until the delta transaction either commits or aborts, wherein the boundary module is further configured to compute a readjusted boundary value based on the updated boundary value, the incremental value, and whether the delta transaction either committed or aborted.

36. A computer-readable medium having data structures stored thereon for tracking a boundary of a data field, the data structures comprising:

a data value field, wherein the data value field comprises a stored data value capable of being modified incrementally;

a plurality of delta value fields, wherein the delta value fields comprise, respectively, ones of a plurality of pending incremental values to be combined with the stored data value; and

at least one boundary field, wherein the at least one boundary field comprises a boundary value of possible data values resulting from a combination of the stored data value with a subset of the plurality of pending incremental values.

37. The computer-readable medium of claim 36, the data structures further comprising at least -one threshold field related to the data value field, wherein the at least one threshold field comprises a threshold value associated with a set of instructions to be executed if the boundary value passes the threshold value.

38. The computer-readable medium of claim 36, wherein the data value field is associated with at least one of the following:

a data storage system, a distributed storage system, a file system, and a distributed file system.