[Zodb-checkins] CVS: ZODB3/ZEO - simul.py:1.12.8.2.18.1

[Jeremy Hylton]

Update of /cvs-repository/ZODB3/ZEO
In directory cvs.zope.org:/tmp/cvs-serv26331

Modified Files:
      Tag: Zope-2_6-branch
	simul.py 
Log Message:
A simulator for the 2Q algorithm.


=== ZODB3/ZEO/simul.py 1.12.8.2 => 1.12.8.2.18.1 ===
--- ZODB3/ZEO/simul.py:1.12.8.2	Wed Oct 16 17:45:59 2002
+++ ZODB3/ZEO/simul.py	Wed Nov 26 15:19:01 2003
@@ -44,7 +44,7 @@
     cachelimit = 20*MB
     simclass = ZEOCacheSimulation
     try:
-        opts, args = getopt.getopt(sys.argv[1:], "bflyzs:")
+        opts, args = getopt.getopt(sys.argv[1:], "bflyz2s:")
     except getopt.error, msg:
         usage(msg)
         return 2
@@ -61,6 +61,8 @@
             simclass = ZEOCacheSimulation
         if o == '-s':
             cachelimit = int(float(a)*MB)
+        if o == '-2':
+            simclass = TwoQSimluation
     if len(args) != 1:
         usage("exactly one file argument required")
         return 2
@@ -428,6 +430,167 @@
         self.prev = prev
         self.next = next
         prev.next = next.prev = self
+
+am = object()
+a1in = object()
+a1out = object()
+
+class TwoQSimluation(Simulation):
+
+    # The original 2Q algorithm is page based and the authors offer
+    # tuning guidlines based on a page-based cache.  Our cache is
+    # object based, so, for example, it's hard to compute the number
+    # of oids to store in a1out based on the size of a1in.
+
+    extraname = "evicts"
+
+    def __init__(self, cachelimit, outlen=100000):
+        Simulation.__init__(self, cachelimit)
+        self.total_evicts = 0
+        self.a1out_limit = outlen
+
+    def makespace(self, size):
+        for space in 0, size:
+            if self.enoughspace(size):
+                return
+            self.evict_a1in(space)
+            if self.enoughspace(size):
+                return
+            self.evict_am(space)
+
+    def enoughspace(self, size):
+        totalsize = self.a1in_size + self.am_size
+        return totalsize + size < self.cachelimit
+
+    def evict_a1in(self, extra):
+        while self.a1in_size + extra > self.a1in_limit:
+            if self.a1in.next is self.a1in:
+                return
+            assert self.a1in.next is not None
+            node = self.a1in.next
+            self.evicts += 1
+            self.total_evicts += 1
+            node.linkbefore(self.a1out)
+            self.a1out_size += 1
+            self.a1in_size -= node.size
+            if self.a1out_size > self.a1out_limit:
+                assert self.a1out.next is not None
+                node = self.a1out.next
+                node.unlink()
+                self.a1out_size -= 1
+
+    def evict_am(self, extra):
+        while self.am_size + extra > self.am_limit:
+            if self.am.next is self.am:
+                return
+            assert self.am.next is not None
+            node = self.am.next
+            self.evicts += 1
+            self.total_evicts += 1
+            # This node hasn't been accessed in a while, so just
+            # forget about it.
+            node.unlink()
+            self.am_size -= node.size
+
+    def write(self, oid, size):
+        # A write always follows a read (ZODB doesn't allow blind writes).
+        # So this write must have followed a recent read of the object.
+        # Don't change it's position, but do update the size.
+
+        # XXX For now, don't evict pages if the new version of the object
+        # is big enough to require eviction.
+        node = self.cache.get(oid)
+        if node is None or node.kind is a1out:
+            return
+        if node.kind is am:
+            self.am_size = self.am_size - node.size + size
+            node.size = size
+            if self.am_size > self.am_limit:
+                print "write exceeded limit", self.am_size - self.am_limit
+        else:
+            self.a1in_size = self.a1in_size - node.size + size
+            node.size = size
+            if self.a1in_size > self.a1in_limit:
+                print "write exceeded limit", self.a1in_size - self.a1in_limit
+
+    def load(self, oid, size):
+        node = self.cache.get(oid)
+        if node is not None:
+            if node.kind is am:
+                self.hits += 1
+                self.total_hits += 1
+                node.linkbefore(self.am)
+            elif node.kind is a1in:
+                self.hits += 1
+                self.total_hits += 1
+            elif node.kind is a1out:
+                self.makespace(node.size)
+                node.linkbefore(self.am)
+        else:
+            # New objects enter the cache via a1in.  If they
+            # are frequently used over a long enough time, they
+            # will be promoted to am.
+            self.makespace(size)
+            node = Node2Q(oid, size, a1in)
+            node.linkbefore(self.a1in)
+            self.cache[oid] = node
+
+    def inval(self, oid):
+        # The original 2Q algorithm didn't have to deal with
+        # invalidations.  My own solution: Move it to the head
+        # of a1out.
+        node = self.cache.get(oid)
+        if node is None:
+            return
+        self.invals += 1
+        self.total_invals += 1
+        # XXX Should an invalidation to a1out count?
+        if node.kind is a1out:
+            return
+        node.linkbefore(self.a1out)
+        if node.kind is am:
+            self.am_size -= node.size
+        else:
+            self.a1in_size -= node.size
+
+    def restart(self):
+        Simulation.restart(self)
+
+        self.evicts = 0
+
+        self.cache = {}
+        self.am_limit = 3 * self.cachelimit / 4
+        self.a1in_limit = self.cachelimit / 4
+        self.am_size = 0
+        self.a1in_size = 0
+        self.a1out_size = 0
+
+        # An LRU queue of hot objects
+        self.am = Node2Q(None, None, am)
+        self.am.linkbefore(self.am)
+        # A FIFO queue of recently referenced objects.  It's purpose
+        # is to absorb references to objects that are accessed a few
+        # times in short order, then forgotten about.
+        self.a1in = Node2Q(None, None, a1in)
+        self.a1in.linkbefore(self.a1in)
+        # A FIFO queue of recently reference oids.
+        # This queue only stores the oids, not any data.  If we get a
+        # hit in this queue, promote the object to am.
+        self.a1out = Node2Q(None, None, a1out)
+        self.a1out.linkbefore(self.a1out)
+
+class Node2Q(Node):
+
+    __slots__ = ["kind"]
+
+    def __init__(self, oid, size, kind):
+        Node.__init__(self, oid, size)
+        self.kind = kind
+
+    def linkbefore(self, next):
+        if next.kind != self.kind:
+            self.kind = next.kind
+        Node.linkbefore(self, next)
 
 class BuddyCacheSimulation(LRUCacheSimulation):