10 Replies Latest reply on Mar 22, 2010 11:00 AM by Manik Surtani

    FIFO Ordering

    Bryan Grunow Newbie

      It looks like in the CR3 timeframe SimpleDataContainer and FIFOSimpleDataContainer were introduced.  FIFOSimpleDataContainer was made the default for FIFO in the DataContainerFactory.

       

      We were using FIFODataContainer to get data back from the cache in FIFO order by asking the DataContainer of the Cache for the iterator.  With the change to FIFOSimpleDataContainer the iterator doesn't appear to be coming back in FIFO order.

       

      I looked at the code and it appears the iterator is ordered based on entry creation time so I'm not sure why it's not coming back in FIFO order.

       

      Just looked again and I set our adds to the cache to be longer than the timestampGranularity to get the ordering to work.

       

      So there are a few options.

       

      1. In the short term is there a simple way to go back using FIFODataContainer?
      2. Can I set the timestampGranularity in the configuration file somehow to shorten the time?
      3. Add the ability into the DataContainerFactory for us to pass a custom class name so we can write our own DataContainer.

       

      We'd prefer #3 if possible.

       

      Bryan

        • 1. Re: FIFO Ordering
          Mircea Markus Master
          It looks like in the CR3 timeframe SimpleDataContainer and FIFOSimpleDataContainer were introduced.  FIFOSimpleDataContainer was made the default for FIFO in the DataContainerFactory.

          We've released Infinispan 4.0.0.FInal, I suggest you move to this version (if not already did so).

           

          With the change to FIFOSimpleDataContainer the iterator doesn't appear to be coming back in FIFO order.

           

          I looked at the code and it appears the iterator is ordered based on entry creation time so I'm not sure why it's not coming back in FIFO order.

          This looks like a bug to me, can you reproduce this in a unit test?

           

          Just looked again and I set our adds to the cache to be longer than the timestampGranularity to get the ordering to work.

          Are you using put.(k,v, timestmap) methods? These are refering to expiraration; the order of elements as returned by FifoSimpleDataContainer is different, and it has to do with eviction. For more an expiration and eviction on infinispan wiki, look for "evictio" and "expiration"

           

            Add the ability into the DataContainerFactory for us to pass a custom class name so we can write our own DataContainer.

          That's a good idea, I'll add a jira for this.

          • 2. Re: FIFO Ordering
            Mircea Markus Master
            https://jira.jboss.org/jira/browse/ISPN-362 created for pluggable DataContainers. Fell like giving it a try?
            • 3. Re: FIFO Ordering
              Bryan Grunow Newbie

              We're using .put(k,v).  The reason we didn't see them coming back in FIFO order is we were putting them in too quickly so they all were within the same second.

               

              I'll take a look at the JIRA issue but it's definitely something we'll look into as our use cases need better iteration performance and sorting the list everytime won't scale for us.

               

              Bryan

              • 4. Re: FIFO Ordering
                Mircea Markus Master
                We're using .put(k,v).  The reason we didn't see them coming back in FIFO order is we were putting them in too quickly so they all were within the same second.

                DataContainer does not rely on the timestamp when data was added; it rather keeps the FIFO order based on the sequence in which they were added. So the addition "speed" should not make any difference at all. Do you have a unit test to replicate this behavior?

                • 5. Re: FIFO Ordering
                  Bryan Grunow Newbie

                  I was looking at the existing unit test testOrdering() you have in org.infinispan.container.FIFODataContainerTest and it does in fact pass but it's configured differently then when using Infinispan.  The test is configured with the FIFOSimpleDataContainer(16, 1) where the second parameter is the timestampGranularity.  In Infinispan it's set to 1000 which gives second-level granularity.

                   

                  When I change the test to use what is configured in Infinispan (1000) the test fails.

                   

                  The parameter should probably be configurable as well.

                   

                  Also, I've got a version working that allows passing a custom DataContainer class name.  It doesn't take parameters but that's all we need.

                   

                  Bryan

                  • 6. Re: FIFO Ordering
                    Manik Surtani Master

                    mircea.markus wrote:

                     

                    We're using .put(k,v).  The reason we didn't see them coming back in FIFO order is we were putting them in too quickly so they all were within the same second.

                    DataContainer does not rely on the timestamp when data was added; it rather keeps the FIFO order based on the sequence in which they were added. So the addition "speed" should not make any difference at all. Do you have a unit test to replicate this behavior?

                    This is not true.  The FIFOSimpleDataContainer does rely on timestamps (see Javadoc comment for details on how this is done). 

                     

                    However, it is true that the original FIFODataContainer did not rely on timestamps (see Javadocs) but this is not used as a default due to thread starvation issues under certain load conditions.

                    • 7. Re: FIFO Ordering
                      Manik Surtani Master

                      imbng wrote:

                       

                      I was looking at the existing unit test testOrdering() you have in org.infinispan.container.FIFODataContainerTest and it does in fact pass but it's configured differently then when using Infinispan.  The test is configured with the FIFOSimpleDataContainer(16, 1) where the second parameter is the timestampGranularity.  In Infinispan it's set to 1000 which gives second-level granularity.

                       

                      When I change the test to use what is configured in Infinispan (1000) the test fails.

                       

                      The parameter should probably be configurable as well.

                       

                      Also, I've got a version working that allows passing a custom DataContainer class name.  It doesn't take parameters but that's all we need.

                       

                      Bryan

                      The coarser granularity used at runtime is to reduce the number of comparisons and hence significantly increase performance.  Ordering is done using the Timsort algorithm (backported from JDK 7), and this performs significantly better when the number of swaps are reduced.

                       

                      Also, keep in mind that the primary purpose of a FIFO based DataContainer is not to provide ordered iterators on the cache, but to provide some form of preference when evicting entries.  As such, this should never be considered as a strict FIFO, but rather as a best-effort FIFO.  The fact that you get ordered iteration over the cache is purely a side-effect.

                       

                      But yes, +1 to making the timestamp granularity configurable - perhaps using a -D system parameter for now, since I expect some changes to the way eviction works as well as the DataContainer interface in 4.1.0 (self-organising, bounded data containers).

                      • 8. Re: FIFO Ordering
                        Mircea Markus Master
                        ah, sorry for the confusion.
                        • 9. Re: FIFO Ordering
                          Bryan Grunow Newbie

                          Manik,

                           

                          What are the proposed changes to DataContainer for 4.1?  Is there a document out there I can look at?

                           

                          We are planning on implementing our own DataContainer and I'd like to see what's changing to get a better idea of what'll be expected.

                           

                          Thanks,

                           

                          Bryan

                          • 10. Re: FIFO Ordering
                            Manik Surtani Master

                            What are the proposed changes to DataContainer for 4.1?  Is there a document out there I can look at?

                            Vladimir just emailed infinispan-dev with some proposed changes earlier today...