Return-Path: X-Original-To: apmail-hbase-commits-archive@www.apache.org Delivered-To: apmail-hbase-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 7A0B018451 for ; Sun, 25 Oct 2015 23:17:28 +0000 (UTC) Received: (qmail 51639 invoked by uid 500); 25 Oct 2015 23:17:28 -0000 Delivered-To: apmail-hbase-commits-archive@hbase.apache.org Received: (qmail 51603 invoked by uid 500); 25 Oct 2015 23:17:28 -0000 Mailing-List: contact commits-help@hbase.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@hbase.apache.org Delivered-To: mailing list commits@hbase.apache.org Received: (qmail 51590 invoked by uid 99); 25 Oct 2015 23:17:28 -0000 Received: from Unknown (HELO spamd2-us-west.apache.org) (209.188.14.142) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 25 Oct 2015 23:17:28 +0000 Received: from localhost (localhost [127.0.0.1]) by spamd2-us-west.apache.org (ASF Mail Server at spamd2-us-west.apache.org) with ESMTP id B26171A097A for ; Sun, 25 Oct 2015 23:17:27 +0000 (UTC) X-Virus-Scanned: Debian amavisd-new at spamd2-us-west.apache.org X-Spam-Flag: NO X-Spam-Score: 0.99 X-Spam-Level: X-Spam-Status: No, score=0.99 tagged_above=-999 required=6.31 tests=[KAM_LAZY_DOMAIN_SECURITY=1, T_RP_MATCHES_RCVD=-0.01] autolearn=disabled Received: from mx1-us-west.apache.org ([10.40.0.8]) by localhost (spamd2-us-west.apache.org [10.40.0.9]) (amavisd-new, port 10024) with ESMTP id 0Eq9_CvTEGV6 for ; Sun, 25 Oct 2015 23:17:13 +0000 (UTC) Received: from mailrelay1-us-west.apache.org (mailrelay1-us-west.apache.org [209.188.14.139]) by mx1-us-west.apache.org (ASF Mail Server at mx1-us-west.apache.org) with ESMTP id A4C5520562 for ; Sun, 25 Oct 2015 23:17:13 +0000 (UTC) Received: from svn01-us-west.apache.org (svn.apache.org [10.41.0.6]) by mailrelay1-us-west.apache.org (ASF Mail Server at mailrelay1-us-west.apache.org) with ESMTP id 0B6F0E08A5 for ; Sun, 25 Oct 2015 23:17:12 +0000 (UTC) Received: from svn01-us-west.apache.org (localhost [127.0.0.1]) by svn01-us-west.apache.org (ASF Mail Server at svn01-us-west.apache.org) with ESMTP id AF8FF3A1032 for ; Sun, 25 Oct 2015 23:17:12 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1710495 [3/12] - in /hbase/hbase.apache.org/trunk: ./ devapidocs/org/apache/hadoop/hbase/io/hfile/bucket/ devapidocs/org/apache/hadoop/hbase/tmpl/master/ devapidocs/org/apache/hadoop/hbase/tmpl/regionserver/ devapidocs/src-html/org/apache/... Date: Sun, 25 Oct 2015 23:17:10 -0000 To: commits@hbase.apache.org From: misty@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20151025231712.AF8FF3A1032@svn01-us-west.apache.org> Modified: hbase/hbase.apache.org/trunk/devapidocs/src-html/org/apache/hadoop/hbase/io/hfile/bucket/BucketAllocator.Bucket.html URL: http://svn.apache.org/viewvc/hbase/hbase.apache.org/trunk/devapidocs/src-html/org/apache/hadoop/hbase/io/hfile/bucket/BucketAllocator.Bucket.html?rev=1710495&r1=1710494&r2=1710495&view=diff ============================================================================== --- hbase/hbase.apache.org/trunk/devapidocs/src-html/org/apache/hadoop/hbase/io/hfile/bucket/BucketAllocator.Bucket.html (original) +++ hbase/hbase.apache.org/trunk/devapidocs/src-html/org/apache/hadoop/hbase/io/hfile/bucket/BucketAllocator.Bucket.html Sun Oct 25 23:17:08 2015 @@ -29,539 +29,541 @@ 021package org.apache.hadoop.hbase.io.hfile.bucket; 022 023import java.util.Arrays; -024import java.util.LinkedList; -025import java.util.List; -026import java.util.Map; -027import java.util.concurrent.atomic.AtomicLong; -028 -029import org.apache.commons.logging.Log; -030import org.apache.commons.logging.LogFactory; -031import org.apache.hadoop.hbase.classification.InterfaceAudience; -032import org.apache.hadoop.hbase.io.hfile.BlockCacheKey; -033import org.apache.hadoop.hbase.io.hfile.CacheConfig; -034import org.apache.hadoop.hbase.io.hfile.bucket.BucketCache.BucketEntry; -035import org.codehaus.jackson.annotate.JsonIgnoreProperties; -036 -037import com.google.common.base.Objects; -038import com.google.common.base.Preconditions; -039import com.google.common.primitives.Ints; -040 -041/** -042 * This class is used to allocate a block with specified size and free the block -043 * when evicting. It manages an array of buckets, each bucket is associated with -044 * a size and caches elements up to this size. For a completely empty bucket, this -045 * size could be re-specified dynamically. -046 * -047 * This class is not thread safe. -048 */ -049@InterfaceAudience.Private -050@JsonIgnoreProperties({"indexStatistics", "freeSize", "usedSize"}) -051public final class BucketAllocator { -052 private static final Log LOG = LogFactory.getLog(BucketAllocator.class); -053 -054 @JsonIgnoreProperties({"completelyFree", "uninstantiated"}) -055 public final static class Bucket { -056 private long baseOffset; -057 private int itemAllocationSize, sizeIndex; -058 private int itemCount; -059 private int freeList[]; -060 private int freeCount, usedCount; -061 -062 public Bucket(long offset) { -063 baseOffset = offset; -064 sizeIndex = -1; -065 } -066 -067 void reconfigure(int sizeIndex, int[] bucketSizes, long bucketCapacity) { -068 Preconditions.checkElementIndex(sizeIndex, bucketSizes.length); -069 this.sizeIndex = sizeIndex; -070 itemAllocationSize = bucketSizes[sizeIndex]; -071 itemCount = (int) (bucketCapacity / (long) itemAllocationSize); -072 freeCount = itemCount; -073 usedCount = 0; -074 freeList = new int[itemCount]; -075 for (int i = 0; i < freeCount; ++i) -076 freeList[i] = i; -077 } -078 -079 public boolean isUninstantiated() { -080 return sizeIndex == -1; -081 } -082 -083 public int sizeIndex() { -084 return sizeIndex; -085 } -086 -087 public int getItemAllocationSize() { -088 return itemAllocationSize; -089 } -090 -091 public boolean hasFreeSpace() { -092 return freeCount > 0; -093 } -094 -095 public boolean isCompletelyFree() { -096 return usedCount == 0; -097 } -098 -099 public int freeCount() { -100 return freeCount; -101 } -102 -103 public int usedCount() { -104 return usedCount; -105 } -106 -107 public int getFreeBytes() { -108 return freeCount * itemAllocationSize; -109 } -110 -111 public int getUsedBytes() { -112 return usedCount * itemAllocationSize; -113 } -114 -115 public long getBaseOffset() { -116 return baseOffset; -117 } -118 -119 /** -120 * Allocate a block in this bucket, return the offset representing the -121 * position in physical space -122 * @return the offset in the IOEngine -123 */ -124 public long allocate() { -125 assert freeCount > 0; // Else should not have been called -126 assert sizeIndex != -1; -127 ++usedCount; -128 long offset = baseOffset + (freeList[--freeCount] * itemAllocationSize); -129 assert offset >= 0; -130 return offset; -131 } -132 -133 public void addAllocation(long offset) throws BucketAllocatorException { -134 offset -= baseOffset; -135 if (offset < 0 || offset % itemAllocationSize != 0) -136 throw new BucketAllocatorException( -137 "Attempt to add allocation for bad offset: " + offset + " base=" -138 + baseOffset + ", bucket size=" + itemAllocationSize); -139 int idx = (int) (offset / itemAllocationSize); -140 boolean matchFound = false; -141 for (int i = 0; i < freeCount; ++i) { -142 if (matchFound) freeList[i - 1] = freeList[i]; -143 else if (freeList[i] == idx) matchFound = true; -144 } -145 if (!matchFound) -146 throw new BucketAllocatorException("Couldn't find match for index " -147 + idx + " in free list"); -148 ++usedCount; -149 --freeCount; -150 } -151 -152 private void free(long offset) { -153 offset -= baseOffset; -154 assert offset >= 0; -155 assert offset < itemCount * itemAllocationSize; -156 assert offset % itemAllocationSize == 0; -157 assert usedCount > 0; -158 assert freeCount < itemCount; // Else duplicate free -159 int item = (int) (offset / (long) itemAllocationSize); -160 assert !freeListContains(item); -161 --usedCount; -162 freeList[freeCount++] = item; -163 } -164 -165 private boolean freeListContains(int blockNo) { -166 for (int i = 0; i < freeCount; ++i) { -167 if (freeList[i] == blockNo) return true; -168 } -169 return false; -170 } -171 } -172 -173 final class BucketSizeInfo { -174 // Free bucket means it has space to allocate a block; -175 // Completely free bucket means it has no block. -176 private List<Bucket> bucketList, freeBuckets, completelyFreeBuckets; -177 private int sizeIndex; -178 -179 BucketSizeInfo(int sizeIndex) { -180 bucketList = new LinkedList<Bucket>(); -181 freeBuckets = new LinkedList<Bucket>(); -182 completelyFreeBuckets = new LinkedList<Bucket>(); -183 this.sizeIndex = sizeIndex; -184 } -185 -186 public synchronized void instantiateBucket(Bucket b) { -187 assert b.isUninstantiated() || b.isCompletelyFree(); -188 b.reconfigure(sizeIndex, bucketSizes, bucketCapacity); -189 bucketList.add(b); -190 freeBuckets.add(b); -191 completelyFreeBuckets.add(b); -192 } -193 -194 public int sizeIndex() { -195 return sizeIndex; -196 } -197 -198 /** -199 * Find a bucket to allocate a block -200 * @return the offset in the IOEngine -201 */ -202 public long allocateBlock() { -203 Bucket b = null; -204 if (freeBuckets.size() > 0) // Use up an existing one first... -205 b = freeBuckets.get(freeBuckets.size() - 1); -206 if (b == null) { -207 b = grabGlobalCompletelyFreeBucket(); -208 if (b != null) instantiateBucket(b); -209 } -210 if (b == null) return -1; -211 long result = b.allocate(); -212 blockAllocated(b); -213 return result; -214 } -215 -216 void blockAllocated(Bucket b) { -217 if (!b.isCompletelyFree()) completelyFreeBuckets.remove(b); -218 if (!b.hasFreeSpace()) freeBuckets.remove(b); -219 } -220 -221 public Bucket findAndRemoveCompletelyFreeBucket() { -222 Bucket b = null; -223 assert bucketList.size() > 0; -224 if (bucketList.size() == 1) { -225 // So we never get complete starvation of a bucket for a size -226 return null; -227 } -228 -229 if (completelyFreeBuckets.size() > 0) { -230 b = completelyFreeBuckets.get(0); -231 removeBucket(b); -232 } -233 return b; -234 } -235 -236 private synchronized void removeBucket(Bucket b) { -237 assert b.isCompletelyFree(); -238 bucketList.remove(b); -239 freeBuckets.remove(b); -240 completelyFreeBuckets.remove(b); -241 } -242 -243 public void freeBlock(Bucket b, long offset) { -244 assert bucketList.contains(b); -245 // else we shouldn't have anything to free... -246 assert (!completelyFreeBuckets.contains(b)); -247 b.free(offset); -248 if (!freeBuckets.contains(b)) freeBuckets.add(b); -249 if (b.isCompletelyFree()) completelyFreeBuckets.add(b); -250 } -251 -252 public synchronized IndexStatistics statistics() { -253 long free = 0, used = 0; -254 for (Bucket b : bucketList) { -255 free += b.freeCount(); -256 used += b.usedCount(); -257 } -258 return new IndexStatistics(free, used, bucketSizes[sizeIndex]); -259 } -260 -261 @Override -262 public String toString() { -263 return Objects.toStringHelper(this.getClass()) -264 .add("sizeIndex", sizeIndex) -265 .add("bucketSize", bucketSizes[sizeIndex]) -266 .toString(); -267 } -268 } -269 -270 // Default block size is 64K, so we choose more sizes near 64K, you'd better -271 // reset it according to your cluster's block size distribution -272 // TODO Support the view of block size distribution statistics -273 private static final int DEFAULT_BUCKET_SIZES[] = { 4 * 1024 + 1024, 8 * 1024 + 1024, -274 16 * 1024 + 1024, 32 * 1024 + 1024, 40 * 1024 + 1024, 48 * 1024 + 1024, -275 56 * 1024 + 1024, 64 * 1024 + 1024, 96 * 1024 + 1024, 128 * 1024 + 1024, -276 192 * 1024 + 1024, 256 * 1024 + 1024, 384 * 1024 + 1024, -277 512 * 1024 + 1024 }; -278 -279 /** -280 * Round up the given block size to bucket size, and get the corresponding -281 * BucketSizeInfo -282 */ -283 public BucketSizeInfo roundUpToBucketSizeInfo(int blockSize) { -284 for (int i = 0; i < bucketSizes.length; ++i) -285 if (blockSize <= bucketSizes[i]) -286 return bucketSizeInfos[i]; -287 return null; -288 } -289 -290 static public final int FEWEST_ITEMS_IN_BUCKET = 4; +024import java.util.Map; +025import java.util.concurrent.atomic.AtomicLong; +026 +027import org.apache.commons.collections.map.LinkedMap; +028import org.apache.commons.logging.Log; +029import org.apache.commons.logging.LogFactory; +030import org.apache.hadoop.hbase.classification.InterfaceAudience; +031import org.apache.hadoop.hbase.io.hfile.BlockCacheKey; +032import org.apache.hadoop.hbase.io.hfile.CacheConfig; +033import org.apache.hadoop.hbase.io.hfile.bucket.BucketCache.BucketEntry; +034import org.codehaus.jackson.annotate.JsonIgnoreProperties; +035 +036import com.google.common.base.Objects; +037import com.google.common.base.Preconditions; +038import com.google.common.primitives.Ints; +039 +040/** +041 * This class is used to allocate a block with specified size and free the block +042 * when evicting. It manages an array of buckets, each bucket is associated with +043 * a size and caches elements up to this size. For a completely empty bucket, this +044 * size could be re-specified dynamically. +045 * +046 * This class is not thread safe. +047 */ +048@InterfaceAudience.Private +049@JsonIgnoreProperties({"indexStatistics", "freeSize", "usedSize"}) +050public final class BucketAllocator { +051 private static final Log LOG = LogFactory.getLog(BucketAllocator.class); +052 +053 @JsonIgnoreProperties({"completelyFree", "uninstantiated"}) +054 public final static class Bucket { +055 private long baseOffset; +056 private int itemAllocationSize, sizeIndex; +057 private int itemCount; +058 private int freeList[]; +059 private int freeCount, usedCount; +060 +061 public Bucket(long offset) { +062 baseOffset = offset; +063 sizeIndex = -1; +064 } +065 +066 void reconfigure(int sizeIndex, int[] bucketSizes, long bucketCapacity) { +067 Preconditions.checkElementIndex(sizeIndex, bucketSizes.length); +068 this.sizeIndex = sizeIndex; +069 itemAllocationSize = bucketSizes[sizeIndex]; +070 itemCount = (int) (bucketCapacity / (long) itemAllocationSize); +071 freeCount = itemCount; +072 usedCount = 0; +073 freeList = new int[itemCount]; +074 for (int i = 0; i < freeCount; ++i) +075 freeList[i] = i; +076 } +077 +078 public boolean isUninstantiated() { +079 return sizeIndex == -1; +080 } +081 +082 public int sizeIndex() { +083 return sizeIndex; +084 } +085 +086 public int getItemAllocationSize() { +087 return itemAllocationSize; +088 } +089 +090 public boolean hasFreeSpace() { +091 return freeCount > 0; +092 } +093 +094 public boolean isCompletelyFree() { +095 return usedCount == 0; +096 } +097 +098 public int freeCount() { +099 return freeCount; +100 } +101 +102 public int usedCount() { +103 return usedCount; +104 } +105 +106 public int getFreeBytes() { +107 return freeCount * itemAllocationSize; +108 } +109 +110 public int getUsedBytes() { +111 return usedCount * itemAllocationSize; +112 } +113 +114 public long getBaseOffset() { +115 return baseOffset; +116 } +117 +118 /** +119 * Allocate a block in this bucket, return the offset representing the +120 * position in physical space +121 * @return the offset in the IOEngine +122 */ +123 public long allocate() { +124 assert freeCount > 0; // Else should not have been called +125 assert sizeIndex != -1; +126 ++usedCount; +127 long offset = baseOffset + (freeList[--freeCount] * itemAllocationSize); +128 assert offset >= 0; +129 return offset; +130 } +131 +132 public void addAllocation(long offset) throws BucketAllocatorException { +133 offset -= baseOffset; +134 if (offset < 0 || offset % itemAllocationSize != 0) +135 throw new BucketAllocatorException( +136 "Attempt to add allocation for bad offset: " + offset + " base=" +137 + baseOffset + ", bucket size=" + itemAllocationSize); +138 int idx = (int) (offset / itemAllocationSize); +139 boolean matchFound = false; +140 for (int i = 0; i < freeCount; ++i) { +141 if (matchFound) freeList[i - 1] = freeList[i]; +142 else if (freeList[i] == idx) matchFound = true; +143 } +144 if (!matchFound) +145 throw new BucketAllocatorException("Couldn't find match for index " +146 + idx + " in free list"); +147 ++usedCount; +148 --freeCount; +149 } +150 +151 private void free(long offset) { +152 offset -= baseOffset; +153 assert offset >= 0; +154 assert offset < itemCount * itemAllocationSize; +155 assert offset % itemAllocationSize == 0; +156 assert usedCount > 0; +157 assert freeCount < itemCount; // Else duplicate free +158 int item = (int) (offset / (long) itemAllocationSize); +159 assert !freeListContains(item); +160 --usedCount; +161 freeList[freeCount++] = item; +162 } +163 +164 private boolean freeListContains(int blockNo) { +165 for (int i = 0; i < freeCount; ++i) { +166 if (freeList[i] == blockNo) return true; +167 } +168 return false; +169 } +170 } +171 +172 final class BucketSizeInfo { +173 // Free bucket means it has space to allocate a block; +174 // Completely free bucket means it has no block. +175 private LinkedMap bucketList, freeBuckets, completelyFreeBuckets; +176 private int sizeIndex; +177 +178 BucketSizeInfo(int sizeIndex) { +179 bucketList = new LinkedMap(); +180 freeBuckets = new LinkedMap(); +181 completelyFreeBuckets = new LinkedMap(); +182 this.sizeIndex = sizeIndex; +183 } +184 +185 public synchronized void instantiateBucket(Bucket b) { +186 assert b.isUninstantiated() || b.isCompletelyFree(); +187 b.reconfigure(sizeIndex, bucketSizes, bucketCapacity); +188 bucketList.put(b, b); +189 freeBuckets.put(b, b); +190 completelyFreeBuckets.put(b, b); +191 } +192 +193 public int sizeIndex() { +194 return sizeIndex; +195 } +196 +197 /** +198 * Find a bucket to allocate a block +199 * @return the offset in the IOEngine +200 */ +201 public long allocateBlock() { +202 Bucket b = null; +203 if (freeBuckets.size() > 0) { +204 // Use up an existing one first... +205 b = (Bucket) freeBuckets.lastKey(); +206 } +207 if (b == null) { +208 b = grabGlobalCompletelyFreeBucket(); +209 if (b != null) instantiateBucket(b); +210 } +211 if (b == null) return -1; +212 long result = b.allocate(); +213 blockAllocated(b); +214 return result; +215 } +216 +217 void blockAllocated(Bucket b) { +218 if (!b.isCompletelyFree()) completelyFreeBuckets.remove(b); +219 if (!b.hasFreeSpace()) freeBuckets.remove(b); +220 } +221 +222 public Bucket findAndRemoveCompletelyFreeBucket() { +223 Bucket b = null; +224 assert bucketList.size() > 0; +225 if (bucketList.size() == 1) { +226 // So we never get complete starvation of a bucket for a size +227 return null; +228 } +229 +230 if (completelyFreeBuckets.size() > 0) { +231 b = (Bucket) completelyFreeBuckets.firstKey(); +232 removeBucket(b); +233 } +234 return b; +235 } +236 +237 private synchronized void removeBucket(Bucket b) { +238 assert b.isCompletelyFree(); +239 bucketList.remove(b); +240 freeBuckets.remove(b); +241 completelyFreeBuckets.remove(b); +242 } +243 +244 public void freeBlock(Bucket b, long offset) { +245 assert bucketList.containsKey(b); +246 // else we shouldn't have anything to free... +247 assert (!completelyFreeBuckets.containsKey(b)); +248 b.free(offset); +249 if (!freeBuckets.containsKey(b)) freeBuckets.put(b, b); +250 if (b.isCompletelyFree()) completelyFreeBuckets.put(b, b); +251 } +252 +253 public synchronized IndexStatistics statistics() { +254 long free = 0, used = 0; +255 for (Object obj : bucketList.keySet()) { +256 Bucket b = (Bucket) obj; +257 free += b.freeCount(); +258 used += b.usedCount(); +259 } +260 return new IndexStatistics(free, used, bucketSizes[sizeIndex]); +261 } +262 +263 @Override +264 public String toString() { +265 return Objects.toStringHelper(this.getClass()) +266 .add("sizeIndex", sizeIndex) +267 .add("bucketSize", bucketSizes[sizeIndex]) +268 .toString(); +269 } +270 } +271 +272 // Default block size is 64K, so we choose more sizes near 64K, you'd better +273 // reset it according to your cluster's block size distribution +274 // TODO Support the view of block size distribution statistics +275 private static final int DEFAULT_BUCKET_SIZES[] = { 4 * 1024 + 1024, 8 * 1024 + 1024, +276 16 * 1024 + 1024, 32 * 1024 + 1024, 40 * 1024 + 1024, 48 * 1024 + 1024, +277 56 * 1024 + 1024, 64 * 1024 + 1024, 96 * 1024 + 1024, 128 * 1024 + 1024, +278 192 * 1024 + 1024, 256 * 1024 + 1024, 384 * 1024 + 1024, +279 512 * 1024 + 1024 }; +280 +281 /** +282 * Round up the given block size to bucket size, and get the corresponding +283 * BucketSizeInfo +284 */ +285 public BucketSizeInfo roundUpToBucketSizeInfo(int blockSize) { +286 for (int i = 0; i < bucketSizes.length; ++i) +287 if (blockSize <= bucketSizes[i]) +288 return bucketSizeInfos[i]; +289 return null; +290 } 291 -292 private final int[] bucketSizes; -293 private final int bigItemSize; -294 // The capacity size for each bucket -295 private final long bucketCapacity; -296 private Bucket[] buckets; -297 private BucketSizeInfo[] bucketSizeInfos; -298 private final long totalSize; -299 private long usedSize = 0; -300 -301 BucketAllocator(long availableSpace, int[] bucketSizes) -302 throws BucketAllocatorException { -303 this.bucketSizes = bucketSizes == null ? DEFAULT_BUCKET_SIZES : bucketSizes; -304 Arrays.sort(this.bucketSizes); -305 this.bigItemSize = Ints.max(this.bucketSizes); -306 this.bucketCapacity = FEWEST_ITEMS_IN_BUCKET * bigItemSize; -307 buckets = new Bucket[(int) (availableSpace / bucketCapacity)]; -308 if (buckets.length < this.bucketSizes.length) -309 throw new BucketAllocatorException( -310 "Bucket allocator size too small - must have room for at least " -311 + this.bucketSizes.length + " buckets"); -312 bucketSizeInfos = new BucketSizeInfo[this.bucketSizes.length]; -313 for (int i = 0; i < this.bucketSizes.length; ++i) { -314 bucketSizeInfos[i] = new BucketSizeInfo(i); -315 } -316 for (int i = 0; i < buckets.length; ++i) { -317 buckets[i] = new Bucket(bucketCapacity * i); -318 bucketSizeInfos[i < this.bucketSizes.length ? i : this.bucketSizes.length - 1] -319 .instantiateBucket(buckets[i]); -320 } -321 this.totalSize = ((long) buckets.length) * bucketCapacity; -322 } -323 -324 /** -325 * Rebuild the allocator's data structures from a persisted map. -326 * @param availableSpace capacity of cache -327 * @param map A map stores the block key and BucketEntry(block's meta data -328 * like offset, length) -329 * @param realCacheSize cached data size statistics for bucket cache -330 * @throws BucketAllocatorException -331 */ -332 BucketAllocator(long availableSpace, int[] bucketSizes, Map<BlockCacheKey, BucketEntry> map, -333 AtomicLong realCacheSize) throws BucketAllocatorException { -334 this(availableSpace, bucketSizes); -335 -336 // each bucket has an offset, sizeindex. probably the buckets are too big -337 // in our default state. so what we do is reconfigure them according to what -338 // we've found. we can only reconfigure each bucket once; if more than once, -339 // we know there's a bug, so we just log the info, throw, and start again... -340 boolean[] reconfigured = new boolean[buckets.length]; -341 for (Map.Entry<BlockCacheKey, BucketEntry> entry : map.entrySet()) { -342 long foundOffset = entry.getValue().offset(); -343 int foundLen = entry.getValue().getLength(); -344 int bucketSizeIndex = -1; -345 for (int i = 0; i < bucketSizes.length; ++i) { -346 if (foundLen <= bucketSizes[i]) { -347 bucketSizeIndex = i; -348 break; -349 } -350 } -351 if (bucketSizeIndex == -1) { -352 throw new BucketAllocatorException( -353 "Can't match bucket size for the block with size " + foundLen); -354 } -355 int bucketNo = (int) (foundOffset / bucketCapacity); -356 if (bucketNo < 0 || bucketNo >= buckets.length) -357 throw new BucketAllocatorException("Can't find bucket " + bucketNo -358 + ", total buckets=" + buckets.length -359 + "; did you shrink the cache?"); -360 Bucket b = buckets[bucketNo]; -361 if (reconfigured[bucketNo]) { -362 if (b.sizeIndex() != bucketSizeIndex) -363 throw new BucketAllocatorException( -364 "Inconsistent allocation in bucket map;"); -365 } else { -366 if (!b.isCompletelyFree()) -367 throw new BucketAllocatorException("Reconfiguring bucket " -368 + bucketNo + " but it's already allocated; corrupt data"); -369 // Need to remove the bucket from whichever list it's currently in at -370 // the moment... -371 BucketSizeInfo bsi = bucketSizeInfos[bucketSizeIndex]; -372 BucketSizeInfo oldbsi = bucketSizeInfos[b.sizeIndex()]; -373 oldbsi.removeBucket(b); -374 bsi.instantiateBucket(b); -375 reconfigured[bucketNo] = true; -376 } -377 realCacheSize.addAndGet(foundLen); -378 buckets[bucketNo].addAllocation(foundOffset); -379 usedSize += buckets[bucketNo].getItemAllocationSize(); -380 bucketSizeInfos[bucketSizeIndex].blockAllocated(b); -381 } -382 } -383 -384 public String toString() { -385 StringBuilder sb = new StringBuilder(1024); -386 for (int i = 0; i < buckets.length; ++i) { -387 Bucket b = buckets[i]; -388 if (i > 0) sb.append(", "); -389 sb.append("bucket.").append(i).append(": size=").append(b.getItemAllocationSize()); -390 sb.append(", freeCount=").append(b.freeCount()).append(", used=").append(b.usedCount()); -391 } -392 return sb.toString(); -393 } -394 -395 public long getUsedSize() { -396 return this.usedSize; -397 } -398 -399 public long getFreeSize() { -400 return this.totalSize - getUsedSize(); -401 } -402 -403 public long getTotalSize() { -404 return this.totalSize; -405 } -406 -407 /** -408 * Allocate a block with specified size. Return the offset -409 * @param blockSize size of block -410 * @throws BucketAllocatorException -411 * @throws CacheFullException -412 * @return the offset in the IOEngine -413 */ -414 public synchronized long allocateBlock(int blockSize) throws CacheFullException, -415 BucketAllocatorException { -416 assert blockSize > 0; -417 BucketSizeInfo bsi = roundUpToBucketSizeInfo(blockSize); -418 if (bsi == null) { -419 throw new BucketAllocatorException("Allocation too big size=" + blockSize + -420 "; adjust BucketCache sizes " + CacheConfig.BUCKET_CACHE_BUCKETS_KEY + -421 " to accomodate if size seems reasonable and you want it cached."); -422 } -423 long offset = bsi.allocateBlock(); -424 -425 // Ask caller to free up space and try again! -426 if (offset < 0) -427 throw new CacheFullException(blockSize, bsi.sizeIndex()); -428 usedSize += bucketSizes[bsi.sizeIndex()]; -429 return offset; -430 } -431 -432 private Bucket grabGlobalCompletelyFreeBucket() { -433 for (BucketSizeInfo bsi : bucketSizeInfos) { -434 Bucket b = bsi.findAndRemoveCompletelyFreeBucket(); -435 if (b != null) return b; -436 } -437 return null; -438 } -439 -440 /** -441 * Free a block with the offset -442 * @param offset block's offset -443 * @return size freed -444 */ -445 public synchronized int freeBlock(long offset) { -446 int bucketNo = (int) (offset / bucketCapacity); -447 assert bucketNo >= 0 && bucketNo < buckets.length; -448 Bucket targetBucket = buckets[bucketNo]; -449 bucketSizeInfos[targetBucket.sizeIndex()].freeBlock(targetBucket, offset); -450 usedSize -= targetBucket.getItemAllocationSize(); -451 return targetBucket.getItemAllocationSize(); -452 } -453 -454 public int sizeIndexOfAllocation(long offset) { -455 int bucketNo = (int) (offset / bucketCapacity); -456 assert bucketNo >= 0 && bucketNo < buckets.length; -457 Bucket targetBucket = buckets[bucketNo]; -458 return targetBucket.sizeIndex(); -459 } -460 -461 public int sizeOfAllocation(long offset) { -462 int bucketNo = (int) (offset / bucketCapacity); -463 assert bucketNo >= 0 && bucketNo < buckets.length; -464 Bucket targetBucket = buckets[bucketNo]; -465 return targetBucket.getItemAllocationSize(); -466 } -467 -468 static class IndexStatistics { -469 private long freeCount, usedCount, itemSize, totalCount; -470 -471 public long freeCount() { -472 return freeCount; -473 } -474 -475 public long usedCount() { -476 return usedCount; -477 } -478 -479 public long totalCount() { -480 return totalCount; -481 } -482 -483 public long freeBytes() { -484 return freeCount * itemSize; -485 } -486 -487 public long usedBytes() { -488 return usedCount * itemSize; -489 } -490 -491 public long totalBytes() { -492 return totalCount * itemSize; -493 } -494 -495 public long itemSize() { -496 return itemSize; -497 } -498 -499 public IndexStatistics(long free, long used, long itemSize) { -500 setTo(free, used, itemSize); -501 } -502 -503 public IndexStatistics() { -504 setTo(-1, -1, 0); -505 } -506 -507 public void setTo(long free, long used, long itemSize) { -508 this.itemSize = itemSize; -509 this.freeCount = free; -510 this.usedCount = used; -511 this.totalCount = free + used; -512 } -513 } -514 -515 public Bucket [] getBuckets() { -516 return this.buckets; -517 } -518 -519 void logStatistics() { -520 IndexStatistics total = new IndexStatistics(); -521 IndexStatistics[] stats = getIndexStatistics(total); -522 LOG.info("Bucket allocator statistics follow:\n"); -523 LOG.info(" Free bytes=" + total.freeBytes() + "+; used bytes=" -524 + total.usedBytes() + "; total bytes=" + total.totalBytes()); -525 for (IndexStatistics s : stats) { -526 LOG.info(" Object size " + s.itemSize() + " used=" + s.usedCount() -527 + "; free=" + s.freeCount() + "; total=" + s.totalCount()); -528 } -529 } -530 -531 IndexStatistics[] getIndexStatistics(IndexStatistics grandTotal) { -532 IndexStatistics[] stats = getIndexStatistics(); -533 long totalfree = 0, totalused = 0; -534 for (IndexStatistics stat : stats) { -535 totalfree += stat.freeBytes(); -536 totalused += stat.usedBytes(); -537 } -538 grandTotal.setTo(totalfree, totalused, 1); -539 return stats; -540 } -541 -542 IndexStatistics[] getIndexStatistics() { -543 IndexStatistics[] stats = new IndexStatistics[bucketSizes.length]; -544 for (int i = 0; i < stats.length; ++i) -545 stats[i] = bucketSizeInfos[i].statistics(); -546 return stats; -547 } -548 -549 public long freeBlock(long freeList[]) { -550 long sz = 0; -551 for (int i = 0; i < freeList.length; ++i) -552 sz += freeBlock(freeList[i]); -553 return sz; -554 } -555 -556} +292 static public final int FEWEST_ITEMS_IN_BUCKET = 4; +293 +294 private final int[] bucketSizes; +295 private final int bigItemSize; +296 // The capacity size for each bucket +297 private final long bucketCapacity; +298 private Bucket[] buckets; +299 private BucketSizeInfo[] bucketSizeInfos; +300 private final long totalSize; +301 private long usedSize = 0; +302 +303 BucketAllocator(long availableSpace, int[] bucketSizes) +304 throws BucketAllocatorException { +305 this.bucketSizes = bucketSizes == null ? DEFAULT_BUCKET_SIZES : bucketSizes; +306 Arrays.sort(this.bucketSizes); +307 this.bigItemSize = Ints.max(this.bucketSizes); +308 this.bucketCapacity = FEWEST_ITEMS_IN_BUCKET * bigItemSize; +309 buckets = new Bucket[(int) (availableSpace / bucketCapacity)]; +310 if (buckets.length < this.bucketSizes.length) +311 throw new BucketAllocatorException( +312 "Bucket allocator size too small - must have room for at least " +313 + this.bucketSizes.length + " buckets"); +314 bucketSizeInfos = new BucketSizeInfo[this.bucketSizes.length]; +315 for (int i = 0; i < this.bucketSizes.length; ++i) { +316 bucketSizeInfos[i] = new BucketSizeInfo(i); +317 } +318 for (int i = 0; i < buckets.length; ++i) { +319 buckets[i] = new Bucket(bucketCapacity * i); +320 bucketSizeInfos[i < this.bucketSizes.length ? i : this.bucketSizes.length - 1] +321 .instantiateBucket(buckets[i]); +322 } +323 this.totalSize = ((long) buckets.length) * bucketCapacity; +324 } +325 +326 /** +327 * Rebuild the allocator's data structures from a persisted map. +328 * @param availableSpace capacity of cache +329 * @param map A map stores the block key and BucketEntry(block's meta data +330 * like offset, length) +331 * @param realCacheSize cached data size statistics for bucket cache +332 * @throws BucketAllocatorException +333 */ +334 BucketAllocator(long availableSpace, int[] bucketSizes, Map<BlockCacheKey, BucketEntry> map, +335 AtomicLong realCacheSize) throws BucketAllocatorException { +336 this(availableSpace, bucketSizes); +337 +338 // each bucket has an offset, sizeindex. probably the buckets are too big +339 // in our default state. so what we do is reconfigure them according to what +340 // we've found. we can only reconfigure each bucket once; if more than once, +341 // we know there's a bug, so we just log the info, throw, and start again... +342 boolean[] reconfigured = new boolean[buckets.length]; +343 for (Map.Entry<BlockCacheKey, BucketEntry> entry : map.entrySet()) { +344 long foundOffset = entry.getValue().offset(); +345 int foundLen = entry.getValue().getLength(); +346 int bucketSizeIndex = -1; +347 for (int i = 0; i < bucketSizes.length; ++i) { +348 if (foundLen <= bucketSizes[i]) { +349 bucketSizeIndex = i; +350 break; +351 } +352 } +353 if (bucketSizeIndex == -1) { +354 throw new BucketAllocatorException( +355 "Can't match bucket size for the block with size " + foundLen); +356 } +357 int bucketNo = (int) (foundOffset / bucketCapacity); +358 if (bucketNo < 0 || bucketNo >= buckets.length) +359 throw new BucketAllocatorException("Can't find bucket " + bucketNo +360 + ", total buckets=" + buckets.length +361 + "; did you shrink the cache?"); +362 Bucket b = buckets[bucketNo]; +363 if (reconfigured[bucketNo]) { +364 if (b.sizeIndex() != bucketSizeIndex) +365 throw new BucketAllocatorException( +366 "Inconsistent allocation in bucket map;"); +367 } else { +368 if (!b.isCompletelyFree()) +369 throw new BucketAllocatorException("Reconfiguring bucket " +370 + bucketNo + " but it's already allocated; corrupt data"); +371 // Need to remove the bucket from whichever list it's currently in at +372 // the moment... +373 BucketSizeInfo bsi = bucketSizeInfos[bucketSizeIndex]; +374 BucketSizeInfo oldbsi = bucketSizeInfos[b.sizeIndex()]; +375 oldbsi.removeBucket(b); +376 bsi.instantiateBucket(b); +377 reconfigured[bucketNo] = true; +378 } +379 realCacheSize.addAndGet(foundLen); +380 buckets[bucketNo].addAllocation(foundOffset); +381 usedSize += buckets[bucketNo].getItemAllocationSize(); +382 bucketSizeInfos[bucketSizeIndex].blockAllocated(b); +383 } +384 } +385 +386 public String toString() { +387 StringBuilder sb = new StringBuilder(1024); +388 for (int i = 0; i < buckets.length; ++i) { +389 Bucket b = buckets[i]; +390 if (i > 0) sb.append(", "); +391 sb.append("bucket.").append(i).append(": size=").append(b.getItemAllocationSize()); +392 sb.append(", freeCount=").append(b.freeCount()).append(", used=").append(b.usedCount()); +393 } +394 return sb.toString(); +395 } +396 +397 public long getUsedSize() { +398 return this.usedSize; +399 } +400 +401 public long getFreeSize() { +402 return this.totalSize - getUsedSize(); +403 } +404 +405 public long getTotalSize() { +406 return this.totalSize; +407 } +408 +409 /** +410 * Allocate a block with specified size. Return the offset +411 * @param blockSize size of block +412 * @throws BucketAllocatorException +413 * @throws CacheFullException +414 * @return the offset in the IOEngine +415 */ +416 public synchronized long allocateBlock(int blockSize) throws CacheFullException, +417 BucketAllocatorException { +418 assert blockSize > 0; +419 BucketSizeInfo bsi = roundUpToBucketSizeInfo(blockSize); +420 if (bsi == null) { +421 throw new BucketAllocatorException("Allocation too big size=" + blockSize + +422 "; adjust BucketCache sizes " + CacheConfig.BUCKET_CACHE_BUCKETS_KEY + +423 " to accomodate if size seems reasonable and you want it cached."); +424 } +425 long offset = bsi.allocateBlock(); +426 +427 // Ask caller to free up space and try again! +428 if (offset < 0) +429 throw new CacheFullException(blockSize, bsi.sizeIndex()); +430 usedSize += bucketSizes[bsi.sizeIndex()]; +431 return offset; [... 131 lines stripped ...]