FileSelector


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: FileSelector.java,v 1.15 2006/10/30 21:14:13 bostic Exp $
7    */
8   
9   package com.sleepycat.je.cleaner;
10  
11  import java.util.Collections  ;
12  import java.util.HashMap  ;
13  import java.util.HashSet  ;
14  import java.util.LinkedList  ;
15  import java.util.List  ;
16  import java.util.Map  ;
17  import java.util.Set  ;
18  import java.util.SortedSet  ;
19  import java.util.TreeSet  ;
20  
21  import com.sleepycat.je.DatabaseException;
22  import com.sleepycat.je.dbi.DatabaseId;
23  import com.sleepycat.je.tree.LN;
24  
25  /**
26   * Keeps track of the status of files for which cleaning is in progres.
27   */
28  public class FileSelector {
29  
30      /*
31       * Each file for which cleaning is in progress is in one of the following
32       * collections.  Files numbers migrate from one collection to another as
33       * their status changes, in order:
34       *
35       * toBeCleaned -> beingCleaned -> cleaned ->
36       * checkpointed -> fullyProcessed -> safeToDelete
37       *
38       * Access to these collections is synchronized to guarantee that the status
39       * is atomically updated.
40       */
41  
42      /*
43       * A file is initially to-be-cleaned when it is selected as part of a batch
44       * of files that, when deleted, will bring total utilization down to the
45       * minimum configured value.  All files in this collection will be cleaned
46       * in lowest-cost-to-clean order.  For two files of equal cost to clean,
47       * the lower numbered (oldest) files is selected; this is why the set is
48       * sorted.
49       */
50      private SortedSet   toBeCleanedFiles;
51  
52      /*
53       * When a file is selected for processing by FileProcessor from the
54       * to-be-cleaned list, it is added to this processing set.  This
55       * distinction is used to prevent a file from being processed by more than
56       * one thread.
57       */
58      private Set   beingCleanedFiles;
59  
60      /*
61       * A file moves to the cleaned set when all log entries have been read and
62       * processed.  However, entries needing migration will be marked with the
63       * BIN entry MIGRATE flag, entries that could not be locked will be in the
64       * pending LN set, and the DBs that were pending deletion will be in the
65       * pending DB set.
66       *
67       * After processing a file, we may identify a set of deferred write dbs
68       * which need a sync before we can safely delete the file. The
69       * cleanedDeferredWriteDbs is the collecton of DatabaseIds for those dw
70       * dbs, and goes lockstep with the cleanedFiles. It's implemented as a
71       * list rather than a set, because a DW db may show up multiple times
72       * for different files, unlike the files in the cleanedFiles set.
73       * For example, suppose 
74       *  - file 20 is cleaned and adds DW dbs 1,3
75       *  - file 25 is cleaned and adds DW dbs 1,5
76       *  - a checkpoint starts, and copies dw db 1,3,5
77       *  - file 30 is cleaned, and adds DW dbs 1,5
78       * When the ckpt returns and removes the proper entries from the list, 
79       * it must make sure that dbs 1,5 stay on the list, because that sync 
80       * must happen for file 30.
81       */
82      private Set   cleanedFiles;
83      private LinkedList   cleanedDeferredWriteDbs;
84  
85      /*
86       * A file moves to the checkpointed set at the end of a checkpoint if it
87       * was in the cleaned set at the beginning of the checkpoint.  Because all
88       * dirty BINs are flushed during the checkpoints, no files in this set
89       * will have entries with the MIGRATE flag set.  However, some entries may
90       * be in the pending LN set and some DBs may be in the pending DB set.
91       */
92      private Set   checkpointedFiles;
93  
94      /*
95       * A file is moved from the checkpointed set to the fully-processed set
96       * when the pending LN/DB sets become empty.  Since a pending LN was not
97       * locked successfully, we don't know its original file.  But we do know
98       * that when no pending LNs are present for any file, all log entries in
99       * checkpointed files are either obsolete or have been migrated.  Note,
100      * however, that the parent BINs of the migrated entries may not have been
101      * logged yet.
102      * 
103      * No special handling is required to coordinate syncing of deferred write
104      * databases for pending, deferred write LNs. Note that although DW
105      * databases are non-txnal, their LNs may be pended because of lock
106      * collisions.  Any required syncing falls out naturally because dbs are
107      * entered into the cleanedDeferredWriteDbs list when a member LN is
108      * successfully processed and removed from the pendingLN set, whether that
109      * happens on the first pass of processing the file, or on future passes
110      * when the LN is removed from the pending set.
111      */
112     private Set   fullyProcessedFiles;
113 
114     /*
115      * A file moves to the safe-to-delete set at the end of a checkpoint if it
116      * was in the fully-processed set at the beginning of the checkpoint.  All
117      * parent BINs of migrated entries have now been logged, and any
118      * deferred write db syncs have been executed and the files are
119      * safe to delete.
120      */
121     private Set   safeToDeleteFiles;
122 
123     /*
124      * Pending LNs are stored in a map of {NodeID -> LNInfo}.  These are LNs
125      * that could not be locked, either during processing or during migration.
126      */
127     private Map   pendingLNs;
128 
129     /*
130      * For processed entries with DBs that are pending deletion, we consider
131      * them to be obsolete but we store their DatabaseIds in a set.  Until the
132      * DB deletion is complete, we can't delete the log files containing those
133      * entries.
134      */
135     private Set   pendingDBs;
136 
137     /*
138      * If during a checkpoint there are no pending LNs or DBs added, we can
139      * move cleaned files to safe-delete files at the end of the checkpoint.
140      * This is an optimization that allows deleting files more quickly when
141      * possible. In particular this impacts the checkpoint during environment
142      * close, since no user operations are active during that checkpoint; this
143      * optimization allows us to delete all cleaned files after the final
144      * checkpoint.
145      */
146     private boolean anyPendingDuringCheckpoint;
147 
148     /*
149      * As a side effect of file selection a set of low utilization files is
150      * determined.  This set is guaranteed to be non-null and read-only, so no
151      * synchronization is needed when accessing it.
152      */
153     private Set   lowUtilizationFiles;
154 
155     FileSelector() {
156         toBeCleanedFiles = new TreeSet  ();
157         cleanedFiles = new HashSet  ();
158         cleanedDeferredWriteDbs = new LinkedList  ();
159         checkpointedFiles = new HashSet  ();
160         fullyProcessedFiles = new HashSet  ();
161         safeToDeleteFiles = new HashSet  ();
162         pendingLNs = new HashMap  ();
163         pendingDBs = new HashSet  ();
164         lowUtilizationFiles = Collections.EMPTY_SET;
165         beingCleanedFiles = new HashSet  ();
166     }
167 
168     /**
169      * Returns the best file that qualifies for cleaning, or null if no file
170      * qualifies.  This method is not thread safe and should only be called
171      * from the cleaner thread.
172      *
173      * @param forceCleaning is true to always select a file, even if its
174      * utilization is above the minimum utilization threshold.
175      *
176      * @param calcLowUtilizationFiles whether to recalculate the set of files
177      * that are below the minimum utilization threshold.
178      *
179      * @param maxBatchFiles is the maximum number of files to be selected at
180      * one time, or zero if there is no limit.
181      *
182      * @return the next file to be cleaned, or null if no file needs cleaning.
183      */
184     Long   selectFileForCleaning(UtilizationProfile profile,
185                                boolean forceCleaning,
186                                boolean calcLowUtilizationFiles,
187                                int maxBatchFiles)
188         throws DatabaseException {
189 
190         Set   newLowUtilizationFiles = calcLowUtilizationFiles ?
191             (new HashSet  ()) : null;
192 
193         /*
194          * Add files until we reach the theoretical minimum utilization
195          * threshold.
196          */
197         while (true) {
198 
199             if (maxBatchFiles > 0) {
200                 synchronized (this) {
201                     if (toBeCleanedFiles.size() >= maxBatchFiles) {
202                         break;
203                     }
204                 }
205             }
206 
207             Long   fileNum = profile.getBestFileForCleaning
208                 (this, forceCleaning, newLowUtilizationFiles);
209 
210             if (fileNum == null) {
211                 break;
212             }
213 
214             synchronized (this) {
215                 toBeCleanedFiles.add(fileNum);
216             }
217         }
218 
219         /* Update the read-only set. */
220         if (newLowUtilizationFiles != null) {
221             lowUtilizationFiles = newLowUtilizationFiles;
222         }
223 
224         /*
225          * Select the cheapest file to clean from a copy of the to-be-cleaned
226          * set.  Then move the file from the to-be-cleaned set to the
227          * being-cleaned set.
228          */
229         SortedSet   availableFiles;
230         synchronized (this) {
231             availableFiles = new TreeSet  (toBeCleanedFiles);
232         }
233         Long   file = profile.getCheapestFileToClean(availableFiles);
234         if (file != null) {
235             synchronized (this) {
236                 toBeCleanedFiles.remove(file);
237                 beingCleanedFiles.add(file);
238             }
239         }
240         return file;
241     }
242 
243     /**
244      * Returns whether the file is in any stage of the cleaning process.
245      */
246     synchronized boolean isFileCleaningInProgress(Long   file) {
247         return toBeCleanedFiles.contains(file) ||
248             beingCleanedFiles.contains(file) ||
249             cleanedFiles.contains(file) ||
250             checkpointedFiles.contains(file) ||
251             fullyProcessedFiles.contains(file) ||
252             safeToDeleteFiles.contains(file);
253     }
254 
255     /**
256      * When file cleaning is aborted, move the file back from the being-cleaned
257      * set to the to-be-cleaned set.
258      */
259     synchronized void putBackFileForCleaning(Long   fileNum) {
260         toBeCleanedFiles.add(fileNum);
261         beingCleanedFiles.remove(fileNum);
262     }
263 
264     /**
265      * When cleaning is complete, move the file from the being-cleaned set to
266      * the cleaned set.
267      */
268     synchronized void addCleanedFile(Long   fileNum, Set   deferredWriteDbs) {
269         cleanedFiles.add(fileNum);
270         cleanedDeferredWriteDbs.addAll(deferredWriteDbs);
271         beingCleanedFiles.remove(fileNum);
272     }
273 
274     /**
275      * Returns a read-only set of low utilization files that can be accessed
276      * without synchronization.
277      */
278     Set   getLowUtilizationFiles() {
279         /* This set is read-only, so there is no need to make a copy. */
280         return lowUtilizationFiles;
281     }
282 
283     /**
284      * Returns a read-only copy of to-be-cleaned and being-cleaned files that
285      * can be accessed without synchronization.
286      */
287     synchronized Set   getMustBeCleanedFiles() {
288         Set   set = new HashSet  (toBeCleanedFiles);
289         set.addAll(beingCleanedFiles);
290         return set;
291     }
292 
293     /**
294      * Returns the number of files waiting to-be-cleaned.
295      */
296     synchronized int getBacklog() {
297         return toBeCleanedFiles.size();
298     }
299 
300     /**
301      * Returns a copy of the cleaned and fully-processed files at the time a
302      * checkpoint starts.
303      */
304     synchronized CheckpointStartCleanerState getFilesAtCheckpointStart() {
305 
306         anyPendingDuringCheckpoint = !pendingLNs.isEmpty() ||
307             !pendingDBs.isEmpty();
308 
309         CheckpointStartCleanerState info = 
310             new CheckpointStartCleanerState(cleanedFiles,
311                                             fullyProcessedFiles,
312                                             cleanedDeferredWriteDbs);
313         return info;
314     }
315 
316     /**
317      * When a checkpoint is complete, move the previously cleaned and
318      * fully-processed files to the checkpointed and safe-to-delete sets.
319      * Also take the dbs that have been synced through this checkpoint off
320      * their place at the top of the deferredWriteDb list
321      */
322     synchronized void updateFilesAtCheckpointEnd(
323                      CheckpointStartCleanerState info) {
324 
325         if (!info.isEmpty()) {
326 
327             Set   previouslyCleanedFiles = info.getCleanedFiles();
328             if (previouslyCleanedFiles != null) {
329                 if (anyPendingDuringCheckpoint) {
330                     checkpointedFiles.addAll(previouslyCleanedFiles);
331                 } else {
332                     safeToDeleteFiles.addAll(previouslyCleanedFiles);
333                 }
334                 cleanedFiles.removeAll(previouslyCleanedFiles);
335             }
336 
337             Set   previouslyProcessedFiles =
338                 info.getFullyProcessedFiles();
339             if (previouslyProcessedFiles != null) {
340                 safeToDeleteFiles.addAll(previouslyProcessedFiles);
341                 fullyProcessedFiles.removeAll(previouslyProcessedFiles);
342             }
343 
344             int previousSize = cleanedDeferredWriteDbs.size();
345             int numDbsSyncedByCheckpoint =
346                 info.getDeferredWriteDbsSize();
347             for (int i = 0; i < numDbsSyncedByCheckpoint; i++) {
348                 cleanedDeferredWriteDbs.removeFirst();
349             }
350 
351             assert cleanedDeferredWriteDbs.size() ==
352                 previousSize - numDbsSyncedByCheckpoint;
353 
354             updateProcessedFiles();
355         }
356     }
357 
358     /**
359      * Adds the given LN info to the pending LN set.
360      */
361     synchronized boolean addPendingLN(LN ln, DatabaseId dbId,
362                                       byte[] key, byte[] dupKey) {
363         assert ln != null;
364 
365         boolean added = pendingLNs.put
366             (new Long  (ln.getNodeId()),
367              new LNInfo(ln, dbId, key, dupKey)) != null;
368 
369         anyPendingDuringCheckpoint = true;
370         return added;
371     }
372 
373     /**
374      * Returns an array of LNInfo for LNs that could not be migrated in a
375      * prior cleaning attempt, or null if no LNs are pending.
376      */
377     synchronized LNInfo[] getPendingLNs() {
378 
379         if (pendingLNs.size() > 0) {
380             LNInfo[] lns = new LNInfo[pendingLNs.size()];
381             pendingLNs.values().toArray(lns);
382             return lns;
383         } else {
384             return null;
385         }
386     }
387 
388     /**
389      * Removes the LN for the given node ID from the pending LN set.
390      */
391     synchronized void removePendingLN(long nodeId) {
392 
393         pendingLNs.remove(new Long  (nodeId));
394         updateProcessedFiles();
395     }
396 
397     /**
398      * Adds the given DatabaseId to the pending DB set.
399      */
400     synchronized boolean addPendingDB(DatabaseId dbId) {
401 
402         boolean added = pendingDBs.add(dbId);
403 
404         anyPendingDuringCheckpoint = true;
405         return added;
406     }
407 
408     /**
409      * Returns an array of DatabaseIds for DBs that were pending deletion in a
410      * prior cleaning attempt, or null if no DBs are pending.
411      */
412     synchronized DatabaseId[] getPendingDBs() {
413 
414         if (pendingDBs.size() > 0) {
415             DatabaseId[] dbs = new DatabaseId[pendingDBs.size()];
416             pendingDBs.toArray(dbs);
417             return dbs;
418         } else {
419             return null;
420         }
421     }
422 
423     /**
424      * Removes the DatabaseId from the pending DB set.
425      */
426     synchronized void removePendingDB(DatabaseId dbId) {
427 
428         pendingDBs.remove(dbId);
429         updateProcessedFiles();
430     }
431 
432     /**
433      * Returns a copy of the safe-to-delete files.
434      */
435     synchronized Set   copySafeToDeleteFiles() {
436         if (safeToDeleteFiles.size() == 0) {
437             return null;
438         } else {
439             return new HashSet  (safeToDeleteFiles);
440         }
441     }
442 
443     /**
444      * Removes file from the safe-to-delete set after the file itself has
445      * finally been deleted.
446      */
447     synchronized void removeDeletedFile(Long   fileNum) {
448         safeToDeleteFiles.remove(fileNum);
449     }
450 
451     /**
452      * If there are no pending LNs or DBs outstanding, move the checkpointed
453      * files to the fully-processed set.  The check for pending LNs/DBs and the
454      * copying of the checkpointed files must be done atomically in a
455      * synchronized block.  All methods that call this method are synchronized.
456      */
457     private void updateProcessedFiles() {
458         if (pendingLNs.isEmpty() && pendingDBs.isEmpty()) {
459             fullyProcessedFiles.addAll(checkpointedFiles);
460             checkpointedFiles.clear();
461         }
462     }
463 
464     /*
465      * Holds copy of all checkpoint-dependent cleaner state.
466      */
467     static public class CheckpointStartCleanerState {
468 
469         /* A snapshot of the cleaner collections at the checkpoint start. */
470         private Set   cleanedFiles;
471         private Set   fullyProcessedFiles;
472         private Set   deferredWriteDbs;
473         
474         CheckpointStartCleanerState(Set   cleanedFiles,
475                                     Set   fullyProcessedFiles,
476                                     List   cleanedDeferredWriteDbs) {
477 
478             /* 
479              * Create snapshots of the collections of various files at the
480              * beginning of the checkpoint.
481              */
482             this.cleanedFiles = new HashSet  (cleanedFiles);
483             this.fullyProcessedFiles = new HashSet  (fullyProcessedFiles);
484             deferredWriteDbs = new HashSet  (cleanedDeferredWriteDbs);
485         }
486 
487         public boolean isEmpty() {
488             return ((cleanedFiles.size() == 0) &&
489                     (fullyProcessedFiles.size() == 0) &&
490                     (deferredWriteDbs.size() == 0));
491         }
492 
493         public Set   getCleanedFiles() {
494             return cleanedFiles;
495         }
496 
497         public Set   getFullyProcessedFiles() {
498             return fullyProcessedFiles;
499         }
500                 
501         public Set   getDeferredWriteDbs() {
502             return deferredWriteDbs;
503         }
504                                   
505         public int getDeferredWriteDbsSize() {
506             return deferredWriteDbs.size();
507         }
508     }
509 }
510
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags