DataCellCache


1   /**
2    * com.mckoi.database.DataCellCache  21 Mar 1998
3    *
4    * Mckoi SQL Database ( http://www.mckoi.com/database )
5    * Copyright (C) 2000, 2001, 2002  Diehl and Associates, Inc.
6    *
7    * This program is free software; you can redistribute it and/or
8    * modify it under the terms of the GNU General Public License
9    * Version 2 as published by the Free Software Foundation.
10   *
11   * This program is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   * GNU General Public License Version 2 for more details.
15   *
16   * You should have received a copy of the GNU General Public License
17   * Version 2 along with this program; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19   *
20   * Change Log:
21   * 
22   * 
23   */
24  
25  package com.mckoi.database;
26  
27  import com.mckoi.util.Cache;
28  import com.mckoi.debug.*;
29  import java.util.HashMap  ;
30  
31  /**
32   * This object represents a cache for accesses to the the data cells within
33   * a Table.  Whenever a column/row index to a cell is accessed, the cache is
34   * first checked.  If the cell is not in the cache then it may go ahead and
35   * read the cell from the file.
36   * <p>
37   * ISSUE: We may need to keep track of memory used.  Since a String may
38   * use up much memory, we may need a cap on the maximum size the cache can grow
39   * to.  For example, we wouldn't want to cache a large document.  This could
40   * be handled at a higher level?
41   *
42   * @author Tobias Downer
43   */
44  
45  final class DataCellCache {
46  
47    /**
48     * The TransactionSystem that this cache is from.
49     */
50    private final TransactionSystem system;
51  
52    /**
53     * The maximum size of a DataCell that is allowed to go in the cache.
54     */
55    private int MAX_CELL_SIZE;
56  
57    /**
58     * The master cache.
59     */
60    private final DCCache cache;
61  
62    /**
63     * The current size of the cache.
64     */
65    private long current_cache_size;
66  
67    /**
68     * The Constructors.
69     *
70     * @param max_cache_size the maximum size in bytes that the cache is allowed
71     *   to grow to (eg. 4000000).
72     * @param max_cell_size the maximum size of an object that can be stored in
73     *   the cache.
74     * @param hash_size the number of elements in the hash (should be a prime
75     *   number).
76     */
77    DataCellCache(TransactionSystem system,
78                  int max_cache_size, int max_cell_size, int hash_size) {
79      this.system = system;
80      MAX_CELL_SIZE = max_cell_size;
81  
82      cache = new DCCache(hash_size, max_cache_size);
83    }
84  
85    DataCellCache(TransactionSystem system,
86                  int max_cache_size, int max_cell_size) {
87      this(system,
88           max_cache_size, max_cell_size, 88547);  // Good prime number hash size
89    }
90  
91    /**
92     * Dynamically resizes the data cell cache so it can store more/less data.
93     * This is used to change cache dynamics at runtime.
94     */
95    public synchronized void alterCacheDynamics(
96                                        int max_cache_size, int max_cell_size) {
97      MAX_CELL_SIZE = max_cell_size;
98      cache.setCacheSize(max_cache_size);
99    }
100 
101   /**
102    * Inner class that creates an object that hashes nicely over the cache
103    * source.
104    */
105   private final static class DCCacheKey {
106     final int row;
107     final short column;
108     final int table_id;
109     DCCacheKey(final int table_id, final short column, final int row) {
110       this.table_id = table_id;
111       this.column = column;
112       this.row = row;
113     }
114     public boolean equals(Object   ob) {
115       DCCacheKey dest_key = (DCCacheKey) ob;
116       return row == dest_key.row &&
117              column == dest_key.column &&
118              table_id == dest_key.table_id;
119     }
120     public int hashCode() {
121       // Yicks - this one is the best by far!
122       return (((int) column + table_id + (row * 189977)) * 50021) << 4;
123     }
124   }
125 
126   /**
127    * Returns an approximation of the amount of memory taken by a TObject.
128    */
129   private static final int amountMemory(TObject cell) {
130     return 16 + cell.approximateMemoryUse();
131   }
132 
133   /**
134    * Puts a TObject on the cache for the given row/column of the table.
135    * Ignores any cells that are larger than the maximum size.
136    */
137   public synchronized void put(int table_key, int row, int column,
138                                TObject cell) {
139     int memory_use = amountMemory(cell);
140     if (memory_use <= MAX_CELL_SIZE) {
141       // Generate the key
142       DCCacheKey key = new DCCacheKey(table_key, (short) column, row);
143       // If there is an existing object here, remove it from the cache and
144       // update the current_cache_size.
145       TObject removed_cell = (TObject) cache.remove(key);
146       if (removed_cell != null) {
147         current_cache_size -= amountMemory(removed_cell);
148       }
149       // Put the new entry in the cache
150       cache.put(key, cell);
151       current_cache_size += memory_use;
152     }
153     else {
154       // If the object is larger than the minimum object size that can be
155       // cached, remove any existing entry (possibly smaller) from the cache.
156       remove(table_key, row, column);
157     }
158   }
159 
160   /**
161    * Gets a TObject from the cache.  If the row/column is not in the cache
162    * then it returns null.
163    */
164   public synchronized TObject get(int table_key, int row, int column) {
165     return (TObject) cache.get(new DCCacheKey(table_key, (short) column, row));
166   }
167 
168   /**
169    * Removes a TObject from the cache.  This is used when we need to notify
170    * the cache that an object has become outdated.  This should be used when
171    * the cell has been removed or changed.
172    * Returns the cell that was removed, or null if there was no cell at the
173    * given location.
174    */
175   public synchronized TObject remove(int table_key, int row, int column) {
176     TObject cell = (TObject) cache.remove(
177                                new DCCacheKey(table_key, (short) column, row));
178 
179     if (cell != null) {
180       current_cache_size -= amountMemory(cell);
181     }
182     return cell;
183   }
184 
185   /**
186    * Completely wipe the cache of all entries.
187    */
188   public synchronized void wipe() {
189     if (cache.nodeCount() == 0 && current_cache_size != 0) {
190       system.Debug().write(Lvl.ERROR, this,
191           "Assertion failed - if nodeCount = 0 then current_cache_size " +
192           "must also be 0.");
193     }
194     if (cache.nodeCount() != 0) {
195       cache.removeAll();
196       system.stats().increment("DataCellCache.total_cache_wipe");
197     }
198     current_cache_size = 0;
199   }
200 
201   /**
202    * Returns an estimation of the current cache size in bytes.
203    */
204   public synchronized long getCurrentCacheSize() {
205     return current_cache_size;
206   }
207 
208   /**
209    * Reduce the cache size by the given amount.
210    */
211   private void reduceCacheSize(long val) {
212     current_cache_size -= val;
213   }
214 
215   // ---------- Primes ----------
216 
217   /**
218    * Returns a prime number from PRIME_LIST that is the closest prime greater
219    * or equal to the given value.
220    */
221   static int closestPrime(int value) {
222     for (int i = 0; i < PRIME_LIST.length; ++i) {
223       if (PRIME_LIST[i] >= value) {
224         return PRIME_LIST[i];
225       }
226     }
227     // Return the last prime
228     return PRIME_LIST[PRIME_LIST.length - 1];
229   }
230 
231   /**
232    * A list of primes ordered from lowest to highest.
233    */
234   private final static int[] PRIME_LIST = new int[] {
235      3001, 4799, 13999, 15377, 21803, 24247, 35083, 40531, 43669, 44263, 47387,
236      50377, 57059, 57773, 59399, 59999, 75913, 96821, 140551, 149011, 175633,
237      176389, 183299, 205507, 209771, 223099, 240259, 258551, 263909, 270761,
238      274679, 286129, 290531, 296269, 298021, 300961, 306407, 327493, 338851,
239      351037, 365489, 366811, 376769, 385069, 410623, 430709, 433729, 434509,
240      441913, 458531, 464351, 470531, 475207, 479629, 501703, 510709, 516017,
241      522211, 528527, 536311, 539723, 557567, 593587, 596209, 597451, 608897,
242      611069, 642547, 670511, 677827, 679051, 688477, 696743, 717683, 745931,
243      757109, 760813, 763957, 766261, 781559, 785597, 788353, 804493, 813559,
244      836917, 854257, 859973, 883217, 884789, 891493, 902281, 910199, 915199,
245      930847, 939749, 940483, 958609, 963847, 974887, 983849, 984299, 996211,
246      999217, 1007519, 1013329, 1014287, 1032959, 1035829, 1043593, 1046459,
247      1076171, 1078109, 1081027, 1090303, 1095613, 1098847, 1114037, 1124429,
248      1125017, 1130191, 1159393, 1170311, 1180631, 1198609, 1200809, 1212943,
249      1213087, 1226581, 1232851, 1287109, 1289867, 1297123, 1304987, 1318661,
250      1331107, 1343161, 1345471, 1377793, 1385117, 1394681, 1410803, 1411987,
251      1445261, 1460497, 1463981, 1464391, 1481173, 1488943, 1491547, 1492807,
252      1528993, 1539961, 1545001, 1548247, 1549843, 1551001, 1553023, 1571417,
253      1579099, 1600259, 1606153, 1606541, 1639751, 1649587, 1657661, 1662653,
254      1667051, 1675273, 1678837, 1715537, 1718489, 1726343, 1746281, 1749107,
255      1775489, 1781881, 1800157, 1806859, 1809149, 1826753, 1834607, 1846561,
256      1849241, 1851991, 1855033, 1879931, 1891133, 1893737, 1899137, 1909513,
257      1916599, 1917749, 1918549, 1919347, 1925557, 1946489, 1961551, 1965389,
258      2011073, 2033077, 2039761, 2054047, 2060171, 2082503, 2084107, 2095099,
259      2096011, 2112193, 2125601, 2144977, 2150831, 2157401, 2170141, 2221829,
260      2233019, 2269027, 2270771, 2292449, 2299397, 2303867, 2309891, 2312407,
261      2344301, 2348573, 2377007, 2385113, 2386661, 2390051, 2395763, 2422999,
262      2448367, 2500529, 2508203, 2509841, 2513677, 2516197, 2518151, 2518177,
263      2542091, 2547469, 2549951, 2556991, 2563601, 2575543, 2597629, 2599577,
264      2612249, 2620003, 2626363, 2626781, 2636773, 2661557, 2674297, 2691571,
265      2718269, 2725691, 2729381, 2772199, 2774953, 2791363, 2792939, 2804293,
266      2843021, 2844911, 2851313, 2863519, 2880797, 2891821, 2897731, 2904887,
267      2910251, 2928943, 2958341, 2975389
268   };
269 
270   // ---------- Inner classes ----------
271 
272   /**
273    * This extends the 'Cache' class.
274    */
275   private final class DCCache extends Cache {
276 
277     /**
278      * The maximum size that the cache can grow to in bytes.
279      */
280     private int MAX_CACHE_SIZE;
281 
282     /**
283      * The Constructor.
284      */
285     public DCCache(int cache_hash_size, int max_cache_size) {
286       super(cache_hash_size, -1, 20);
287       this.MAX_CACHE_SIZE = max_cache_size;
288     }
289 
290     /**
291      * Used to dynamically alter the size of the cache.  May cause a cache
292      * clean if the size is over the limit.
293      */
294     public void setCacheSize(int cache_size) {
295       this.MAX_CACHE_SIZE = cache_size;
296       checkClean();
297     }
298 
299     // ----- Overwritten from Cache -----
300 
301     protected void checkClean() {
302 
303       if (getCurrentCacheSize() >= MAX_CACHE_SIZE) {
304 
305         // Update the current cache size (before we wiped).
306         system.stats().set((int) getCurrentCacheSize(),
307                              "DataCellCache.current_cache_size");
308         clean();
309 
310         // The number of times we've cleared away old data cell nodes.
311         system.stats().increment("DataCellCache.cache_clean");
312 
313       }
314     }
315 
316     protected boolean shouldWipeMoreNodes() {
317       return (getCurrentCacheSize() >= (int) ((MAX_CACHE_SIZE * 100L) / 115L));
318     }
319 
320     protected void notifyWipingNode(Object   ob) {
321       super.notifyWipingNode(ob);
322 
323       // Update our memory indicator accordingly.
324       TObject cell = (TObject) ob;
325       reduceCacheSize(amountMemory(cell));
326       
327     }
328 
329     protected void notifyGetWalks(long total_walks, long total_get_ops) {
330       int avg = (int) ((total_walks * 1000000L) / total_get_ops);
331       system.stats().set(avg, "DataCellCache.avg_hash_get_mul_1000000");
332       system.stats().set((int) getCurrentCacheSize(),
333                                       "DataCellCache.current_cache_size");
334       system.stats().set(nodeCount(), "DataCellCache.current_node_count");
335     }
336 
337   }
338 
339 }
340
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags