OPENDJ-1711 - re-implement VLV support for pluggable backends

Matthew Swift

02.16.2015 df310fa66969c2058dbb1f8f23e90a4d717df44c

OPENDJ-1711 - re-implement VLV support for pluggable backends

Add unit tests for key encoding:

* fixed a bug where bytes were incorrectly escaped in descending order
* optimized null key encoding
* added Javadoc describing key encoding logic.

 opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java

@@ -607,7 +607,7 @@
      final ByteStringBuilder encodedPrimaryKey = new ByteStringBuilder(assertion.length() + 10);
      final MatchingRule matchingRule = primarySortKey.getAttributeType().getOrderingMatchingRule();
      final ByteString normalizedAttributeValue = matchingRule.normalizeAttributeValue(assertion);
      encodeVLVKeyValue(primarySortKey, normalizedAttributeValue, encodedPrimaryKey);
      encodeVLVKeyValue(normalizedAttributeValue, encodedPrimaryKey, primarySortKey.ascending());
      return encodedPrimaryKey;
    }
    catch (final DecodeException e)
@@ -803,37 +803,61 @@
          }
        }
      }
      encodeVLVKeyValue(sortKey, sortValue, builder);
      encodeVLVKeyValue(sortValue, builder, sortKey.ascending());
    }
  }

  private static void encodeVLVKeyValue(final SortKey sortKey, final ByteString normalizedAttributeValue,
      final ByteStringBuilder builder)
  /**
   * Package private for testing.
   * <p>
   * Keys are logically encoded as follows:
   * <ul>
   * <li>if the key is {@code null} then append {@code 0xff} in order to ensure that all
   * {@code null} keys sort after non-{@code null} keys in ascending order
   * <li>else
   * <ul>
   * <li>escape any bytes that look like a separator byte ({@code 0x00}) or a separator escape byte
   * ({@code 0x01}) by prefixing the byte with a separator escape byte ({@code 0x01})
   * <li>escape the first byte if it looks like a null key byte ({@code 0xff}) or a null key escape
   * byte ({@code 0xfe}) by prefixing the byte with a null key escape byte ({@code 0xfe})
   * </ul>
   * <li>append a separator byte ({@code 0x00}) which will be used for distinguishing between the
   * end of the key and the start of the next key
   * <li>invert all the bytes if the sort order is descending.
   * </ul>
   */
  static void encodeVLVKeyValue(final ByteString keyBytes, final ByteStringBuilder builder,
      final boolean ascending)
  {
    final boolean ascending = sortKey.ascending();
    final byte separator = ascending ? (byte) 0x00 : (byte) 0xff;
    if (normalizedAttributeValue != null)
    if (keyBytes != null)
    {
      // Ensure that all keys sort before (ascending) or after (descending) missing keys.
      builder.append(separator);

      final byte escape = ascending ? (byte) 0x01 : (byte) 0xfe;
      final byte sortOrderMask = separator;
      final int length = normalizedAttributeValue.length();
      final int length = keyBytes.length();
      for (int i = 0; i < length; i++)
      {
        final byte b = normalizedAttributeValue.byteAt(i);
        if (b == separator || b == escape)
        final byte b = keyBytes.byteAt(i);
        if ((b & (byte) 0x01) == b)
        {
          // Escape bytes that look like a separator.
          builder.append(escape);
        }
        else if (i == 0 && (b & (byte) 0xfe) == (byte) 0xfe)
        {
          /*
           * Ensure that all keys sort before (ascending) or after (descending) null keys, by
           * escaping the first byte if it looks like a null key.
           */
          builder.append((byte) ~escape);
        }
        // Invert the bits if this key is in descending order.
        builder.append((byte) (b ^ sortOrderMask));
      }
    }
    else
    {
      // Ensure that missing keys sort after (ascending) or before (descending) all other keys.
      // Ensure that null keys sort after (ascending) or before (descending) all other keys.
      builder.append(ascending ? (byte) 0xff : (byte) 0x00);
    }
    builder.append(separator);

 opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/ControlsTestCase.java

@@ -43,6 +43,7 @@

import org.forgerock.opendj.config.server.ConfigException;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;
import org.forgerock.opendj.ldap.ResultCode;
import org.forgerock.opendj.ldap.SearchScope;
import org.opends.server.DirectoryServerTestCase;
@@ -169,6 +170,76 @@
  }

  @DataProvider
  private Object[][] encodedKeyDataProvider()
  {
    // @formatter:off
    return new Object[][] {
      // Null keys sort after everything else.
      { null,           null,           0 },
      { "",             null,          -1 },
      { null,           "",             1 },
      { "00",           null,          -1 },
      { null,           "00",           1 },
      { "ff",           null,          -1 },
      { null,           "ff",           1 },

      // Empty keys sort before everything else.
      { "",             "",             0 },
      { "00",           "",             1 },
      { "",             "00",          -1 },
      { "ff",           "",             1 },
      { "",             "ff",          -1 },

      // Bytes comparisons are unsigned.
      { "00",           "00",           0 },
      { "00",           "ff",          -1 },
      { "ff",           "00",           1 },
      { "ff",           "ff",           0 },

      // Short keys sort before long keys.
      { "0000",         "00",           1 },
      { "00",           "0000",        -1 },
      { "ffff",         "ff",           1 },
      { "ff",           "ffff",        -1 },
      { "0000",         "0000",         0 },
      { "ffff",         "ffff",         0 },
      { "0000",         "ffff",        -1 },
      { "ffff",         "0000",         1 },
    };
    // @formatter:on
  }

  @Test(dataProvider = "encodedKeyDataProvider")
  public void vlvKeyEncodingGenerateCorrectAscendingSortOrder(String key1, String key2, int expectedCompareResult)
  {
    ByteString bytes1 = key1 != null ? ByteString.valueOfHex(key1) : null;
    ByteStringBuilder encodedBytes1 = new ByteStringBuilder();
    VLVIndex.encodeVLVKeyValue(bytes1, encodedBytes1, true);

    ByteString bytes2 = key2 != null ? ByteString.valueOfHex(key2) : null;
    ByteStringBuilder encodedBytes2 = new ByteStringBuilder();
    VLVIndex.encodeVLVKeyValue(bytes2, encodedBytes2, true);

    int actualResult = Math.min(Math.max(encodedBytes1.compareTo(encodedBytes2), -1), 1);
    assertThat(actualResult).isEqualTo(expectedCompareResult);
  }

  @Test(dataProvider = "encodedKeyDataProvider")
  public void vlvKeyEncodingGenerateCorrectDescendingSortOrder(String key1, String key2, int expectedCompareResult)
  {
    ByteString bytes1 = key1 != null ? ByteString.valueOfHex(key1) : null;
    ByteStringBuilder encodedBytes1 = new ByteStringBuilder();
    VLVIndex.encodeVLVKeyValue(bytes1, encodedBytes1, false);

    ByteString bytes2 = key2 != null ? ByteString.valueOfHex(key2) : null;
    ByteStringBuilder encodedBytes2 = new ByteStringBuilder();
    VLVIndex.encodeVLVKeyValue(bytes2, encodedBytes2, false);

    int actualResult = Math.min(Math.max(encodedBytes1.compareTo(encodedBytes2), -1), 1);
    assertThat(actualResult).isEqualTo(-expectedCompareResult);
  }

  @DataProvider
  private Object[][] indexedVlvByAssertionDataProvider()
  {
    // @formatter:off