← Back to branch summary

~ubuntu-branches/ubuntu/quantal/ehcache/quantal

« back to all changes in this revision

Viewing changes to src/main/java/net/sf/ehcache/pool/impl/AbstractBalancedAccessEvictor.java

  • Committer: Package Import Robot
  • Author(s): Miguel Landaeta
  • Date: 2012-03-01 19:15:46 UTC
  • mfrom: (1.1.6) (2.1.7 sid)
  • Revision ID: package-import@ubuntu.com-20120301191546-rvlk8tomip0c2m9p
Tags: 2.5.0-1
http://bugs.debian.org/661450
* Team upload.
* New upstream release. (Closes: #661450).
* Bump Standards-Version to 3.9.3. No changes were required.
* Fix lintian warning with copyright file.
* Remove unnecessary dependencies on JRE for libehcache-java.
* Wrap list of dependencies and uploaders.
* Fix clean target by adding a mh_clean call, to allow twice in a row builds.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/main/java/net/sf/ehcache/pool/impl/AbstractBalancedAccessEvictor.java
 
1
/**
 
2
 *  Copyright 2003-2010 Terracotta, Inc.
 
3
 *
 
4
 *  Licensed under the Apache License, Version 2.0 (the "License");
 
5
 *  you may not use this file except in compliance with the License.
 
6
 *  You may obtain a copy of the License at
 
7
 *
 
8
 *      http://www.apache.org/licenses/LICENSE-2.0
 
9
 *
 
10
 *  Unless required by applicable law or agreed to in writing, software
 
11
 *  distributed under the License is distributed on an "AS IS" BASIS,
 
12
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
13
 *  See the License for the specific language governing permissions and
 
14
 *  limitations under the License.
 
15
 */
 
16
 
 
17
package net.sf.ehcache.pool.impl;
 
18
 
 
19
import java.util.ArrayList;
 
20
import java.util.Collection;
 
21
import java.util.Collections;
 
22
import java.util.Comparator;
 
23
import java.util.IdentityHashMap;
 
24
import java.util.List;
 
25
import java.util.Map;
 
26
 
 
27
import net.sf.ehcache.pool.PoolEvictor;
 
28
 
 
29
/**
 
30
 * Abstract implementation of a global 'cache value' maximizing pool eviction algorithm.
 
31
 * <p>
 
32
 *
 
33
 * @author Chris Dennis
 
34
 *
 
35
 * @param <T> type of store handled by this evictor
 
36
 */
 
37
public abstract class AbstractBalancedAccessEvictor<T> implements PoolEvictor<T> {
 
38
 
 
39
    private static final double ALPHA = 1.0;
 
40
    private static final int SAMPLE_SIZE = 5;
 
41
 
 
42
    /**
 
43
     * Comparator used to rank the stores in order of eviction 'cost'.
 
44
     */
 
45
    private final class EvictionCostComparator implements Comparator<T> {
 
46
 
 
47
        private final long unloadedSize;
 
48
        private final Map<T, Float> evictionCostCache;
 
49
 
 
50
        public EvictionCostComparator(long unloadedSize, int collectionSize) {
 
51
            this.unloadedSize = unloadedSize;
 
52
            this.evictionCostCache = new IdentityHashMap<T, Float>(collectionSize);
 
53
        }
 
54
 
 
55
        public int compare(T s1, T s2) {
 
56
            Float f1 = evictionCostCache.get(s1);
 
57
            if (f1 == null) {
 
58
              f1 = evictionCost(s1, unloadedSize);
 
59
              evictionCostCache.put(s1, f1);
 
60
            }
 
61
            Float f2 = evictionCostCache.get(s2);
 
62
            if (f2 == null) {
 
63
              f2 = evictionCost(s2, unloadedSize);
 
64
              evictionCostCache.put(s2, f2);
 
65
            }
 
66
            return Float.compare(f1, f2);
 
67
        }
 
68
    }
 
69
 
 
70
    /**
 
71
     * Evict the specified number of bytes or the hinted number of elements from the specified store
 
72
     *
 
73
     * @param store store to evict from
 
74
     * @param count number of elements to evict
 
75
     * @param bytes number of bytes to evict
 
76
     * @return {@code true} if the eviction succeeded
 
77
     */
 
78
    protected abstract boolean evict(T store, int count, long bytes);
 
79
 
 
80
    /**
 
81
     * Return the hit rate for the supplied store.
 
82
     *
 
83
     * @param store store to query
 
84
     * @return hit rate
 
85
     */
 
86
    protected abstract float hitRate(T store);
 
87
 
 
88
    /**
 
89
     * Return the miss rate for the supplied store.
 
90
     *
 
91
     * @param store store to query
 
92
     * @return miss rate
 
93
     */
 
94
    protected abstract float missRate(T store);
 
95
 
 
96
    /**
 
97
     * Return the number of mappings in the supplied store.
 
98
     *
 
99
     * @param store store to size
 
100
     * @return mapping count
 
101
     */
 
102
    protected abstract long countSize(T store);
 
103
 
 
104
    /**
 
105
     * Return the size in bytes of the supplied store.
 
106
     *
 
107
     * @param store store to size
 
108
     * @return size in bytes
 
109
     */
 
110
    protected abstract long byteSize(T store);
 
111
 
 
112
    /**
 
113
     * {@inheritDoc}
 
114
     */
 
115
    public boolean freeSpace(Collection<T> from, long bytes) {
 
116
        if (from == null || from.isEmpty()) {
 
117
            return false;
 
118
        }
 
119
        List<T> random = new ArrayList<T>(from);
 
120
        Collections.shuffle(random);
 
121
 
 
122
        for (int i = 0; i < random.size(); i += SAMPLE_SIZE) {
 
123
            List<T> sorted = random.subList(i, Math.min(SAMPLE_SIZE + i, random.size()));
 
124
            Collections.sort(sorted, new EvictionCostComparator(getDesiredUnloadedSize(sorted), sorted.size() + 1));
 
125
 
 
126
            for (T store : sorted) {
 
127
                int count;
 
128
                long byteSize = byteSize(store);
 
129
                long countSize = countSize(store);
 
130
                if (countSize == 0 || byteSize == 0) {
 
131
                    count = 1;
 
132
                } else {
 
133
                    count = (int) Math.max((bytes * countSize) / byteSize, 1L);
 
134
                }
 
135
                if (evict(store, count, bytes)) {
 
136
                    return true;
 
137
                }
 
138
            }
 
139
        }
 
140
 
 
141
        return false;
 
142
    }
 
143
 
 
144
    private float evictionCost(T store, long unloadedSize) {
 
145
        /*
 
146
         * The code below is a simplified version of this:
 
147
         *
 
148
         * float meanEntrySize = byteSize / countSize;
 
149
         * float accessRate = hitRate + missRate;
 
150
         * float fillLevel = hitRate / accessRate;
 
151
         * float deltaFillLevel = fillLevel / byteSize;
 
152
         *
 
153
         * return meanEntrySize * accessRate * deltaFillLevel * hitDistributionFunction(fillLevel);
 
154
         */
 
155
 
 
156
        float hitRate = hitRate(store);
 
157
        float missRate = missRate(store);
 
158
        long countSize = countSize(store);
 
159
        float accessRate = hitRate + missRate;
 
160
 
 
161
        if (accessRate == 0.0f) {
 
162
            if (byteSize(store) > unloadedSize) {
 
163
                return Float.NEGATIVE_INFINITY;
 
164
            } else {
 
165
                return Float.POSITIVE_INFINITY;
 
166
            }
 
167
        } else if (hitRate == 0.0f) {
 
168
            return Float.POSITIVE_INFINITY;
 
169
        } else {
 
170
            float cost = (hitRate / countSize) * hitDistributionFunction(hitRate / accessRate);
 
171
            if (Float.isNaN(cost)) {
 
172
                throw new AssertionError(String.format("NaN Eviction Cost [hit:%f miss:%f size:%d]", hitRate, missRate, countSize));
 
173
            } else {
 
174
                return cost;
 
175
            }
 
176
        }
 
177
    }
 
178
 
 
179
    private static float hitDistributionFunction(float fillLevel) {
 
180
        return (float) Math.pow(fillLevel, -ALPHA);
 
181
    }
 
182
 
 
183
    private long getDesiredUnloadedSize(Collection<T> from) {
 
184
        long unloadedSize = 0L;
 
185
        for (T s : from) {
 
186
            unloadedSize += byteSize(s);
 
187
        }
 
188
        return unloadedSize / from.size();
 
189
    }
 
190
}