You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by zh...@apache.org on 2018/11/06 01:26:41 UTC
hbase git commit: HBASE-21314 The implementation of BitSetNode is not
efficient
Repository: hbase
Updated Branches:
refs/heads/master eaf0baf7d -> 01603278a
HBASE-21314 The implementation of BitSetNode is not efficient
Project: http://git-wip-us.apache.org/repos/asf/hbase/repo
Commit: http://git-wip-us.apache.org/repos/asf/hbase/commit/01603278
Tree: http://git-wip-us.apache.org/repos/asf/hbase/tree/01603278
Diff: http://git-wip-us.apache.org/repos/asf/hbase/diff/01603278
Branch: refs/heads/master
Commit: 01603278a39e0659a4de3947ac7c5798dfebd198
Parents: eaf0baf
Author: zhangduo <zh...@apache.org>
Authored: Mon Nov 5 21:53:05 2018 +0800
Committer: zhangduo <zh...@apache.org>
Committed: Tue Nov 6 09:19:45 2018 +0800
----------------------------------------------------------------------
.../hbase/procedure2/store/BitSetNode.java | 113 ++++++++++---------
.../hbase/procedure2/store/TestBitSetNode.java | 48 ++++++++
2 files changed, 110 insertions(+), 51 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/hbase/blob/01603278/hbase-procedure/src/main/java/org/apache/hadoop/hbase/procedure2/store/BitSetNode.java
----------------------------------------------------------------------
diff --git a/hbase-procedure/src/main/java/org/apache/hadoop/hbase/procedure2/store/BitSetNode.java b/hbase-procedure/src/main/java/org/apache/hadoop/hbase/procedure2/store/BitSetNode.java
index 3102bde..f42199b 100644
--- a/hbase-procedure/src/main/java/org/apache/hadoop/hbase/procedure2/store/BitSetNode.java
+++ b/hbase-procedure/src/main/java/org/apache/hadoop/hbase/procedure2/store/BitSetNode.java
@@ -57,7 +57,11 @@ class BitSetNode {
private static final long WORD_MASK = 0xffffffffffffffffL;
private static final int ADDRESS_BITS_PER_WORD = 6;
private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
- private static final int MAX_NODE_SIZE = 1 << ADDRESS_BITS_PER_WORD;
+ // The BitSetNode itself has 48 bytes overhead, which is the size of 6 longs, so here we use a max
+ // node size 4, which is 8 longs since we have an array for modified and also an array for
+ // deleted. The assumption here is that most procedures will be deleted soon so we'd better keep
+ // the BitSetNode small.
+ private static final int MAX_NODE_SIZE = 4 << ADDRESS_BITS_PER_WORD;
/**
* Mimics {@link ProcedureStoreTracker#partial}. It will effect how we fill the new deleted bits
@@ -162,6 +166,9 @@ class BitSetNode {
return start;
}
+ /**
+ * Inclusive.
+ */
public long getEnd() {
return start + (modified.length << ADDRESS_BITS_PER_WORD) - 1;
}
@@ -176,6 +183,8 @@ class BitSetNode {
if (wordIndex >= deleted.length) {
return DeleteState.MAYBE;
}
+ // The left shift of java only takes care of the lowest several bits(5 for int and 6 for long),
+ // so here we can use bitmapIndex directly, without mod 64
return (deleted[wordIndex] & (1L << bitmapIndex)) != 0 ? DeleteState.YES : DeleteState.NO;
}
@@ -185,6 +194,8 @@ class BitSetNode {
if (wordIndex >= modified.length) {
return false;
}
+ // The left shift of java only takes care of the lowest several bits(5 for int and 6 for long),
+ // so here we can use bitmapIndex directly, without mod 64
return (modified[wordIndex] & (1L << bitmapIndex)) != 0;
}
@@ -269,72 +280,72 @@ class BitSetNode {
// ========================================================================
// Grow/Merge Helpers
// ========================================================================
- public boolean canGrow(final long procId) {
- return Math.abs(procId - start) < MAX_NODE_SIZE;
+ public boolean canGrow(long procId) {
+ if (procId <= start) {
+ return getEnd() - procId < MAX_NODE_SIZE;
+ } else {
+ return procId - start < MAX_NODE_SIZE;
+ }
}
- public boolean canMerge(final BitSetNode rightNode) {
+ public boolean canMerge(BitSetNode rightNode) {
// Can just compare 'starts' since boundaries are aligned to multiples of BITS_PER_WORD.
assert start < rightNode.start;
return (rightNode.getEnd() - start) < MAX_NODE_SIZE;
}
- public void grow(final long procId) {
- int delta, offset;
-
+ public void grow(long procId) {
+ // make sure you have call canGrow first before calling this method
+ assert canGrow(procId);
if (procId < start) {
- // add to head
+ // grow to left
long newStart = alignDown(procId);
- delta = (int) (start - newStart) >> ADDRESS_BITS_PER_WORD;
- offset = delta;
+ int delta = (int) (start - newStart) >> ADDRESS_BITS_PER_WORD;
start = newStart;
+ long[] newModified = new long[modified.length + delta];
+ System.arraycopy(modified, 0, newModified, delta, modified.length);
+ modified = newModified;
+ long[] newDeleted = new long[deleted.length + delta];
+ if (!partial) {
+ for (int i = 0; i < delta; i++) {
+ newDeleted[i] = WORD_MASK;
+ }
+ }
+ System.arraycopy(deleted, 0, newDeleted, delta, deleted.length);
+ deleted = newDeleted;
} else {
- // Add to tail
+ // grow to right
long newEnd = alignUp(procId + 1);
- delta = (int) (newEnd - getEnd()) >> ADDRESS_BITS_PER_WORD;
- offset = 0;
- }
-
- long[] newBitmap;
- int oldSize = modified.length;
-
- newBitmap = new long[oldSize + delta];
- for (int i = 0; i < newBitmap.length; ++i) {
- newBitmap[i] = 0;
- }
- System.arraycopy(modified, 0, newBitmap, offset, oldSize);
- modified = newBitmap;
-
- newBitmap = new long[deleted.length + delta];
- for (int i = 0; i < newBitmap.length; ++i) {
- newBitmap[i] = partial ? 0 : WORD_MASK;
+ int delta = (int) (newEnd - getEnd()) >> ADDRESS_BITS_PER_WORD;
+ int newSize = modified.length + delta;
+ long[] newModified = Arrays.copyOf(modified, newSize);
+ modified = newModified;
+ long[] newDeleted = Arrays.copyOf(deleted, newSize);
+ if (!partial) {
+ for (int i = deleted.length; i < newSize; i++) {
+ newDeleted[i] = WORD_MASK;
+ }
+ }
+ deleted = newDeleted;
}
- System.arraycopy(deleted, 0, newBitmap, offset, oldSize);
- deleted = newBitmap;
}
- public void merge(final BitSetNode rightNode) {
- int delta = (int) (rightNode.getEnd() - getEnd()) >> ADDRESS_BITS_PER_WORD;
-
- long[] newBitmap;
- int oldSize = modified.length;
- int newSize = (delta - rightNode.modified.length);
- int offset = oldSize + newSize;
-
- newBitmap = new long[oldSize + delta];
- System.arraycopy(modified, 0, newBitmap, 0, oldSize);
- System.arraycopy(rightNode.modified, 0, newBitmap, offset, rightNode.modified.length);
- modified = newBitmap;
-
- newBitmap = new long[oldSize + delta];
- System.arraycopy(deleted, 0, newBitmap, 0, oldSize);
- System.arraycopy(rightNode.deleted, 0, newBitmap, offset, rightNode.deleted.length);
- deleted = newBitmap;
-
- for (int i = 0; i < newSize; ++i) {
- modified[offset + i] = 0;
- deleted[offset + i] = partial ? 0 : WORD_MASK;
+ public void merge(BitSetNode rightNode) {
+ assert start < rightNode.start;
+ int newSize = (int) (rightNode.getEnd() - start + 1) >> ADDRESS_BITS_PER_WORD;
+ long[] newModified = Arrays.copyOf(modified, newSize);
+ System.arraycopy(rightNode.modified, 0, newModified, newSize - rightNode.modified.length,
+ rightNode.modified.length);
+ long[] newDeleted = Arrays.copyOf(deleted, newSize);
+ System.arraycopy(rightNode.deleted, 0, newDeleted, newSize - rightNode.deleted.length,
+ rightNode.deleted.length);
+ if (!partial) {
+ for (int i = deleted.length, n = newSize - rightNode.deleted.length; i < n; i++) {
+ newDeleted[i] = WORD_MASK;
+ }
}
+ modified = newModified;
+ deleted = newDeleted;
}
@Override
http://git-wip-us.apache.org/repos/asf/hbase/blob/01603278/hbase-procedure/src/test/java/org/apache/hadoop/hbase/procedure2/store/TestBitSetNode.java
----------------------------------------------------------------------
diff --git a/hbase-procedure/src/test/java/org/apache/hadoop/hbase/procedure2/store/TestBitSetNode.java b/hbase-procedure/src/test/java/org/apache/hadoop/hbase/procedure2/store/TestBitSetNode.java
index 8d193d0..cfc3809 100644
--- a/hbase-procedure/src/test/java/org/apache/hadoop/hbase/procedure2/store/TestBitSetNode.java
+++ b/hbase-procedure/src/test/java/org/apache/hadoop/hbase/procedure2/store/TestBitSetNode.java
@@ -18,9 +18,12 @@
package org.apache.hadoop.hbase.procedure2.store;
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
import org.apache.hadoop.hbase.HBaseClassTestRule;
import org.apache.hadoop.hbase.procedure2.Procedure;
+import org.apache.hadoop.hbase.procedure2.store.ProcedureStoreTracker.DeleteState;
import org.apache.hadoop.hbase.testclassification.MasterTests;
import org.apache.hadoop.hbase.testclassification.SmallTests;
import org.junit.ClassRule;
@@ -56,4 +59,49 @@ public class TestBitSetNode {
assertEquals(Procedure.NO_PROC_ID, node.getActiveMinProcId());
assertEquals(Procedure.NO_PROC_ID, node.getActiveMaxProcId());
}
+
+ @Test
+ public void testGrow() {
+ BitSetNode node = new BitSetNode(1000, false);
+ // contains, do not need to grow but should not fail
+ assertTrue(node.canGrow(1024));
+ assertTrue(node.canGrow(900));
+ assertTrue(node.canGrow(1100));
+ assertFalse(node.canGrow(100));
+ assertFalse(node.canGrow(10000));
+
+ // grow to right
+ node.grow(1100);
+ assertTrue(node.contains(1100));
+ assertTrue(node.isModified(1000));
+ // grow to left
+ node.grow(900);
+ assertTrue(node.contains(900));
+ assertTrue(node.isModified(1000));
+ for (long i = node.getStart(); i <= node.getEnd(); i++) {
+ if (i != 1000) {
+ assertEquals(DeleteState.YES, node.isDeleted(i));
+ } else {
+ assertEquals(DeleteState.NO, node.isDeleted(i));
+ }
+ }
+ }
+
+ @Test
+ public void testMerge() {
+ BitSetNode node = new BitSetNode(1000, false);
+ assertTrue(node.canMerge(new BitSetNode(1200, false)));
+ assertFalse(node.canMerge(new BitSetNode(10000, false)));
+ BitSetNode rightNode = new BitSetNode(1200, false);
+ node.merge(rightNode);
+ assertTrue(node.isModified(1000));
+ assertTrue(node.isModified(1200));
+ for (long i = node.getStart(); i <= node.getEnd(); i++) {
+ if (i != 1000 && i != 1200) {
+ assertEquals(DeleteState.YES, node.isDeleted(i));
+ } else {
+ assertEquals(DeleteState.NO, node.isDeleted(i));
+ }
+ }
+ }
}