Memory efficient directory coherency maintenance

• US 5,860,153 A
• Filed: 11/22/1995
• Issued: 01/12/1999
• Est. Priority Date: 11/22/1995
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Bernabeu-Auban, Jose M., Khalidi, Yousef A., Shirriff, Kenneth W., Matena, Vladimir, Thadani, Moti N.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): KING, CONLEY BURRELL
• Application Number:
  US08/562,177
• Time in Patent Office: 1,147 Days
• Field of Search: 395/200.01, 395/200.09, 395/468, 395/471, 395/421.06, 395/200.3, 395/200.47, 395/200.48, 395/200.49, 711/141, 711/144, 711/216
• US Class Current: 711/216
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming

Abstract

A bit map is maintained by a provider object of a name server to keep track of names cached by a cache object of the client. The bit map is indexed by performing a hash of the name. When a name is looked up by the server on behalf of a client, the server hashes the name, and sets the bit in the bit map indexed by the result of the hash modulo the size of the bit map. The result of the hash is returned to the client and is stored with the entry in the cache. A bit "set" in the bit map indicates that the client caches at least one name that hashes into the bit. When the server invalidates a name, a hash of the name to be invalidated is used to find the corresponding bit in the bit mask. If the bit is set, the server sends an invalidation request to the client. The invalidation request includes the result of the hash, and the size of the provider'"'"'s bit map. The client invalidates all entries that hash into the specified bit in the bitmap on the server. Alternatively, the invalidation request also includes the name to be invalidated and the client invalidates only the entry that matches the name.

Claims

1. A directory coherence mechanism for use in a client-server system having a server and a plurality of clients, said mechanism comprising:

a cache configured to store name information; and

a name server configured to provide the name information to the cache, the name server having a data structure and setting a hash indicator of the data structure when providing the cache name information of a particular object name, the hash indicator having a hash index calculated by hashing the particular object name, wherein if the name server receives a directory invalidate request for a name to be invalidated, the name server hashes the name to be invalidated and if a data of the data structure indexed by the hash of the name to be invalidated has been set, the name server orders the cache to invalidate all cached name information associated with the data indexed by the hash of the name to be invalidated and the name server resets the data indexed by the hash of the name to be invalidated.

2. The directory coherence mechanism as set forth in claim 1, wherein the cache indicates to a name server cache when all cached object name information associated with the data indexed by the hash of the name to be invalidated has been invalidated.

3. The directory coherence mechanism as set forth in claim 2, wherein the name server indicates a successful invalidation after the cache has indicated to the name server that all of the cached name information associated with the data indexed by the hash of the name to be invalidated has been invalidated.

4. The directory coherence mechanism as set forth in claim 1, wherein the name server indicates a successful invalidation if the name server hashes the name to be invalidated and the data of the data structure indexed by the hash of the name to be invalidated has not been set.

5. The directory coherence mechanism as set forth in claim 1, wherein if the name server receives a directory invalidate request for a name to be invalidated, the name server hashes the name to be invalidated and, if a data of the data structure indexed by the hash of the name to be invalidated has been set, the name server orders the cache to invalidate cached name information associated with the name to be invalidated, then, if the cache indicates that the cached name information associated with the name to be invalidated has been invalidated, the name server resets said data indexed by the hash of the name to be invalidated only if there are no other cached entries mapping to the same data.

6. The directory coherence mechanism as set forth in claim 5, wherein the cache indicates to the name server when the cached name information associated with the name to be invalidated has been invalidated and when no name information associated with the name has been cached.

7. The directory coherence mechanism as set forth in claim 6, wherein the name server indicates a successful invalidation after the cache has indicated to the name server that the cached name information associated with the name to be invalidated has been invalidated.

8. The directory coherence mechanism as set forth in claim 5, wherein the name server indicates a successful invalidation if the name server hashes the name to be invalidated and the data of the data structure indexed by the hash of the name to be invalidated has not been set.

9. The directory coherence mechanism as set forth in claim 5, wherein said data structure is a bit map, said data is a bit and said hash indicator is a hash bit.

10. A method for maintaining directory coherence, comprising the steps of:

caching name information;

providing the name information from a name server to a cache, the name server having a data structure and setting a hash indicator of the data structure when providing the name information of a particular name, the hash indicator having a hash index calculated by hashing the particular name;

hashing the name to be invalidated, said hashing performed by the name server, if the name server receives a directory invalidate request for a name to be invalidated; and

if a data of the data structure indexed by the hash of the name to be invalidated has been set, said method ordering the cache to invalidate all cached name information associated with said data indexed by the hash of the name to be invalidated and resetting the data indexed by the hash of the name to be invalidated, said ordering performed by the name server.

11. The method as set forth in claim 10, wherein if the name server receives a directory invalidate request for a name to be invalidated, further comprising the steps of:

hashing the name to be invalidated, said hashing performed by the name server;

if a data of the data structure indexed by the hash of the name to be invalidated has been set, said method ordering the cache to invalidate all cached name information associated with the data indexed by the hash of the name to be invalidated, said ordering performed by the name server; and

resetting a bit indexed by the hash of an object name to be invalidated, said resetting performed by the name server.

12. The method as set forth in claim 11, further comprising the step of:

indicating to the name server when all cached name information associated with the data indexed by the hash of the name to be invalidated has been invalidated, said indicating performed by the cache.

13. The method as set forth in claim 12, further comprising the step of:

indicating a successful invalidation after the cache has indicated to the name server that all of the cached name information associated with the data indexed by the hash of the name to be invalidated has been invalidated, said indicating performed by the name server.

14. The method as set forth in claim 11, further comprising the step of:

indicating a successful invalidation if the name server hashes the name to be invalidated and the data of the data structure indexed by the hash of the name to be invalidated has not been set, said indicating performed by the name server.

15. The method as set forth in claim 10, wherein if the name server receives a directory invalidate request for a name to be invalidated, the method further comprises the steps of:

hashing the name to be invalidated;

if a data of the data structure indexed by the hash of the name to be invalidated has been set, ordering the cache to invalidate cached name information associated with the name to be invalidated, said ordering performed by the name server; and

then,

if the cache indicates that the cached name information associated with the name to be invalidated has been invalidated, resetting a bit hashed for the name to be invalidated, said indicating performed by the name server.

16. The method as set forth in claim 15, further comprising the steps of:

indicating to the name server when the cached name information associated with the name to be invalidated has been invalidated, said indicating performed by the cache.

17. The method as set forth in claim 16, further comprising the step of:

indicating a successful invalidation after the cache has indicated to the name server that the cached name information associated with the name to be invalidated has been invalidated, said indicating performed by the name server.

18. The method as set forth in claim 15, further comprising the step of:

indicating a successful invalidation if the name server hashes the name to be invalidated and the data of the data structure indexed by the hash of the name to be invalidated has not been set, said indicating performed by the name server.

19. The method as set forth in claim 15, further comprising the step of:

keeping the data set if there are entries left in the cache that map to the same data, said keeping performed by the name server.

20. The method as set forth in claim 12 wherein said data is a bit, said data structure is a bit map and said hash indicator is a hash bit.