1 2 Previous Next 18 Replies Latest reply on Aug 14, 2008 3:16 AM by manik

    Eviction redesign

    brian.stansberry

      Discussion re: any redesign of eviction for JBC 3.

      Somewhat quoting myself from a tangent on another thread:

      Looking at the eviction system in JBC, it seems nicely set up to work a la carte:

      1) An interceptor that generates events and passes them to the region, which queues them. (This is somewhat coupled to #2 via the EvictionPolicy.canIgnoreEvent() call the interceptor makes.)
      2) The EvictionPolicy/Algorithm which can process the region's queue of events and determine what to evict, and then evict it.
      3) The evict() API on the cache, which is used by EvictionPolicy/Algorithm but also allows self-managed eviction.
      4) A thread-management system that kicks off #2.

      So, main thing is I think JBC should support these combos from the a la carte menu:

      #1 + #2 + #3 + #4 (of course)

      #3

      #1 + #2 + #3.

      The last can be achieved by setting the wakeupIntervalSeconds to 0, which effectively disables #4. An application can then manage eviction itself by:

      a) getting the EvictionPolicy associated with the region (which is part of the public API of Region)
      b) get the EvictionAlgorithm from that (which is part of the public EvictionPolicy API) c) process() on that (which is part of the public EvictionAlgorithm API).

      So, to provide a la carte eviction the main thing is to keep logical equivalents to those 3 API calls I described above available.

      I don't see any point in JBC trying to support #1 + #3 (i.e. add a way to bypass the EvictionInterceptor call to EvictionPolicy.canIgnoreEvent()). If someone wants that they can just implement a CacheListener to get events.

      The area where things are a bit clunky is the API of EvictionPolicy/EvictionAlgorithm. Currently those are a bit of a mix of API and SPI, with an implementation detail (delegate to EvictionAlgorithm) mixed in. Some initial thoughts on improving this:

      1) No one should need to call EvictionAlgorithm except an EvictionPolicy impl. That is, that's an internal implementation detail.

      2) Perhaps the EvictionPolicy interface should just be a client interface. That is, just expose what's needed by a thread that wants to run eviction: process()

      3) Then add an EvictionPolicySPI interface. That includes methods needed to integrate the policy impl into the cache, plus those needed by the event tracking mechanism (e.g. canIgnoreEvent()).

      Separating the SPI from EvictionPolicy is kind of just being anal, but if it doesn't introduce problems I think anal is good. :-) Doing #1 will change the EvictionPolicy interface anyway, so not existing impls will break anyway.

        • 1. Re: Eviction redesign
          manik

          I agree with your suggestions.

          But from what I gather, by being able to disable the eviction thread, you effectively have all of the a la carte combos you want.

          What really is need here, then, is just some tidying up and formalisation of the public API and SPI. TBH, I think Regions are desperately in need of some formalisation as well - it is a bit of a free-for-all at the moment and that's a bit sucky.

          Let me have a think about it and put up some ideas. I think eviction and regions will need to be done hand-in-hand, and that will then suck in marshalling regions as well.

          • 2. Re: Eviction redesign
            manik
            • 3. Re: Eviction redesign
              manik

              Also look at JBCACHE-1141

              • 4. Re: Eviction redesign
                manik

                Okay, so here is what I propose (and yes, it will break existing custom eviction policies and cfgs).

                Just to sum things up first, there are 4 tasks involved in the eviction system:

                1. Identify and record node activity (performed by the EvictionInterceptor, recorded on the Region)
                2. Triggering processing of eviction queue (performed either by the EvictionTimerTask, or manually by calling Region.getEvictionPolicy().getEvictionAlgorithm().process())
                3. Identifying which nodes are to be evicted: EvictionAlgorithm.process()
                4. Evicting the node: EvictionPolicy.evict();

                2 triggers 3 which triggers 4, so logically only 2 need be exposed to users via an API.

                E.g., Region should just have 3 eviction-related methods on its public interface:

                Region.processEvictionQueue();
                Region.resetEvictionQueue();
                Region.putNodeEvent(); // used by the EvictionInterceptor
                


                EvictionPolicy and EvictionAlgorithm are never exposed to client code.

                Configuration

                There have been requests for greater flexibility here, and I think there are 4 aspects to configuring eviction, which should be independent of one another:

                * Region - region that the cfg applies to
                * EvictionAlgorithm - how are nodes selected for eviction
                * EvictionAlgorithmConfiguration - cfg details for an EvictionAlgorithm, such as maxNodes, etc.
                * EvictionPolicy - what happens when nodes are evicted
                * ancillary aspects to the eviction region such as queue size

                The above will allow people to configure a LFUAlgorithm with, for example, SimpleEvictPolicy that just does a cache.evict(). Or, an LFUAlgorithm could be coupled with a RemoveOnEvictPolicy, which as the name suggests, does a remove.

                Basically I see the following exposed on each of the interfaces:

                EvictionPolicy.evict(Fqn f); // this is what happens when a node is evicted.
                
                EvictionAlgorithm.process(Queue eventQueue, EvictionPolicy policy); // processes a region. Decides what to evict, sets up internal queues, and then calls policy.evict();
                


                Region.processEvictionQueue() would:

                algorithm.process(eventQueue, policy);
                


                I also propose that we change the XML configuration to be more consisent with what w are doing with cache loaders, to look like:

                 <eviction wakeupInterval="5000">
                 <region name="/org/mydata" policyClass="o.j.c.e.SimpleEvictPolicy" algorithmClass="o.j.c.e.LFUAlgorithm" eventQueueSize="100000">
                 <properties>
                 maxNodes=10
                 timeToLive=300
                 </properties>
                 </region>
                 </eviction>
                


                What do people think? The benefit is a much cleaner and easier-to-understand set of interfaces and extension points.



                • 5. Re: Eviction redesign
                  manik

                  Re: XML configuration, I also propose dropping defaultPolicyClass and defaultEventQueueSize from the eviction element since there is a default element within the eviction element to denote settings for the default region, e.g.:

                   <eviction wakeUpInterval="5">
                   <default policyClass="o.j.c.e.SimpleEvictPolicy" algorithmClass="o.j.c.e.LFUAlgorithm" eventQueueSize="100000">
                   <properties>
                   maxNodes=10
                   timeToLive=300
                   </properties>
                   </default>
                   </eviction>
                  


                  Or is this shorthand for
                  <region name="/" ...>
                  

                  pointless? WDYT?

                  • 6. Re: Eviction redesign
                    manik

                    In terms of breaking compatibility, here is the impact:

                    1. XML cfg

                    No impact here since XML cfg is changing anyway. Mircea's translation script can be modeified to take care of this.

                    2. Programmatic cfg

                    * Minor impact, EvictionConfig.set/getDefaultXXX will go away.
                    * XmlConfigurationParser would have to create a normal EvictionRegionConfig for the default element and add it to the EvictionConfig using setDefaultEvictionRegionConfig().
                    * All other EvictionRegionConfigs will inherit values from EvictionConfig.getDefaultEvictionRegionConfig() for unset properties. This could be done by EvictionConfig when addEvictionRegionConfig() is called.
                    * XXXPolicyConfig will have to be replaced with XXXAlgorithmConfig.
                    * EvictionPolicyConfig interface replaced with EvictionAlgorithmConfig
                    * EvictionRegionConfig references to EvictionPolicyConfig will be changed to EvictionAlgorithmConfig
                    * EvictionRegionConfig will also take in a EvictionPolicy class name.

                    3. Using Region

                    * getEvictionPolicy(), getEvictionPolicyConfig(), getEvictionRegionConfig(), and all other eviction related methods will disappear, save for the 3 methods detailed above.

                    4. Implementing custom eviction algorithms.

                    * If extending an existing EvictionAlgorithm or the BaseEvictionAlgorithm, this should be simple and not require any changes.
                    * Any new algorithm implemented will have to provide an EvictionAlgorithmConfig instead of an EvictionPolicyConfig

                    • 7. Re: Eviction redesign
                      manik

                      I suppose the impact of #2 above could be minimised by:

                      * Keeping EvictionPolicyConfig but marking it as deprecated
                      * EvictionRegionConfig could issue a warning if an EvictionPolicyConfig is used, and copy all values across from here to an EvictionAlgorithmConfig
                      * Use a default EvictionPolicyClassName if none is specified (default: SimpleEvictionPolicy that just does Cache.evict()?)

                      • 8. Re: Eviction redesign
                        brian.stansberry

                        The defaultPolicyClass and defaultEventQueueSize do more than define the values for the "/" region. They also let you skip specifying those values for other regions you define.

                        IMO it's OK to drop that feature if doing so makes things meaningfully cleaner. Just wanted to point out that the feature exists.

                        • 9. Re: Eviction redesign
                          brian.stansberry

                          Perhaps a different name for "EvictionPolicy", maybe "EvictionActionPolicy" or something. Using the same term for a different thing will be confusing.

                          • 10. Re: Eviction redesign
                            manik

                             

                            "bstansberry@jboss.com" wrote:
                            The defaultPolicyClass and defaultEventQueueSize do more than define the values for the "/" region. They also let you skip specifying those values for other regions you define.

                            IMO it's OK to drop that feature if doing so makes things meaningfully cleaner. Just wanted to point out that the feature exists.


                            Yup, see my comment above:

                            "manik.surtani@jboss.com" wrote:

                            ...
                            * All other EvictionRegionConfigs will inherit values from EvictionConfig.getDefaultEvictionRegionConfig() for unset properties. This could be done by EvictionConfig when addEvictionRegionConfig() is called.
                            ...


                            • 11. Re: Eviction redesign
                              manik

                               

                              "bstansberry@jboss.com" wrote:
                              Perhaps a different name for "EvictionPolicy", maybe "EvictionActionPolicy" or something. Using the same term for a different thing will be confusing.


                              +1.

                              • 12. Re: Eviction redesign
                                brian.stansberry

                                I think you need a Region.canIgnoreEvent(Fqn fqn, NodeEventType eventType). Only having Region.putNodeEvent(NodeEvent event) is less efficient as you have to create the event object even if it will be ignored.

                                Hmm -- if I do this

                                cache.put(Fqn.fromString("/a/really/deeply/nested/node", "key", "value")

                                and all the higher level nodes already exist, are any eviction events generated for "/a", "/a/really", "/a/really/deeply", "/a/really/deeply/nested"?

                                If not there's probably no benefit to Region.canIgnoreEvent(Fqn fqn, NodeEventType eventType).

                                • 13. Re: Eviction redesign
                                  brian.stansberry

                                   

                                  "manik.surtani@jboss.com" wrote:
                                  Yup, see my comment above:

                                  "manik.surtani@jboss.com" wrote:

                                  ...
                                  * All other EvictionRegionConfigs will inherit values from EvictionConfig.getDefaultEvictionRegionConfig() for unset properties. This could be done by EvictionConfig when addEvictionRegionConfig() is called.
                                  ...


                                  Sounds good.

                                  My only other comment on this is to make sure a richly configured cache config can be built up using an IOC framework; i.e. not just by custom java code that knows the rules. And preferably without requiring a lot of advanced IOC usage to do it; just straight injection of pojos into a tree structure. I *think* what you are proposing does that, but it's lunch time, and I'm lazy, so I'm not sure. ;)

                                  • 14. Re: Eviction redesign
                                    manik

                                     

                                    "bstansberry@jboss.com" wrote:
                                    Hmm -- if I do this

                                    cache.put(Fqn.fromString("/a/really/deeply/nested/node", "key", "value")

                                    and all the higher level nodes already exist, are any eviction events generated for "/a", "/a/really", "/a/really/deeply", "/a/really/deeply/nested"?


                                    No. :-)

                                    There is merit to suppressing the construction of the EvictedEventNode if it is not needed though - perhaps Region.putNodeEvent() should look like:

                                    Region.putNodeEvent(Fqn fqn, NodeEventType type, int elementDifference)
                                    


                                    and the region can construct the EvictedEventNode if needed.

                                    1 2 Previous Next