001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.regionserver;
019
020import static org.junit.Assert.assertEquals;
021import static org.junit.Assert.assertFalse;
022import static org.junit.Assert.assertNotNull;
023import static org.junit.Assert.assertTrue;
024
025import java.lang.management.ManagementFactory;
026import java.nio.ByteBuffer;
027import java.util.Iterator;
028import java.util.NavigableMap;
029import java.util.NavigableSet;
030import java.util.SortedSet;
031import org.apache.hadoop.conf.Configuration;
032import org.apache.hadoop.hbase.Cell;
033import org.apache.hadoop.hbase.CellComparator;
034import org.apache.hadoop.hbase.CellUtil;
035import org.apache.hadoop.hbase.HBaseClassTestRule;
036import org.apache.hadoop.hbase.KeyValue;
037import org.apache.hadoop.hbase.KeyValueUtil;
038import org.apache.hadoop.hbase.io.util.MemorySizeUtil;
039import org.apache.hadoop.hbase.regionserver.ChunkCreator.ChunkType;
040import org.apache.hadoop.hbase.testclassification.RegionServerTests;
041import org.apache.hadoop.hbase.testclassification.SmallTests;
042import org.apache.hadoop.hbase.util.ByteBufferUtils;
043import org.apache.hadoop.hbase.util.Bytes;
044import org.apache.hadoop.hbase.util.ClassSize;
045import org.junit.Before;
046import org.junit.ClassRule;
047import org.junit.Test;
048import org.junit.experimental.categories.Category;
049import org.junit.runner.RunWith;
050import org.junit.runners.Parameterized;
051
052@Category({ RegionServerTests.class, SmallTests.class })
053@RunWith(Parameterized.class)
054public class TestCellFlatSet {
055
056  @ClassRule
057  public static final HBaseClassTestRule CLASS_RULE =
058    HBaseClassTestRule.forClass(TestCellFlatSet.class);
059
060  @Parameterized.Parameters
061  public static Object[] data() {
062    return new Object[] { "SMALL_CHUNKS", "NORMAL_CHUNKS" }; // test with different chunk sizes
063  }
064
065  private static final int NUM_OF_CELLS = 4;
066  private static final int SMALL_CHUNK_SIZE = 64;
067  private Cell ascCells[];
068  private CellArrayMap ascCbOnHeap;
069  private Cell descCells[];
070  private CellArrayMap descCbOnHeap;
071  private final static Configuration CONF = new Configuration();
072  private KeyValue lowerOuterCell;
073  private KeyValue upperOuterCell;
074
075  private CellChunkMap ascCCM; // for testing ascending CellChunkMap with one chunk in array
076  private CellChunkMap descCCM; // for testing descending CellChunkMap with one chunk in array
077  private final boolean smallChunks;
078  private static ChunkCreator chunkCreator;
079
080  public TestCellFlatSet(String chunkType) {
081    long globalMemStoreLimit =
082      (long) (ManagementFactory.getMemoryMXBean().getHeapMemoryUsage().getMax()
083        * MemorySizeUtil.getGlobalMemStoreHeapPercent(CONF, false));
084    if (chunkType.equals("NORMAL_CHUNKS")) {
085      chunkCreator = ChunkCreator.initialize(MemStoreLAB.CHUNK_SIZE_DEFAULT, false,
086        globalMemStoreLimit, 0.2f, MemStoreLAB.POOL_INITIAL_SIZE_DEFAULT, null,
087        MemStoreLAB.INDEX_CHUNK_SIZE_PERCENTAGE_DEFAULT);
088      assertNotNull(chunkCreator);
089      smallChunks = false;
090    } else {
091      // chunkCreator with smaller chunk size, so only 3 cell-representations can accommodate a
092      // chunk
093      chunkCreator = ChunkCreator.initialize(SMALL_CHUNK_SIZE, false, globalMemStoreLimit, 0.2f,
094        MemStoreLAB.POOL_INITIAL_SIZE_DEFAULT, null,
095        MemStoreLAB.INDEX_CHUNK_SIZE_PERCENTAGE_DEFAULT);
096      assertNotNull(chunkCreator);
097      smallChunks = true;
098    }
099  }
100
101  @Before
102  public void setUp() throws Exception {
103    // create array of Cells to bass to the CellFlatMap under CellSet
104    final byte[] one = Bytes.toBytes(15);
105    final byte[] two = Bytes.toBytes(25);
106    final byte[] three = Bytes.toBytes(35);
107    final byte[] four = Bytes.toBytes(45);
108
109    final byte[] f = Bytes.toBytes("f");
110    final byte[] q = Bytes.toBytes("q");
111    final byte[] v = Bytes.toBytes(4);
112
113    final KeyValue kv1 = new KeyValue(one, f, q, 10, v);
114    final KeyValue kv2 = new KeyValue(two, f, q, 20, v);
115    final KeyValue kv3 = new KeyValue(three, f, q, 30, v);
116    final KeyValue kv4 = new KeyValue(four, f, q, 40, v);
117    lowerOuterCell = new KeyValue(Bytes.toBytes(10), f, q, 10, v);
118    upperOuterCell = new KeyValue(Bytes.toBytes(50), f, q, 10, v);
119    ascCells = new Cell[] { kv1, kv2, kv3, kv4 };
120    ascCbOnHeap = new CellArrayMap(CellComparator.getInstance(), ascCells, 0, NUM_OF_CELLS, false);
121    descCells = new Cell[] { kv4, kv3, kv2, kv1 };
122    descCbOnHeap = new CellArrayMap(CellComparator.getInstance(), descCells, 0, NUM_OF_CELLS, true);
123
124    CONF.setBoolean(MemStoreLAB.USEMSLAB_KEY, true);
125    CONF.setFloat(MemStoreLAB.CHUNK_POOL_MAXSIZE_KEY, 0.2f);
126    ChunkCreator.chunkPoolDisabled = false;
127
128    // create ascending and descending CellChunkMaps
129    // according to parameter, once built with normal chunks and at second with small chunks
130    ascCCM = setUpCellChunkMap(true);
131    descCCM = setUpCellChunkMap(false);
132
133    if (smallChunks) { // check jumbo chunks as well
134      ascCCM = setUpJumboCellChunkMap(true);
135    }
136  }
137
138  /* Create and test ascending CellSet based on CellArrayMap */
139  @Test
140  public void testCellArrayMapAsc() throws Exception {
141    CellSet cs = new CellSet(ascCbOnHeap);
142    testCellBlocks(cs);
143    testIterators(cs);
144  }
145
146  /* Create and test ascending and descending CellSet based on CellChunkMap */
147  @Test
148  public void testCellChunkMap() throws Exception {
149    CellSet cs = new CellSet(ascCCM);
150    testCellBlocks(cs);
151    testIterators(cs);
152    testSubSet(cs);
153    cs = new CellSet(descCCM);
154    testSubSet(cs);
155    // cs = new CellSet(ascMultCCM);
156    // testCellBlocks(cs);
157    // testSubSet(cs);
158    // cs = new CellSet(descMultCCM);
159    // testSubSet(cs);
160  }
161
162  @Test
163  public void testAsc() throws Exception {
164    CellSet ascCs = new CellSet(ascCbOnHeap);
165    assertEquals(NUM_OF_CELLS, ascCs.size());
166    testSubSet(ascCs);
167  }
168
169  @Test
170  public void testDesc() throws Exception {
171    CellSet descCs = new CellSet(descCbOnHeap);
172    assertEquals(NUM_OF_CELLS, descCs.size());
173    testSubSet(descCs);
174  }
175
176  private void testSubSet(CellSet cs) throws Exception {
177    for (int i = 0; i != ascCells.length; ++i) {
178      NavigableSet<Cell> excludeTail = cs.tailSet(ascCells[i], false);
179      NavigableSet<Cell> includeTail = cs.tailSet(ascCells[i], true);
180      assertEquals(ascCells.length - 1 - i, excludeTail.size());
181      assertEquals(ascCells.length - i, includeTail.size());
182      Iterator<Cell> excludeIter = excludeTail.iterator();
183      Iterator<Cell> includeIter = includeTail.iterator();
184      for (int j = 1 + i; j != ascCells.length; ++j) {
185        assertEquals(true, CellUtil.equals(excludeIter.next(), ascCells[j]));
186      }
187      for (int j = i; j != ascCells.length; ++j) {
188        assertEquals(true, CellUtil.equals(includeIter.next(), ascCells[j]));
189      }
190    }
191    assertEquals(NUM_OF_CELLS, cs.tailSet(lowerOuterCell, false).size());
192    assertEquals(0, cs.tailSet(upperOuterCell, false).size());
193    for (int i = 0; i != ascCells.length; ++i) {
194      NavigableSet<Cell> excludeHead = cs.headSet(ascCells[i], false);
195      NavigableSet<Cell> includeHead = cs.headSet(ascCells[i], true);
196      assertEquals(i, excludeHead.size());
197      assertEquals(i + 1, includeHead.size());
198      Iterator<Cell> excludeIter = excludeHead.iterator();
199      Iterator<Cell> includeIter = includeHead.iterator();
200      for (int j = 0; j != i; ++j) {
201        assertEquals(true, CellUtil.equals(excludeIter.next(), ascCells[j]));
202      }
203      for (int j = 0; j != i + 1; ++j) {
204        assertEquals(true, CellUtil.equals(includeIter.next(), ascCells[j]));
205      }
206    }
207    assertEquals(0, cs.headSet(lowerOuterCell, false).size());
208    assertEquals(NUM_OF_CELLS, cs.headSet(upperOuterCell, false).size());
209
210    NavigableMap<Cell, Cell> sub =
211      cs.getDelegatee().subMap(lowerOuterCell, true, upperOuterCell, true);
212    assertEquals(NUM_OF_CELLS, sub.size());
213    Iterator<Cell> iter = sub.values().iterator();
214    for (int i = 0; i != ascCells.length; ++i) {
215      assertEquals(true, CellUtil.equals(iter.next(), ascCells[i]));
216    }
217  }
218
219  /* Generic basic test for immutable CellSet */
220  private void testCellBlocks(CellSet cs) throws Exception {
221    final byte[] oneAndHalf = Bytes.toBytes(20);
222    final byte[] f = Bytes.toBytes("f");
223    final byte[] q = Bytes.toBytes("q");
224    final byte[] v = Bytes.toBytes(4);
225    final KeyValue outerCell = new KeyValue(oneAndHalf, f, q, 10, v);
226
227    assertEquals(NUM_OF_CELLS, cs.size()); // check size
228    assertFalse(cs.contains(outerCell)); // check outer cell
229
230    assertTrue(cs.contains(ascCells[0])); // check existence of the first
231    Cell first = cs.first();
232    assertTrue(ascCells[0].equals(first));
233
234    assertTrue(cs.contains(ascCells[NUM_OF_CELLS - 1])); // check last
235    Cell last = cs.last();
236    assertTrue(ascCells[NUM_OF_CELLS - 1].equals(last));
237
238    SortedSet<Cell> tail = cs.tailSet(ascCells[1]); // check tail abd head sizes
239    assertEquals(NUM_OF_CELLS - 1, tail.size());
240    SortedSet<Cell> head = cs.headSet(ascCells[1]);
241    assertEquals(1, head.size());
242
243    SortedSet<Cell> tailOuter = cs.tailSet(outerCell); // check tail starting from outer cell
244    assertEquals(NUM_OF_CELLS - 1, tailOuter.size());
245
246    Cell tailFirst = tail.first();
247    assertTrue(ascCells[1].equals(tailFirst));
248    Cell tailLast = tail.last();
249    assertTrue(ascCells[NUM_OF_CELLS - 1].equals(tailLast));
250
251    Cell headFirst = head.first();
252    assertTrue(ascCells[0].equals(headFirst));
253    Cell headLast = head.last();
254    assertTrue(ascCells[0].equals(headLast));
255  }
256
257  /* Generic iterators test for immutable CellSet */
258  private void testIterators(CellSet cs) throws Exception {
259
260    // Assert that we have NUM_OF_CELLS values and that they are in order
261    int count = 0;
262    for (Cell kv : cs) {
263      assertEquals(
264        "\n\n-------------------------------------------------------------------\n"
265          + "Comparing iteration number " + (count + 1) + " the returned cell: " + kv
266          + ", the first Cell in the CellBlocksMap: " + ascCells[count]
267          + ", and the same transformed to String: " + ascCells[count].toString()
268          + "\n-------------------------------------------------------------------\n",
269        ascCells[count], kv);
270      count++;
271    }
272    assertEquals(NUM_OF_CELLS, count);
273
274    // Test descending iterator
275    count = 0;
276    for (Iterator<Cell> i = cs.descendingIterator(); i.hasNext();) {
277      Cell kv = i.next();
278      assertEquals(ascCells[NUM_OF_CELLS - (count + 1)], kv);
279      count++;
280    }
281    assertEquals(NUM_OF_CELLS, count);
282  }
283
284  /* Create CellChunkMap with four cells inside the index chunk */
285  private CellChunkMap setUpCellChunkMap(boolean asc) {
286
287    // allocate new chunks and use the data chunk to hold the full data of the cells
288    // and the index chunk to hold the cell-representations
289    Chunk dataChunk = chunkCreator.getChunk();
290    Chunk idxChunk = chunkCreator.getChunk();
291    // the array of index chunks to be used as a basis for CellChunkMap
292    Chunk chunkArray[] = new Chunk[8]; // according to test currently written 8 is way enough
293    int chunkArrayIdx = 0;
294    chunkArray[chunkArrayIdx++] = idxChunk;
295
296    ByteBuffer idxBuffer = idxChunk.getData(); // the buffers of the chunks
297    ByteBuffer dataBuffer = dataChunk.getData();
298    int dataOffset = ChunkCreator.SIZEOF_CHUNK_HEADER; // offset inside data buffer
299    int idxOffset = ChunkCreator.SIZEOF_CHUNK_HEADER; // skip the space for chunk ID
300
301    Cell[] cellArray = asc ? ascCells : descCells;
302
303    for (Cell kv : cellArray) {
304      // do we have enough space to write the cell data on the data chunk?
305      if (dataOffset + kv.getSerializedSize() > chunkCreator.getChunkSize()) {
306        // allocate more data chunks if needed
307        dataChunk = chunkCreator.getChunk();
308        dataBuffer = dataChunk.getData();
309        dataOffset = ChunkCreator.SIZEOF_CHUNK_HEADER;
310      }
311      int dataStartOfset = dataOffset;
312      dataOffset = KeyValueUtil.appendTo(kv, dataBuffer, dataOffset, false); // write deep cell data
313
314      // do we have enough space to write the cell-representation on the index chunk?
315      if (idxOffset + ClassSize.CELL_CHUNK_MAP_ENTRY > chunkCreator.getChunkSize()) {
316        // allocate more index chunks if needed
317        idxChunk = chunkCreator.getChunk();
318        idxBuffer = idxChunk.getData();
319        idxOffset = ChunkCreator.SIZEOF_CHUNK_HEADER;
320        chunkArray[chunkArrayIdx++] = idxChunk;
321      }
322      idxOffset = ByteBufferUtils.putInt(idxBuffer, idxOffset, dataChunk.getId()); // write data
323                                                                                   // chunk id
324      idxOffset = ByteBufferUtils.putInt(idxBuffer, idxOffset, dataStartOfset); // offset
325      idxOffset = ByteBufferUtils.putInt(idxBuffer, idxOffset, kv.getSerializedSize()); // length
326      idxOffset = ByteBufferUtils.putLong(idxBuffer, idxOffset, kv.getSequenceId()); // seqId
327    }
328
329    return new CellChunkMap(CellComparator.getInstance(), chunkArray, 0, NUM_OF_CELLS, !asc);
330  }
331
332  /*
333   * Create CellChunkMap with four cells inside the data jumbo chunk. This test is working only with
334   * small chunks sized SMALL_CHUNK_SIZE (64) bytes
335   */
336  private CellChunkMap setUpJumboCellChunkMap(boolean asc) {
337    int smallChunkSize = SMALL_CHUNK_SIZE + 8;
338    // allocate new chunks and use the data JUMBO chunk to hold the full data of the cells
339    // and the normal index chunk to hold the cell-representations
340    Chunk dataJumboChunk = chunkCreator.getChunk(ChunkType.JUMBO_CHUNK, smallChunkSize);
341    assertTrue(dataJumboChunk.isJumbo());
342    Chunk idxChunk = chunkCreator.getChunk();
343    // the array of index chunks to be used as a basis for CellChunkMap
344    Chunk[] chunkArray = new Chunk[8]; // according to test currently written 8 is way enough
345    int chunkArrayIdx = 0;
346    chunkArray[chunkArrayIdx++] = idxChunk;
347
348    ByteBuffer idxBuffer = idxChunk.getData(); // the buffers of the chunks
349    ByteBuffer dataBuffer = dataJumboChunk.getData();
350    int dataOffset = ChunkCreator.SIZEOF_CHUNK_HEADER; // offset inside data buffer
351    int idxOffset = ChunkCreator.SIZEOF_CHUNK_HEADER; // skip the space for chunk ID
352
353    Cell[] cellArray = asc ? ascCells : descCells;
354
355    for (Cell kv : cellArray) {
356      int dataStartOfset = dataOffset;
357      dataOffset = KeyValueUtil.appendTo(kv, dataBuffer, dataOffset, false); // write deep cell data
358
359      // do we have enough space to write the cell-representation on the index chunk?
360      if (idxOffset + ClassSize.CELL_CHUNK_MAP_ENTRY > chunkCreator.getChunkSize()) {
361        // allocate more index chunks if needed
362        idxChunk = chunkCreator.getChunk();
363        idxBuffer = idxChunk.getData();
364        idxOffset = ChunkCreator.SIZEOF_CHUNK_HEADER;
365        chunkArray[chunkArrayIdx++] = idxChunk;
366      }
367      // write data chunk id
368      idxOffset = ByteBufferUtils.putInt(idxBuffer, idxOffset, dataJumboChunk.getId());
369      idxOffset = ByteBufferUtils.putInt(idxBuffer, idxOffset, dataStartOfset); // offset
370      idxOffset = ByteBufferUtils.putInt(idxBuffer, idxOffset, kv.getSerializedSize()); // length
371      idxOffset = ByteBufferUtils.putLong(idxBuffer, idxOffset, kv.getSequenceId()); // seqId
372
373      // Jumbo chunks are working only with one cell per chunk, thus always allocate a new jumbo
374      // data chunk for next cell
375      dataJumboChunk = chunkCreator.getChunk(ChunkType.JUMBO_CHUNK, smallChunkSize);
376      assertTrue(dataJumboChunk.isJumbo());
377      dataBuffer = dataJumboChunk.getData();
378      dataOffset = ChunkCreator.SIZEOF_CHUNK_HEADER;
379    }
380
381    return new CellChunkMap(CellComparator.getInstance(), chunkArray, 0, NUM_OF_CELLS, !asc);
382  }
383}