Method and system for protecting the consistency of information in a distributed file system

• US 20060136369A1
• Filed: 12/17/2004
• Published: 06/22/2006
• Est. Priority Date: 12/17/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Howell, Jonathan R.
• Granted Patent: US 7,783,664 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

Disclosed are “black-box leases” that protect information consistency and that allow for information sharing in a distributed file system while hiding from a client information about other clients'"'"' use of the file system. This information hiding also allows greater concurrency because changes to the file system are permitted as long as they do not affect the leases as observed by the clients. For each data field protected by a black-box lease, a client has a two-value data structure: SelfValue represents the client'"'"'s intended use of the data field, and OtherValue is an aggregation of the other clients'"'"' intended uses of that data field. Knowing only this aggregate OtherValue, but without knowing any specifics of the other clients'"'"' usage patterns, the client knows how it may use the data field without adversely affecting the consistency of data in the distributed file system.

Claims

1. In a computing environment comprising a lease coordinator, a data object, and a plurality of client devices, a method for protecting consistency of properties of the data object, the method comprising:

by each of at least a subset of the plurality of client devices, sending to the lease coordinator a self value representative of that client device'"'"'s intended use of the data object;

by the lease coordinator, receiving at least a subset of the self values sent by the client devices;

by the lease coordinator, calculating for a target client device an other value representative of that target client device'"'"'s permissible use of the data object, the other value based, at least in part, on at least a subset of the self values sent by the client devices;

by the lease coordinator, sending to the target client device the other value calculated for the target client device; and

by the target client device, receiving the other value calculated for the target client device.

2. The method of claim 1 wherein the lease coordinator is one of the plurality of client devices.

3. The method of claim 2 wherein the lease coordinator is the target client device.

4. The method of claim 1 wherein the data object is selected from the group consisting of:

a data file, a set of data files, contents of a data file, a data folder, a set of data folders, and a data field in a database.

5. The method of claim 1 wherein a self value is representative of an access mode selected from the group consisting of:

read from the data object, write to the data object, delete the data object, exclude read from the data object, exclude write to the data object, and exclude delete the data object.

6. The method of claim 1 wherein the calculated other value is based, at least in part, on at least a subset of the self values sent by the client devices exclusive of the target client device.

7. The method of claim 1 wherein the self values sent by the computing devices are Boolean values and wherein calculating an other value comprises taking a logical OR of at least a subset of the self values sent by the client devices.

8. The method of claim 1 wherein the self values sent by the computing devices are Boolean values and wherein calculating an other value comprises taking a logical AND of at least a subset of the self values sent by the client devices.

9. The method of claim 1 wherein the self values sent by the computing devices are non-negative integers and wherein calculating an other value comprises taking a minimum of at least a subset of the self values sent by the client devices.

10. The method of claim 1 wherein the self values sent by the computing devices are non-negative integers and wherein calculating an other value comprises taking a maximum of at least a subset of the self values sent by the client devices.

11. The method of claim 1 wherein the self values sent by the computing devices are non-negative integers and wherein calculating an other value comprises taking a sum of at least a subset of the self values sent by the client devices.

12. The method of claim 1 wherein the self values sent by the computing devices are elements from a finite set and wherein calculating an other value comprises taking a union of at least a subset of the self values sent by the client devices.

13. The method of claim 1 further comprising:

by the lease coordinator, calculating for each client device in a plurality of client devices an other value representative of that client device'"'"'s permissible use of the data object, the other value based, at least in part, on at least a subset of the self values sent by the client devices;

by the lease coordinator, sending to each client device the other value calculated for that client device; and

by each client device, receiving the other value calculated for that client device.

14. The method of claim 13 wherein each other value calculated for a client device is based, at least in part, on at least a subset of the self values sent by the client devices exclusive of that client device.

15. The method of claim 1 further comprising:

by the target client device, using the data object, the using based, at least in part, on the received other value calculated for the target client device.

