Utility-based invalidation propagation scheme selection for distributed cache consistency

Patent metadata

Field	Value
Publication number	US-9832278-B2
Application number	US-201314040746-A
Country	US
Kind code	B2
Filing date	Sep 30, 2013
Priority date	Sep 30, 2013
Publication date	Nov 28, 2017
Grant date	Nov 28, 2017

Abstract

A computerized method for dynamic consistency management of server side cache management units in a distributed cache, comprising: updating a server side cache management unit by a client; assigning each of a plurality of server side cache management units to one of a plurality of propagation topology groups according to an analysis of a plurality of cache usage measurements thereof, each of said propagation topology groups is associated with a different write request propagation scheme; and managing client update notifications of members of each of said propagation topology groups according to the respective said different write request propagation scheme which is associated therewith.

First claim

What is claimed is:

1. A computerized method for dynamic consistency management of server side cache management units in a distributed cache, comprising:
collecting a plurality of cache usage measurements of a plurality of server side cache management units;
storing at least one of said plurality of server side cache management units responsive to a chosen write request propagation scheme;
estimating an amount of distributed messages saved by said storing;
analyzing said plurality of cache usage measurements to assess a utilization of each of said plurality of server side cache management units by a plurality of clients;
recognizing an event of one of said plurality of server side cache management units by a client;
assigning each of said plurality of server side cache management units to one of a plurality of propagation topology groups according to said utilization, each of said propagation topology groups is associated with a different write request propagation scheme, wherein said different write request propagation scheme comprises instructions for managing updates of said plurality of server side cache management units; and
managing client update notifications of members of each of said propagation topology groups according to respective said different write request propagation scheme which is associated therewith
wherein said analyzing is performed by calculating a ratio between estimated said amount of distributed messages and a digitalized-memory size used for said storing of said server side cache management units.

2. The method of claim 1 , wherein said event comprises at least one of writing an element of said server side cache management unit, reading an element of said server side cache management unit, changing load of a network connecting said client and said server, changing load on client itself, notification by said client concerning eviction of a client side cache management unit and passing time.

3. The method of claim 1 , wherein a write request propagation scheme is at least one of:
a client-set write request propagation scheme recording a plurality of clients sets and according to clients' access to said plurality of server side cache management units and sending a plurality of cache messages according to said plurality of clients sets; and
a least recently used write request propagation scheme, recording usage time for said plurality of server side cache management units and sending a plurality of cache messages for least recently used server side cache management units wherein each said plurality of clients sets is a sub-group chosen from a plurality of clients.

4. The method of claim 3 , wherein said assigning each of a plurality of cache management units is to one of two propagation topology groups.

5. The method of claim 4 , further comprising:
associating said client-set write request propagation scheme with first of said two propagation topology groups; and
associating a notifying all clients write request propagation scheme with second of said two propagation topology groups.

6. The method of claim 1 , wherein a write request propagation scheme is at least one of notifying all clients, a broadcasting protocol, a periodic update protocol for sending periodic cache updates to at least one client cache.

7. The method of claim 1 , wherein said assigning is performed independently of a cache transaction.

8. The method of claim 1 , further comprising:
bounding a memory of a computer readable medium; and
storing at least one of a plurality of cache datums responsive to a chosen write request propagation scheme in bounded said memory.

9. The method of claim 1 , further comprising:
manually choosing, by a user, a substitute write request propagation scheme for at least one of said plurality of server side cache management units, said substitute write request propagation scheme over-riding an automatically chosen write request propagation scheme.

10. The method of claim 1 , wherein a plurality of write request propagation scheme supporting measurements are recorded on a server local storage by one write request propagation scheme.

11. The method of claim 1 , wherein said analyzing and said assigning are iteratively repeated.

12. A system for dynamic cache consistency management of server side cache management units by assignment of server side cache management units to write request propagation schemes, comprising:
a memory of a computer readable medium, said memory stores a dynamic cache consistency management code;
a processor executing said dynamic cache consistency management code for:
automatically choosing, using a computerized processor, a subset of a plurality of cache usage measurements for monitoring,
monitoring said subset of said plurality of cache usage measurements,
storing a plurality of values of said plurality of cache usage measurements collected by said monitoring on said memory,

analyzing stored said plurality of values to assess a utilization of a plurality of server side cache management units by a plurality of clients, and
automatically assigning, using a computerized processor, each of said plurality of server side cache management units, each datum having said plurality of cache usage measurements, to a write request propagation scheme according to said utilization, wherein said write request propagation scheme comprises instructions for managing updates of each of said plurality of server side cache management units;
wherein said processor is further configured for executing said code for:
instructing a storage of at least one of said plurality of server side cache management units responsive to chosen said write request propagation scheme;
estimating an amount of distributed messages saved by storing for a server side cache management unit; and
wherein said analying is performed by calculating a ratio analyzing by calculating a ratio between estimated said amount of distributed messages and a digitalized-memory size used for said storing of said server side cache management unit.

13. The system of claim 12 , wherein said processor instructs storing at least one of said plurality of server side cache management units responsive to chosen said write request propagation scheme in said memory.

14. The system of claim 12 , wherein said automatically choosing is randomly selected.

15. The system of claim 12 , wherein said automatically assigning is initiated as a random assignment of one of said plurality of write request propagation schemes to each of said plurality of server side cache management units.

Assignees

• IBM

Inventors

• Chockler Gregory
• Laden Guy
• Luboshitz Eli
• Melamed Roie
• Parees Benjamin M
• Tock Yoav

Classifications

• H04L67/2852 Primary

  Electricity · mapped topic

• G06F12/0824

  Distributed directories, e.g. linked lists of caches · CPC title

• G06F12/0808

  with cache invalidating means (G06F12/0815 takes precedence) · CPC title

• H04L67/5682 Primary

  Policies or rules for updating, deleting or replacing the stored data · CPC title