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