16. A computer-readable medium having computer-executable instructions for performing a method, in a computing environment comprising a lease coordinator, a data object, and a plurality of client devices, for protecting consistency of properties of the data object, the method comprising:

by each of at least a subset of the plurality of client devices, sending to the lease coordinator a self value representative of that client device'"'"'s intended use of the data object;

by the lease coordinator, receiving at least a subset of the self values sent by the client devices;

by the lease coordinator, calculating for a target client device an other value representative of that target client device'"'"'s permissible use of the data object, the other value based, at least in part, on at least a subset of the self values sent by the client devices;

by the lease coordinator, sending to the target client device the other value calculated for the target client device; and

by the target client device, receiving the other value calculated for the target client device.

17. In a computing environment comprising a lease coordinator, a data object, and a plurality of client devices, a method for a target client device to protect consistency of properties of the data object, the method comprising:

sending to the lease coordinator a self value representative of the target client device'"'"'s intended use of the data object;

receiving from the lease coordinator an other value for the target client device; and

using the data object, the using based, at least in part, on the received other value for the target client device.

18. The method of claim 17 wherein the data object is selected from the group consisting of:

a data file, a set of data files, contents of a data file, a data folder, a set of data folders, and a data field in a database.

19. The method of claim 17 wherein the self value is representative of an access mode selected from the group consisting of:

read from the data object, write to the data object, delete the data object, exclude read from the data object, exclude write to the data object, and exclude delete the data object.

20. The method of claim 17 wherein the self value is selected from the set consisting of:

a Boolean value, a non-negative integer, and an element from a finite set.

21. A computer-readable medium having computer-executable instructions for performing a method, in a computing environment comprising a lease coordinator, a data object, and a plurality of client devices, for a target client device to protect consistency of properties of the data object, the method comprising:

sending to the lease coordinator a self value representative of the target client device'"'"'s intended use of the data object;

receiving from the lease coordinator an other value for the target client device; and

using the data object, the using based, at least in part, on the received other value for the target client device.

22. In a computing environment comprising a lease coordinator, a data object, and a plurality of client devices, a method for the lease coordinator to protect consistency of properties of the data object, the method comprising:

receiving from each of at least a subset of the plurality of client devices a self value representative of that client device'"'"'s intended use of the data object;

calculating for a target client device an other value representative of that target client device'"'"'s permissible use of the data object, the other value based, at least in part, on at least a subset of the self values sent by the client devices; and

sending to the target client device the other value calculated for the target client device.

23. The method of claim 22 wherein the lease coordinator is one of the plurality of client devices.

24. The method of claim 22 wherein the data object is selected from the group consisting of:

a data file, a set of data files, contents of a data file, a data folder, a set of data folders, and a data field in a database.

25. The method of claim 22 wherein a self value is representative of an access mode selected from the group consisting of:

read from the data object, write to the data object, delete the data object, exclude read from the data object, exclude write to the data object, and exclude delete the data object.

26. The method of claim 22 wherein the calculated other value is based, at least in part, on at least a subset of the self values sent by the client devices exclusive of the target client device.

27. The method of claim 22 wherein the self values sent by the computing devices are Boolean values and wherein calculating an other value comprises taking a logical OR of at least a subset of the self values sent by the client devices.

28. The method of claim 22 wherein the self values sent by the computing devices are Boolean values and wherein calculating an other value comprises taking a logical AND of at least a subset of the self values sent by the client devices.

29. The method of claim 22 wherein the self values sent by the computing devices are non-negative integers and wherein calculating an other value comprises taking a minimum of at least a subset of the self values sent by the client devices.

30. The method of claim 22 wherein the self values sent by the computing devices are non-negative integers and wherein calculating an other value comprises taking a maximum of at least a subset of the self values sent by the client devices.

31. The method of claim 22 wherein the self values sent by the computing devices are non-negative integers and wherein calculating an other value comprises taking a sum of at least a subset of the self values sent by the client devices.

