From 8c65daf79d1c7fbe47f556c4d4bba2c2859851d1 Mon Sep 17 00:00:00 2001
From: boli <boli@localhost>
Date: Mon, 21 Apr 2008 21:08:12 +0000
Subject: [PATCH] This patch adds index buffering capabilities to the JE backend as to avoid using a fixed lock timeout for subtree delete and mod DN operations. Previously, any index modifications to subordinate entries of the affected operations will be performed with dn2id and id2entry modifications. This creates multiple random access to index database keys which could cause deadlocks in face of multiple parallel operations. With this fix, all index modifications are buffered up until the end of the operation so that each key of each index will be accessed once and in order. This maintains the DB access ordering in the JE backend of dn2id, id2entry, dn2uri, indexes in config order, VLV indexes in config order, and finally id2children and id2subtree. Since deadlocks should no longer occur in the JE backend, JE lock timeouts are now disabled at the JE environment level instead of the txn level. With this change, the performance of subtree deletes and mod DN operations have increased dramatically.
---
opends/src/server/org/opends/server/backends/jeb/SortValuesSet.java | 359 ++++++++++++++++++++++++++++++++++-------------------------
1 files changed, 204 insertions(+), 155 deletions(-)
diff --git a/opends/src/server/org/opends/server/backends/jeb/SortValuesSet.java b/opends/src/server/org/opends/server/backends/jeb/SortValuesSet.java
index 417cdc5..94bf340 100644
--- a/opends/src/server/org/opends/server/backends/jeb/SortValuesSet.java
+++ b/opends/src/server/org/opends/server/backends/jeb/SortValuesSet.java
@@ -28,8 +28,9 @@
import org.opends.server.types.*;
import org.opends.server.protocols.asn1.ASN1OctetString;
+import org.opends.server.protocols.asn1.ASN1Element;
-import java.util.HashMap;
+import java.util.LinkedList;
import com.sleepycat.je.DatabaseException;
@@ -39,38 +40,28 @@
*/
public class SortValuesSet
{
- private static final int ENCODED_VALUE_SIZE = 16;
- private static final int ENCODED_VALUE_LENGTH_SIZE =
- encodedLengthSize(ENCODED_VALUE_SIZE);
- private static final int ENCODED_ATTRIBUTE_VALUE_SIZE =
- ENCODED_VALUE_LENGTH_SIZE + ENCODED_VALUE_SIZE;
-
- private ID2Entry id2entry;
-
private long[] entryIDs;
+ private int[] valuesBytesOffsets;
+
private byte[] valuesBytes;
private byte[] keyBytes;
- private HashMap<EntryID, AttributeValue[]> cachedAttributeValues;
-
private VLVIndex vlvIndex;
/**
* Construct an empty sort values set with the given information.
*
* @param vlvIndex The VLV index using this set.
- * @param id2entry The ID2Entry database.
*/
- public SortValuesSet(VLVIndex vlvIndex, ID2Entry id2entry)
+ public SortValuesSet(VLVIndex vlvIndex)
{
this.keyBytes = new byte[0];
this.entryIDs = null;
this.valuesBytes = null;
- this.id2entry = id2entry;
+ this.valuesBytesOffsets = null;
this.vlvIndex = vlvIndex;
- this.cachedAttributeValues = new HashMap<EntryID, AttributeValue[]>();
}
/**
@@ -79,16 +70,11 @@
* @param keyBytes The database key used to locate this set.
* @param dataBytes The bytes to decode and construct this set.
* @param vlvIndex The VLV index using this set.
- * @param id2entry The ID2Entry database.
*/
- public SortValuesSet(byte[] keyBytes, byte[] dataBytes, VLVIndex vlvIndex,
- ID2Entry id2entry)
+ public SortValuesSet(byte[] keyBytes, byte[] dataBytes, VLVIndex vlvIndex)
{
this.keyBytes = keyBytes;
- this.id2entry = id2entry;
this.vlvIndex = vlvIndex;
- this.cachedAttributeValues = new HashMap<EntryID, AttributeValue[]>();
-
if(dataBytes == null)
{
entryIDs = new long[0];
@@ -96,22 +82,16 @@
}
entryIDs = getEncodedIDs(dataBytes, 0);
- valuesBytes = new byte[entryIDs.length * ENCODED_ATTRIBUTE_VALUE_SIZE *
- vlvIndex.sortOrder.getSortKeys().length];
- System.arraycopy(dataBytes, entryIDs.length * 8 + 4, valuesBytes, 0,
- valuesBytes.length);
+ int valuesBytesOffset = entryIDs.length * 8 + 4;
+ int valuesBytesLength = dataBytes.length - valuesBytesOffset;
+ valuesBytes = new byte[valuesBytesLength];
+ System.arraycopy(dataBytes, valuesBytesOffset, valuesBytes, 0,
+ valuesBytesLength);
+ this.valuesBytesOffsets = null;
}
- private SortValuesSet(long[] entryIDs, byte[] keyBytes, byte[] valuesBytes,
- VLVIndex vlvIndex, ID2Entry id2entry)
- {
- this.keyBytes = keyBytes;
- this.id2entry = id2entry;
- this.entryIDs = entryIDs;
- this.valuesBytes = valuesBytes;
- this.vlvIndex = vlvIndex;
- this.cachedAttributeValues = new HashMap<EntryID, AttributeValue[]>();
- }
+ private SortValuesSet()
+ {}
/**
* Add the given entryID and values from this VLV idnex.
@@ -137,10 +117,14 @@
entryIDs = new long[1];
entryIDs[0] = entryID;
valuesBytes = attributeValuesToDatabase(values);
+ if(valuesBytesOffsets != null)
+ {
+ valuesBytesOffsets = new int[1];
+ valuesBytesOffsets[0] = 0;
+ }
return true;
}
- if(vlvIndex.comparator.compareValuesInSet(this,
- entryIDs.length - 1, entryID,
+ if(vlvIndex.comparator.compare(this, entryIDs.length - 1, entryID,
values) < 0)
{
long[] updatedEntryIDs = new long[entryIDs.length + 1];
@@ -156,6 +140,17 @@
valuesBytes.length,
newValuesBytes.length);
+ if(valuesBytesOffsets != null)
+ {
+ int[] updatedValuesBytesOffsets =
+ new int[valuesBytesOffsets.length + 1];
+ System.arraycopy(valuesBytesOffsets, 0, updatedValuesBytesOffsets,
+ 0, valuesBytesOffsets.length);
+ updatedValuesBytesOffsets[valuesBytesOffsets.length] =
+ updatedValuesBytes.length - newValuesBytes.length;
+ valuesBytesOffsets = updatedValuesBytesOffsets;
+ }
+
entryIDs = updatedEntryIDs;
valuesBytes = updatedValuesBytes;
return true;
@@ -186,7 +181,7 @@
updatedEntryIDs[pos] = entryID;
byte[] newValuesBytes = attributeValuesToDatabase(values);
- int valuesPos = pos * newValuesBytes.length;
+ int valuesPos = valuesBytesOffsets[pos];
byte[] updatedValuesBytes = new byte[valuesBytes.length +
newValuesBytes.length];
System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0, valuesPos);
@@ -196,6 +191,22 @@
System.arraycopy(newValuesBytes, 0, updatedValuesBytes, valuesPos,
newValuesBytes.length);
+ if(valuesBytesOffsets != null)
+ {
+ int[] updatedValuesBytesOffsets =
+ new int[valuesBytesOffsets.length + 1];
+ System.arraycopy(valuesBytesOffsets, 0, updatedValuesBytesOffsets,
+ 0, pos);
+ // Update the rest of the offsets one by one - Expensive!
+ for(int i = pos; i < valuesBytesOffsets.length; i++)
+ {
+ updatedValuesBytesOffsets[i+1] =
+ valuesBytesOffsets[i] + newValuesBytes.length;
+ }
+ updatedValuesBytesOffsets[pos] = valuesBytesOffsets[pos];
+ valuesBytesOffsets = updatedValuesBytesOffsets;
+ }
+
entryIDs = updatedEntryIDs;
valuesBytes = updatedValuesBytes;
}
@@ -222,6 +233,11 @@
return false;
}
+ if(valuesBytesOffsets == null)
+ {
+ updateValuesBytesOffsets();
+ }
+
int pos = binarySearch(entryID, values);
if(pos < 0)
{
@@ -235,54 +251,93 @@
System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, pos);
System.arraycopy(entryIDs, pos+1, updatedEntryIDs, pos,
entryIDs.length-pos-1);
-
- int valuesLength = ENCODED_ATTRIBUTE_VALUE_SIZE *
- vlvIndex.sortOrder.getSortKeys().length;
- int valuesPos = pos * valuesLength;
+ int valuesLength;
+ int valuesPos = valuesBytesOffsets[pos];
+ if(pos < valuesBytesOffsets.length - 1)
+ {
+ valuesLength = valuesBytesOffsets[pos+1] - valuesPos;
+ }
+ else
+ {
+ valuesLength = valuesBytes.length - valuesPos;
+ }
byte[] updatedValuesBytes = new byte[valuesBytes.length - valuesLength];
System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0, valuesPos);
System.arraycopy(valuesBytes, valuesPos + valuesLength,
updatedValuesBytes, valuesPos,
valuesBytes.length - valuesPos - valuesLength);
+ int[] updatedValuesBytesOffsets = new int[valuesBytesOffsets.length - 1];
+ System.arraycopy(valuesBytesOffsets, 0, updatedValuesBytesOffsets,
+ 0, pos);
+ // Update the rest of the offsets one by one - Expensive!
+ for(int i = pos + 1; i < valuesBytesOffsets.length; i++)
+ {
+ updatedValuesBytesOffsets[i-1] =
+ valuesBytesOffsets[i] - valuesLength;
+ }
+
entryIDs = updatedEntryIDs;
valuesBytes = updatedValuesBytes;
+ valuesBytesOffsets = updatedValuesBytesOffsets;
return true;
}
}
/**
* Split portions of this set into another set. The values of the new set is
- * from the front of this set.
+ * from the end of this set.
*
* @param splitLength The size of the new set.
* @return The split set.
*/
public SortValuesSet split(int splitLength)
{
+ if(valuesBytesOffsets == null)
+ {
+ updateValuesBytesOffsets();
+ }
+
long[] splitEntryIDs = new long[splitLength];
- byte[] splitValuesBytes = new byte[splitLength *
- ENCODED_ATTRIBUTE_VALUE_SIZE * vlvIndex.sortOrder.getSortKeys().length];
+ byte[] splitValuesBytes = new byte[valuesBytes.length -
+ valuesBytesOffsets[valuesBytesOffsets.length - splitLength]];
+ int[] splitValuesBytesOffsets = new int[splitLength];
long[] updatedEntryIDs = new long[entryIDs.length - splitEntryIDs.length];
System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, updatedEntryIDs.length);
System.arraycopy(entryIDs, updatedEntryIDs.length, splitEntryIDs, 0,
splitEntryIDs.length);
- byte[] updatedValuesBytes = new byte[valuesBytes.length -
- splitValuesBytes.length];
+ byte[] updatedValuesBytes =
+ new byte[valuesBytesOffsets[valuesBytesOffsets.length - splitLength]];
System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0,
updatedValuesBytes.length);
System.arraycopy(valuesBytes, updatedValuesBytes.length, splitValuesBytes,
0, splitValuesBytes.length);
- SortValuesSet splitValuesSet = new SortValuesSet(splitEntryIDs,
- keyBytes,
- splitValuesBytes,
- vlvIndex, id2entry);
+ int[] updatedValuesBytesOffsets =
+ new int[valuesBytesOffsets.length - splitValuesBytesOffsets.length];
+ System.arraycopy(valuesBytesOffsets, 0, updatedValuesBytesOffsets,
+ 0, updatedValuesBytesOffsets.length);
+ for(int i = updatedValuesBytesOffsets.length;
+ i < valuesBytesOffsets.length; i++)
+ {
+ splitValuesBytesOffsets[i - updatedValuesBytesOffsets.length] =
+ valuesBytesOffsets[i] -
+ valuesBytesOffsets[updatedValuesBytesOffsets.length];
+ }
+
+ SortValuesSet splitValuesSet = new SortValuesSet();
+
+ splitValuesSet.entryIDs = splitEntryIDs;
+ splitValuesSet.keyBytes = this.keyBytes;
+ splitValuesSet.valuesBytes = splitValuesBytes;
+ splitValuesSet.valuesBytesOffsets = splitValuesBytesOffsets;
+ splitValuesSet.vlvIndex = this.vlvIndex;
entryIDs = updatedEntryIDs;
valuesBytes = updatedValuesBytes;
+ valuesBytesOffsets = updatedValuesBytesOffsets;
keyBytes = null;
return splitValuesSet;
@@ -369,7 +424,7 @@
for(int j = entryIDs.length - 1; i <= j;)
{
int k = i + j >> 1;
- int l = vlvIndex.comparator.compareValuesInSet(this, k, entryID, values);
+ int l = vlvIndex.comparator.compare(this, k, entryID, values);
if(l < 0)
i = k + 1;
else
@@ -407,71 +462,38 @@
return entryIDs;
}
- private static int encodedLengthSize(int length)
- {
- if ((length & 0x000000FF) == length)
- {
- return 1;
- }
- else if ((length & 0x0000FFFF) == length)
- {
- return 2;
- }
- else if ((length & 0x00FFFFFF) == length)
- {
- return 3;
- }
- else
- {
- return 4;
- }
- }
-
private byte[] attributeValuesToDatabase(AttributeValue[] values)
throws DirectoryException
{
- byte[] valuesBytes = new byte[values.length *
- (ENCODED_ATTRIBUTE_VALUE_SIZE)];
- for(int i = 0; i < values.length; i++)
+ int totalValueBytes = 0;
+ LinkedList<byte[]> valueBytes = new LinkedList<byte[]>();
+ for (AttributeValue v : values)
{
- AttributeValue value = values[i];
- int length;
- byte[] lengthBytes = new byte[ENCODED_VALUE_LENGTH_SIZE];
- if(value == null)
+ byte[] vBytes;
+ if(v == null)
{
- length = 0;
+ vBytes = new byte[0];
}
else
{
- byte[] valueBytes = value.getNormalizedValueBytes();
- length = valueBytes.length;
- if(valueBytes.length > ENCODED_VALUE_SIZE)
- {
- System.arraycopy(valueBytes, 0, valuesBytes,
- i * ENCODED_ATTRIBUTE_VALUE_SIZE +
- ENCODED_VALUE_LENGTH_SIZE,
- ENCODED_VALUE_SIZE);
- }
- else
- {
- System.arraycopy(valueBytes, 0, valuesBytes,
- i * ENCODED_ATTRIBUTE_VALUE_SIZE +
- ENCODED_VALUE_LENGTH_SIZE,
- valueBytes.length);
- }
+ vBytes = v.getNormalizedValueBytes();
}
-
- for (int j = ENCODED_VALUE_LENGTH_SIZE - 1; j >= 0; j--)
- {
- lengthBytes[j] = (byte) (length & 0xFF);
- length >>>= 8;
- }
-
- System.arraycopy(lengthBytes, 0, valuesBytes,
- i * (ENCODED_ATTRIBUTE_VALUE_SIZE),
- lengthBytes.length);
+ byte[] vLength = ASN1Element.encodeLength(vBytes.length);
+ valueBytes.add(vLength);
+ valueBytes.add(vBytes);
+ totalValueBytes += vLength.length + vBytes.length;
}
- return valuesBytes;
+
+ byte[] attrBytes = new byte[totalValueBytes];
+
+ int pos = 0;
+ for (byte[] b : valueBytes)
+ {
+ System.arraycopy(b, 0, attrBytes, pos, b.length);
+ pos += b.length;
+ }
+
+ return attrBytes;
}
/**
@@ -496,18 +518,22 @@
return keyBytes;
}
- SortKey[] sortKeys = vlvIndex.sortOrder.getSortKeys();
- int numValues = sortKeys.length;
- AttributeValue[] values =
- new AttributeValue[numValues];
- for (int i = (entryIDs.length - 1) * numValues, j = 0;
- i < entryIDs.length * numValues;
- i++, j++)
+ if(valuesBytesOffsets == null)
{
- values[j] = new AttributeValue(sortKeys[j].getAttributeType(),
- new ASN1OctetString(getValue(i)));
+ updateValuesBytesOffsets();
}
- keyBytes = vlvIndex.encodeKey(entryIDs[entryIDs.length - 1], values);
+
+ int vBytesPos = valuesBytesOffsets[valuesBytesOffsets.length - 1];
+ int vBytesLength = valuesBytes.length - vBytesPos;
+
+ byte[] idBytes =
+ JebFormat.entryIDToDatabase(entryIDs[entryIDs.length - 1]);
+ keyBytes =
+ new byte[vBytesLength + idBytes.length];
+
+ System.arraycopy(valuesBytes, vBytesPos, keyBytes, 0, vBytesLength);
+ System.arraycopy(idBytes, 0, keyBytes, vBytesLength, idBytes.length);
+
return keyBytes;
}
@@ -587,6 +613,34 @@
return new SortValues(id, values, vlvIndex.sortOrder);
}
+ private void updateValuesBytesOffsets()
+ {
+ valuesBytesOffsets = new int[entryIDs.length];
+ int vBytesPos = 0;
+ int numAttributes = vlvIndex.sortOrder.getSortKeys().length;
+
+ for(int pos = 0; pos < entryIDs.length; pos++)
+ {
+ valuesBytesOffsets[pos] = vBytesPos;
+
+ for(int i = 0; i < numAttributes; i++)
+ {
+ int valueLength = valuesBytes[vBytesPos] & 0x7F;
+ if (valueLength != valuesBytes[vBytesPos++])
+ {
+ int valueLengthBytes = valueLength;
+ valueLength = 0;
+ for (int j=0; j < valueLengthBytes; j++, vBytesPos++)
+ {
+ valueLength = (valueLength << 8) | (valuesBytes[vBytesPos] & 0xFF);
+ }
+ }
+
+ vBytesPos += valueLength;
+ }
+ }
+ }
+
/**
* Retrieve an attribute value from this values set. The index is the
* absolute index. (ie. for a sort on 3 attributes per entry, an vlvIndex of 6
@@ -601,52 +655,47 @@
public byte[] getValue(int index)
throws JebException, DatabaseException, DirectoryException
{
- // If values bytes is null, we have to get the value by getting the
- // entry by ID and getting the value.
- if(valuesBytes != null)
+ if(valuesBytesOffsets == null)
{
- int pos = index * ENCODED_ATTRIBUTE_VALUE_SIZE;
- int length = 0;
- byte[] valueBytes;
- for (int k = 0; k < ENCODED_VALUE_LENGTH_SIZE; k++, pos++)
+ updateValuesBytesOffsets();
+ }
+ int numAttributes = vlvIndex.sortOrder.getSortKeys().length;
+ int vIndex = index / numAttributes;
+ int vOffset = index % numAttributes;
+ int vBytesPos = valuesBytesOffsets[vIndex];
+
+ // Find the desired value in the sort order set.
+ for(int i = 0; i <= vOffset; i++)
+ {
+ int valueLength = valuesBytes[vBytesPos] & 0x7F;
+ if (valueLength != valuesBytes[vBytesPos++])
{
- length <<= 8;
- length |= (valuesBytes[pos] & 0xFF);
+ int valueLengthBytes = valueLength;
+ valueLength = 0;
+ for (int j=0; j < valueLengthBytes; j++, vBytesPos++)
+ {
+ valueLength = (valueLength << 8) | (valuesBytes[vBytesPos] & 0xFF);
+ }
}
- if(length == 0)
+ if(i == vOffset)
{
- return null;
+ if(valueLength == 0)
+ {
+ return null;
+ }
+ else
+ {
+ byte[] valueBytes = new byte[valueLength];
+ System.arraycopy(valuesBytes, vBytesPos, valueBytes, 0, valueLength);
+ return valueBytes;
+ }
}
- // If the value has exceeded the max value size, we have to get the
- // value by getting the entry by ID.
- else if(length <= ENCODED_VALUE_SIZE && length > 0)
+ else
{
- valueBytes = new byte[length];
- System.arraycopy(valuesBytes, pos, valueBytes, 0, length);
-
- return valueBytes;
+ vBytesPos += valueLength;
}
}
-
- if(id2entry == null)
- {
- return new byte[0];
- }
-
- // Get the entry from id2entry and assign the values from the entry.
- // Once the values are assigned from the retrieved entry, it will
- // not be retrieve again from future compares.
- EntryID id = new EntryID(entryIDs[index /
- vlvIndex.sortOrder.getSortKeys().length]);
- AttributeValue[] values = cachedAttributeValues.get(id);
- if(values == null)
- {
- values = vlvIndex.getSortValues(id2entry.get(null, id));
- cachedAttributeValues.put(id, values);
- }
- int offset = index % values.length;
- return values[offset].getNormalizedValueBytes();
+ return new byte[0];
}
-
}
--
Gitblit v1.10.0