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 java.io.IOException;
021import java.nio.ByteBuffer;
022import org.apache.hadoop.hbase.ByteBufferKeyValue;
023import org.apache.hadoop.hbase.CellComparator;
024import org.apache.hadoop.hbase.CellUtil;
025import org.apache.hadoop.hbase.ExtendedCell;
026import org.apache.hadoop.hbase.KeyValue;
027import org.apache.hadoop.hbase.util.ByteBufferUtils;
028import org.apache.hadoop.hbase.util.ClassSize;
029import org.apache.yetus.audience.InterfaceAudience;
030
031/**
032 * CellChunkImmutableSegment extends the API supported by a {@link Segment}, and
033 * {@link ImmutableSegment}. This immutable segment is working with CellSet with CellChunkMap
034 * delegatee.
035 */
036@InterfaceAudience.Private
037public class CellChunkImmutableSegment extends ImmutableSegment {
038
039  public static final long DEEP_OVERHEAD_CCM =
040    ImmutableSegment.DEEP_OVERHEAD + ClassSize.CELL_CHUNK_MAP;
041  public static final float INDEX_CHUNK_UNUSED_SPACE_PRECENTAGE = 0.1f;
042
043  ///////////////////// CONSTRUCTORS /////////////////////
044  /**
045   * ------------------------------------------------------------------------ C-tor to be used when
046   * new CellChunkImmutableSegment is built as a result of compaction/merge of a list of older
047   * ImmutableSegments. The given iterator returns the Cells that "survived" the compaction.
048   */
049  protected CellChunkImmutableSegment(CellComparator comparator, MemStoreSegmentsIterator iterator,
050    MemStoreLAB memStoreLAB, int numOfCells, MemStoreCompactionStrategy.Action action) {
051    super(null, comparator, memStoreLAB); // initialize the CellSet with NULL
052    long indexOverhead = DEEP_OVERHEAD_CCM;
053    // memStoreLAB cannot be null in this class
054    boolean onHeap = getMemStoreLAB().isOnHeap();
055    // initiate the heapSize with the size of the segment metadata
056    if (onHeap) {
057      incMemStoreSize(0, indexOverhead, 0, 0);
058    } else {
059      incMemStoreSize(0, 0, indexOverhead, 0);
060    }
061    // build the new CellSet based on CellArrayMap and update the CellSet of the new Segment
062    initializeCellSet(numOfCells, iterator, action);
063  }
064
065  /**
066   * ------------------------------------------------------------------------ C-tor to be used when
067   * new CellChunkImmutableSegment is built as a result of flattening of CSLMImmutableSegment The
068   * given iterator returns the Cells that "survived" the compaction.
069   */
070  protected CellChunkImmutableSegment(CSLMImmutableSegment segment, MemStoreSizing memstoreSizing,
071    MemStoreCompactionStrategy.Action action) {
072    super(segment); // initiailize the upper class
073    long indexOverhead = -CSLMImmutableSegment.DEEP_OVERHEAD_CSLM + DEEP_OVERHEAD_CCM;
074    // memStoreLAB cannot be null in this class
075    boolean onHeap = getMemStoreLAB().isOnHeap();
076    // initiate the heapSize with the size of the segment metadata
077    if (onHeap) {
078      incMemStoreSize(0, indexOverhead, 0, 0);
079      memstoreSizing.incMemStoreSize(0, indexOverhead, 0, 0);
080    } else {
081      incMemStoreSize(0, -CSLMImmutableSegment.DEEP_OVERHEAD_CSLM, DEEP_OVERHEAD_CCM, 0);
082      memstoreSizing.incMemStoreSize(0, -CSLMImmutableSegment.DEEP_OVERHEAD_CSLM, DEEP_OVERHEAD_CCM,
083        0);
084    }
085    int numOfCells = segment.getCellsCount();
086    // build the new CellSet based on CellChunkMap
087    reinitializeCellSet(numOfCells, segment.getScanner(Long.MAX_VALUE), segment.getCellSet(),
088      memstoreSizing, action);
089    // arrange the meta-data size, decrease all meta-data sizes related to SkipList;
090    // add sizes of CellChunkMap entry, decrease also Cell object sizes
091    // (reinitializeCellSet doesn't take the care for the sizes)
092    long newSegmentSizeDelta =
093      numOfCells * (indexEntrySize() - ClassSize.CONCURRENT_SKIPLISTMAP_ENTRY);
094    if (onHeap) {
095      incMemStoreSize(0, newSegmentSizeDelta, 0, 0);
096      memstoreSizing.incMemStoreSize(0, newSegmentSizeDelta, 0, 0);
097    } else {
098      incMemStoreSize(0, 0, newSegmentSizeDelta, 0);
099      memstoreSizing.incMemStoreSize(0, 0, newSegmentSizeDelta, 0);
100
101    }
102  }
103
104  @Override
105  protected long indexEntryOnHeapSize(boolean onHeap) {
106    if (onHeap) {
107      return indexEntrySize();
108    }
109    // else the index is allocated off-heap
110    return 0;
111  }
112
113  @Override
114  protected long indexEntryOffHeapSize(boolean offHeap) {
115    if (offHeap) {
116      return indexEntrySize();
117    }
118    // else the index is allocated on-heap
119    return 0;
120  }
121
122  @Override
123  protected long indexEntrySize() {
124    return ((long) ClassSize.CELL_CHUNK_MAP_ENTRY - KeyValue.FIXED_OVERHEAD);
125  }
126
127  @Override
128  protected boolean canBeFlattened() {
129    return false;
130  }
131
132  ///////////////////// PRIVATE METHODS /////////////////////
133  /*------------------------------------------------------------------------*/
134  // Create CellSet based on CellChunkMap from compacting iterator
135  private void initializeCellSet(int numOfCells, MemStoreSegmentsIterator iterator,
136    MemStoreCompactionStrategy.Action action) {
137    int numOfCellsAfterCompaction = 0;
138    int currentChunkIdx = 0;
139    int offsetInCurentChunk = ChunkCreator.SIZEOF_CHUNK_HEADER;
140    int numUniqueKeys = 0;
141    ExtendedCell prev = null;
142    Chunk[] chunks = allocIndexChunks(numOfCells);
143    while (iterator.hasNext()) { // the iterator hides the elimination logic for compaction
144      boolean alreadyCopied = false;
145      ExtendedCell c = iterator.next();
146      numOfCellsAfterCompaction++;
147      if (c.getChunkId() == ExtendedCell.CELL_NOT_BASED_ON_CHUNK) {
148        // CellChunkMap assumes all cells are allocated on MSLAB.
149        // Therefore, cells which are not allocated on MSLAB initially,
150        // are copied into MSLAB here.
151        c = copyCellIntoMSLAB(c, null); // no memstore sizing object to update
152        alreadyCopied = true;
153      }
154      if (offsetInCurentChunk + ClassSize.CELL_CHUNK_MAP_ENTRY > chunks[currentChunkIdx].size) {
155        currentChunkIdx++; // continue to the next index chunk
156        offsetInCurentChunk = ChunkCreator.SIZEOF_CHUNK_HEADER;
157      }
158      if (action == MemStoreCompactionStrategy.Action.COMPACT && !alreadyCopied) {
159
160        // For compaction copy cell to the new segment (MSLAB copy),here we set forceCloneOfBigCell
161        // to true, because the chunk which the cell is allocated may be freed after the compaction
162        // is completed, see HBASE-27464.
163        c = maybeCloneWithAllocator(c, true);
164      }
165      offsetInCurentChunk = // add the Cell reference to the index chunk
166        createCellReference((ByteBufferKeyValue) c, chunks[currentChunkIdx].getData(),
167          offsetInCurentChunk);
168      // the sizes still need to be updated in the new segment
169      // second parameter true, because in compaction/merge the addition of the cell to new segment
170      // is always successful
171      updateMetaInfo(c, true, null); // updates the size per cell
172      if (action == MemStoreCompactionStrategy.Action.MERGE_COUNT_UNIQUE_KEYS) {
173        // counting number of unique keys
174        if (prev != null) {
175          if (!CellUtil.matchingRowColumnBytes(prev, c)) {
176            numUniqueKeys++;
177          }
178        } else {
179          numUniqueKeys++;
180        }
181      }
182      prev = c;
183    }
184    if (action == MemStoreCompactionStrategy.Action.COMPACT) {
185      numUniqueKeys = numOfCells;
186    } else if (action != MemStoreCompactionStrategy.Action.MERGE_COUNT_UNIQUE_KEYS) {
187      numUniqueKeys = CellSet.UNKNOWN_NUM_UNIQUES;
188    }
189    // build the immutable CellSet
190    CellChunkMap<ExtendedCell> ccm =
191      new CellChunkMap<>(getComparator(), chunks, 0, numOfCellsAfterCompaction, false);
192    this.setCellSet(null, new CellSet<>(ccm, numUniqueKeys)); // update the CellSet of this Segment
193  }
194
195  /*------------------------------------------------------------------------*/
196  // Create CellSet based on CellChunkMap from current ConcurrentSkipListMap based CellSet
197  // (without compacting iterator)
198  // This is a service for not-flat immutable segments
199  private void reinitializeCellSet(int numOfCells, KeyValueScanner segmentScanner,
200    CellSet<ExtendedCell> oldCellSet, MemStoreSizing memstoreSizing,
201    MemStoreCompactionStrategy.Action action) {
202    ExtendedCell curCell;
203    Chunk[] chunks = allocIndexChunks(numOfCells);
204
205    int currentChunkIdx = 0;
206    int offsetInCurentChunk = ChunkCreator.SIZEOF_CHUNK_HEADER;
207
208    int numUniqueKeys = 0;
209    ExtendedCell prev = null;
210    try {
211      while ((curCell = segmentScanner.next()) != null) {
212        if (curCell.getChunkId() == ExtendedCell.CELL_NOT_BASED_ON_CHUNK) {
213          // CellChunkMap assumes all cells are allocated on MSLAB.
214          // Therefore, cells which are not allocated on MSLAB initially,
215          // are copied into MSLAB here.
216          curCell = copyCellIntoMSLAB(curCell, memstoreSizing);
217        }
218        if (offsetInCurentChunk + ClassSize.CELL_CHUNK_MAP_ENTRY > chunks[currentChunkIdx].size) {
219          // continue to the next metadata chunk
220          currentChunkIdx++;
221          offsetInCurentChunk = ChunkCreator.SIZEOF_CHUNK_HEADER;
222        }
223        offsetInCurentChunk = createCellReference((ByteBufferKeyValue) curCell,
224          chunks[currentChunkIdx].getData(), offsetInCurentChunk);
225        if (action == MemStoreCompactionStrategy.Action.FLATTEN_COUNT_UNIQUE_KEYS) {
226          // counting number of unique keys
227          if (prev != null) {
228            if (!CellUtil.matchingRowColumn(prev, curCell)) {
229              numUniqueKeys++;
230            }
231          } else {
232            numUniqueKeys++;
233          }
234        }
235        prev = curCell;
236      }
237      if (action != MemStoreCompactionStrategy.Action.FLATTEN_COUNT_UNIQUE_KEYS) {
238        numUniqueKeys = CellSet.UNKNOWN_NUM_UNIQUES;
239      }
240    } catch (IOException ie) {
241      throw new IllegalStateException(ie);
242    } finally {
243      segmentScanner.close();
244    }
245
246    CellChunkMap<ExtendedCell> ccm =
247      new CellChunkMap<>(getComparator(), chunks, 0, numOfCells, false);
248    // update the CellSet of this Segment
249    this.setCellSet(oldCellSet, new CellSet<>(ccm, numUniqueKeys));
250  }
251
252  /*------------------------------------------------------------------------*/
253  // for a given cell, write the cell representation on the index chunk
254  private int createCellReference(ByteBufferKeyValue cell, ByteBuffer idxBuffer, int idxOffset) {
255    int offset = idxOffset;
256    int dataChunkID = cell.getChunkId();
257
258    offset = ByteBufferUtils.putInt(idxBuffer, offset, dataChunkID); // write data chunk id
259    offset = ByteBufferUtils.putInt(idxBuffer, offset, cell.getOffset()); // offset
260    offset = ByteBufferUtils.putInt(idxBuffer, offset, cell.getSerializedSize()); // length
261    offset = ByteBufferUtils.putLong(idxBuffer, offset, cell.getSequenceId()); // seqId
262
263    return offset;
264  }
265
266  private int calculateNumberOfChunks(int numOfCells, int chunkSize) {
267    int numOfCellsInChunk = calcNumOfCellsInChunk(chunkSize);
268    int numberOfChunks = numOfCells / numOfCellsInChunk;
269    if (numOfCells % numOfCellsInChunk != 0) { // if cells cannot be divided evenly between chunks
270      numberOfChunks++; // add one additional chunk
271    }
272    return numberOfChunks;
273  }
274
275  // Assuming we are going to use regular data chunks as index chunks,
276  // we check here how much free space will remain in the last allocated chunk
277  // (the least occupied one).
278  // If the percentage of its remaining free space is above the INDEX_CHUNK_UNUSED_SPACE
279  // threshold, then we will use index chunks (which are smaller) instead.
280  private ChunkCreator.ChunkType useIndexChunks(int numOfCells) {
281    int dataChunkSize = ChunkCreator.getInstance().getChunkSize();
282    int numOfCellsInChunk = calcNumOfCellsInChunk(dataChunkSize);
283    int cellsInLastChunk = numOfCells % numOfCellsInChunk;
284    if (cellsInLastChunk == 0) { // There is no free space in the last chunk and thus,
285      return ChunkCreator.ChunkType.DATA_CHUNK; // no need to use index chunks.
286    } else {
287      int chunkSpace = dataChunkSize - ChunkCreator.SIZEOF_CHUNK_HEADER;
288      int freeSpaceInLastChunk = chunkSpace - cellsInLastChunk * ClassSize.CELL_CHUNK_MAP_ENTRY;
289      if (freeSpaceInLastChunk > INDEX_CHUNK_UNUSED_SPACE_PRECENTAGE * chunkSpace) {
290        return ChunkCreator.ChunkType.INDEX_CHUNK;
291      }
292      return ChunkCreator.ChunkType.DATA_CHUNK;
293    }
294  }
295
296  private int calcNumOfCellsInChunk(int chunkSize) {
297    int chunkSpace = chunkSize - ChunkCreator.SIZEOF_CHUNK_HEADER;
298    int numOfCellsInChunk = chunkSpace / ClassSize.CELL_CHUNK_MAP_ENTRY;
299    return numOfCellsInChunk;
300  }
301
302  private Chunk[] allocIndexChunks(int numOfCells) {
303    // Decide whether to use regular or small chunks and then
304    // calculate how many chunks we will need for index
305
306    ChunkCreator.ChunkType chunkType = useIndexChunks(numOfCells);
307    int chunkSize = ChunkCreator.getInstance().getChunkSize(chunkType);
308    int numberOfChunks = calculateNumberOfChunks(numOfCells, chunkSize);
309    // all index Chunks are allocated from ChunkCreator
310    Chunk[] chunks = new Chunk[numberOfChunks];
311    // all index Chunks are allocated from ChunkCreator
312    for (int i = 0; i < numberOfChunks; i++) {
313      chunks[i] = this.getMemStoreLAB().getNewExternalChunk(chunkType);
314    }
315    return chunks;
316  }
317
318  private ExtendedCell copyCellIntoMSLAB(ExtendedCell cell, MemStoreSizing memstoreSizing) {
319    // Take care for a special case when a cell is copied from on-heap to (probably off-heap) MSLAB.
320    // The cell allocated as an on-heap JVM object (byte array) occupies slightly different
321    // amount of memory, than when the cell serialized and allocated on the MSLAB.
322    // Here, we update the heap size of the new segment only for the difference between object and
323    // serialized size. This is a decrease of the size as serialized cell is a bit smaller.
324    // The actual size of the cell is not added yet, and will be added (only in compaction)
325    // in initializeCellSet#updateMetaInfo().
326    long oldHeapSize = heapSizeChange(cell, true);
327    long oldOffHeapSize = offHeapSizeChange(cell, true);
328    long oldCellSize = getCellLength(cell);
329    cell = maybeCloneWithAllocator(cell, true);
330    long newHeapSize = heapSizeChange(cell, true);
331    long newOffHeapSize = offHeapSizeChange(cell, true);
332    long newCellSize = getCellLength(cell);
333    long heapOverhead = newHeapSize - oldHeapSize;
334    long offHeapOverhead = newOffHeapSize - oldOffHeapSize;
335    incMemStoreSize(newCellSize - oldCellSize, heapOverhead, offHeapOverhead, 0);
336    if (memstoreSizing != null) {
337      memstoreSizing.incMemStoreSize(newCellSize - oldCellSize, heapOverhead, offHeapOverhead, 0);
338    }
339    return cell;
340  }
341}