db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Db-derby Wiki] Update of "DerbyLruCacheManager" by GokulSoundararajan
Date Sat, 10 Jun 2006 17:26:27 GMT
Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Db-derby Wiki" for change notification.

The following page has been changed by GokulSoundararajan:
http://wiki.apache.org/db-derby/DerbyLruCacheManager

------------------------------------------------------------------------------
  
  In databases, caching plays an important role in performance. To obtain high performance,
we need to cache pages from disk in memory to reduce access time. The problem stated is that
the existing replacement algorithm performs poorly so we need to research new algorithms for
page replacement and implement it in Apache Derby. The benefit of a better algorithm is improved
performance.
  
- In this project, I first have to look at existing work to quantify the different replacement
algorithms used in databases. From these, I (with my mentor's help) need decide which one
suits well with the workloads people run on Apache Derby. After selecting the algorithm, I
will implement it in Derby. In addition, I will implement unit tests. Finally, I will perform
experiments showing the benefit of the new algorithm over the existing algorithm.
+ In this project, I first have to look at existing work to quantify the different replacement
algorithms used in databases. From these, I (with my mentor's help) need decide which one
suits well with the workloads people run on Apache Derby. After selecting the algorithm, I
will implement it in Derby. In addition, I will  implement unit tests. Finally, I will perform
experiments showing the benefit of the new algorithm over the existing algorithm.
  
  == Schedule ==
  
  == Design and Implementation Plan/Thoughts ==
  
+ === References ===
+ 
+  1. '''2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm''' -
Theodore Johnson and Dennis Shasha [http://citeseer.ist.psu.edu/rd/91247933%2C63909%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/5729/http:zSzzSzcs.nyu.eduzSzcszSzfacultyzSzshashazSzpaperszSzvldb94_3.pdf/q-a-low-overhead.pdf
Link]
+ 
+  1. '''CAR: Clock with Adaptive Replacement''' - Sorav Bansal and Dharmendra S. Modha  [http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf
Link]
+  1. '''The LRU-K Page Replacement Algorithm For Database Disk Buffering''' - Elizabeth J.
O'Neil, Patrick E. O'Neil, Gergard Weikum [http://citeseer.ist.psu.edu/rd/0%2C16869%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/1208/http:zSzzSzwww.cs.umb.eduzSz%7EponeilzSzlru-k.pdf/oneil93lruk.pdf
Link]
+  1. '''ARC: A Self-Tuning, Low Overhead Replacement Cache''' - Nimrod Megiddo and Dharmendra
S. Modha [http://www.almaden.ibm.com/StorageSystems/Advanced_Storage_Systems/ARC/arcfast.pdf
Link]
+ 
  == Status/Updates ==
+ 
+ === June 10, 2006 ===
+ 
+ Commenting on the original thread in Derby Dev Mailing List [http://thread.gmane.org/gmane.comp.apache.db.derby.devel/21263/focus=21263
Link]
+ 
+ Thanks to all who commented on my early results. I have added the results of a mixed workload
containing both Zipf and Scans. I followed the example provided in the 2Q paper in which they
tried out scans of different lengths. I used a 10000 item cache with 100000 item dataset and
ran a mixed workload of 0.8 Zipf with 33% scans of lengths (0, 10, 100, 1000, 10000). The
resulting graph is available as [http://www.eecg.toronto.edu/~gokul/soc/mixed-80zipf-10000items.png
PNG] and [http://www.eecg.toronto.edu/~gokul/soc/mixed-80zipf-10000items.png PDF]. The results
show that there is a significant benefit by using the CART algorithm. Earlier, I was leaning
towards using the 2Q algorithm but I found out that it has a significant synchronization penalty.
The Postgres community implemented the 2Q algorithm (in 8.0) when they found out that ARC
was patented by IBM. Since then, they have gone to Clock (in 8.1) mostly due to the contention
penalty in 2Q. Since CART is a cousin of Clock
 , it may have less overhead.
  
  === June 04, 2006 ===
  

Mime
View raw message