32. The method of claim 22 wherein the self values sent by the computing devices are elements from a finite set and wherein calculating an other value comprises taking a union of at least a subset of the self values sent by the client devices.

33. The method of claim 22 further comprising:

calculating for each client device in a plurality of client devices an other value representative of that client device'"'"'s permissible use of the data object, the other value based, at least in part, on at least a subset of the self values sent by the client devices; and

sending to each client device the other value calculated for that client device.

34. The method of claim 33 wherein each other value calculated for a client device is based, at least in part, on at least a subset of the self values sent by the client devices exclusive of that client device.

35. A computer-readable medium having computer-executable instructions for performing a method, in a computing environment comprising a lease coordinator, a data object, and a plurality of client devices, for the lease coordinator to protect consistency of properties of the data object, the method comprising:

receiving from each of at least a subset of the plurality of client devices a self value representative of that client device'"'"'s intended use of the data object;

calculating for a target client device an other value representative of that target client device'"'"'s permissible use of the data object, the other value based, at least in part, on at least a subset of the self values sent by the client devices; and

sending to the target client device the other value calculated for the target client device.

36. A system for protecting consistency of properties of a data object, the system comprising:

the data object;

a plurality of client devices, each client device configured for sending to a lease coordinator a self value representative of that client device'"'"'s intended use of the data object;

the lease coordinator configured for receiving at least a subset of the self values sent by the client devices, for calculating for a target client device an other value representative of that target client device'"'"'s permissible use of the data object, the other value based, at least in part, on at least a subset of the self values sent by the client devices, and for sending to the target client device the other value calculated for the target client device; and

a target client device configured for receiving the other value calculated for the target client device.

37. The system of claim 36 wherein the lease coordinator is one of the plurality of client devices.

38. The system of claim 36 wherein the lease coordinator is the target client device.

39. The system of claim 36 wherein the data object is selected from the group consisting of:

a data file, a set of data files, contents of a data file, a data folder, a set of data folders, and a data field in a database.

40. The system of claim 36 wherein:

the lease coordinator is further configured for calculating for each client device in a plurality of client devices an other value representative of that client device'"'"'s permissible use of the data object, the other value based, at least in part, on at least a subset of the self values sent by the client devices, and for sending to each client device the other value calculated for that client device; and

wherein

each client device is further configured for receiving the other value calculated for that client device.

41. The system of claim 36 wherein the target client device is further configured for:

using the data object, the using based, at least in part, on the received other value calculated for the target client device.

42. A computer-readable medium having stored thereon a lease data structure, the lease data structure comprising:

a first data field containing data representing, for a first use mode of a data object, a self value representative of a target client device'"'"'s intended use of the data object; and

a second data field containing data representing, for the first use mode of the data object, an other value representative of an aggregation of a plurality of client devices'"'"' intended uses of the data object.

43. The computer-readable medium of claim 42 wherein the data object is selected from the group consisting of:

a data file, a set of data files, contents of a data file, a data folder, a set of data folders, and a data field in a database.

44. The computer-readable medium of claim 42 wherein the first use mode is selected from the group consisting of:

read from the data object, write to the data object, delete the data object, exclude read from the data object, exclude write to the data object, and exclude delete the data object.

45. The computer-readable medium of claim 42 wherein the aggregation is exclusive of the target client device'"'"'s intended use of the data object.

46. The computer-readable medium of claim 42 wherein the lease data structure further comprises:

a third data field containing data representing, for a second use mode of the data object, a self value representative of a target client device'"'"'s intended use of the data object; and

a fourth data field containing data representing, for the second use mode of the data object, an other value representative of an aggregation of a plurality of client devices'"'"' intended uses of the data object.

47. The computer-readable medium of claim 46 wherein the second use mode is selected from the group consisting of:

read from the data object, write to the data object, delete the data object, exclude read from the data object, exclude write to the data object, and exclude delete the data object.