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

• US 7,783,664 B2
• Filed: 12/17/2004
• Issued: 08/24/2010
• Est. Priority Date: 12/17/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Howell, Jonathan R.
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Yen; Syling
• Application Number:
  US11/015,227
• Publication Number:
  US 20060136369A1
• Time in Patent Office: 2,076 Days
• Field of Search: 707/200, 707/999.2, 707/999.01, 707/999.009, 707/999.008, 707/610, 707/640, 707/661, 707/704, 707/736, 707/781, 707/822, 711/161, 711/114, 711/154, 714/4, 714/11, 714/12
• US Class Current: 707/783
• 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 plurality of client devices;

by the lease coordinator, calculating, for a target client device, another value representative of an aggregation of the respective self values of the others of the subset of the plurality of client devices, the other value indicating which of a plurality of access modes are permissible for use by the target client device,

wherein each other value is protected by another read lease controlling whether the client is authorized to observe the other value, and

wherein the lease coordinator grants the other read lease to the target client device in an event at least one other client has a self value set TRUE, or in an event no other client has a self value set FALSE and none of the respective other clients is authorized to change the self value to TRUE; and

by the lease coordinator, sending, to the target client device, the other value calculated for the target client device such that usage patterns of particular other clients are hidden from 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 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.

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

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

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

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

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

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

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

13. 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 specific other value calculated for the target client device.

14. The method of claim 1, wherein each self value is protected by a self write lease controlling whether the client is authorized to change the self value.

15. A computer-readable storage medium having computer-executable instructions, that when executed by a processor, perform 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 plurality of client devices;

by the lease coordinator, aggregating the respective self values of the others of the subset of the plurality of client devices to calculate, for a target client device, another value representative of the target client device'"'"'s permissible use of the data object, the other value indicating which of a plurality of access modes are permissible for use by the target client device,

wherein each other value is protected by another read lease controlling whether the client is authorized to observe the other value, and

wherein the lease coordinator grants the other read lease to the target client device in an event at least one other client has a self value set TRUE, or in an event no other client has a self value set FALSE and none of the respective other clients is authorized to change the self value to TRUE; and

by the lease coordinator, sending to the target client device the other value calculated for the target client device, such that usage patterns of the other clients'"'"' are hidden from the target client device.

16. 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 another value representative of an aggregation of the respective self values of the others of the subset of the plurality of client devices, the other value indicating which of a plurality of access modes are permissible for use by the target client device,

wherein each other value is protected by another read lease controlling whether the client is authorized to observe the other value, and

wherein the lease coordinator grants the other read lease to the target client device in an event at least one other client has a self value set TRUE, or in an event no other client has a self value set FALSE and none of the respective other clients is authorized to change the self value to TRUE; and

sending to the target client device the other value calculated for the target client device, such that usage patterns of the other clients are hidden from the target client device.

17. The method of claim 16, wherein the lease coordinator is one of the plurality of client devices.

18. The method of claim 16, 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 16, 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 16, wherein the other value calculated is the aggregation of, at least in part, at least a subset of the self values sent by each of the subset of the plurality of client devices exclusive of the target client device.

21. The method of claim 16, wherein the self values sent by each of the subset of the plurality of client devices are Boolean values, and wherein further the calculating the other value comprises taking a logical OR of at least a subset of the self values sent by the plurality of client devices.

22. The method of claim 16, wherein the self values sent by each of the subset of the plurality of client devices are Boolean values, and wherein further the calculating the other value comprises taking a logical AND of at least a subset of the self values sent by the plurality of client devices.

23. The method of claim 16, wherein the self values sent by each of the subset of the plurality of client devices are non-negative integers, and wherein further the calculating the other value comprises taking a minimum of at least a subset of the self values sent by the plurality of client devices.

24. The method of claim 16, wherein the self values sent by each of the subset of the plurality of client devices are non-negative integers, and wherein further the calculating the other value comprises taking a maximum of at least a subset of the self values sent by the plurality of client devices.

25. The method of claim 16, wherein the self values sent by each of the subset of the plurality of client devices are non-negative integers, and wherein further the calculating the other value comprises taking a sum of at least a subset of the self values sent by the plurality of client devices.

26. The method of claim 16, wherein the self values sent by each of the subset of the plurality of client devices are elements from a finite set, and wherein further the calculating the other value comprises taking a union of at least a subset of the self values sent by the plurality of client devices.

27. A computer-readable storage medium having computer-executable instructions, that when executed by a processor, perform 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, another value representative of an aggregation of the respective self values of the others of the subset of the plurality of client devices, the other value being further representative of that target client device'"'"'s permissible use of the data object by indicating which of a plurality of access modes are permissible for use by the target client device,

wherein each other value is protected by another read lease controlling whether the client is authorized to observe the other value, and

wherein the lease coordinator grants the other read lease to the target client in an event at least one other client has a self value set TRUE, or in an event no other client has a self value set FALSE and none of the respective other clients is authorized to change the self value to TRUE; and

sending, to the target client device, the other value calculated for the target client device, such that usage patterns of the other clients are hidden from the target client device.

28. 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 plurality of client devices;

aggregating the respective self values of others of the plurality of client devices to calculate, for a target client device, another value specific for the target client device and representative of that target client device'"'"'s permissible use of the data object, the other value indicating which of a plurality of access modes are permissible for use by the target client device,

wherein each other value is protected by another read lease controlling whether the client is authorized to observe the other value, and

wherein the lease coordinator grants the other read lease to the target client in an event at least one other client has a self value set TRUE, or in an event no other client has a self value set FALSE and none of the respective other clients is authorized to change the self value to TRUE; and

sending to the target client device the other value calculated for the target client device such that usage patterns of the other clients are hidden from the target client device; and

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

29. The system of claim 28, wherein the lease coordinator is one of the plurality of client devices.

30. The system of claim 28, wherein the lease coordinator is the target client device.

31. The system of claim 28, 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.

32. The system of claim 28, 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.