You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by al...@apache.org on 2014/02/20 19:35:52 UTC
[1/2] git commit: Fast ABSC.addAll() path + ASPCSI optimization
Repository: cassandra
Updated Branches:
refs/heads/cassandra-2.1 5223c4797 -> 6ed241acb
Fast ABSC.addAll() path + ASPCSI optimization
patch by Benedict Elliott Smith; reviewed by Aleksey Yeschenko
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/6ed241ac
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/6ed241ac
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/6ed241ac
Branch: refs/heads/cassandra-2.1
Commit: 6ed241acb33087e6cedf8f4637aca5dce0fe502c
Parents: e69e526
Author: Aleksey Yeschenko <al...@apache.org>
Authored: Thu Feb 20 21:33:28 2014 +0300
Committer: Aleksey Yeschenko <al...@apache.org>
Committed: Thu Feb 20 21:35:33 2014 +0300
----------------------------------------------------------------------
.../cassandra/db/ArrayBackedSortedColumns.java | 44 ++++++++++++++++----
.../apache/cassandra/db/AtomicBTreeColumns.java | 2 +-
.../org/apache/cassandra/db/ColumnFamily.java | 7 +++-
.../AbstractSimplePerColumnSecondaryIndex.java | 19 +--------
4 files changed, 46 insertions(+), 26 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/6ed241ac/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
index 0ce36e2..1fdebd8 100644
--- a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
+++ b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
@@ -52,18 +52,18 @@ public class ArrayBackedSortedColumns extends ColumnFamily
public static final ColumnFamily.Factory<ArrayBackedSortedColumns> factory = new Factory<ArrayBackedSortedColumns>()
{
- public ArrayBackedSortedColumns create(CFMetaData metadata, boolean insertReversed)
+ public ArrayBackedSortedColumns create(CFMetaData metadata, boolean insertReversed, int initialCapacity)
{
- return new ArrayBackedSortedColumns(metadata, insertReversed);
+ return new ArrayBackedSortedColumns(metadata, insertReversed, initialCapacity);
}
};
- private ArrayBackedSortedColumns(CFMetaData metadata, boolean reversed)
+ private ArrayBackedSortedColumns(CFMetaData metadata, boolean reversed, int initialCapacity)
{
super(metadata);
this.reversed = reversed;
this.deletionInfo = DeletionInfo.live();
- this.cells = EMPTY_ARRAY;
+ this.cells = initialCapacity == 0 ? EMPTY_ARRAY : new Cell[initialCapacity];
this.size = 0;
this.sortedSize = 0;
this.isSorted = true;
@@ -235,9 +235,39 @@ public class ArrayBackedSortedColumns extends ColumnFamily
if (other.getColumnCount() == 0)
return;
- Iterator<Cell> iterator = reversed ? other.reverseIterator() : other.iterator();
- while (iterator.hasNext())
- addColumn(iterator.next());
+ // In reality, with ABSC being the only remaining container (aside from ABTC), other will aways be ABSC.
+ if (size == 0 && other instanceof ArrayBackedSortedColumns)
+ {
+ fastAddAll((ArrayBackedSortedColumns) other);
+ }
+ else
+ {
+ Iterator<Cell> iterator = reversed ? other.reverseIterator() : other.iterator();
+ while (iterator.hasNext())
+ addColumn(iterator.next());
+ }
+ }
+
+ // Fast path, when this ABSC is empty.
+ private void fastAddAll(ArrayBackedSortedColumns other)
+ {
+ if (other.isInsertReversed() == isInsertReversed())
+ {
+ cells = Arrays.copyOf(other.cells, other.cells.length);
+ size = other.size;
+ sortedSize = other.sortedSize;
+ isSorted = other.isSorted;
+ }
+ else
+ {
+ if (cells.length < other.getColumnCount())
+ cells = new Cell[Math.max(MINIMAL_CAPACITY, other.getColumnCount())];
+ Iterator<Cell> iterator = reversed ? other.reverseIterator() : other.iterator();
+ while (iterator.hasNext())
+ cells[size++] = iterator.next();
+ sortedSize = size;
+ isSorted = true;
+ }
}
/**
http://git-wip-us.apache.org/repos/asf/cassandra/blob/6ed241ac/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java b/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
index f75efd2..5cc43d9 100644
--- a/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
+++ b/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
@@ -66,7 +66,7 @@ public class AtomicBTreeColumns extends ColumnFamily
public static final Factory<AtomicBTreeColumns> factory = new Factory<AtomicBTreeColumns>()
{
- public AtomicBTreeColumns create(CFMetaData metadata, boolean insertReversed)
+ public AtomicBTreeColumns create(CFMetaData metadata, boolean insertReversed, int initialCapacity)
{
if (insertReversed)
throw new IllegalArgumentException();
http://git-wip-us.apache.org/repos/asf/cassandra/blob/6ed241ac/src/java/org/apache/cassandra/db/ColumnFamily.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/ColumnFamily.java b/src/java/org/apache/cassandra/db/ColumnFamily.java
index 3437410..8762462 100644
--- a/src/java/org/apache/cassandra/db/ColumnFamily.java
+++ b/src/java/org/apache/cassandra/db/ColumnFamily.java
@@ -493,7 +493,12 @@ public abstract class ColumnFamily implements Iterable<Cell>, IRowCacheEntry
* allow optimizing for both forward and reversed slices. This does not matter for ThreadSafeSortedColumns.
* Note that this is only an hint on how we expect to do insertion, this does not change the map sorting.
*/
- public abstract T create(CFMetaData metadata, boolean insertReversed);
+ public abstract T create(CFMetaData metadata, boolean insertReversed, int initialCapacity);
+
+ public T create(CFMetaData metadata, boolean insertReversed)
+ {
+ return create(metadata, insertReversed, 0);
+ }
public T create(CFMetaData metadata)
{
http://git-wip-us.apache.org/repos/asf/cassandra/blob/6ed241ac/src/java/org/apache/cassandra/db/index/AbstractSimplePerColumnSecondaryIndex.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/index/AbstractSimplePerColumnSecondaryIndex.java b/src/java/org/apache/cassandra/db/index/AbstractSimplePerColumnSecondaryIndex.java
index e2a6608..9788168 100644
--- a/src/java/org/apache/cassandra/db/index/AbstractSimplePerColumnSecondaryIndex.java
+++ b/src/java/org/apache/cassandra/db/index/AbstractSimplePerColumnSecondaryIndex.java
@@ -86,21 +86,6 @@ public abstract class AbstractSimplePerColumnSecondaryIndex extends PerColumnSec
baseCfs.metadata.getColumnDefinition(expr.column).type.getString(expr.value));
}
- public void delete(ByteBuffer rowKey, Cell cell)
- {
- throw new IllegalStateException();
- }
-
- public void insert(ByteBuffer rowKey, Cell cell)
- {
- throw new IllegalStateException();
- }
-
- public void update(ByteBuffer rowKey, Cell cell)
- {
- throw new IllegalStateException();
- }
-
public void delete(ByteBuffer rowKey, Cell cell, OpOrder.Group opGroup)
{
if (cell.isMarkedForDelete(System.currentTimeMillis()))
@@ -108,7 +93,7 @@ public abstract class AbstractSimplePerColumnSecondaryIndex extends PerColumnSec
DecoratedKey valueKey = getIndexKeyFor(getIndexedValue(rowKey, cell));
int localDeletionTime = (int) (System.currentTimeMillis() / 1000);
- ColumnFamily cfi = ArrayBackedSortedColumns.factory.create(indexCfs.metadata);
+ ColumnFamily cfi = ArrayBackedSortedColumns.factory.create(indexCfs.metadata, false, 1);
cfi.addTombstone(makeIndexColumnName(rowKey, cell), localDeletionTime, cell.timestamp());
indexCfs.apply(valueKey, cfi, SecondaryIndexManager.nullUpdater, opGroup, null);
if (logger.isDebugEnabled())
@@ -118,7 +103,7 @@ public abstract class AbstractSimplePerColumnSecondaryIndex extends PerColumnSec
public void insert(ByteBuffer rowKey, Cell cell, OpOrder.Group opGroup)
{
DecoratedKey valueKey = getIndexKeyFor(getIndexedValue(rowKey, cell));
- ColumnFamily cfi = ArrayBackedSortedColumns.factory.create(indexCfs.metadata);
+ ColumnFamily cfi = ArrayBackedSortedColumns.factory.create(indexCfs.metadata, false, 1);
CellName name = makeIndexColumnName(rowKey, cell);
if (cell instanceof ExpiringCell)
{
[2/2] git commit: Better solution for CASSANDRA-6742
Posted by al...@apache.org.
Better solution for CASSANDRA-6742
patch by Aleksey Yeschenko; reviewed by Benedict Elliott Smith for
CASSANDRA-6742
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/e69e526b
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/e69e526b
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/e69e526b
Branch: refs/heads/cassandra-2.1
Commit: e69e526b9053e3d3634a005cc94a8954c2d7d41f
Parents: 5223c47
Author: Aleksey Yeschenko <al...@apache.org>
Authored: Thu Feb 20 21:26:21 2014 +0300
Committer: Aleksey Yeschenko <al...@apache.org>
Committed: Thu Feb 20 21:35:33 2014 +0300
----------------------------------------------------------------------
.../cassandra/db/ArrayBackedSortedColumns.java | 86 ++++++++++----------
1 file changed, 42 insertions(+), 44 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/e69e526b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
index 24a0755..0ce36e2 100644
--- a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
+++ b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
@@ -43,12 +43,12 @@ public class ArrayBackedSortedColumns extends ColumnFamily
private static final int MINIMAL_CAPACITY = 10;
private final boolean reversed;
- private DeletionInfo deletionInfo;
+ private DeletionInfo deletionInfo;
private Cell[] cells;
-
- private volatile int size;
- private volatile int sortedSize;
+ private int size;
+ private int sortedSize;
+ private volatile boolean isSorted;
public static final ColumnFamily.Factory<ArrayBackedSortedColumns> factory = new Factory<ArrayBackedSortedColumns>()
{
@@ -66,6 +66,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily
this.cells = EMPTY_ARRAY;
this.size = 0;
this.sortedSize = 0;
+ this.isSorted = true;
}
private ArrayBackedSortedColumns(ArrayBackedSortedColumns original)
@@ -76,6 +77,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily
this.cells = Arrays.copyOf(original.cells, original.size);
this.size = original.size;
this.sortedSize = original.sortedSize;
+ this.isSorted = original.isSorted;
}
public ColumnFamily.Factory getFactory()
@@ -100,7 +102,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily
private void maybeSortCells()
{
- if (size != sortedSize)
+ if (!isSorted)
sortCells();
}
@@ -109,8 +111,8 @@ public class ArrayBackedSortedColumns extends ColumnFamily
*/
private synchronized void sortCells()
{
- if (size == sortedSize)
- return; // Just sorted by a previous call.
+ if (isSorted)
+ return; // Just sorted by a previous call
Comparator<Cell> comparator = reversed
? getComparator().columnReverseComparator()
@@ -133,8 +135,8 @@ public class ArrayBackedSortedColumns extends ColumnFamily
int rightStart = sortedSize;
int rightEnd = size;
- sortedSize = -1; // Set to -1 to avoid the pos == sortedSize edge case
- size = pos; // 'Trim' the size to what's left without the leftCopy
+ // 'Trim' the sizes to what's left without the leftCopy
+ size = sortedSize = pos;
// Merge the cells from both segments. When adding from the left segment we can rely on it not having any
// duplicate cells, and thus omit the comparison with the previously entered cell - we'll never need to reconcile.
@@ -143,23 +145,38 @@ public class ArrayBackedSortedColumns extends ColumnFamily
{
int cmp = comparator.compare(leftCopy[l], cells[r]);
if (cmp < 0)
- internalAppend(leftCopy[l++]);
+ append(leftCopy[l++]);
else if (cmp == 0)
- internalAppend(leftCopy[l++].reconcile(cells[r++]));
+ append(leftCopy[l++].reconcile(cells[r++]));
else
- internalAppendOrReconcile(cells[r++]);
+ appendOrReconcile(cells[r++]);
}
while (l < leftCopy.length)
- internalAppend(leftCopy[l++]);
+ append(leftCopy[l++]);
while (r < rightEnd)
- internalAppendOrReconcile(cells[r++]);
-
- // Fully sorted at this point
- sortedSize = size;
+ appendOrReconcile(cells[r++]);
// Nullify the remainder of the array (in case we had duplicate cells that got reconciled)
for (int i = size; i < rightEnd; i++)
cells[i] = null;
+
+ // Fully sorted at this point
+ isSorted = true;
+ }
+
+ private void appendOrReconcile(Cell cell)
+ {
+ if (size > 0 && cells[size - 1].name().equals(cell.name()))
+ reconcileWith(size - 1, cell);
+ else
+ append(cell);
+ }
+
+ private void append(Cell cell)
+ {
+ cells[size] = cell;
+ size++;
+ sortedSize++;
}
public Cell getColumn(CellName name)
@@ -200,9 +217,14 @@ public class ArrayBackedSortedColumns extends ColumnFamily
{
int pos = binarySearch(cell.name());
if (pos >= 0) // Reconcile with an existing cell
+ {
reconcileWith(pos, cell);
+ }
else
+ {
internalAdd(cell); // Append to the end, making cells unsorted from now on
+ isSorted = false;
+ }
}
}
@@ -223,33 +245,8 @@ public class ArrayBackedSortedColumns extends ColumnFamily
*/
private void internalAdd(Cell cell)
{
- if (cells == EMPTY_ARRAY)
- cells = new Cell[MINIMAL_CAPACITY];
- else if (cells.length == size)
- cells = Arrays.copyOf(cells, size * 3 / 2 + 1);
-
- cells[size++] = cell;
- }
-
- /**
- * Appends a cell to the array, with the knowledge that array has enough capacity for the new cell, and that
- * the cell is being added in the sorted order, but may or may not need to be reconciled with the previously
- * appended one.
- */
- private void internalAppendOrReconcile(Cell cell)
- {
- if (size > 0 && cells[size - 1].name().equals(cell.name()))
- reconcileWith(size - 1, cell);
- else
- internalAppend(cell);
- }
-
- /**
- * Appends a cell to the array, with the knowledge that array has enough capacity for the new cell, and that
- * the cell is being added in the sorted order, and the added cell is not a duplicate of a previously inserted one.
- */
- private void internalAppend(Cell cell)
- {
+ if (cells.length == size)
+ cells = Arrays.copyOf(cells, Math.max(MINIMAL_CAPACITY, size * 3 / 2 + 1));
cells[size++] = cell;
}
@@ -328,6 +325,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily
for (int i = 0; i < size; i++)
cells[i] = null;
size = sortedSize = 0;
+ isSorted = true;
}
public DeletionInfo deletionInfo()