Issue 4807 - CLOCK-Pro cache replacement
Summary: CLOCK-Pro cache replacement
Status: VERIFIED FIXED
Alias: None
Product: OpenLDAP
Classification: Unclassified
Component: slapd (show other issues)
Version: unspecified
Hardware: All All
: --- normal
Target Milestone: ---
Assignee: OpenLDAP project
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2007-01-17 02:10 UTC by Howard Chu
Modified: 2014-08-01 21:04 UTC (History)
0 users

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description Howard Chu 2007-01-17 02:10:43 UTC
Full_Name: Howard Chu
Version: HEAD
OS: 
URL: ftp://ftp.openldap.org/incoming/hyc-20070116.txt
Submission from: (NULL) (76.168.84.21)
Submitted by: hyc


This is a rough implementation of the CLOCK-Pro cache replacement algorithm for
back-bdb. It's based on the paper published here

http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs05-3.html

Currently the performance is not very good; the algorithm can invoke multiple
scans of the Clock list and our lock overhead for those scans is too high. I'm
not planning to do any more with this at the moment, just wanted to post it so
it doesn't get lost, in case someone else is interested. I didn't want to commit
it behind #ifdef's because that would get too messy.

This implementation deviates from the paper in two major respects:
1) it's possible for an EntryInfo node to get its Reference bit set even when
the entry is not Resident. This happens very frequently, in cache_find_ndn. As
such, EntryInfo nodes without an Entry, but that have been Referenced, do not
get flushed by HANDtest.

2) Nodes can get their Reference bit cleared at many points during the Clock-Pro
processing, so the bit is not a good indication of whether a node is currently
in use and may be safely freed. So, elaborate lock checks are used at each point
where the original algorithm would simply free a node (HANDcold, HANDtest).

It would be nice if our locking setup could be simplified. If someone else wants
to jump in and clean it up, it may be worth committing down the road.

Comment 1 Howard Chu 2007-01-17 02:11:09 UTC
moved from Incoming to Software Enhancements
Comment 2 Howard Chu 2007-11-21 15:29:19 UTC
changed notes
changed state Open to Closed
Comment 3 OpenLDAP project 2014-08-01 21:04:53 UTC
obsoleted by http://www.openldap.org/lists/openldap-commit/200711/msg00068.html