| <!DOCTYPE HTML> |
| <html lang="en"> |
| <head> |
| <!-- Generated by javadoc (17) --> |
| <title>Source code</title> |
| <meta name="viewport" content="width=device-width, initial-scale=1"> |
| <meta name="description" content="source: package: org.apache.hadoop.hbase.io.hfile, class: HFileBlockIndex"> |
| <meta name="generator" content="javadoc/SourceToHTMLConverter"> |
| <link rel="stylesheet" type="text/css" href="../../../../../../../stylesheet.css" title="Style"> |
| </head> |
| <body class="source-page"> |
| <main role="main"> |
| <div class="source-container"> |
| <pre><span class="source-line-no">001</span><span id="line-1">/*</span> |
| <span class="source-line-no">002</span><span id="line-2"> * Licensed to the Apache Software Foundation (ASF) under one</span> |
| <span class="source-line-no">003</span><span id="line-3"> * or more contributor license agreements. See the NOTICE file</span> |
| <span class="source-line-no">004</span><span id="line-4"> * distributed with this work for additional information</span> |
| <span class="source-line-no">005</span><span id="line-5"> * regarding copyright ownership. The ASF licenses this file</span> |
| <span class="source-line-no">006</span><span id="line-6"> * to you under the Apache License, Version 2.0 (the</span> |
| <span class="source-line-no">007</span><span id="line-7"> * "License"); you may not use this file except in compliance</span> |
| <span class="source-line-no">008</span><span id="line-8"> * with the License. You may obtain a copy of the License at</span> |
| <span class="source-line-no">009</span><span id="line-9"> *</span> |
| <span class="source-line-no">010</span><span id="line-10"> * http://www.apache.org/licenses/LICENSE-2.0</span> |
| <span class="source-line-no">011</span><span id="line-11"> *</span> |
| <span class="source-line-no">012</span><span id="line-12"> * Unless required by applicable law or agreed to in writing, software</span> |
| <span class="source-line-no">013</span><span id="line-13"> * distributed under the License is distributed on an "AS IS" BASIS,</span> |
| <span class="source-line-no">014</span><span id="line-14"> * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.</span> |
| <span class="source-line-no">015</span><span id="line-15"> * See the License for the specific language governing permissions and</span> |
| <span class="source-line-no">016</span><span id="line-16"> * limitations under the License.</span> |
| <span class="source-line-no">017</span><span id="line-17"> */</span> |
| <span class="source-line-no">018</span><span id="line-18">package org.apache.hadoop.hbase.io.hfile;</span> |
| <span class="source-line-no">019</span><span id="line-19"></span> |
| <span class="source-line-no">020</span><span id="line-20">import java.io.ByteArrayOutputStream;</span> |
| <span class="source-line-no">021</span><span id="line-21">import java.io.DataInput;</span> |
| <span class="source-line-no">022</span><span id="line-22">import java.io.DataInputStream;</span> |
| <span class="source-line-no">023</span><span id="line-23">import java.io.DataOutput;</span> |
| <span class="source-line-no">024</span><span id="line-24">import java.io.DataOutputStream;</span> |
| <span class="source-line-no">025</span><span id="line-25">import java.io.IOException;</span> |
| <span class="source-line-no">026</span><span id="line-26">import java.nio.ByteBuffer;</span> |
| <span class="source-line-no">027</span><span id="line-27">import java.util.ArrayList;</span> |
| <span class="source-line-no">028</span><span id="line-28">import java.util.Collections;</span> |
| <span class="source-line-no">029</span><span id="line-29">import java.util.List;</span> |
| <span class="source-line-no">030</span><span id="line-30">import java.util.concurrent.atomic.AtomicReference;</span> |
| <span class="source-line-no">031</span><span id="line-31">import org.apache.hadoop.conf.Configuration;</span> |
| <span class="source-line-no">032</span><span id="line-32">import org.apache.hadoop.fs.FSDataOutputStream;</span> |
| <span class="source-line-no">033</span><span id="line-33">import org.apache.hadoop.hbase.ByteBufferKeyOnlyKeyValue;</span> |
| <span class="source-line-no">034</span><span id="line-34">import org.apache.hadoop.hbase.Cell;</span> |
| <span class="source-line-no">035</span><span id="line-35">import org.apache.hadoop.hbase.CellComparator;</span> |
| <span class="source-line-no">036</span><span id="line-36">import org.apache.hadoop.hbase.CellUtil;</span> |
| <span class="source-line-no">037</span><span id="line-37">import org.apache.hadoop.hbase.ExtendedCell;</span> |
| <span class="source-line-no">038</span><span id="line-38">import org.apache.hadoop.hbase.KeyValue;</span> |
| <span class="source-line-no">039</span><span id="line-39">import org.apache.hadoop.hbase.KeyValue.KeyOnlyKeyValue;</span> |
| <span class="source-line-no">040</span><span id="line-40">import org.apache.hadoop.hbase.PrivateCellUtil;</span> |
| <span class="source-line-no">041</span><span id="line-41">import org.apache.hadoop.hbase.io.HeapSize;</span> |
| <span class="source-line-no">042</span><span id="line-42">import org.apache.hadoop.hbase.io.encoding.DataBlockEncoding;</span> |
| <span class="source-line-no">043</span><span id="line-43">import org.apache.hadoop.hbase.io.hfile.HFile.CachingBlockReader;</span> |
| <span class="source-line-no">044</span><span id="line-44">import org.apache.hadoop.hbase.nio.ByteBuff;</span> |
| <span class="source-line-no">045</span><span id="line-45">import org.apache.hadoop.hbase.regionserver.KeyValueScanner;</span> |
| <span class="source-line-no">046</span><span id="line-46">import org.apache.hadoop.hbase.util.Bytes;</span> |
| <span class="source-line-no">047</span><span id="line-47">import org.apache.hadoop.hbase.util.ClassSize;</span> |
| <span class="source-line-no">048</span><span id="line-48">import org.apache.hadoop.hbase.util.ObjectIntPair;</span> |
| <span class="source-line-no">049</span><span id="line-49">import org.apache.hadoop.io.WritableUtils;</span> |
| <span class="source-line-no">050</span><span id="line-50">import org.apache.hadoop.util.StringUtils;</span> |
| <span class="source-line-no">051</span><span id="line-51">import org.apache.yetus.audience.InterfaceAudience;</span> |
| <span class="source-line-no">052</span><span id="line-52">import org.slf4j.Logger;</span> |
| <span class="source-line-no">053</span><span id="line-53">import org.slf4j.LoggerFactory;</span> |
| <span class="source-line-no">054</span><span id="line-54"></span> |
| <span class="source-line-no">055</span><span id="line-55">/**</span> |
| <span class="source-line-no">056</span><span id="line-56"> * Provides functionality to write ({@link BlockIndexWriter}) and read BlockIndexReader single-level</span> |
| <span class="source-line-no">057</span><span id="line-57"> * and multi-level block indexes. Examples of how to use the block index writer can be found in</span> |
| <span class="source-line-no">058</span><span id="line-58"> * {@link org.apache.hadoop.hbase.io.hfile.CompoundBloomFilterWriter} and {@link HFileWriterImpl}.</span> |
| <span class="source-line-no">059</span><span id="line-59"> * Examples of how to use the reader can be found in {@link HFileReaderImpl} and</span> |
| <span class="source-line-no">060</span><span id="line-60"> * org.apache.hadoop.hbase.io.hfile.TestHFileBlockIndex.</span> |
| <span class="source-line-no">061</span><span id="line-61"> */</span> |
| <span class="source-line-no">062</span><span id="line-62">@InterfaceAudience.Private</span> |
| <span class="source-line-no">063</span><span id="line-63">public class HFileBlockIndex {</span> |
| <span class="source-line-no">064</span><span id="line-64"></span> |
| <span class="source-line-no">065</span><span id="line-65"> private static final Logger LOG = LoggerFactory.getLogger(HFileBlockIndex.class);</span> |
| <span class="source-line-no">066</span><span id="line-66"></span> |
| <span class="source-line-no">067</span><span id="line-67"> static final int DEFAULT_MAX_CHUNK_SIZE = 128 * 1024;</span> |
| <span class="source-line-no">068</span><span id="line-68"></span> |
| <span class="source-line-no">069</span><span id="line-69"> /**</span> |
| <span class="source-line-no">070</span><span id="line-70"> * The maximum size guideline for index blocks (both leaf, intermediate, and root). If not</span> |
| <span class="source-line-no">071</span><span id="line-71"> * specified, <code>DEFAULT_MAX_CHUNK_SIZE</code> is used.</span> |
| <span class="source-line-no">072</span><span id="line-72"> */</span> |
| <span class="source-line-no">073</span><span id="line-73"> public static final String MAX_CHUNK_SIZE_KEY = "hfile.index.block.max.size";</span> |
| <span class="source-line-no">074</span><span id="line-74"></span> |
| <span class="source-line-no">075</span><span id="line-75"> /**</span> |
| <span class="source-line-no">076</span><span id="line-76"> * Minimum number of entries in a single index block. Even if we are above the</span> |
| <span class="source-line-no">077</span><span id="line-77"> * hfile.index.block.max.size we will keep writing to the same block unless we have that many</span> |
| <span class="source-line-no">078</span><span id="line-78"> * entries. We should have at least a few entries so that we don't have too many levels in the</span> |
| <span class="source-line-no">079</span><span id="line-79"> * multi-level index. This should be at least 2 to make sure there is no infinite recursion.</span> |
| <span class="source-line-no">080</span><span id="line-80"> */</span> |
| <span class="source-line-no">081</span><span id="line-81"> public static final String MIN_INDEX_NUM_ENTRIES_KEY = "hfile.index.block.min.entries";</span> |
| <span class="source-line-no">082</span><span id="line-82"></span> |
| <span class="source-line-no">083</span><span id="line-83"> static final int DEFAULT_MIN_INDEX_NUM_ENTRIES = 16;</span> |
| <span class="source-line-no">084</span><span id="line-84"></span> |
| <span class="source-line-no">085</span><span id="line-85"> /**</span> |
| <span class="source-line-no">086</span><span id="line-86"> * The number of bytes stored in each "secondary index" entry in addition to key bytes in the</span> |
| <span class="source-line-no">087</span><span id="line-87"> * non-root index block format. The first long is the file offset of the deeper-level block the</span> |
| <span class="source-line-no">088</span><span id="line-88"> * entry points to, and the int that follows is that block's on-disk size without including</span> |
| <span class="source-line-no">089</span><span id="line-89"> * header.</span> |
| <span class="source-line-no">090</span><span id="line-90"> */</span> |
| <span class="source-line-no">091</span><span id="line-91"> static final int SECONDARY_INDEX_ENTRY_OVERHEAD = Bytes.SIZEOF_INT + Bytes.SIZEOF_LONG;</span> |
| <span class="source-line-no">092</span><span id="line-92"></span> |
| <span class="source-line-no">093</span><span id="line-93"> /**</span> |
| <span class="source-line-no">094</span><span id="line-94"> * Error message when trying to use inline block API in single-level mode.</span> |
| <span class="source-line-no">095</span><span id="line-95"> */</span> |
| <span class="source-line-no">096</span><span id="line-96"> private static final String INLINE_BLOCKS_NOT_ALLOWED =</span> |
| <span class="source-line-no">097</span><span id="line-97"> "Inline blocks are not allowed in the single-level-only mode";</span> |
| <span class="source-line-no">098</span><span id="line-98"></span> |
| <span class="source-line-no">099</span><span id="line-99"> /**</span> |
| <span class="source-line-no">100</span><span id="line-100"> * The size of a meta-data record used for finding the mid-key in a multi-level index. Consists of</span> |
| <span class="source-line-no">101</span><span id="line-101"> * the middle leaf-level index block offset (long), its on-disk size without header included</span> |
| <span class="source-line-no">102</span><span id="line-102"> * (int), and the mid-key entry's zero-based index in that leaf index block.</span> |
| <span class="source-line-no">103</span><span id="line-103"> */</span> |
| <span class="source-line-no">104</span><span id="line-104"> protected static final int MID_KEY_METADATA_SIZE = Bytes.SIZEOF_LONG + 2 * Bytes.SIZEOF_INT;</span> |
| <span class="source-line-no">105</span><span id="line-105"></span> |
| <span class="source-line-no">106</span><span id="line-106"> /**</span> |
| <span class="source-line-no">107</span><span id="line-107"> * An implementation of the BlockIndexReader that deals with block keys which are plain byte[]</span> |
| <span class="source-line-no">108</span><span id="line-108"> * like MetaBlock or the Bloom Block for ROW bloom. Does not need a comparator. It can work on</span> |
| <span class="source-line-no">109</span><span id="line-109"> * Bytes.BYTES_RAWCOMPARATOR</span> |
| <span class="source-line-no">110</span><span id="line-110"> */</span> |
| <span class="source-line-no">111</span><span id="line-111"> static class ByteArrayKeyBlockIndexReader extends BlockIndexReader {</span> |
| <span class="source-line-no">112</span><span id="line-112"></span> |
| <span class="source-line-no">113</span><span id="line-113"> private byte[][] blockKeys;</span> |
| <span class="source-line-no">114</span><span id="line-114"></span> |
| <span class="source-line-no">115</span><span id="line-115"> public ByteArrayKeyBlockIndexReader(final int treeLevel) {</span> |
| <span class="source-line-no">116</span><span id="line-116"> // Can be null for METAINDEX block</span> |
| <span class="source-line-no">117</span><span id="line-117"> searchTreeLevel = treeLevel;</span> |
| <span class="source-line-no">118</span><span id="line-118"> }</span> |
| <span class="source-line-no">119</span><span id="line-119"></span> |
| <span class="source-line-no">120</span><span id="line-120"> @Override</span> |
| <span class="source-line-no">121</span><span id="line-121"> protected long calculateHeapSizeForBlockKeys(long heapSize) {</span> |
| <span class="source-line-no">122</span><span id="line-122"> // Calculating the size of blockKeys</span> |
| <span class="source-line-no">123</span><span id="line-123"> if (blockKeys != null) {</span> |
| <span class="source-line-no">124</span><span id="line-124"> heapSize += ClassSize.REFERENCE;</span> |
| <span class="source-line-no">125</span><span id="line-125"> // Adding array + references overhead</span> |
| <span class="source-line-no">126</span><span id="line-126"> heapSize += ClassSize.align(ClassSize.ARRAY + blockKeys.length * ClassSize.REFERENCE);</span> |
| <span class="source-line-no">127</span><span id="line-127"></span> |
| <span class="source-line-no">128</span><span id="line-128"> // Adding bytes</span> |
| <span class="source-line-no">129</span><span id="line-129"> for (byte[] key : blockKeys) {</span> |
| <span class="source-line-no">130</span><span id="line-130"> heapSize += ClassSize.align(ClassSize.ARRAY + key.length);</span> |
| <span class="source-line-no">131</span><span id="line-131"> }</span> |
| <span class="source-line-no">132</span><span id="line-132"> }</span> |
| <span class="source-line-no">133</span><span id="line-133"> return heapSize;</span> |
| <span class="source-line-no">134</span><span id="line-134"> }</span> |
| <span class="source-line-no">135</span><span id="line-135"></span> |
| <span class="source-line-no">136</span><span id="line-136"> @Override</span> |
| <span class="source-line-no">137</span><span id="line-137"> public boolean isEmpty() {</span> |
| <span class="source-line-no">138</span><span id="line-138"> return blockKeys.length == 0;</span> |
| <span class="source-line-no">139</span><span id="line-139"> }</span> |
| <span class="source-line-no">140</span><span id="line-140"></span> |
| <span class="source-line-no">141</span><span id="line-141"> /**</span> |
| <span class="source-line-no">142</span><span id="line-142"> * from 0 to {@link #getRootBlockCount() - 1}</span> |
| <span class="source-line-no">143</span><span id="line-143"> */</span> |
| <span class="source-line-no">144</span><span id="line-144"> public byte[] getRootBlockKey(int i) {</span> |
| <span class="source-line-no">145</span><span id="line-145"> return blockKeys[i];</span> |
| <span class="source-line-no">146</span><span id="line-146"> }</span> |
| <span class="source-line-no">147</span><span id="line-147"></span> |
| <span class="source-line-no">148</span><span id="line-148"> @Override</span> |
| <span class="source-line-no">149</span><span id="line-149"> public BlockWithScanInfo loadDataBlockWithScanInfo(ExtendedCell key, HFileBlock currentBlock,</span> |
| <span class="source-line-no">150</span><span id="line-150"> boolean cacheBlocks, boolean pread, boolean isCompaction,</span> |
| <span class="source-line-no">151</span><span id="line-151"> DataBlockEncoding expectedDataBlockEncoding, CachingBlockReader cachingBlockReader)</span> |
| <span class="source-line-no">152</span><span id="line-152"> throws IOException {</span> |
| <span class="source-line-no">153</span><span id="line-153"> // this would not be needed</span> |
| <span class="source-line-no">154</span><span id="line-154"> return null;</span> |
| <span class="source-line-no">155</span><span id="line-155"> }</span> |
| <span class="source-line-no">156</span><span id="line-156"></span> |
| <span class="source-line-no">157</span><span id="line-157"> @Override</span> |
| <span class="source-line-no">158</span><span id="line-158"> public Cell midkey(CachingBlockReader cachingBlockReader) throws IOException {</span> |
| <span class="source-line-no">159</span><span id="line-159"> // Not needed here</span> |
| <span class="source-line-no">160</span><span id="line-160"> return null;</span> |
| <span class="source-line-no">161</span><span id="line-161"> }</span> |
| <span class="source-line-no">162</span><span id="line-162"></span> |
| <span class="source-line-no">163</span><span id="line-163"> @Override</span> |
| <span class="source-line-no">164</span><span id="line-164"> protected void initialize(int numEntries) {</span> |
| <span class="source-line-no">165</span><span id="line-165"> blockKeys = new byte[numEntries][];</span> |
| <span class="source-line-no">166</span><span id="line-166"> }</span> |
| <span class="source-line-no">167</span><span id="line-167"></span> |
| <span class="source-line-no">168</span><span id="line-168"> @Override</span> |
| <span class="source-line-no">169</span><span id="line-169"> protected void add(final byte[] key, final long offset, final int dataSize) {</span> |
| <span class="source-line-no">170</span><span id="line-170"> blockOffsets[rootCount] = offset;</span> |
| <span class="source-line-no">171</span><span id="line-171"> blockKeys[rootCount] = key;</span> |
| <span class="source-line-no">172</span><span id="line-172"> blockDataSizes[rootCount] = dataSize;</span> |
| <span class="source-line-no">173</span><span id="line-173"> rootCount++;</span> |
| <span class="source-line-no">174</span><span id="line-174"> }</span> |
| <span class="source-line-no">175</span><span id="line-175"></span> |
| <span class="source-line-no">176</span><span id="line-176"> @Override</span> |
| <span class="source-line-no">177</span><span id="line-177"> public int rootBlockContainingKey(byte[] key, int offset, int length, CellComparator comp) {</span> |
| <span class="source-line-no">178</span><span id="line-178"> int pos = Bytes.binarySearch(blockKeys, key, offset, length);</span> |
| <span class="source-line-no">179</span><span id="line-179"> // pos is between -(blockKeys.length + 1) to blockKeys.length - 1, see</span> |
| <span class="source-line-no">180</span><span id="line-180"> // binarySearch's javadoc.</span> |
| <span class="source-line-no">181</span><span id="line-181"></span> |
| <span class="source-line-no">182</span><span id="line-182"> if (pos >= 0) {</span> |
| <span class="source-line-no">183</span><span id="line-183"> // This means this is an exact match with an element of blockKeys.</span> |
| <span class="source-line-no">184</span><span id="line-184"> assert pos < blockKeys.length;</span> |
| <span class="source-line-no">185</span><span id="line-185"> return pos;</span> |
| <span class="source-line-no">186</span><span id="line-186"> }</span> |
| <span class="source-line-no">187</span><span id="line-187"></span> |
| <span class="source-line-no">188</span><span id="line-188"> // Otherwise, pos = -(i + 1), where blockKeys[i - 1] < key < blockKeys[i],</span> |
| <span class="source-line-no">189</span><span id="line-189"> // and i is in [0, blockKeys.length]. We are returning j = i - 1 such that</span> |
| <span class="source-line-no">190</span><span id="line-190"> // blockKeys[j] <= key < blockKeys[j + 1]. In particular, j = -1 if</span> |
| <span class="source-line-no">191</span><span id="line-191"> // key < blockKeys[0], meaning the file does not contain the given key.</span> |
| <span class="source-line-no">192</span><span id="line-192"></span> |
| <span class="source-line-no">193</span><span id="line-193"> int i = -pos - 1;</span> |
| <span class="source-line-no">194</span><span id="line-194"> assert 0 <= i && i <= blockKeys.length;</span> |
| <span class="source-line-no">195</span><span id="line-195"> return i - 1;</span> |
| <span class="source-line-no">196</span><span id="line-196"> }</span> |
| <span class="source-line-no">197</span><span id="line-197"></span> |
| <span class="source-line-no">198</span><span id="line-198"> @Override</span> |
| <span class="source-line-no">199</span><span id="line-199"> public int rootBlockContainingKey(Cell key) {</span> |
| <span class="source-line-no">200</span><span id="line-200"> // Should not be called on this because here it deals only with byte[]</span> |
| <span class="source-line-no">201</span><span id="line-201"> throw new UnsupportedOperationException(</span> |
| <span class="source-line-no">202</span><span id="line-202"> "Cannot search for a key that is of Cell type. Only plain byte array keys "</span> |
| <span class="source-line-no">203</span><span id="line-203"> + "can be searched for");</span> |
| <span class="source-line-no">204</span><span id="line-204"> }</span> |
| <span class="source-line-no">205</span><span id="line-205"></span> |
| <span class="source-line-no">206</span><span id="line-206"> @Override</span> |
| <span class="source-line-no">207</span><span id="line-207"> public String toString() {</span> |
| <span class="source-line-no">208</span><span id="line-208"> StringBuilder sb = new StringBuilder();</span> |
| <span class="source-line-no">209</span><span id="line-209"> sb.append("size=" + rootCount).append("\n");</span> |
| <span class="source-line-no">210</span><span id="line-210"> for (int i = 0; i < rootCount; i++) {</span> |
| <span class="source-line-no">211</span><span id="line-211"> sb.append("key=").append(KeyValue.keyToString(blockKeys[i])).append("\n offset=")</span> |
| <span class="source-line-no">212</span><span id="line-212"> .append(blockOffsets[i]).append(", dataSize=" + blockDataSizes[i]).append("\n");</span> |
| <span class="source-line-no">213</span><span id="line-213"> }</span> |
| <span class="source-line-no">214</span><span id="line-214"> return sb.toString();</span> |
| <span class="source-line-no">215</span><span id="line-215"> }</span> |
| <span class="source-line-no">216</span><span id="line-216"> }</span> |
| <span class="source-line-no">217</span><span id="line-217"></span> |
| <span class="source-line-no">218</span><span id="line-218"> /**</span> |
| <span class="source-line-no">219</span><span id="line-219"> * An implementation of the BlockIndexReader that deals with block keys which are the key part of</span> |
| <span class="source-line-no">220</span><span id="line-220"> * a cell like the Data block index or the ROW_COL bloom blocks This needs a comparator to work</span> |
| <span class="source-line-no">221</span><span id="line-221"> * with the Cells</span> |
| <span class="source-line-no">222</span><span id="line-222"> */</span> |
| <span class="source-line-no">223</span><span id="line-223"> static class CellBasedKeyBlockIndexReader extends BlockIndexReader {</span> |
| <span class="source-line-no">224</span><span id="line-224"></span> |
| <span class="source-line-no">225</span><span id="line-225"> private ExtendedCell[] blockKeys;</span> |
| <span class="source-line-no">226</span><span id="line-226"> /** Pre-computed mid-key */</span> |
| <span class="source-line-no">227</span><span id="line-227"> private AtomicReference<ExtendedCell> midKey = new AtomicReference<>();</span> |
| <span class="source-line-no">228</span><span id="line-228"> /** Needed doing lookup on blocks. */</span> |
| <span class="source-line-no">229</span><span id="line-229"> protected CellComparator comparator;</span> |
| <span class="source-line-no">230</span><span id="line-230"></span> |
| <span class="source-line-no">231</span><span id="line-231"> public CellBasedKeyBlockIndexReader(final CellComparator c, final int treeLevel) {</span> |
| <span class="source-line-no">232</span><span id="line-232"> // Can be null for METAINDEX block</span> |
| <span class="source-line-no">233</span><span id="line-233"> comparator = c;</span> |
| <span class="source-line-no">234</span><span id="line-234"> searchTreeLevel = treeLevel;</span> |
| <span class="source-line-no">235</span><span id="line-235"> }</span> |
| <span class="source-line-no">236</span><span id="line-236"></span> |
| <span class="source-line-no">237</span><span id="line-237"> @Override</span> |
| <span class="source-line-no">238</span><span id="line-238"> protected long calculateHeapSizeForBlockKeys(long heapSize) {</span> |
| <span class="source-line-no">239</span><span id="line-239"> if (blockKeys != null) {</span> |
| <span class="source-line-no">240</span><span id="line-240"> heapSize += ClassSize.REFERENCE;</span> |
| <span class="source-line-no">241</span><span id="line-241"> // Adding array + references overhead</span> |
| <span class="source-line-no">242</span><span id="line-242"> heapSize += ClassSize.align(ClassSize.ARRAY + blockKeys.length * ClassSize.REFERENCE);</span> |
| <span class="source-line-no">243</span><span id="line-243"></span> |
| <span class="source-line-no">244</span><span id="line-244"> // Adding blockKeys</span> |
| <span class="source-line-no">245</span><span id="line-245"> for (Cell key : blockKeys) {</span> |
| <span class="source-line-no">246</span><span id="line-246"> heapSize += ClassSize.align(key.heapSize());</span> |
| <span class="source-line-no">247</span><span id="line-247"> }</span> |
| <span class="source-line-no">248</span><span id="line-248"> }</span> |
| <span class="source-line-no">249</span><span id="line-249"> // Add comparator and the midkey atomicreference</span> |
| <span class="source-line-no">250</span><span id="line-250"> heapSize += 2 * ClassSize.REFERENCE;</span> |
| <span class="source-line-no">251</span><span id="line-251"> return heapSize;</span> |
| <span class="source-line-no">252</span><span id="line-252"> }</span> |
| <span class="source-line-no">253</span><span id="line-253"></span> |
| <span class="source-line-no">254</span><span id="line-254"> @Override</span> |
| <span class="source-line-no">255</span><span id="line-255"> public boolean isEmpty() {</span> |
| <span class="source-line-no">256</span><span id="line-256"> return blockKeys.length == 0;</span> |
| <span class="source-line-no">257</span><span id="line-257"> }</span> |
| <span class="source-line-no">258</span><span id="line-258"></span> |
| <span class="source-line-no">259</span><span id="line-259"> /**</span> |
| <span class="source-line-no">260</span><span id="line-260"> * from 0 to {@link #getRootBlockCount() - 1}</span> |
| <span class="source-line-no">261</span><span id="line-261"> */</span> |
| <span class="source-line-no">262</span><span id="line-262"> public ExtendedCell getRootBlockKey(int i) {</span> |
| <span class="source-line-no">263</span><span id="line-263"> return blockKeys[i];</span> |
| <span class="source-line-no">264</span><span id="line-264"> }</span> |
| <span class="source-line-no">265</span><span id="line-265"></span> |
| <span class="source-line-no">266</span><span id="line-266"> @Override</span> |
| <span class="source-line-no">267</span><span id="line-267"> public BlockWithScanInfo loadDataBlockWithScanInfo(ExtendedCell key, HFileBlock currentBlock,</span> |
| <span class="source-line-no">268</span><span id="line-268"> boolean cacheBlocks, boolean pread, boolean isCompaction,</span> |
| <span class="source-line-no">269</span><span id="line-269"> DataBlockEncoding expectedDataBlockEncoding, CachingBlockReader cachingBlockReader)</span> |
| <span class="source-line-no">270</span><span id="line-270"> throws IOException {</span> |
| <span class="source-line-no">271</span><span id="line-271"> int rootLevelIndex = rootBlockContainingKey(key);</span> |
| <span class="source-line-no">272</span><span id="line-272"> if (rootLevelIndex < 0 || rootLevelIndex >= blockOffsets.length) {</span> |
| <span class="source-line-no">273</span><span id="line-273"> return null;</span> |
| <span class="source-line-no">274</span><span id="line-274"> }</span> |
| <span class="source-line-no">275</span><span id="line-275"></span> |
| <span class="source-line-no">276</span><span id="line-276"> // the next indexed key</span> |
| <span class="source-line-no">277</span><span id="line-277"> ExtendedCell nextIndexedKey = null;</span> |
| <span class="source-line-no">278</span><span id="line-278"></span> |
| <span class="source-line-no">279</span><span id="line-279"> // Read the next-level (intermediate or leaf) index block.</span> |
| <span class="source-line-no">280</span><span id="line-280"> long currentOffset = blockOffsets[rootLevelIndex];</span> |
| <span class="source-line-no">281</span><span id="line-281"> int currentOnDiskSize = blockDataSizes[rootLevelIndex];</span> |
| <span class="source-line-no">282</span><span id="line-282"></span> |
| <span class="source-line-no">283</span><span id="line-283"> if (rootLevelIndex < blockKeys.length - 1) {</span> |
| <span class="source-line-no">284</span><span id="line-284"> nextIndexedKey = blockKeys[rootLevelIndex + 1];</span> |
| <span class="source-line-no">285</span><span id="line-285"> } else {</span> |
| <span class="source-line-no">286</span><span id="line-286"> nextIndexedKey = KeyValueScanner.NO_NEXT_INDEXED_KEY;</span> |
| <span class="source-line-no">287</span><span id="line-287"> }</span> |
| <span class="source-line-no">288</span><span id="line-288"></span> |
| <span class="source-line-no">289</span><span id="line-289"> int lookupLevel = 1; // How many levels deep we are in our lookup.</span> |
| <span class="source-line-no">290</span><span id="line-290"> int index = -1;</span> |
| <span class="source-line-no">291</span><span id="line-291"></span> |
| <span class="source-line-no">292</span><span id="line-292"> HFileBlock block = null;</span> |
| <span class="source-line-no">293</span><span id="line-293"> KeyOnlyKeyValue tmpNextIndexKV = new KeyValue.KeyOnlyKeyValue();</span> |
| <span class="source-line-no">294</span><span id="line-294"> while (true) {</span> |
| <span class="source-line-no">295</span><span id="line-295"> try {</span> |
| <span class="source-line-no">296</span><span id="line-296"> // Must initialize it with null here, because if don't and once an exception happen in</span> |
| <span class="source-line-no">297</span><span id="line-297"> // readBlock, then we'll release the previous assigned block twice in the finally block.</span> |
| <span class="source-line-no">298</span><span id="line-298"> // (See HBASE-22422)</span> |
| <span class="source-line-no">299</span><span id="line-299"> block = null;</span> |
| <span class="source-line-no">300</span><span id="line-300"> if (currentBlock != null && currentBlock.getOffset() == currentOffset) {</span> |
| <span class="source-line-no">301</span><span id="line-301"> // Avoid reading the same block again, even with caching turned off.</span> |
| <span class="source-line-no">302</span><span id="line-302"> // This is crucial for compaction-type workload which might have</span> |
| <span class="source-line-no">303</span><span id="line-303"> // caching turned off. This is like a one-block cache inside the</span> |
| <span class="source-line-no">304</span><span id="line-304"> // scanner.</span> |
| <span class="source-line-no">305</span><span id="line-305"> block = currentBlock;</span> |
| <span class="source-line-no">306</span><span id="line-306"> } else {</span> |
| <span class="source-line-no">307</span><span id="line-307"> // Call HFile's caching block reader API. We always cache index</span> |
| <span class="source-line-no">308</span><span id="line-308"> // blocks, otherwise we might get terrible performance.</span> |
| <span class="source-line-no">309</span><span id="line-309"> boolean shouldCache = cacheBlocks || (lookupLevel < searchTreeLevel);</span> |
| <span class="source-line-no">310</span><span id="line-310"> BlockType expectedBlockType;</span> |
| <span class="source-line-no">311</span><span id="line-311"> if (lookupLevel < searchTreeLevel - 1) {</span> |
| <span class="source-line-no">312</span><span id="line-312"> expectedBlockType = BlockType.INTERMEDIATE_INDEX;</span> |
| <span class="source-line-no">313</span><span id="line-313"> } else if (lookupLevel == searchTreeLevel - 1) {</span> |
| <span class="source-line-no">314</span><span id="line-314"> expectedBlockType = BlockType.LEAF_INDEX;</span> |
| <span class="source-line-no">315</span><span id="line-315"> } else {</span> |
| <span class="source-line-no">316</span><span id="line-316"> // this also accounts for ENCODED_DATA</span> |
| <span class="source-line-no">317</span><span id="line-317"> expectedBlockType = BlockType.DATA;</span> |
| <span class="source-line-no">318</span><span id="line-318"> }</span> |
| <span class="source-line-no">319</span><span id="line-319"> block = cachingBlockReader.readBlock(currentOffset, currentOnDiskSize, shouldCache,</span> |
| <span class="source-line-no">320</span><span id="line-320"> pread, isCompaction, true, expectedBlockType, expectedDataBlockEncoding);</span> |
| <span class="source-line-no">321</span><span id="line-321"> }</span> |
| <span class="source-line-no">322</span><span id="line-322"></span> |
| <span class="source-line-no">323</span><span id="line-323"> if (block == null) {</span> |
| <span class="source-line-no">324</span><span id="line-324"> throw new IOException("Failed to read block at offset " + currentOffset</span> |
| <span class="source-line-no">325</span><span id="line-325"> + ", onDiskSize=" + currentOnDiskSize);</span> |
| <span class="source-line-no">326</span><span id="line-326"> }</span> |
| <span class="source-line-no">327</span><span id="line-327"></span> |
| <span class="source-line-no">328</span><span id="line-328"> // Found a data block, break the loop and check our level in the tree.</span> |
| <span class="source-line-no">329</span><span id="line-329"> if (block.getBlockType().isData()) {</span> |
| <span class="source-line-no">330</span><span id="line-330"> break;</span> |
| <span class="source-line-no">331</span><span id="line-331"> }</span> |
| <span class="source-line-no">332</span><span id="line-332"></span> |
| <span class="source-line-no">333</span><span id="line-333"> // Not a data block. This must be a leaf-level or intermediate-level</span> |
| <span class="source-line-no">334</span><span id="line-334"> // index block. We don't allow going deeper than searchTreeLevel.</span> |
| <span class="source-line-no">335</span><span id="line-335"> if (++lookupLevel > searchTreeLevel) {</span> |
| <span class="source-line-no">336</span><span id="line-336"> throw new IOException("Search Tree Level overflow: lookupLevel=" + lookupLevel</span> |
| <span class="source-line-no">337</span><span id="line-337"> + ", searchTreeLevel=" + searchTreeLevel);</span> |
| <span class="source-line-no">338</span><span id="line-338"> }</span> |
| <span class="source-line-no">339</span><span id="line-339"></span> |
| <span class="source-line-no">340</span><span id="line-340"> // Locate the entry corresponding to the given key in the non-root</span> |
| <span class="source-line-no">341</span><span id="line-341"> // (leaf or intermediate-level) index block.</span> |
| <span class="source-line-no">342</span><span id="line-342"> ByteBuff buffer = block.getBufferWithoutHeader();</span> |
| <span class="source-line-no">343</span><span id="line-343"> index = locateNonRootIndexEntry(buffer, key, comparator);</span> |
| <span class="source-line-no">344</span><span id="line-344"> if (index == -1) {</span> |
| <span class="source-line-no">345</span><span id="line-345"> // This has to be changed</span> |
| <span class="source-line-no">346</span><span id="line-346"> // For now change this to key value</span> |
| <span class="source-line-no">347</span><span id="line-347"> throw new IOException("The key " + CellUtil.getCellKeyAsString(key) + " is before the"</span> |
| <span class="source-line-no">348</span><span id="line-348"> + " first key of the non-root index block " + block);</span> |
| <span class="source-line-no">349</span><span id="line-349"> }</span> |
| <span class="source-line-no">350</span><span id="line-350"></span> |
| <span class="source-line-no">351</span><span id="line-351"> currentOffset = buffer.getLong();</span> |
| <span class="source-line-no">352</span><span id="line-352"> currentOnDiskSize = buffer.getInt();</span> |
| <span class="source-line-no">353</span><span id="line-353"></span> |
| <span class="source-line-no">354</span><span id="line-354"> // Only update next indexed key if there is a next indexed key in the current level</span> |
| <span class="source-line-no">355</span><span id="line-355"> byte[] nonRootIndexedKey = getNonRootIndexedKey(buffer, index + 1);</span> |
| <span class="source-line-no">356</span><span id="line-356"> if (nonRootIndexedKey != null) {</span> |
| <span class="source-line-no">357</span><span id="line-357"> tmpNextIndexKV.setKey(nonRootIndexedKey, 0, nonRootIndexedKey.length);</span> |
| <span class="source-line-no">358</span><span id="line-358"> nextIndexedKey = tmpNextIndexKV;</span> |
| <span class="source-line-no">359</span><span id="line-359"> }</span> |
| <span class="source-line-no">360</span><span id="line-360"> } finally {</span> |
| <span class="source-line-no">361</span><span id="line-361"> if (block != null && !block.getBlockType().isData()) {</span> |
| <span class="source-line-no">362</span><span id="line-362"> // Release the block immediately if it is not the data block</span> |
| <span class="source-line-no">363</span><span id="line-363"> block.release();</span> |
| <span class="source-line-no">364</span><span id="line-364"> }</span> |
| <span class="source-line-no">365</span><span id="line-365"> }</span> |
| <span class="source-line-no">366</span><span id="line-366"> }</span> |
| <span class="source-line-no">367</span><span id="line-367"></span> |
| <span class="source-line-no">368</span><span id="line-368"> if (lookupLevel != searchTreeLevel) {</span> |
| <span class="source-line-no">369</span><span id="line-369"> assert block.getBlockType().isData();</span> |
| <span class="source-line-no">370</span><span id="line-370"> // Though we have retrieved a data block we have found an issue</span> |
| <span class="source-line-no">371</span><span id="line-371"> // in the retrieved data block. Hence returned the block so that</span> |
| <span class="source-line-no">372</span><span id="line-372"> // the ref count can be decremented</span> |
| <span class="source-line-no">373</span><span id="line-373"> if (block != null) {</span> |
| <span class="source-line-no">374</span><span id="line-374"> block.release();</span> |
| <span class="source-line-no">375</span><span id="line-375"> }</span> |
| <span class="source-line-no">376</span><span id="line-376"> throw new IOException("Reached a data block at level " + lookupLevel</span> |
| <span class="source-line-no">377</span><span id="line-377"> + " but the number of levels is " + searchTreeLevel);</span> |
| <span class="source-line-no">378</span><span id="line-378"> }</span> |
| <span class="source-line-no">379</span><span id="line-379"></span> |
| <span class="source-line-no">380</span><span id="line-380"> // set the next indexed key for the current block.</span> |
| <span class="source-line-no">381</span><span id="line-381"> return new BlockWithScanInfo(block, nextIndexedKey);</span> |
| <span class="source-line-no">382</span><span id="line-382"> }</span> |
| <span class="source-line-no">383</span><span id="line-383"></span> |
| <span class="source-line-no">384</span><span id="line-384"> @Override</span> |
| <span class="source-line-no">385</span><span id="line-385"> public ExtendedCell midkey(CachingBlockReader cachingBlockReader) throws IOException {</span> |
| <span class="source-line-no">386</span><span id="line-386"> if (rootCount == 0) {</span> |
| <span class="source-line-no">387</span><span id="line-387"> throw new IOException("HFile empty");</span> |
| <span class="source-line-no">388</span><span id="line-388"> }</span> |
| <span class="source-line-no">389</span><span id="line-389"></span> |
| <span class="source-line-no">390</span><span id="line-390"> ExtendedCell targetMidKey = this.midKey.get();</span> |
| <span class="source-line-no">391</span><span id="line-391"> if (targetMidKey != null) {</span> |
| <span class="source-line-no">392</span><span id="line-392"> return targetMidKey;</span> |
| <span class="source-line-no">393</span><span id="line-393"> }</span> |
| <span class="source-line-no">394</span><span id="line-394"></span> |
| <span class="source-line-no">395</span><span id="line-395"> if (midLeafBlockOffset >= 0) {</span> |
| <span class="source-line-no">396</span><span id="line-396"> if (cachingBlockReader == null) {</span> |
| <span class="source-line-no">397</span><span id="line-397"> throw new IOException(</span> |
| <span class="source-line-no">398</span><span id="line-398"> "Have to read the middle leaf block but " + "no block reader available");</span> |
| <span class="source-line-no">399</span><span id="line-399"> }</span> |
| <span class="source-line-no">400</span><span id="line-400"></span> |
| <span class="source-line-no">401</span><span id="line-401"> // Caching, using pread, assuming this is not a compaction.</span> |
| <span class="source-line-no">402</span><span id="line-402"> HFileBlock midLeafBlock = cachingBlockReader.readBlock(midLeafBlockOffset,</span> |
| <span class="source-line-no">403</span><span id="line-403"> midLeafBlockOnDiskSize, true, true, false, true, BlockType.LEAF_INDEX, null);</span> |
| <span class="source-line-no">404</span><span id="line-404"> try {</span> |
| <span class="source-line-no">405</span><span id="line-405"> byte[] bytes = getNonRootIndexedKey(midLeafBlock.getBufferWithoutHeader(), midKeyEntry);</span> |
| <span class="source-line-no">406</span><span id="line-406"> assert bytes != null;</span> |
| <span class="source-line-no">407</span><span id="line-407"> targetMidKey = new KeyValue.KeyOnlyKeyValue(bytes, 0, bytes.length);</span> |
| <span class="source-line-no">408</span><span id="line-408"> } finally {</span> |
| <span class="source-line-no">409</span><span id="line-409"> midLeafBlock.release();</span> |
| <span class="source-line-no">410</span><span id="line-410"> }</span> |
| <span class="source-line-no">411</span><span id="line-411"> } else {</span> |
| <span class="source-line-no">412</span><span id="line-412"> // The middle of the root-level index.</span> |
| <span class="source-line-no">413</span><span id="line-413"> targetMidKey = blockKeys[rootCount / 2];</span> |
| <span class="source-line-no">414</span><span id="line-414"> }</span> |
| <span class="source-line-no">415</span><span id="line-415"></span> |
| <span class="source-line-no">416</span><span id="line-416"> this.midKey.set(targetMidKey);</span> |
| <span class="source-line-no">417</span><span id="line-417"> return targetMidKey;</span> |
| <span class="source-line-no">418</span><span id="line-418"> }</span> |
| <span class="source-line-no">419</span><span id="line-419"></span> |
| <span class="source-line-no">420</span><span id="line-420"> @Override</span> |
| <span class="source-line-no">421</span><span id="line-421"> protected void initialize(int numEntries) {</span> |
| <span class="source-line-no">422</span><span id="line-422"> blockKeys = new ExtendedCell[numEntries];</span> |
| <span class="source-line-no">423</span><span id="line-423"> }</span> |
| <span class="source-line-no">424</span><span id="line-424"></span> |
| <span class="source-line-no">425</span><span id="line-425"> /**</span> |
| <span class="source-line-no">426</span><span id="line-426"> * Adds a new entry in the root block index. Only used when reading.</span> |
| <span class="source-line-no">427</span><span id="line-427"> * @param key Last key in the block</span> |
| <span class="source-line-no">428</span><span id="line-428"> * @param offset file offset where the block is stored</span> |
| <span class="source-line-no">429</span><span id="line-429"> * @param dataSize the uncompressed data size</span> |
| <span class="source-line-no">430</span><span id="line-430"> */</span> |
| <span class="source-line-no">431</span><span id="line-431"> @Override</span> |
| <span class="source-line-no">432</span><span id="line-432"> protected void add(final byte[] key, final long offset, final int dataSize) {</span> |
| <span class="source-line-no">433</span><span id="line-433"> blockOffsets[rootCount] = offset;</span> |
| <span class="source-line-no">434</span><span id="line-434"> // Create the blockKeys as Cells once when the reader is opened</span> |
| <span class="source-line-no">435</span><span id="line-435"> blockKeys[rootCount] = new KeyValue.KeyOnlyKeyValue(key, 0, key.length);</span> |
| <span class="source-line-no">436</span><span id="line-436"> blockDataSizes[rootCount] = dataSize;</span> |
| <span class="source-line-no">437</span><span id="line-437"> rootCount++;</span> |
| <span class="source-line-no">438</span><span id="line-438"> }</span> |
| <span class="source-line-no">439</span><span id="line-439"></span> |
| <span class="source-line-no">440</span><span id="line-440"> @Override</span> |
| <span class="source-line-no">441</span><span id="line-441"> public int rootBlockContainingKey(final byte[] key, int offset, int length,</span> |
| <span class="source-line-no">442</span><span id="line-442"> CellComparator comp) {</span> |
| <span class="source-line-no">443</span><span id="line-443"> // This should always be called with Cell not with a byte[] key</span> |
| <span class="source-line-no">444</span><span id="line-444"> throw new UnsupportedOperationException("Cannot find for a key containing plain byte "</span> |
| <span class="source-line-no">445</span><span id="line-445"> + "array. Only cell based keys can be searched for");</span> |
| <span class="source-line-no">446</span><span id="line-446"> }</span> |
| <span class="source-line-no">447</span><span id="line-447"></span> |
| <span class="source-line-no">448</span><span id="line-448"> @Override</span> |
| <span class="source-line-no">449</span><span id="line-449"> public int rootBlockContainingKey(Cell key) {</span> |
| <span class="source-line-no">450</span><span id="line-450"> // Here the comparator should not be null as this happens for the root-level block</span> |
| <span class="source-line-no">451</span><span id="line-451"> int pos = Bytes.binarySearch(blockKeys, key, comparator);</span> |
| <span class="source-line-no">452</span><span id="line-452"> // pos is between -(blockKeys.length + 1) to blockKeys.length - 1, see</span> |
| <span class="source-line-no">453</span><span id="line-453"> // binarySearch's javadoc.</span> |
| <span class="source-line-no">454</span><span id="line-454"></span> |
| <span class="source-line-no">455</span><span id="line-455"> if (pos >= 0) {</span> |
| <span class="source-line-no">456</span><span id="line-456"> // This means this is an exact match with an element of blockKeys.</span> |
| <span class="source-line-no">457</span><span id="line-457"> assert pos < blockKeys.length;</span> |
| <span class="source-line-no">458</span><span id="line-458"> return pos;</span> |
| <span class="source-line-no">459</span><span id="line-459"> }</span> |
| <span class="source-line-no">460</span><span id="line-460"></span> |
| <span class="source-line-no">461</span><span id="line-461"> // Otherwise, pos = -(i + 1), where blockKeys[i - 1] < key < blockKeys[i],</span> |
| <span class="source-line-no">462</span><span id="line-462"> // and i is in [0, blockKeys.length]. We are returning j = i - 1 such that</span> |
| <span class="source-line-no">463</span><span id="line-463"> // blockKeys[j] <= key < blockKeys[j + 1]. In particular, j = -1 if</span> |
| <span class="source-line-no">464</span><span id="line-464"> // key < blockKeys[0], meaning the file does not contain the given key.</span> |
| <span class="source-line-no">465</span><span id="line-465"></span> |
| <span class="source-line-no">466</span><span id="line-466"> int i = -pos - 1;</span> |
| <span class="source-line-no">467</span><span id="line-467"> assert 0 <= i && i <= blockKeys.length;</span> |
| <span class="source-line-no">468</span><span id="line-468"> return i - 1;</span> |
| <span class="source-line-no">469</span><span id="line-469"> }</span> |
| <span class="source-line-no">470</span><span id="line-470"></span> |
| <span class="source-line-no">471</span><span id="line-471"> @Override</span> |
| <span class="source-line-no">472</span><span id="line-472"> public String toString() {</span> |
| <span class="source-line-no">473</span><span id="line-473"> StringBuilder sb = new StringBuilder();</span> |
| <span class="source-line-no">474</span><span id="line-474"> sb.append("size=" + rootCount).append("\n");</span> |
| <span class="source-line-no">475</span><span id="line-475"> for (int i = 0; i < rootCount; i++) {</span> |
| <span class="source-line-no">476</span><span id="line-476"> sb.append("key=").append((blockKeys[i])).append("\n offset=").append(blockOffsets[i])</span> |
| <span class="source-line-no">477</span><span id="line-477"> .append(", dataSize=" + blockDataSizes[i]).append("\n");</span> |
| <span class="source-line-no">478</span><span id="line-478"> }</span> |
| <span class="source-line-no">479</span><span id="line-479"> return sb.toString();</span> |
| <span class="source-line-no">480</span><span id="line-480"> }</span> |
| <span class="source-line-no">481</span><span id="line-481"> }</span> |
| <span class="source-line-no">482</span><span id="line-482"></span> |
| <span class="source-line-no">483</span><span id="line-483"> static class CellBasedKeyBlockIndexReaderV2 extends CellBasedKeyBlockIndexReader {</span> |
| <span class="source-line-no">484</span><span id="line-484"></span> |
| <span class="source-line-no">485</span><span id="line-485"> private HFileIndexBlockEncoder indexBlockEncoder;</span> |
| <span class="source-line-no">486</span><span id="line-486"></span> |
| <span class="source-line-no">487</span><span id="line-487"> private HFileIndexBlockEncoder.EncodedSeeker seeker;</span> |
| <span class="source-line-no">488</span><span id="line-488"></span> |
| <span class="source-line-no">489</span><span id="line-489"> public CellBasedKeyBlockIndexReaderV2(final CellComparator c, final int treeLevel) {</span> |
| <span class="source-line-no">490</span><span id="line-490"> this(c, treeLevel, null);</span> |
| <span class="source-line-no">491</span><span id="line-491"> }</span> |
| <span class="source-line-no">492</span><span id="line-492"></span> |
| <span class="source-line-no">493</span><span id="line-493"> public CellBasedKeyBlockIndexReaderV2(final CellComparator c, final int treeLevel,</span> |
| <span class="source-line-no">494</span><span id="line-494"> HFileIndexBlockEncoder indexBlockEncoder) {</span> |
| <span class="source-line-no">495</span><span id="line-495"> super(c, treeLevel);</span> |
| <span class="source-line-no">496</span><span id="line-496"> // Can be null for METAINDEX block</span> |
| <span class="source-line-no">497</span><span id="line-497"> this.indexBlockEncoder =</span> |
| <span class="source-line-no">498</span><span id="line-498"> indexBlockEncoder != null ? indexBlockEncoder : NoOpIndexBlockEncoder.INSTANCE;</span> |
| <span class="source-line-no">499</span><span id="line-499"> }</span> |
| <span class="source-line-no">500</span><span id="line-500"></span> |
| <span class="source-line-no">501</span><span id="line-501"> @Override</span> |
| <span class="source-line-no">502</span><span id="line-502"> public boolean isEmpty() {</span> |
| <span class="source-line-no">503</span><span id="line-503"> return seeker.isEmpty();</span> |
| <span class="source-line-no">504</span><span id="line-504"> }</span> |
| <span class="source-line-no">505</span><span id="line-505"></span> |
| <span class="source-line-no">506</span><span id="line-506"> @Override</span> |
| <span class="source-line-no">507</span><span id="line-507"> public BlockWithScanInfo loadDataBlockWithScanInfo(ExtendedCell key, HFileBlock currentBlock,</span> |
| <span class="source-line-no">508</span><span id="line-508"> boolean cacheBlocks, boolean pread, boolean isCompaction,</span> |
| <span class="source-line-no">509</span><span id="line-509"> DataBlockEncoding expectedDataBlockEncoding, CachingBlockReader cachingBlockReader)</span> |
| <span class="source-line-no">510</span><span id="line-510"> throws IOException {</span> |
| <span class="source-line-no">511</span><span id="line-511"> return seeker.loadDataBlockWithScanInfo(key, currentBlock, cacheBlocks, pread, isCompaction,</span> |
| <span class="source-line-no">512</span><span id="line-512"> expectedDataBlockEncoding, cachingBlockReader);</span> |
| <span class="source-line-no">513</span><span id="line-513"> }</span> |
| <span class="source-line-no">514</span><span id="line-514"></span> |
| <span class="source-line-no">515</span><span id="line-515"> @Override</span> |
| <span class="source-line-no">516</span><span id="line-516"> public ExtendedCell midkey(CachingBlockReader cachingBlockReader) throws IOException {</span> |
| <span class="source-line-no">517</span><span id="line-517"> return seeker.midkey(cachingBlockReader);</span> |
| <span class="source-line-no">518</span><span id="line-518"> }</span> |
| <span class="source-line-no">519</span><span id="line-519"></span> |
| <span class="source-line-no">520</span><span id="line-520"> /**</span> |
| <span class="source-line-no">521</span><span id="line-521"> * from 0 to {@link #getRootBlockCount() - 1}</span> |
| <span class="source-line-no">522</span><span id="line-522"> */</span> |
| <span class="source-line-no">523</span><span id="line-523"> public ExtendedCell getRootBlockKey(int i) {</span> |
| <span class="source-line-no">524</span><span id="line-524"> return seeker.getRootBlockKey(i);</span> |
| <span class="source-line-no">525</span><span id="line-525"> }</span> |
| <span class="source-line-no">526</span><span id="line-526"></span> |
| <span class="source-line-no">527</span><span id="line-527"> @Override</span> |
| <span class="source-line-no">528</span><span id="line-528"> public int getRootBlockCount() {</span> |
| <span class="source-line-no">529</span><span id="line-529"> return seeker.getRootBlockCount();</span> |
| <span class="source-line-no">530</span><span id="line-530"> }</span> |
| <span class="source-line-no">531</span><span id="line-531"></span> |
| <span class="source-line-no">532</span><span id="line-532"> @Override</span> |
| <span class="source-line-no">533</span><span id="line-533"> public int rootBlockContainingKey(Cell key) {</span> |
| <span class="source-line-no">534</span><span id="line-534"> return seeker.rootBlockContainingKey(key);</span> |
| <span class="source-line-no">535</span><span id="line-535"> }</span> |
| <span class="source-line-no">536</span><span id="line-536"></span> |
| <span class="source-line-no">537</span><span id="line-537"> @Override</span> |
| <span class="source-line-no">538</span><span id="line-538"> protected long calculateHeapSizeForBlockKeys(long heapSize) {</span> |
| <span class="source-line-no">539</span><span id="line-539"> heapSize = super.calculateHeapSizeForBlockKeys(heapSize);</span> |
| <span class="source-line-no">540</span><span id="line-540"> if (seeker != null) {</span> |
| <span class="source-line-no">541</span><span id="line-541"> heapSize += ClassSize.REFERENCE;</span> |
| <span class="source-line-no">542</span><span id="line-542"> heapSize += ClassSize.align(seeker.heapSize());</span> |
| <span class="source-line-no">543</span><span id="line-543"> }</span> |
| <span class="source-line-no">544</span><span id="line-544"> return heapSize;</span> |
| <span class="source-line-no">545</span><span id="line-545"> }</span> |
| <span class="source-line-no">546</span><span id="line-546"></span> |
| <span class="source-line-no">547</span><span id="line-547"> @Override</span> |
| <span class="source-line-no">548</span><span id="line-548"> public void readMultiLevelIndexRoot(HFileBlock blk, final int numEntries) throws IOException {</span> |
| <span class="source-line-no">549</span><span id="line-549"> seeker = indexBlockEncoder.createSeeker();</span> |
| <span class="source-line-no">550</span><span id="line-550"> seeker.initRootIndex(blk, numEntries, comparator, searchTreeLevel);</span> |
| <span class="source-line-no">551</span><span id="line-551"> }</span> |
| <span class="source-line-no">552</span><span id="line-552"></span> |
| <span class="source-line-no">553</span><span id="line-553"> @Override</span> |
| <span class="source-line-no">554</span><span id="line-554"> public String toString() {</span> |
| <span class="source-line-no">555</span><span id="line-555"> return seeker.toString();</span> |
| <span class="source-line-no">556</span><span id="line-556"> }</span> |
| <span class="source-line-no">557</span><span id="line-557"> }</span> |
| <span class="source-line-no">558</span><span id="line-558"></span> |
| <span class="source-line-no">559</span><span id="line-559"> /**</span> |
| <span class="source-line-no">560</span><span id="line-560"> * The reader will always hold the root level index in the memory. Index blocks at all other</span> |
| <span class="source-line-no">561</span><span id="line-561"> * levels will be cached in the LRU cache in practice, although this API does not enforce that.</span> |
| <span class="source-line-no">562</span><span id="line-562"> * <p></span> |
| <span class="source-line-no">563</span><span id="line-563"> * All non-root (leaf and intermediate) index blocks contain what we call a "secondary index": an</span> |
| <span class="source-line-no">564</span><span id="line-564"> * array of offsets to the entries within the block. This allows us to do binary search for the</span> |
| <span class="source-line-no">565</span><span id="line-565"> * entry corresponding to the given key without having to deserialize the block.</span> |
| <span class="source-line-no">566</span><span id="line-566"> */</span> |
| <span class="source-line-no">567</span><span id="line-567"> static abstract class BlockIndexReader implements HeapSize {</span> |
| <span class="source-line-no">568</span><span id="line-568"></span> |
| <span class="source-line-no">569</span><span id="line-569"> protected long[] blockOffsets;</span> |
| <span class="source-line-no">570</span><span id="line-570"> protected int[] blockDataSizes;</span> |
| <span class="source-line-no">571</span><span id="line-571"> protected int rootCount = 0;</span> |
| <span class="source-line-no">572</span><span id="line-572"></span> |
| <span class="source-line-no">573</span><span id="line-573"> // Mid-key metadata.</span> |
| <span class="source-line-no">574</span><span id="line-574"> protected long midLeafBlockOffset = -1;</span> |
| <span class="source-line-no">575</span><span id="line-575"> protected int midLeafBlockOnDiskSize = -1;</span> |
| <span class="source-line-no">576</span><span id="line-576"> protected int midKeyEntry = -1;</span> |
| <span class="source-line-no">577</span><span id="line-577"></span> |
| <span class="source-line-no">578</span><span id="line-578"> /**</span> |
| <span class="source-line-no">579</span><span id="line-579"> * The number of levels in the block index tree. One if there is only root level, two for root</span> |
| <span class="source-line-no">580</span><span id="line-580"> * and leaf levels, etc.</span> |
| <span class="source-line-no">581</span><span id="line-581"> */</span> |
| <span class="source-line-no">582</span><span id="line-582"> protected int searchTreeLevel;</span> |
| <span class="source-line-no">583</span><span id="line-583"></span> |
| <span class="source-line-no">584</span><span id="line-584"> /** Returns true if the block index is empty. */</span> |
| <span class="source-line-no">585</span><span id="line-585"> public abstract boolean isEmpty();</span> |
| <span class="source-line-no">586</span><span id="line-586"></span> |
| <span class="source-line-no">587</span><span id="line-587"> /**</span> |
| <span class="source-line-no">588</span><span id="line-588"> * Verifies that the block index is non-empty and throws an {@link IllegalStateException}</span> |
| <span class="source-line-no">589</span><span id="line-589"> * otherwise.</span> |
| <span class="source-line-no">590</span><span id="line-590"> */</span> |
| <span class="source-line-no">591</span><span id="line-591"> public void ensureNonEmpty() {</span> |
| <span class="source-line-no">592</span><span id="line-592"> if (isEmpty()) {</span> |
| <span class="source-line-no">593</span><span id="line-593"> throw new IllegalStateException("Block index is empty or not loaded");</span> |
| <span class="source-line-no">594</span><span id="line-594"> }</span> |
| <span class="source-line-no">595</span><span id="line-595"> }</span> |
| <span class="source-line-no">596</span><span id="line-596"></span> |
| <span class="source-line-no">597</span><span id="line-597"> /**</span> |
| <span class="source-line-no">598</span><span id="line-598"> * Return the data block which contains this key. This function will only be called when the</span> |
| <span class="source-line-no">599</span><span id="line-599"> * HFile version is larger than 1.</span> |
| <span class="source-line-no">600</span><span id="line-600"> * @param key the key we are looking for</span> |
| <span class="source-line-no">601</span><span id="line-601"> * @param currentBlock the current block, to avoid re-reading the same block</span> |
| <span class="source-line-no">602</span><span id="line-602"> * @param expectedDataBlockEncoding the data block encoding the caller is expecting the data</span> |
| <span class="source-line-no">603</span><span id="line-603"> * block to be in, or null to not perform this check and return</span> |
| <span class="source-line-no">604</span><span id="line-604"> * the block irrespective of the encoding</span> |
| <span class="source-line-no">605</span><span id="line-605"> * @return reader a basic way to load blocks</span> |
| <span class="source-line-no">606</span><span id="line-606"> */</span> |
| <span class="source-line-no">607</span><span id="line-607"> public HFileBlock seekToDataBlock(final ExtendedCell key, HFileBlock currentBlock,</span> |
| <span class="source-line-no">608</span><span id="line-608"> boolean cacheBlocks, boolean pread, boolean isCompaction,</span> |
| <span class="source-line-no">609</span><span id="line-609"> DataBlockEncoding expectedDataBlockEncoding, CachingBlockReader cachingBlockReader)</span> |
| <span class="source-line-no">610</span><span id="line-610"> throws IOException {</span> |
| <span class="source-line-no">611</span><span id="line-611"> BlockWithScanInfo blockWithScanInfo = loadDataBlockWithScanInfo(key, currentBlock,</span> |
| <span class="source-line-no">612</span><span id="line-612"> cacheBlocks, pread, isCompaction, expectedDataBlockEncoding, cachingBlockReader);</span> |
| <span class="source-line-no">613</span><span id="line-613"> if (blockWithScanInfo == null) {</span> |
| <span class="source-line-no">614</span><span id="line-614"> return null;</span> |
| <span class="source-line-no">615</span><span id="line-615"> } else {</span> |
| <span class="source-line-no">616</span><span id="line-616"> return blockWithScanInfo.getHFileBlock();</span> |
| <span class="source-line-no">617</span><span id="line-617"> }</span> |
| <span class="source-line-no">618</span><span id="line-618"> }</span> |
| <span class="source-line-no">619</span><span id="line-619"></span> |
| <span class="source-line-no">620</span><span id="line-620"> /**</span> |
| <span class="source-line-no">621</span><span id="line-621"> * Return the BlockWithScanInfo, a data structure which contains the Data HFileBlock with other</span> |
| <span class="source-line-no">622</span><span id="line-622"> * scan info such as the key that starts the next HFileBlock. This function will only be called</span> |
| <span class="source-line-no">623</span><span id="line-623"> * when the HFile version is larger than 1.</span> |
| <span class="source-line-no">624</span><span id="line-624"> * @param key the key we are looking for</span> |
| <span class="source-line-no">625</span><span id="line-625"> * @param currentBlock the current block, to avoid re-reading the same block</span> |
| <span class="source-line-no">626</span><span id="line-626"> * @param expectedDataBlockEncoding the data block encoding the caller is expecting the data</span> |
| <span class="source-line-no">627</span><span id="line-627"> * block to be in, or null to not perform this check and return</span> |
| <span class="source-line-no">628</span><span id="line-628"> * the block irrespective of the encoding.</span> |
| <span class="source-line-no">629</span><span id="line-629"> * @return the BlockWithScanInfo which contains the DataBlock with other scan info such as</span> |
| <span class="source-line-no">630</span><span id="line-630"> * nextIndexedKey.</span> |
| <span class="source-line-no">631</span><span id="line-631"> */</span> |
| <span class="source-line-no">632</span><span id="line-632"> public abstract BlockWithScanInfo loadDataBlockWithScanInfo(ExtendedCell key,</span> |
| <span class="source-line-no">633</span><span id="line-633"> HFileBlock currentBlock, boolean cacheBlocks, boolean pread, boolean isCompaction,</span> |
| <span class="source-line-no">634</span><span id="line-634"> DataBlockEncoding expectedDataBlockEncoding, CachingBlockReader cachingBlockReader)</span> |
| <span class="source-line-no">635</span><span id="line-635"> throws IOException;</span> |
| <span class="source-line-no">636</span><span id="line-636"></span> |
| <span class="source-line-no">637</span><span id="line-637"> /**</span> |
| <span class="source-line-no">638</span><span id="line-638"> * An approximation to the {@link HFile}'s mid-key. Operates on block boundaries, and does not</span> |
| <span class="source-line-no">639</span><span id="line-639"> * go inside blocks. In other words, returns the first key of the middle block of the file.</span> |
| <span class="source-line-no">640</span><span id="line-640"> * @return the first key of the middle block</span> |
| <span class="source-line-no">641</span><span id="line-641"> */</span> |
| <span class="source-line-no">642</span><span id="line-642"> public abstract Cell midkey(CachingBlockReader cachingBlockReader) throws IOException;</span> |
| <span class="source-line-no">643</span><span id="line-643"></span> |
| <span class="source-line-no">644</span><span id="line-644"> /**</span> |
| <span class="source-line-no">645</span><span id="line-645"> * @param i from 0 to {@link #getRootBlockCount() - 1}</span> |
| <span class="source-line-no">646</span><span id="line-646"> */</span> |
| <span class="source-line-no">647</span><span id="line-647"> public long getRootBlockOffset(int i) {</span> |
| <span class="source-line-no">648</span><span id="line-648"> return blockOffsets[i];</span> |
| <span class="source-line-no">649</span><span id="line-649"> }</span> |
| <span class="source-line-no">650</span><span id="line-650"></span> |
| <span class="source-line-no">651</span><span id="line-651"> /**</span> |
| <span class="source-line-no">652</span><span id="line-652"> * @param i zero-based index of a root-level block</span> |
| <span class="source-line-no">653</span><span id="line-653"> * @return the on-disk size of the root-level block for version 2, or the uncompressed size for</span> |
| <span class="source-line-no">654</span><span id="line-654"> * version 1</span> |
| <span class="source-line-no">655</span><span id="line-655"> */</span> |
| <span class="source-line-no">656</span><span id="line-656"> public int getRootBlockDataSize(int i) {</span> |
| <span class="source-line-no">657</span><span id="line-657"> return blockDataSizes[i];</span> |
| <span class="source-line-no">658</span><span id="line-658"> }</span> |
| <span class="source-line-no">659</span><span id="line-659"></span> |
| <span class="source-line-no">660</span><span id="line-660"> /** Returns the number of root-level blocks in this block index */</span> |
| <span class="source-line-no">661</span><span id="line-661"> public int getRootBlockCount() {</span> |
| <span class="source-line-no">662</span><span id="line-662"> return rootCount;</span> |
| <span class="source-line-no">663</span><span id="line-663"> }</span> |
| <span class="source-line-no">664</span><span id="line-664"></span> |
| <span class="source-line-no">665</span><span id="line-665"> /**</span> |
| <span class="source-line-no">666</span><span id="line-666"> * Finds the root-level index block containing the given key. Key to find the comparator to be</span> |
| <span class="source-line-no">667</span><span id="line-667"> * used</span> |
| <span class="source-line-no">668</span><span id="line-668"> * @return Offset of block containing <code>key</code> (between 0 and the number of blocks - 1)</span> |
| <span class="source-line-no">669</span><span id="line-669"> * or -1 if this file does not contain the request.</span> |
| <span class="source-line-no">670</span><span id="line-670"> */</span> |
| <span class="source-line-no">671</span><span id="line-671"> // When we want to find the meta index block or bloom block for ROW bloom</span> |
| <span class="source-line-no">672</span><span id="line-672"> // type Bytes.BYTES_RAWCOMPARATOR would be enough. For the ROW_COL bloom case we need the</span> |
| <span class="source-line-no">673</span><span id="line-673"> // CellComparator.</span> |
| <span class="source-line-no">674</span><span id="line-674"> public abstract int rootBlockContainingKey(final byte[] key, int offset, int length,</span> |
| <span class="source-line-no">675</span><span id="line-675"> CellComparator comp);</span> |
| <span class="source-line-no">676</span><span id="line-676"></span> |
| <span class="source-line-no">677</span><span id="line-677"> /**</span> |
| <span class="source-line-no">678</span><span id="line-678"> * Finds the root-level index block containing the given key. Key to find</span> |
| <span class="source-line-no">679</span><span id="line-679"> * @return Offset of block containing <code>key</code> (between 0 and the number of blocks - 1)</span> |
| <span class="source-line-no">680</span><span id="line-680"> * or -1 if this file does not contain the request.</span> |
| <span class="source-line-no">681</span><span id="line-681"> */</span> |
| <span class="source-line-no">682</span><span id="line-682"> // When we want to find the meta index block or bloom block for ROW bloom</span> |
| <span class="source-line-no">683</span><span id="line-683"> // type</span> |
| <span class="source-line-no">684</span><span id="line-684"> // Bytes.BYTES_RAWCOMPARATOR would be enough. For the ROW_COL bloom case we</span> |
| <span class="source-line-no">685</span><span id="line-685"> // need the CellComparator.</span> |
| <span class="source-line-no">686</span><span id="line-686"> public int rootBlockContainingKey(final byte[] key, int offset, int length) {</span> |
| <span class="source-line-no">687</span><span id="line-687"> return rootBlockContainingKey(key, offset, length, null);</span> |
| <span class="source-line-no">688</span><span id="line-688"> }</span> |
| <span class="source-line-no">689</span><span id="line-689"></span> |
| <span class="source-line-no">690</span><span id="line-690"> /**</span> |
| <span class="source-line-no">691</span><span id="line-691"> * Finds the root-level index block containing the given key. Key to find</span> |
| <span class="source-line-no">692</span><span id="line-692"> */</span> |
| <span class="source-line-no">693</span><span id="line-693"> public abstract int rootBlockContainingKey(final Cell key);</span> |
| <span class="source-line-no">694</span><span id="line-694"></span> |
| <span class="source-line-no">695</span><span id="line-695"> /**</span> |
| <span class="source-line-no">696</span><span id="line-696"> * The indexed key at the ith position in the nonRootIndex. The position starts at 0.</span> |
| <span class="source-line-no">697</span><span id="line-697"> * @param i the ith position</span> |
| <span class="source-line-no">698</span><span id="line-698"> * @return The indexed key at the ith position in the nonRootIndex.</span> |
| <span class="source-line-no">699</span><span id="line-699"> */</span> |
| <span class="source-line-no">700</span><span id="line-700"> static byte[] getNonRootIndexedKey(ByteBuff nonRootIndex, int i) {</span> |
| <span class="source-line-no">701</span><span id="line-701"> int numEntries = nonRootIndex.getInt(0);</span> |
| <span class="source-line-no">702</span><span id="line-702"> if (i < 0 || i >= numEntries) {</span> |
| <span class="source-line-no">703</span><span id="line-703"> return null;</span> |
| <span class="source-line-no">704</span><span id="line-704"> }</span> |
| <span class="source-line-no">705</span><span id="line-705"></span> |
| <span class="source-line-no">706</span><span id="line-706"> // Entries start after the number of entries and the secondary index.</span> |
| <span class="source-line-no">707</span><span id="line-707"> // The secondary index takes numEntries + 1 ints.</span> |
| <span class="source-line-no">708</span><span id="line-708"> int entriesOffset = Bytes.SIZEOF_INT * (numEntries + 2);</span> |
| <span class="source-line-no">709</span><span id="line-709"> // Targetkey's offset relative to the end of secondary index</span> |
| <span class="source-line-no">710</span><span id="line-710"> int targetKeyRelOffset = nonRootIndex.getInt(Bytes.SIZEOF_INT * (i + 1));</span> |
| <span class="source-line-no">711</span><span id="line-711"></span> |
| <span class="source-line-no">712</span><span id="line-712"> // The offset of the target key in the blockIndex buffer</span> |
| <span class="source-line-no">713</span><span id="line-713"> int targetKeyOffset = entriesOffset // Skip secondary index</span> |
| <span class="source-line-no">714</span><span id="line-714"> + targetKeyRelOffset // Skip all entries until mid</span> |
| <span class="source-line-no">715</span><span id="line-715"> + SECONDARY_INDEX_ENTRY_OVERHEAD; // Skip offset and on-disk-size</span> |
| <span class="source-line-no">716</span><span id="line-716"></span> |
| <span class="source-line-no">717</span><span id="line-717"> // We subtract the two consecutive secondary index elements, which</span> |
| <span class="source-line-no">718</span><span id="line-718"> // gives us the size of the whole (offset, onDiskSize, key) tuple. We</span> |
| <span class="source-line-no">719</span><span id="line-719"> // then need to subtract the overhead of offset and onDiskSize.</span> |
| <span class="source-line-no">720</span><span id="line-720"> int targetKeyLength = nonRootIndex.getInt(Bytes.SIZEOF_INT * (i + 2)) - targetKeyRelOffset</span> |
| <span class="source-line-no">721</span><span id="line-721"> - SECONDARY_INDEX_ENTRY_OVERHEAD;</span> |
| <span class="source-line-no">722</span><span id="line-722"></span> |
| <span class="source-line-no">723</span><span id="line-723"> // TODO check whether we can make BB backed Cell here? So can avoid bytes copy.</span> |
| <span class="source-line-no">724</span><span id="line-724"> return nonRootIndex.toBytes(targetKeyOffset, targetKeyLength);</span> |
| <span class="source-line-no">725</span><span id="line-725"> }</span> |
| <span class="source-line-no">726</span><span id="line-726"></span> |
| <span class="source-line-no">727</span><span id="line-727"> /**</span> |
| <span class="source-line-no">728</span><span id="line-728"> * Performs a binary search over a non-root level index block. Utilizes the secondary index,</span> |
| <span class="source-line-no">729</span><span id="line-729"> * which records the offsets of (offset, onDiskSize, firstKey) tuples of all entries. the key we</span> |
| <span class="source-line-no">730</span><span id="line-730"> * are searching for offsets to individual entries in the blockIndex buffer the non-root index</span> |
| <span class="source-line-no">731</span><span id="line-731"> * block buffer, starting with the secondary index. The position is ignored.</span> |
| <span class="source-line-no">732</span><span id="line-732"> * @return the index i in [0, numEntries - 1] such that keys[i] <= key < keys[i + 1], if keys is</span> |
| <span class="source-line-no">733</span><span id="line-733"> * the array of all keys being searched, or -1 otherwise</span> |
| <span class="source-line-no">734</span><span id="line-734"> */</span> |
| <span class="source-line-no">735</span><span id="line-735"> static int binarySearchNonRootIndex(Cell key, ByteBuff nonRootIndex,</span> |
| <span class="source-line-no">736</span><span id="line-736"> CellComparator comparator) {</span> |
| <span class="source-line-no">737</span><span id="line-737"></span> |
| <span class="source-line-no">738</span><span id="line-738"> int numEntries = nonRootIndex.getIntAfterPosition(0);</span> |
| <span class="source-line-no">739</span><span id="line-739"> int low = 0;</span> |
| <span class="source-line-no">740</span><span id="line-740"> int high = numEntries - 1;</span> |
| <span class="source-line-no">741</span><span id="line-741"> int mid = 0;</span> |
| <span class="source-line-no">742</span><span id="line-742"></span> |
| <span class="source-line-no">743</span><span id="line-743"> // Entries start after the number of entries and the secondary index.</span> |
| <span class="source-line-no">744</span><span id="line-744"> // The secondary index takes numEntries + 1 ints.</span> |
| <span class="source-line-no">745</span><span id="line-745"> int entriesOffset = Bytes.SIZEOF_INT * (numEntries + 2);</span> |
| <span class="source-line-no">746</span><span id="line-746"></span> |
| <span class="source-line-no">747</span><span id="line-747"> // If we imagine that keys[-1] = -Infinity and</span> |
| <span class="source-line-no">748</span><span id="line-748"> // keys[numEntries] = Infinity, then we are maintaining an invariant that</span> |
| <span class="source-line-no">749</span><span id="line-749"> // keys[low - 1] < key < keys[high + 1] while narrowing down the range.</span> |
| <span class="source-line-no">750</span><span id="line-750"> ByteBufferKeyOnlyKeyValue nonRootIndexkeyOnlyKV = new ByteBufferKeyOnlyKeyValue();</span> |
| <span class="source-line-no">751</span><span id="line-751"> ObjectIntPair<ByteBuffer> pair = new ObjectIntPair<>();</span> |
| <span class="source-line-no">752</span><span id="line-752"> while (low <= high) {</span> |
| <span class="source-line-no">753</span><span id="line-753"> mid = low + ((high - low) >> 1);</span> |
| <span class="source-line-no">754</span><span id="line-754"></span> |
| <span class="source-line-no">755</span><span id="line-755"> // Midkey's offset relative to the end of secondary index</span> |
| <span class="source-line-no">756</span><span id="line-756"> int midKeyRelOffset = nonRootIndex.getIntAfterPosition(Bytes.SIZEOF_INT * (mid + 1));</span> |
| <span class="source-line-no">757</span><span id="line-757"></span> |
| <span class="source-line-no">758</span><span id="line-758"> // The offset of the middle key in the blockIndex buffer</span> |
| <span class="source-line-no">759</span><span id="line-759"> int midKeyOffset = entriesOffset // Skip secondary index</span> |
| <span class="source-line-no">760</span><span id="line-760"> + midKeyRelOffset // Skip all entries until mid</span> |
| <span class="source-line-no">761</span><span id="line-761"> + SECONDARY_INDEX_ENTRY_OVERHEAD; // Skip offset and on-disk-size</span> |
| <span class="source-line-no">762</span><span id="line-762"></span> |
| <span class="source-line-no">763</span><span id="line-763"> // We subtract the two consecutive secondary index elements, which</span> |
| <span class="source-line-no">764</span><span id="line-764"> // gives us the size of the whole (offset, onDiskSize, key) tuple. We</span> |
| <span class="source-line-no">765</span><span id="line-765"> // then need to subtract the overhead of offset and onDiskSize.</span> |
| <span class="source-line-no">766</span><span id="line-766"> int midLength = nonRootIndex.getIntAfterPosition(Bytes.SIZEOF_INT * (mid + 2))</span> |
| <span class="source-line-no">767</span><span id="line-767"> - midKeyRelOffset - SECONDARY_INDEX_ENTRY_OVERHEAD;</span> |
| <span class="source-line-no">768</span><span id="line-768"></span> |
| <span class="source-line-no">769</span><span id="line-769"> // we have to compare in this order, because the comparator order</span> |
| <span class="source-line-no">770</span><span id="line-770"> // has special logic when the 'left side' is a special key.</span> |
| <span class="source-line-no">771</span><span id="line-771"> // TODO make KeyOnlyKeyValue to be Buffer backed and avoid array() call. This has to be</span> |
| <span class="source-line-no">772</span><span id="line-772"> // done after HBASE-12224 & HBASE-12282</span> |
| <span class="source-line-no">773</span><span id="line-773"> // TODO avoid array call.</span> |
| <span class="source-line-no">774</span><span id="line-774"> nonRootIndex.asSubByteBuffer(midKeyOffset, midLength, pair);</span> |
| <span class="source-line-no">775</span><span id="line-775"> nonRootIndexkeyOnlyKV.setKey(pair.getFirst(), pair.getSecond(), midLength);</span> |
| <span class="source-line-no">776</span><span id="line-776"> int cmp = PrivateCellUtil.compareKeyIgnoresMvcc(comparator, key, nonRootIndexkeyOnlyKV);</span> |
| <span class="source-line-no">777</span><span id="line-777"></span> |
| <span class="source-line-no">778</span><span id="line-778"> // key lives above the midpoint</span> |
| <span class="source-line-no">779</span><span id="line-779"> if (cmp > 0) low = mid + 1; // Maintain the invariant that keys[low - 1] < key</span> |
| <span class="source-line-no">780</span><span id="line-780"> // key lives below the midpoint</span> |
| <span class="source-line-no">781</span><span id="line-781"> else if (cmp < 0) high = mid - 1; // Maintain the invariant that key < keys[high + 1]</span> |
| <span class="source-line-no">782</span><span id="line-782"> else return mid; // exact match</span> |
| <span class="source-line-no">783</span><span id="line-783"> }</span> |
| <span class="source-line-no">784</span><span id="line-784"></span> |
| <span class="source-line-no">785</span><span id="line-785"> // As per our invariant, keys[low - 1] < key < keys[high + 1], meaning</span> |
| <span class="source-line-no">786</span><span id="line-786"> // that low - 1 < high + 1 and (low - high) <= 1. As per the loop break</span> |
| <span class="source-line-no">787</span><span id="line-787"> // condition, low >= high + 1. Therefore, low = high + 1.</span> |
| <span class="source-line-no">788</span><span id="line-788"></span> |
| <span class="source-line-no">789</span><span id="line-789"> if (low != high + 1) {</span> |
| <span class="source-line-no">790</span><span id="line-790"> throw new IllegalStateException(</span> |
| <span class="source-line-no">791</span><span id="line-791"> "Binary search broken: low=" + low + " " + "instead of " + (high + 1));</span> |
| <span class="source-line-no">792</span><span id="line-792"> }</span> |
| <span class="source-line-no">793</span><span id="line-793"></span> |
| <span class="source-line-no">794</span><span id="line-794"> // OK, our invariant says that keys[low - 1] < key < keys[low]. We need to</span> |
| <span class="source-line-no">795</span><span id="line-795"> // return i such that keys[i] <= key < keys[i + 1]. Therefore i = low - 1.</span> |
| <span class="source-line-no">796</span><span id="line-796"> int i = low - 1;</span> |
| <span class="source-line-no">797</span><span id="line-797"></span> |
| <span class="source-line-no">798</span><span id="line-798"> // Some extra validation on the result.</span> |
| <span class="source-line-no">799</span><span id="line-799"> if (i < -1 || i >= numEntries) {</span> |
| <span class="source-line-no">800</span><span id="line-800"> throw new IllegalStateException("Binary search broken: result is " + i</span> |
| <span class="source-line-no">801</span><span id="line-801"> + " but expected to be between -1 and (numEntries - 1) = " + (numEntries - 1));</span> |
| <span class="source-line-no">802</span><span id="line-802"> }</span> |
| <span class="source-line-no">803</span><span id="line-803"></span> |
| <span class="source-line-no">804</span><span id="line-804"> return i;</span> |
| <span class="source-line-no">805</span><span id="line-805"> }</span> |
| <span class="source-line-no">806</span><span id="line-806"></span> |
| <span class="source-line-no">807</span><span id="line-807"> /**</span> |
| <span class="source-line-no">808</span><span id="line-808"> * Search for one key using the secondary index in a non-root block. In case of success,</span> |
| <span class="source-line-no">809</span><span id="line-809"> * positions the provided buffer at the entry of interest, where the file offset and the</span> |
| <span class="source-line-no">810</span><span id="line-810"> * on-disk-size can be read. a non-root block without header. Initial position does not matter.</span> |
| <span class="source-line-no">811</span><span id="line-811"> * the byte array containing the key</span> |
| <span class="source-line-no">812</span><span id="line-812"> * @return the index position where the given key was found, otherwise return -1 in the case the</span> |
| <span class="source-line-no">813</span><span id="line-813"> * given key is before the first key.</span> |
| <span class="source-line-no">814</span><span id="line-814"> */</span> |
| <span class="source-line-no">815</span><span id="line-815"> static int locateNonRootIndexEntry(ByteBuff nonRootBlock, Cell key, CellComparator comparator) {</span> |
| <span class="source-line-no">816</span><span id="line-816"> int entryIndex = binarySearchNonRootIndex(key, nonRootBlock, comparator);</span> |
| <span class="source-line-no">817</span><span id="line-817"></span> |
| <span class="source-line-no">818</span><span id="line-818"> if (entryIndex != -1) {</span> |
| <span class="source-line-no">819</span><span id="line-819"> int numEntries = nonRootBlock.getIntAfterPosition(0);</span> |
| <span class="source-line-no">820</span><span id="line-820"></span> |
| <span class="source-line-no">821</span><span id="line-821"> // The end of secondary index and the beginning of entries themselves.</span> |
| <span class="source-line-no">822</span><span id="line-822"> int entriesOffset = Bytes.SIZEOF_INT * (numEntries + 2);</span> |
| <span class="source-line-no">823</span><span id="line-823"></span> |
| <span class="source-line-no">824</span><span id="line-824"> // The offset of the entry we are interested in relative to the end of</span> |
| <span class="source-line-no">825</span><span id="line-825"> // the secondary index.</span> |
| <span class="source-line-no">826</span><span id="line-826"> int entryRelOffset = nonRootBlock.getIntAfterPosition(Bytes.SIZEOF_INT * (1 + entryIndex));</span> |
| <span class="source-line-no">827</span><span id="line-827"></span> |
| <span class="source-line-no">828</span><span id="line-828"> nonRootBlock.position(entriesOffset + entryRelOffset);</span> |
| <span class="source-line-no">829</span><span id="line-829"> }</span> |
| <span class="source-line-no">830</span><span id="line-830"></span> |
| <span class="source-line-no">831</span><span id="line-831"> return entryIndex;</span> |
| <span class="source-line-no">832</span><span id="line-832"> }</span> |
| <span class="source-line-no">833</span><span id="line-833"></span> |
| <span class="source-line-no">834</span><span id="line-834"> /**</span> |
| <span class="source-line-no">835</span><span id="line-835"> * Read in the root-level index from the given input stream. Must match what was written into</span> |
| <span class="source-line-no">836</span><span id="line-836"> * the root level by {@link BlockIndexWriter#writeIndexBlocks(FSDataOutputStream)} at the offset</span> |
| <span class="source-line-no">837</span><span id="line-837"> * that function returned.</span> |
| <span class="source-line-no">838</span><span id="line-838"> * @param in the buffered input stream or wrapped byte input stream</span> |
| <span class="source-line-no">839</span><span id="line-839"> * @param numEntries the number of root-level index entries</span> |
| <span class="source-line-no">840</span><span id="line-840"> */</span> |
| <span class="source-line-no">841</span><span id="line-841"> public void readRootIndex(DataInput in, final int numEntries) throws IOException {</span> |
| <span class="source-line-no">842</span><span id="line-842"> blockOffsets = new long[numEntries];</span> |
| <span class="source-line-no">843</span><span id="line-843"> initialize(numEntries);</span> |
| <span class="source-line-no">844</span><span id="line-844"> blockDataSizes = new int[numEntries];</span> |
| <span class="source-line-no">845</span><span id="line-845"></span> |
| <span class="source-line-no">846</span><span id="line-846"> // If index size is zero, no index was written.</span> |
| <span class="source-line-no">847</span><span id="line-847"> if (numEntries > 0) {</span> |
| <span class="source-line-no">848</span><span id="line-848"> for (int i = 0; i < numEntries; ++i) {</span> |
| <span class="source-line-no">849</span><span id="line-849"> long offset = in.readLong();</span> |
| <span class="source-line-no">850</span><span id="line-850"> int dataSize = in.readInt();</span> |
| <span class="source-line-no">851</span><span id="line-851"> byte[] key = Bytes.readByteArray(in);</span> |
| <span class="source-line-no">852</span><span id="line-852"> add(key, offset, dataSize);</span> |
| <span class="source-line-no">853</span><span id="line-853"> }</span> |
| <span class="source-line-no">854</span><span id="line-854"> }</span> |
| <span class="source-line-no">855</span><span id="line-855"> }</span> |
| <span class="source-line-no">856</span><span id="line-856"></span> |
| <span class="source-line-no">857</span><span id="line-857"> protected abstract void initialize(int numEntries);</span> |
| <span class="source-line-no">858</span><span id="line-858"></span> |
| <span class="source-line-no">859</span><span id="line-859"> protected abstract void add(final byte[] key, final long offset, final int dataSize);</span> |
| <span class="source-line-no">860</span><span id="line-860"></span> |
| <span class="source-line-no">861</span><span id="line-861"> /**</span> |
| <span class="source-line-no">862</span><span id="line-862"> * Read in the root-level index from the given input stream. Must match what was written into</span> |
| <span class="source-line-no">863</span><span id="line-863"> * the root level by {@link BlockIndexWriter#writeIndexBlocks(FSDataOutputStream)} at the offset</span> |
| <span class="source-line-no">864</span><span id="line-864"> * that function returned.</span> |
| <span class="source-line-no">865</span><span id="line-865"> * @param blk the HFile block</span> |
| <span class="source-line-no">866</span><span id="line-866"> * @param numEntries the number of root-level index entries</span> |
| <span class="source-line-no">867</span><span id="line-867"> * @return the buffered input stream or wrapped byte input stream</span> |
| <span class="source-line-no">868</span><span id="line-868"> */</span> |
| <span class="source-line-no">869</span><span id="line-869"> public DataInputStream readRootIndex(HFileBlock blk, final int numEntries) throws IOException {</span> |
| <span class="source-line-no">870</span><span id="line-870"> DataInputStream in = blk.getByteStream();</span> |
| <span class="source-line-no">871</span><span id="line-871"> readRootIndex(in, numEntries);</span> |
| <span class="source-line-no">872</span><span id="line-872"> return in;</span> |
| <span class="source-line-no">873</span><span id="line-873"> }</span> |
| <span class="source-line-no">874</span><span id="line-874"></span> |
| <span class="source-line-no">875</span><span id="line-875"> /**</span> |
| <span class="source-line-no">876</span><span id="line-876"> * Read the root-level metadata of a multi-level block index. Based on</span> |
| <span class="source-line-no">877</span><span id="line-877"> * {@link #readRootIndex(DataInput, int)}, but also reads metadata necessary to compute the</span> |
| <span class="source-line-no">878</span><span id="line-878"> * mid-key in a multi-level index.</span> |
| <span class="source-line-no">879</span><span id="line-879"> * @param blk the HFile block</span> |
| <span class="source-line-no">880</span><span id="line-880"> * @param numEntries the number of root-level index entries</span> |
| <span class="source-line-no">881</span><span id="line-881"> */</span> |
| <span class="source-line-no">882</span><span id="line-882"> public void readMultiLevelIndexRoot(HFileBlock blk, final int numEntries) throws IOException {</span> |
| <span class="source-line-no">883</span><span id="line-883"> DataInputStream in = readRootIndex(blk, numEntries);</span> |
| <span class="source-line-no">884</span><span id="line-884"> // HFileBlock.getByteStream() returns a byte stream for reading the data(excluding checksum)</span> |
| <span class="source-line-no">885</span><span id="line-885"> // of root index block, so after reading the root index there is no need to subtract the</span> |
| <span class="source-line-no">886</span><span id="line-886"> // checksum bytes.</span> |
| <span class="source-line-no">887</span><span id="line-887"> if (in.available() < MID_KEY_METADATA_SIZE) {</span> |
| <span class="source-line-no">888</span><span id="line-888"> // No mid-key metadata available.</span> |
| <span class="source-line-no">889</span><span id="line-889"> return;</span> |
| <span class="source-line-no">890</span><span id="line-890"> }</span> |
| <span class="source-line-no">891</span><span id="line-891"> midLeafBlockOffset = in.readLong();</span> |
| <span class="source-line-no">892</span><span id="line-892"> midLeafBlockOnDiskSize = in.readInt();</span> |
| <span class="source-line-no">893</span><span id="line-893"> midKeyEntry = in.readInt();</span> |
| <span class="source-line-no">894</span><span id="line-894"> }</span> |
| <span class="source-line-no">895</span><span id="line-895"></span> |
| <span class="source-line-no">896</span><span id="line-896"> @Override</span> |
| <span class="source-line-no">897</span><span id="line-897"> public long heapSize() {</span> |
| <span class="source-line-no">898</span><span id="line-898"> // The BlockIndexReader does not have the blockKey, comparator and the midkey atomic reference</span> |
| <span class="source-line-no">899</span><span id="line-899"> long heapSize =</span> |
| <span class="source-line-no">900</span><span id="line-900"> ClassSize.align(3 * ClassSize.REFERENCE + 2 * Bytes.SIZEOF_INT + ClassSize.OBJECT);</span> |
| <span class="source-line-no">901</span><span id="line-901"></span> |
| <span class="source-line-no">902</span><span id="line-902"> // Mid-key metadata.</span> |
| <span class="source-line-no">903</span><span id="line-903"> heapSize += MID_KEY_METADATA_SIZE;</span> |
| <span class="source-line-no">904</span><span id="line-904"></span> |
| <span class="source-line-no">905</span><span id="line-905"> heapSize = calculateHeapSizeForBlockKeys(heapSize);</span> |
| <span class="source-line-no">906</span><span id="line-906"></span> |
| <span class="source-line-no">907</span><span id="line-907"> if (blockOffsets != null) {</span> |
| <span class="source-line-no">908</span><span id="line-908"> heapSize += ClassSize.align(ClassSize.ARRAY + blockOffsets.length * Bytes.SIZEOF_LONG);</span> |
| <span class="source-line-no">909</span><span id="line-909"> }</span> |
| <span class="source-line-no">910</span><span id="line-910"></span> |
| <span class="source-line-no">911</span><span id="line-911"> if (blockDataSizes != null) {</span> |
| <span class="source-line-no">912</span><span id="line-912"> heapSize += ClassSize.align(ClassSize.ARRAY + blockDataSizes.length * Bytes.SIZEOF_INT);</span> |
| <span class="source-line-no">913</span><span id="line-913"> }</span> |
| <span class="source-line-no">914</span><span id="line-914"></span> |
| <span class="source-line-no">915</span><span id="line-915"> return ClassSize.align(heapSize);</span> |
| <span class="source-line-no">916</span><span id="line-916"> }</span> |
| <span class="source-line-no">917</span><span id="line-917"></span> |
| <span class="source-line-no">918</span><span id="line-918"> protected abstract long calculateHeapSizeForBlockKeys(long heapSize);</span> |
| <span class="source-line-no">919</span><span id="line-919"> }</span> |
| <span class="source-line-no">920</span><span id="line-920"></span> |
| <span class="source-line-no">921</span><span id="line-921"> /**</span> |
| <span class="source-line-no">922</span><span id="line-922"> * Writes the block index into the output stream. Generate the tree from bottom up. The leaf level</span> |
| <span class="source-line-no">923</span><span id="line-923"> * is written to disk as a sequence of inline blocks, if it is larger than a certain number of</span> |
| <span class="source-line-no">924</span><span id="line-924"> * bytes. If the leaf level is not large enough, we write all entries to the root level instead.</span> |
| <span class="source-line-no">925</span><span id="line-925"> * After all leaf blocks have been written, we end up with an index referencing the resulting leaf</span> |
| <span class="source-line-no">926</span><span id="line-926"> * index blocks. If that index is larger than the allowed root index size, the writer will break</span> |
| <span class="source-line-no">927</span><span id="line-927"> * it up into reasonable-size intermediate-level index block chunks write those chunks out, and</span> |
| <span class="source-line-no">928</span><span id="line-928"> * create another index referencing those chunks. This will be repeated until the remaining index</span> |
| <span class="source-line-no">929</span><span id="line-929"> * is small enough to become the root index. However, in most practical cases we will only have</span> |
| <span class="source-line-no">930</span><span id="line-930"> * leaf-level blocks and the root index, or just the root index.</span> |
| <span class="source-line-no">931</span><span id="line-931"> */</span> |
| <span class="source-line-no">932</span><span id="line-932"> public static class BlockIndexWriter implements InlineBlockWriter {</span> |
| <span class="source-line-no">933</span><span id="line-933"> /**</span> |
| <span class="source-line-no">934</span><span id="line-934"> * While the index is being written, this represents the current block index referencing all</span> |
| <span class="source-line-no">935</span><span id="line-935"> * leaf blocks, with one exception. If the file is being closed and there are not enough blocks</span> |
| <span class="source-line-no">936</span><span id="line-936"> * to complete even a single leaf block, no leaf blocks get written and this contains the entire</span> |
| <span class="source-line-no">937</span><span id="line-937"> * block index. After all levels of the index were written by</span> |
| <span class="source-line-no">938</span><span id="line-938"> * {@link #writeIndexBlocks(FSDataOutputStream)}, this contains the final root-level index.</span> |
| <span class="source-line-no">939</span><span id="line-939"> */</span> |
| <span class="source-line-no">940</span><span id="line-940"> private BlockIndexChunk rootChunk = new BlockIndexChunkImpl();</span> |
| <span class="source-line-no">941</span><span id="line-941"></span> |
| <span class="source-line-no">942</span><span id="line-942"> /**</span> |
| <span class="source-line-no">943</span><span id="line-943"> * Current leaf-level chunk. New entries referencing data blocks get added to this chunk until</span> |
| <span class="source-line-no">944</span><span id="line-944"> * it grows large enough to be written to disk.</span> |
| <span class="source-line-no">945</span><span id="line-945"> */</span> |
| <span class="source-line-no">946</span><span id="line-946"> private BlockIndexChunk curInlineChunk = new BlockIndexChunkImpl();</span> |
| <span class="source-line-no">947</span><span id="line-947"></span> |
| <span class="source-line-no">948</span><span id="line-948"> /**</span> |
| <span class="source-line-no">949</span><span id="line-949"> * The number of block index levels. This is one if there is only root level (even empty), two</span> |
| <span class="source-line-no">950</span><span id="line-950"> * if there a leaf level and root level, and is higher if there are intermediate levels. This is</span> |
| <span class="source-line-no">951</span><span id="line-951"> * only final after {@link #writeIndexBlocks(FSDataOutputStream)} has been called. The initial</span> |
| <span class="source-line-no">952</span><span id="line-952"> * value accounts for the root level, and will be increased to two as soon as we find out there</span> |
| <span class="source-line-no">953</span><span id="line-953"> * is a leaf-level in {@link #blockWritten(long, int, int)}.</span> |
| <span class="source-line-no">954</span><span id="line-954"> */</span> |
| <span class="source-line-no">955</span><span id="line-955"> private int numLevels = 1;</span> |
| <span class="source-line-no">956</span><span id="line-956"></span> |
| <span class="source-line-no">957</span><span id="line-957"> private HFileBlock.Writer blockWriter;</span> |
| <span class="source-line-no">958</span><span id="line-958"> private byte[] firstKey = null;</span> |
| <span class="source-line-no">959</span><span id="line-959"></span> |
| <span class="source-line-no">960</span><span id="line-960"> /**</span> |
| <span class="source-line-no">961</span><span id="line-961"> * The total number of leaf-level entries, i.e. entries referenced by leaf-level blocks. For the</span> |
| <span class="source-line-no">962</span><span id="line-962"> * data block index this is equal to the number of data blocks.</span> |
| <span class="source-line-no">963</span><span id="line-963"> */</span> |
| <span class="source-line-no">964</span><span id="line-964"> private long totalNumEntries;</span> |
| <span class="source-line-no">965</span><span id="line-965"></span> |
| <span class="source-line-no">966</span><span id="line-966"> /** Total compressed size of all index blocks. */</span> |
| <span class="source-line-no">967</span><span id="line-967"> private long totalBlockOnDiskSize;</span> |
| <span class="source-line-no">968</span><span id="line-968"></span> |
| <span class="source-line-no">969</span><span id="line-969"> /** Total uncompressed size of all index blocks. */</span> |
| <span class="source-line-no">970</span><span id="line-970"> private long totalBlockUncompressedSize;</span> |
| <span class="source-line-no">971</span><span id="line-971"></span> |
| <span class="source-line-no">972</span><span id="line-972"> /** The maximum size guideline of all multi-level index blocks. */</span> |
| <span class="source-line-no">973</span><span id="line-973"> private int maxChunkSize;</span> |
| <span class="source-line-no">974</span><span id="line-974"></span> |
| <span class="source-line-no">975</span><span id="line-975"> /** The maximum level of multi-level index blocks */</span> |
| <span class="source-line-no">976</span><span id="line-976"> private int minIndexNumEntries;</span> |
| <span class="source-line-no">977</span><span id="line-977"></span> |
| <span class="source-line-no">978</span><span id="line-978"> /** Whether we require this block index to always be single-level. */</span> |
| <span class="source-line-no">979</span><span id="line-979"> private boolean singleLevelOnly;</span> |
| <span class="source-line-no">980</span><span id="line-980"></span> |
| <span class="source-line-no">981</span><span id="line-981"> /** CacheConfig, or null if cache-on-write is disabled */</span> |
| <span class="source-line-no">982</span><span id="line-982"> private CacheConfig cacheConf;</span> |
| <span class="source-line-no">983</span><span id="line-983"></span> |
| <span class="source-line-no">984</span><span id="line-984"> /** Name to use for computing cache keys */</span> |
| <span class="source-line-no">985</span><span id="line-985"> private String nameForCaching;</span> |
| <span class="source-line-no">986</span><span id="line-986"></span> |
| <span class="source-line-no">987</span><span id="line-987"> /** Type of encoding used for index blocks in HFile */</span> |
| <span class="source-line-no">988</span><span id="line-988"> private HFileIndexBlockEncoder indexBlockEncoder;</span> |
| <span class="source-line-no">989</span><span id="line-989"></span> |
| <span class="source-line-no">990</span><span id="line-990"> /** Creates a single-level block index writer */</span> |
| <span class="source-line-no">991</span><span id="line-991"> public BlockIndexWriter() {</span> |
| <span class="source-line-no">992</span><span id="line-992"> this(null, null, null, null);</span> |
| <span class="source-line-no">993</span><span id="line-993"> singleLevelOnly = true;</span> |
| <span class="source-line-no">994</span><span id="line-994"> }</span> |
| <span class="source-line-no">995</span><span id="line-995"></span> |
| <span class="source-line-no">996</span><span id="line-996"> /**</span> |
| <span class="source-line-no">997</span><span id="line-997"> * Creates a multi-level block index writer.</span> |
| <span class="source-line-no">998</span><span id="line-998"> * @param blockWriter the block writer to use to write index blocks</span> |
| <span class="source-line-no">999</span><span id="line-999"> * @param cacheConf used to determine when and how a block should be cached-on-write.</span> |
| <span class="source-line-no">1000</span><span id="line-1000"> */</span> |
| <span class="source-line-no">1001</span><span id="line-1001"> public BlockIndexWriter(HFileBlock.Writer blockWriter, CacheConfig cacheConf,</span> |
| <span class="source-line-no">1002</span><span id="line-1002"> String nameForCaching, HFileIndexBlockEncoder indexBlockEncoder) {</span> |
| <span class="source-line-no">1003</span><span id="line-1003"> if ((cacheConf == null) != (nameForCaching == null)) {</span> |
| <span class="source-line-no">1004</span><span id="line-1004"> throw new IllegalArgumentException(</span> |
| <span class="source-line-no">1005</span><span id="line-1005"> "Block cache and file name for " + "caching must be both specified or both null");</span> |
| <span class="source-line-no">1006</span><span id="line-1006"> }</span> |
| <span class="source-line-no">1007</span><span id="line-1007"></span> |
| <span class="source-line-no">1008</span><span id="line-1008"> this.blockWriter = blockWriter;</span> |
| <span class="source-line-no">1009</span><span id="line-1009"> this.cacheConf = cacheConf;</span> |
| <span class="source-line-no">1010</span><span id="line-1010"> this.nameForCaching = nameForCaching;</span> |
| <span class="source-line-no">1011</span><span id="line-1011"> this.maxChunkSize = HFileBlockIndex.DEFAULT_MAX_CHUNK_SIZE;</span> |
| <span class="source-line-no">1012</span><span id="line-1012"> this.minIndexNumEntries = HFileBlockIndex.DEFAULT_MIN_INDEX_NUM_ENTRIES;</span> |
| <span class="source-line-no">1013</span><span id="line-1013"> this.indexBlockEncoder =</span> |
| <span class="source-line-no">1014</span><span id="line-1014"> indexBlockEncoder != null ? indexBlockEncoder : NoOpIndexBlockEncoder.INSTANCE;</span> |
| <span class="source-line-no">1015</span><span id="line-1015"> }</span> |
| <span class="source-line-no">1016</span><span id="line-1016"></span> |
| <span class="source-line-no">1017</span><span id="line-1017"> public void setMaxChunkSize(int maxChunkSize) {</span> |
| <span class="source-line-no">1018</span><span id="line-1018"> if (maxChunkSize <= 0) {</span> |
| <span class="source-line-no">1019</span><span id="line-1019"> throw new IllegalArgumentException("Invalid maximum index block size");</span> |
| <span class="source-line-no">1020</span><span id="line-1020"> }</span> |
| <span class="source-line-no">1021</span><span id="line-1021"> this.maxChunkSize = maxChunkSize;</span> |
| <span class="source-line-no">1022</span><span id="line-1022"> }</span> |
| <span class="source-line-no">1023</span><span id="line-1023"></span> |
| <span class="source-line-no">1024</span><span id="line-1024"> public void setMinIndexNumEntries(int minIndexNumEntries) {</span> |
| <span class="source-line-no">1025</span><span id="line-1025"> if (minIndexNumEntries <= 1) {</span> |
| <span class="source-line-no">1026</span><span id="line-1026"> throw new IllegalArgumentException("Invalid maximum index level, should be >= 2");</span> |
| <span class="source-line-no">1027</span><span id="line-1027"> }</span> |
| <span class="source-line-no">1028</span><span id="line-1028"> this.minIndexNumEntries = minIndexNumEntries;</span> |
| <span class="source-line-no">1029</span><span id="line-1029"> }</span> |
| <span class="source-line-no">1030</span><span id="line-1030"></span> |
| <span class="source-line-no">1031</span><span id="line-1031"> /**</span> |
| <span class="source-line-no">1032</span><span id="line-1032"> * Writes the root level and intermediate levels of the block index into the output stream,</span> |
| <span class="source-line-no">1033</span><span id="line-1033"> * generating the tree from bottom up. Assumes that the leaf level has been inline-written to</span> |
| <span class="source-line-no">1034</span><span id="line-1034"> * the disk if there is enough data for more than one leaf block. We iterate by breaking the</span> |
| <span class="source-line-no">1035</span><span id="line-1035"> * current level of the block index, starting with the index of all leaf-level blocks, into</span> |
| <span class="source-line-no">1036</span><span id="line-1036"> * chunks small enough to be written to disk, and generate its parent level, until we end up</span> |
| <span class="source-line-no">1037</span><span id="line-1037"> * with a level small enough to become the root level. If the leaf level is not large enough,</span> |
| <span class="source-line-no">1038</span><span id="line-1038"> * there is no inline block index anymore, so we only write that level of block index to disk as</span> |
| <span class="source-line-no">1039</span><span id="line-1039"> * the root level.</span> |
| <span class="source-line-no">1040</span><span id="line-1040"> * @param out FSDataOutputStream</span> |
| <span class="source-line-no">1041</span><span id="line-1041"> * @return position at which we entered the root-level index.</span> |
| <span class="source-line-no">1042</span><span id="line-1042"> */</span> |
| <span class="source-line-no">1043</span><span id="line-1043"> public long writeIndexBlocks(FSDataOutputStream out) throws IOException {</span> |
| <span class="source-line-no">1044</span><span id="line-1044"> if (curInlineChunk != null && curInlineChunk.getNumEntries() != 0) {</span> |
| <span class="source-line-no">1045</span><span id="line-1045"> throw new IOException("Trying to write a multi-level block index, " + "but are "</span> |
| <span class="source-line-no">1046</span><span id="line-1046"> + curInlineChunk.getNumEntries() + " entries in the " + "last inline chunk.");</span> |
| <span class="source-line-no">1047</span><span id="line-1047"> }</span> |
| <span class="source-line-no">1048</span><span id="line-1048"></span> |
| <span class="source-line-no">1049</span><span id="line-1049"> // We need to get mid-key metadata before we create intermediate</span> |
| <span class="source-line-no">1050</span><span id="line-1050"> // indexes and overwrite the root chunk.</span> |
| <span class="source-line-no">1051</span><span id="line-1051"> byte[] midKeyMetadata = numLevels > 1 ? rootChunk.getMidKeyMetadata() : null;</span> |
| <span class="source-line-no">1052</span><span id="line-1052"></span> |
| <span class="source-line-no">1053</span><span id="line-1053"> if (curInlineChunk != null) {</span> |
| <span class="source-line-no">1054</span><span id="line-1054"> while (</span> |
| <span class="source-line-no">1055</span><span id="line-1055"> rootChunk.getRootSize() > maxChunkSize</span> |
| <span class="source-line-no">1056</span><span id="line-1056"> // HBASE-16288: if firstKey is larger than maxChunkSize we will loop indefinitely</span> |
| <span class="source-line-no">1057</span><span id="line-1057"> && rootChunk.getNumEntries() > minIndexNumEntries</span> |
| <span class="source-line-no">1058</span><span id="line-1058"> // Sanity check. We will not hit this (minIndexNumEntries ^ 16) blocks can be addressed</span> |
| <span class="source-line-no">1059</span><span id="line-1059"> && numLevels < 16</span> |
| <span class="source-line-no">1060</span><span id="line-1060"> ) {</span> |
| <span class="source-line-no">1061</span><span id="line-1061"> rootChunk = writeIntermediateLevel(out, rootChunk);</span> |
| <span class="source-line-no">1062</span><span id="line-1062"> numLevels += 1;</span> |
| <span class="source-line-no">1063</span><span id="line-1063"> }</span> |
| <span class="source-line-no">1064</span><span id="line-1064"> }</span> |
| <span class="source-line-no">1065</span><span id="line-1065"></span> |
| <span class="source-line-no">1066</span><span id="line-1066"> // write the root level</span> |
| <span class="source-line-no">1067</span><span id="line-1067"> long rootLevelIndexPos = out.getPos();</span> |
| <span class="source-line-no">1068</span><span id="line-1068"></span> |
| <span class="source-line-no">1069</span><span id="line-1069"> {</span> |
| <span class="source-line-no">1070</span><span id="line-1070"> DataOutput blockStream = blockWriter.startWriting(BlockType.ROOT_INDEX);</span> |
| <span class="source-line-no">1071</span><span id="line-1071"> indexBlockEncoder.encode(rootChunk, true, blockStream);</span> |
| <span class="source-line-no">1072</span><span id="line-1072"> if (midKeyMetadata != null) blockStream.write(midKeyMetadata);</span> |
| <span class="source-line-no">1073</span><span id="line-1073"> blockWriter.writeHeaderAndData(out);</span> |
| <span class="source-line-no">1074</span><span id="line-1074"> if (cacheConf != null) {</span> |
| <span class="source-line-no">1075</span><span id="line-1075"> cacheConf.getBlockCache().ifPresent(cache -> {</span> |
| <span class="source-line-no">1076</span><span id="line-1076"> HFileBlock blockForCaching = blockWriter.getBlockForCaching(cacheConf);</span> |
| <span class="source-line-no">1077</span><span id="line-1077"> cache.cacheBlock(new BlockCacheKey(nameForCaching, rootLevelIndexPos, true,</span> |
| <span class="source-line-no">1078</span><span id="line-1078"> blockForCaching.getBlockType()), blockForCaching);</span> |
| <span class="source-line-no">1079</span><span id="line-1079"> });</span> |
| <span class="source-line-no">1080</span><span id="line-1080"> }</span> |
| <span class="source-line-no">1081</span><span id="line-1081"> }</span> |
| <span class="source-line-no">1082</span><span id="line-1082"></span> |
| <span class="source-line-no">1083</span><span id="line-1083"> // Add root index block size</span> |
| <span class="source-line-no">1084</span><span id="line-1084"> totalBlockOnDiskSize += blockWriter.getOnDiskSizeWithoutHeader();</span> |
| <span class="source-line-no">1085</span><span id="line-1085"> totalBlockUncompressedSize += blockWriter.getUncompressedSizeWithoutHeader();</span> |
| <span class="source-line-no">1086</span><span id="line-1086"></span> |
| <span class="source-line-no">1087</span><span id="line-1087"> if (LOG.isTraceEnabled()) {</span> |
| <span class="source-line-no">1088</span><span id="line-1088"> LOG.trace("Wrote a " + numLevels + "-level index with root level at pos "</span> |
| <span class="source-line-no">1089</span><span id="line-1089"> + rootLevelIndexPos + ", " + rootChunk.getNumEntries() + " root-level entries, "</span> |
| <span class="source-line-no">1090</span><span id="line-1090"> + totalNumEntries + " total entries, "</span> |
| <span class="source-line-no">1091</span><span id="line-1091"> + StringUtils.humanReadableInt(this.totalBlockOnDiskSize) + " on-disk size, "</span> |
| <span class="source-line-no">1092</span><span id="line-1092"> + StringUtils.humanReadableInt(totalBlockUncompressedSize) + " total uncompressed size.");</span> |
| <span class="source-line-no">1093</span><span id="line-1093"> }</span> |
| <span class="source-line-no">1094</span><span id="line-1094"> return rootLevelIndexPos;</span> |
| <span class="source-line-no">1095</span><span id="line-1095"> }</span> |
| <span class="source-line-no">1096</span><span id="line-1096"></span> |
| <span class="source-line-no">1097</span><span id="line-1097"> /**</span> |
| <span class="source-line-no">1098</span><span id="line-1098"> * Writes the block index data as a single level only. Does not do any block framing.</span> |
| <span class="source-line-no">1099</span><span id="line-1099"> * @param out the buffered output stream to write the index to. Typically a stream</span> |
| <span class="source-line-no">1100</span><span id="line-1100"> * writing into an {@link HFile} block.</span> |
| <span class="source-line-no">1101</span><span id="line-1101"> * @param description a short description of the index being written. Used in a log message.</span> |
| <span class="source-line-no">1102</span><span id="line-1102"> */</span> |
| <span class="source-line-no">1103</span><span id="line-1103"> public void writeSingleLevelIndex(DataOutput out, String description) throws IOException {</span> |
| <span class="source-line-no">1104</span><span id="line-1104"> expectNumLevels(1);</span> |
| <span class="source-line-no">1105</span><span id="line-1105"></span> |
| <span class="source-line-no">1106</span><span id="line-1106"> if (!singleLevelOnly) throw new IOException("Single-level mode is turned off");</span> |
| <span class="source-line-no">1107</span><span id="line-1107"></span> |
| <span class="source-line-no">1108</span><span id="line-1108"> if (rootChunk.getNumEntries() > 0)</span> |
| <span class="source-line-no">1109</span><span id="line-1109"> throw new IOException("Root-level entries already added in " + "single-level mode");</span> |
| <span class="source-line-no">1110</span><span id="line-1110"></span> |
| <span class="source-line-no">1111</span><span id="line-1111"> rootChunk = curInlineChunk;</span> |
| <span class="source-line-no">1112</span><span id="line-1112"> curInlineChunk = new BlockIndexChunkImpl();</span> |
| <span class="source-line-no">1113</span><span id="line-1113"></span> |
| <span class="source-line-no">1114</span><span id="line-1114"> if (LOG.isTraceEnabled()) {</span> |
| <span class="source-line-no">1115</span><span id="line-1115"> LOG.trace("Wrote a single-level " + description + " index with " + rootChunk.getNumEntries()</span> |
| <span class="source-line-no">1116</span><span id="line-1116"> + " entries, " + rootChunk.getRootSize() + " bytes");</span> |
| <span class="source-line-no">1117</span><span id="line-1117"> }</span> |
| <span class="source-line-no">1118</span><span id="line-1118"> indexBlockEncoder.encode(rootChunk, true, out);</span> |
| <span class="source-line-no">1119</span><span id="line-1119"> }</span> |
| <span class="source-line-no">1120</span><span id="line-1120"></span> |
| <span class="source-line-no">1121</span><span id="line-1121"> /**</span> |
| <span class="source-line-no">1122</span><span id="line-1122"> * Split the current level of the block index into intermediate index blocks of permitted size</span> |
| <span class="source-line-no">1123</span><span id="line-1123"> * and write those blocks to disk. Return the next level of the block index referencing those</span> |
| <span class="source-line-no">1124</span><span id="line-1124"> * intermediate-level blocks.</span> |
| <span class="source-line-no">1125</span><span id="line-1125"> * @param currentLevel the current level of the block index, such as the a chunk referencing all</span> |
| <span class="source-line-no">1126</span><span id="line-1126"> * leaf-level index blocks</span> |
| <span class="source-line-no">1127</span><span id="line-1127"> * @return the parent level block index, which becomes the root index after a few (usually zero)</span> |
| <span class="source-line-no">1128</span><span id="line-1128"> * iterations</span> |
| <span class="source-line-no">1129</span><span id="line-1129"> */</span> |
| <span class="source-line-no">1130</span><span id="line-1130"> private BlockIndexChunk writeIntermediateLevel(FSDataOutputStream out,</span> |
| <span class="source-line-no">1131</span><span id="line-1131"> BlockIndexChunk currentLevel) throws IOException {</span> |
| <span class="source-line-no">1132</span><span id="line-1132"> // Entries referencing intermediate-level blocks we are about to create.</span> |
| <span class="source-line-no">1133</span><span id="line-1133"> BlockIndexChunk parent = new BlockIndexChunkImpl();</span> |
| <span class="source-line-no">1134</span><span id="line-1134"></span> |
| <span class="source-line-no">1135</span><span id="line-1135"> // The current intermediate-level block index chunk.</span> |
| <span class="source-line-no">1136</span><span id="line-1136"> BlockIndexChunk curChunk = new BlockIndexChunkImpl();</span> |
| <span class="source-line-no">1137</span><span id="line-1137"></span> |
| <span class="source-line-no">1138</span><span id="line-1138"> for (int i = 0; i < currentLevel.getNumEntries(); ++i) {</span> |
| <span class="source-line-no">1139</span><span id="line-1139"> curChunk.add(currentLevel.getBlockKey(i), currentLevel.getBlockOffset(i),</span> |
| <span class="source-line-no">1140</span><span id="line-1140"> currentLevel.getOnDiskDataSize(i));</span> |
| <span class="source-line-no">1141</span><span id="line-1141"></span> |
| <span class="source-line-no">1142</span><span id="line-1142"> // HBASE-16288: We have to have at least minIndexNumEntries(16) items in the index so that</span> |
| <span class="source-line-no">1143</span><span id="line-1143"> // we won't end up with too-many levels for a index with very large rowKeys. Also, if the</span> |
| <span class="source-line-no">1144</span><span id="line-1144"> // first key is larger than maxChunkSize this will cause infinite recursion.</span> |
| <span class="source-line-no">1145</span><span id="line-1145"> if (i >= minIndexNumEntries && curChunk.getRootSize() >= maxChunkSize) {</span> |
| <span class="source-line-no">1146</span><span id="line-1146"> writeIntermediateBlock(out, parent, curChunk);</span> |
| <span class="source-line-no">1147</span><span id="line-1147"> }</span> |
| <span class="source-line-no">1148</span><span id="line-1148"> }</span> |
| <span class="source-line-no">1149</span><span id="line-1149"></span> |
| <span class="source-line-no">1150</span><span id="line-1150"> if (curChunk.getNumEntries() > 0) {</span> |
| <span class="source-line-no">1151</span><span id="line-1151"> writeIntermediateBlock(out, parent, curChunk);</span> |
| <span class="source-line-no">1152</span><span id="line-1152"> }</span> |
| <span class="source-line-no">1153</span><span id="line-1153"></span> |
| <span class="source-line-no">1154</span><span id="line-1154"> return parent;</span> |
| <span class="source-line-no">1155</span><span id="line-1155"> }</span> |
| <span class="source-line-no">1156</span><span id="line-1156"></span> |
| <span class="source-line-no">1157</span><span id="line-1157"> private void writeIntermediateBlock(FSDataOutputStream out, BlockIndexChunk parent,</span> |
| <span class="source-line-no">1158</span><span id="line-1158"> BlockIndexChunk curChunk) throws IOException {</span> |
| <span class="source-line-no">1159</span><span id="line-1159"> long beginOffset = out.getPos();</span> |
| <span class="source-line-no">1160</span><span id="line-1160"> DataOutputStream dos = blockWriter.startWriting(BlockType.INTERMEDIATE_INDEX);</span> |
| <span class="source-line-no">1161</span><span id="line-1161"> indexBlockEncoder.encode(curChunk, false, dos);</span> |
| <span class="source-line-no">1162</span><span id="line-1162"> byte[] curFirstKey = curChunk.getBlockKey(0);</span> |
| <span class="source-line-no">1163</span><span id="line-1163"> blockWriter.writeHeaderAndData(out);</span> |
| <span class="source-line-no">1164</span><span id="line-1164"></span> |
| <span class="source-line-no">1165</span><span id="line-1165"> if (getCacheOnWrite()) {</span> |
| <span class="source-line-no">1166</span><span id="line-1166"> cacheConf.getBlockCache().ifPresent(cache -> {</span> |
| <span class="source-line-no">1167</span><span id="line-1167"> HFileBlock blockForCaching = blockWriter.getBlockForCaching(cacheConf);</span> |
| <span class="source-line-no">1168</span><span id="line-1168"> cache.cacheBlock(</span> |
| <span class="source-line-no">1169</span><span id="line-1169"> new BlockCacheKey(nameForCaching, beginOffset, true, blockForCaching.getBlockType()),</span> |
| <span class="source-line-no">1170</span><span id="line-1170"> blockForCaching);</span> |
| <span class="source-line-no">1171</span><span id="line-1171"> });</span> |
| <span class="source-line-no">1172</span><span id="line-1172"> }</span> |
| <span class="source-line-no">1173</span><span id="line-1173"></span> |
| <span class="source-line-no">1174</span><span id="line-1174"> // Add intermediate index block size</span> |
| <span class="source-line-no">1175</span><span id="line-1175"> totalBlockOnDiskSize += blockWriter.getOnDiskSizeWithoutHeader();</span> |
| <span class="source-line-no">1176</span><span id="line-1176"> totalBlockUncompressedSize += blockWriter.getUncompressedSizeWithoutHeader();</span> |
| <span class="source-line-no">1177</span><span id="line-1177"></span> |
| <span class="source-line-no">1178</span><span id="line-1178"> // OFFSET is the beginning offset the chunk of block index entries.</span> |
| <span class="source-line-no">1179</span><span id="line-1179"> // SIZE is the total byte size of the chunk of block index entries</span> |
| <span class="source-line-no">1180</span><span id="line-1180"> // + the secondary index size</span> |
| <span class="source-line-no">1181</span><span id="line-1181"> // FIRST_KEY is the first key in the chunk of block index</span> |
| <span class="source-line-no">1182</span><span id="line-1182"> // entries.</span> |
| <span class="source-line-no">1183</span><span id="line-1183"> parent.add(curFirstKey, beginOffset, blockWriter.getOnDiskSizeWithHeader());</span> |
| <span class="source-line-no">1184</span><span id="line-1184"></span> |
| <span class="source-line-no">1185</span><span id="line-1185"> // clear current block index chunk</span> |
| <span class="source-line-no">1186</span><span id="line-1186"> curChunk.clear();</span> |
| <span class="source-line-no">1187</span><span id="line-1187"> curFirstKey = null;</span> |
| <span class="source-line-no">1188</span><span id="line-1188"> }</span> |
| <span class="source-line-no">1189</span><span id="line-1189"></span> |
| <span class="source-line-no">1190</span><span id="line-1190"> /** Returns how many block index entries there are in the root level */</span> |
| <span class="source-line-no">1191</span><span id="line-1191"> public final int getNumRootEntries() {</span> |
| <span class="source-line-no">1192</span><span id="line-1192"> return rootChunk.getNumEntries();</span> |
| <span class="source-line-no">1193</span><span id="line-1193"> }</span> |
| <span class="source-line-no">1194</span><span id="line-1194"></span> |
| <span class="source-line-no">1195</span><span id="line-1195"> /** Returns the number of levels in this block index. */</span> |
| <span class="source-line-no">1196</span><span id="line-1196"> public int getNumLevels() {</span> |
| <span class="source-line-no">1197</span><span id="line-1197"> return numLevels;</span> |
| <span class="source-line-no">1198</span><span id="line-1198"> }</span> |
| <span class="source-line-no">1199</span><span id="line-1199"></span> |
| <span class="source-line-no">1200</span><span id="line-1200"> private void expectNumLevels(int expectedNumLevels) {</span> |
| <span class="source-line-no">1201</span><span id="line-1201"> if (numLevels != expectedNumLevels) {</span> |
| <span class="source-line-no">1202</span><span id="line-1202"> throw new IllegalStateException("Number of block index levels is " + numLevels</span> |
| <span class="source-line-no">1203</span><span id="line-1203"> + "but is expected to be " + expectedNumLevels);</span> |
| <span class="source-line-no">1204</span><span id="line-1204"> }</span> |
| <span class="source-line-no">1205</span><span id="line-1205"> }</span> |
| <span class="source-line-no">1206</span><span id="line-1206"></span> |
| <span class="source-line-no">1207</span><span id="line-1207"> /**</span> |
| <span class="source-line-no">1208</span><span id="line-1208"> * Whether there is an inline block ready to be written. In general, we write an leaf-level</span> |
| <span class="source-line-no">1209</span><span id="line-1209"> * index block as an inline block as soon as its size as serialized in the non-root format</span> |
| <span class="source-line-no">1210</span><span id="line-1210"> * reaches a certain threshold.</span> |
| <span class="source-line-no">1211</span><span id="line-1211"> */</span> |
| <span class="source-line-no">1212</span><span id="line-1212"> @Override</span> |
| <span class="source-line-no">1213</span><span id="line-1213"> public boolean shouldWriteBlock(boolean closing) {</span> |
| <span class="source-line-no">1214</span><span id="line-1214"> if (singleLevelOnly) {</span> |
| <span class="source-line-no">1215</span><span id="line-1215"> throw new UnsupportedOperationException(INLINE_BLOCKS_NOT_ALLOWED);</span> |
| <span class="source-line-no">1216</span><span id="line-1216"> }</span> |
| <span class="source-line-no">1217</span><span id="line-1217"></span> |
| <span class="source-line-no">1218</span><span id="line-1218"> if (curInlineChunk == null) {</span> |
| <span class="source-line-no">1219</span><span id="line-1219"> throw new IllegalStateException("curInlineChunk is null; has shouldWriteBlock been "</span> |
| <span class="source-line-no">1220</span><span id="line-1220"> + "called with closing=true and then called again?");</span> |
| <span class="source-line-no">1221</span><span id="line-1221"> }</span> |
| <span class="source-line-no">1222</span><span id="line-1222"></span> |
| <span class="source-line-no">1223</span><span id="line-1223"> if (curInlineChunk.getNumEntries() == 0) {</span> |
| <span class="source-line-no">1224</span><span id="line-1224"> return false;</span> |
| <span class="source-line-no">1225</span><span id="line-1225"> }</span> |
| <span class="source-line-no">1226</span><span id="line-1226"></span> |
| <span class="source-line-no">1227</span><span id="line-1227"> // We do have some entries in the current inline chunk.</span> |
| <span class="source-line-no">1228</span><span id="line-1228"> if (closing) {</span> |
| <span class="source-line-no">1229</span><span id="line-1229"> if (rootChunk.getNumEntries() == 0) {</span> |
| <span class="source-line-no">1230</span><span id="line-1230"> // We did not add any leaf-level blocks yet. Instead of creating a</span> |
| <span class="source-line-no">1231</span><span id="line-1231"> // leaf level with one block, move these entries to the root level.</span> |
| <span class="source-line-no">1232</span><span id="line-1232"></span> |
| <span class="source-line-no">1233</span><span id="line-1233"> expectNumLevels(1);</span> |
| <span class="source-line-no">1234</span><span id="line-1234"> rootChunk = curInlineChunk;</span> |
| <span class="source-line-no">1235</span><span id="line-1235"> curInlineChunk = null; // Disallow adding any more index entries.</span> |
| <span class="source-line-no">1236</span><span id="line-1236"> return false;</span> |
| <span class="source-line-no">1237</span><span id="line-1237"> }</span> |
| <span class="source-line-no">1238</span><span id="line-1238"></span> |
| <span class="source-line-no">1239</span><span id="line-1239"> return true;</span> |
| <span class="source-line-no">1240</span><span id="line-1240"> } else {</span> |
| <span class="source-line-no">1241</span><span id="line-1241"> return curInlineChunk.getNonRootSize() >= maxChunkSize;</span> |
| <span class="source-line-no">1242</span><span id="line-1242"> }</span> |
| <span class="source-line-no">1243</span><span id="line-1243"> }</span> |
| <span class="source-line-no">1244</span><span id="line-1244"></span> |
| <span class="source-line-no">1245</span><span id="line-1245"> /**</span> |
| <span class="source-line-no">1246</span><span id="line-1246"> * Write out the current inline index block. Inline blocks are non-root blocks, so the non-root</span> |
| <span class="source-line-no">1247</span><span id="line-1247"> * index format is used.</span> |
| <span class="source-line-no">1248</span><span id="line-1248"> */</span> |
| <span class="source-line-no">1249</span><span id="line-1249"> @Override</span> |
| <span class="source-line-no">1250</span><span id="line-1250"> public void writeInlineBlock(DataOutput out) throws IOException {</span> |
| <span class="source-line-no">1251</span><span id="line-1251"> if (singleLevelOnly) throw new UnsupportedOperationException(INLINE_BLOCKS_NOT_ALLOWED);</span> |
| <span class="source-line-no">1252</span><span id="line-1252"></span> |
| <span class="source-line-no">1253</span><span id="line-1253"> // Write the inline block index to the output stream in the non-root</span> |
| <span class="source-line-no">1254</span><span id="line-1254"> // index block format.</span> |
| <span class="source-line-no">1255</span><span id="line-1255"> indexBlockEncoder.encode(curInlineChunk, false, out);</span> |
| <span class="source-line-no">1256</span><span id="line-1256"></span> |
| <span class="source-line-no">1257</span><span id="line-1257"> // Save the first key of the inline block so that we can add it to the</span> |
| <span class="source-line-no">1258</span><span id="line-1258"> // parent-level index.</span> |
| <span class="source-line-no">1259</span><span id="line-1259"> firstKey = curInlineChunk.getBlockKey(0);</span> |
| <span class="source-line-no">1260</span><span id="line-1260"></span> |
| <span class="source-line-no">1261</span><span id="line-1261"> // Start a new inline index block</span> |
| <span class="source-line-no">1262</span><span id="line-1262"> curInlineChunk.clear();</span> |
| <span class="source-line-no">1263</span><span id="line-1263"> }</span> |
| <span class="source-line-no">1264</span><span id="line-1264"></span> |
| <span class="source-line-no">1265</span><span id="line-1265"> /**</span> |
| <span class="source-line-no">1266</span><span id="line-1266"> * Called after an inline block has been written so that we can add an entry referring to that</span> |
| <span class="source-line-no">1267</span><span id="line-1267"> * block to the parent-level index.</span> |
| <span class="source-line-no">1268</span><span id="line-1268"> */</span> |
| <span class="source-line-no">1269</span><span id="line-1269"> @Override</span> |
| <span class="source-line-no">1270</span><span id="line-1270"> public void blockWritten(long offset, int onDiskSize, int uncompressedSize) {</span> |
| <span class="source-line-no">1271</span><span id="line-1271"> // Add leaf index block size</span> |
| <span class="source-line-no">1272</span><span id="line-1272"> totalBlockOnDiskSize += onDiskSize;</span> |
| <span class="source-line-no">1273</span><span id="line-1273"> totalBlockUncompressedSize += uncompressedSize;</span> |
| <span class="source-line-no">1274</span><span id="line-1274"></span> |
| <span class="source-line-no">1275</span><span id="line-1275"> if (singleLevelOnly) throw new UnsupportedOperationException(INLINE_BLOCKS_NOT_ALLOWED);</span> |
| <span class="source-line-no">1276</span><span id="line-1276"></span> |
| <span class="source-line-no">1277</span><span id="line-1277"> if (firstKey == null) {</span> |
| <span class="source-line-no">1278</span><span id="line-1278"> throw new IllegalStateException(</span> |
| <span class="source-line-no">1279</span><span id="line-1279"> "Trying to add second-level index " + "entry with offset=" + offset + " and onDiskSize="</span> |
| <span class="source-line-no">1280</span><span id="line-1280"> + onDiskSize + "but the first key was not set in writeInlineBlock");</span> |
| <span class="source-line-no">1281</span><span id="line-1281"> }</span> |
| <span class="source-line-no">1282</span><span id="line-1282"></span> |
| <span class="source-line-no">1283</span><span id="line-1283"> if (rootChunk.getNumEntries() == 0) {</span> |
| <span class="source-line-no">1284</span><span id="line-1284"> // We are writing the first leaf block, so increase index level.</span> |
| <span class="source-line-no">1285</span><span id="line-1285"> expectNumLevels(1);</span> |
| <span class="source-line-no">1286</span><span id="line-1286"> numLevels = 2;</span> |
| <span class="source-line-no">1287</span><span id="line-1287"> }</span> |
| <span class="source-line-no">1288</span><span id="line-1288"></span> |
| <span class="source-line-no">1289</span><span id="line-1289"> // Add another entry to the second-level index. Include the number of</span> |
| <span class="source-line-no">1290</span><span id="line-1290"> // entries in all previous leaf-level chunks for mid-key calculation.</span> |
| <span class="source-line-no">1291</span><span id="line-1291"> rootChunk.add(firstKey, offset, onDiskSize, totalNumEntries);</span> |
| <span class="source-line-no">1292</span><span id="line-1292"> firstKey = null;</span> |
| <span class="source-line-no">1293</span><span id="line-1293"> }</span> |
| <span class="source-line-no">1294</span><span id="line-1294"></span> |
| <span class="source-line-no">1295</span><span id="line-1295"> @Override</span> |
| <span class="source-line-no">1296</span><span id="line-1296"> public BlockType getInlineBlockType() {</span> |
| <span class="source-line-no">1297</span><span id="line-1297"> return BlockType.LEAF_INDEX;</span> |
| <span class="source-line-no">1298</span><span id="line-1298"> }</span> |
| <span class="source-line-no">1299</span><span id="line-1299"></span> |
| <span class="source-line-no">1300</span><span id="line-1300"> /**</span> |
| <span class="source-line-no">1301</span><span id="line-1301"> * Add one index entry to the current leaf-level block. When the leaf-level block gets large</span> |
| <span class="source-line-no">1302</span><span id="line-1302"> * enough, it will be flushed to disk as an inline block.</span> |
| <span class="source-line-no">1303</span><span id="line-1303"> * @param firstKey the first key of the data block</span> |
| <span class="source-line-no">1304</span><span id="line-1304"> * @param blockOffset the offset of the data block</span> |
| <span class="source-line-no">1305</span><span id="line-1305"> * @param blockDataSize the on-disk size of the data block ({@link HFile} format version 2), or</span> |
| <span class="source-line-no">1306</span><span id="line-1306"> * the uncompressed size of the data block ( {@link HFile} format version</span> |
| <span class="source-line-no">1307</span><span id="line-1307"> * 1).</span> |
| <span class="source-line-no">1308</span><span id="line-1308"> */</span> |
| <span class="source-line-no">1309</span><span id="line-1309"> public void addEntry(byte[] firstKey, long blockOffset, int blockDataSize) {</span> |
| <span class="source-line-no">1310</span><span id="line-1310"> curInlineChunk.add(firstKey, blockOffset, blockDataSize);</span> |
| <span class="source-line-no">1311</span><span id="line-1311"> ++totalNumEntries;</span> |
| <span class="source-line-no">1312</span><span id="line-1312"> }</span> |
| <span class="source-line-no">1313</span><span id="line-1313"></span> |
| <span class="source-line-no">1314</span><span id="line-1314"> /**</span> |
| <span class="source-line-no">1315</span><span id="line-1315"> * @throws IOException if we happened to write a multi-level index.</span> |
| <span class="source-line-no">1316</span><span id="line-1316"> */</span> |
| <span class="source-line-no">1317</span><span id="line-1317"> public void ensureSingleLevel() throws IOException {</span> |
| <span class="source-line-no">1318</span><span id="line-1318"> if (numLevels > 1) {</span> |
| <span class="source-line-no">1319</span><span id="line-1319"> throw new IOException(</span> |
| <span class="source-line-no">1320</span><span id="line-1320"> "Wrote a " + numLevels + "-level index with " + rootChunk.getNumEntries()</span> |
| <span class="source-line-no">1321</span><span id="line-1321"> + " root-level entries, but " + "this is expected to be a single-level block index.");</span> |
| <span class="source-line-no">1322</span><span id="line-1322"> }</span> |
| <span class="source-line-no">1323</span><span id="line-1323"> }</span> |
| <span class="source-line-no">1324</span><span id="line-1324"></span> |
| <span class="source-line-no">1325</span><span id="line-1325"> /**</span> |
| <span class="source-line-no">1326</span><span id="line-1326"> * @return true if we are using cache-on-write. This is configured by the caller of the</span> |
| <span class="source-line-no">1327</span><span id="line-1327"> * constructor by either passing a valid block cache or null.</span> |
| <span class="source-line-no">1328</span><span id="line-1328"> */</span> |
| <span class="source-line-no">1329</span><span id="line-1329"> @Override</span> |
| <span class="source-line-no">1330</span><span id="line-1330"> public boolean getCacheOnWrite() {</span> |
| <span class="source-line-no">1331</span><span id="line-1331"> return cacheConf != null && cacheConf.shouldCacheIndexesOnWrite();</span> |
| <span class="source-line-no">1332</span><span id="line-1332"> }</span> |
| <span class="source-line-no">1333</span><span id="line-1333"></span> |
| <span class="source-line-no">1334</span><span id="line-1334"> /**</span> |
| <span class="source-line-no">1335</span><span id="line-1335"> * The total uncompressed size of the root index block, intermediate-level index blocks, and</span> |
| <span class="source-line-no">1336</span><span id="line-1336"> * leaf-level index blocks.</span> |
| <span class="source-line-no">1337</span><span id="line-1337"> * @return the total uncompressed size of all index blocks</span> |
| <span class="source-line-no">1338</span><span id="line-1338"> */</span> |
| <span class="source-line-no">1339</span><span id="line-1339"> public long getTotalUncompressedSize() {</span> |
| <span class="source-line-no">1340</span><span id="line-1340"> return totalBlockUncompressedSize;</span> |
| <span class="source-line-no">1341</span><span id="line-1341"> }</span> |
| <span class="source-line-no">1342</span><span id="line-1342"></span> |
| <span class="source-line-no">1343</span><span id="line-1343"> }</span> |
| <span class="source-line-no">1344</span><span id="line-1344"></span> |
| <span class="source-line-no">1345</span><span id="line-1345"> /**</span> |
| <span class="source-line-no">1346</span><span id="line-1346"> * A single chunk of the block index in the process of writing. The data in this chunk can become</span> |
| <span class="source-line-no">1347</span><span id="line-1347"> * a leaf-level, intermediate-level, or root index block.</span> |
| <span class="source-line-no">1348</span><span id="line-1348"> */</span> |
| <span class="source-line-no">1349</span><span id="line-1349"> static class BlockIndexChunkImpl implements BlockIndexChunk {</span> |
| <span class="source-line-no">1350</span><span id="line-1350"></span> |
| <span class="source-line-no">1351</span><span id="line-1351"> /** First keys of the key range corresponding to each index entry. */</span> |
| <span class="source-line-no">1352</span><span id="line-1352"> private final List<byte[]> blockKeys = new ArrayList<>();</span> |
| <span class="source-line-no">1353</span><span id="line-1353"></span> |
| <span class="source-line-no">1354</span><span id="line-1354"> /** Block offset in backing stream. */</span> |
| <span class="source-line-no">1355</span><span id="line-1355"> private final List<Long> blockOffsets = new ArrayList<>();</span> |
| <span class="source-line-no">1356</span><span id="line-1356"></span> |
| <span class="source-line-no">1357</span><span id="line-1357"> /** On-disk data sizes of lower-level data or index blocks. */</span> |
| <span class="source-line-no">1358</span><span id="line-1358"> private final List<Integer> onDiskDataSizes = new ArrayList<>();</span> |
| <span class="source-line-no">1359</span><span id="line-1359"></span> |
| <span class="source-line-no">1360</span><span id="line-1360"> /**</span> |
| <span class="source-line-no">1361</span><span id="line-1361"> * The cumulative number of sub-entries, i.e. entries on deeper-level block index entries.</span> |
| <span class="source-line-no">1362</span><span id="line-1362"> * numSubEntriesAt[i] is the number of sub-entries in the blocks corresponding to this chunk's</span> |
| <span class="source-line-no">1363</span><span id="line-1363"> * entries #0 through #i inclusively.</span> |
| <span class="source-line-no">1364</span><span id="line-1364"> */</span> |
| <span class="source-line-no">1365</span><span id="line-1365"> private final List<Long> numSubEntriesAt = new ArrayList<>();</span> |
| <span class="source-line-no">1366</span><span id="line-1366"></span> |
| <span class="source-line-no">1367</span><span id="line-1367"> /**</span> |
| <span class="source-line-no">1368</span><span id="line-1368"> * The offset of the next entry to be added, relative to the end of the "secondary index" in the</span> |
| <span class="source-line-no">1369</span><span id="line-1369"> * "non-root" format representation of this index chunk. This is the next value to be added to</span> |
| <span class="source-line-no">1370</span><span id="line-1370"> * the secondary index.</span> |
| <span class="source-line-no">1371</span><span id="line-1371"> */</span> |
| <span class="source-line-no">1372</span><span id="line-1372"> private int curTotalNonRootEntrySize = 0;</span> |
| <span class="source-line-no">1373</span><span id="line-1373"></span> |
| <span class="source-line-no">1374</span><span id="line-1374"> /**</span> |
| <span class="source-line-no">1375</span><span id="line-1375"> * The accumulated size of this chunk if stored in the root index format.</span> |
| <span class="source-line-no">1376</span><span id="line-1376"> */</span> |
| <span class="source-line-no">1377</span><span id="line-1377"> private int curTotalRootSize = 0;</span> |
| <span class="source-line-no">1378</span><span id="line-1378"></span> |
| <span class="source-line-no">1379</span><span id="line-1379"> /**</span> |
| <span class="source-line-no">1380</span><span id="line-1380"> * The "secondary index" used for binary search over variable-length records in a "non-root"</span> |
| <span class="source-line-no">1381</span><span id="line-1381"> * format block. These offsets are relative to the end of this secondary index.</span> |
| <span class="source-line-no">1382</span><span id="line-1382"> */</span> |
| <span class="source-line-no">1383</span><span id="line-1383"> private final List<Integer> secondaryIndexOffsetMarks = new ArrayList<>();</span> |
| <span class="source-line-no">1384</span><span id="line-1384"></span> |
| <span class="source-line-no">1385</span><span id="line-1385"> /**</span> |
| <span class="source-line-no">1386</span><span id="line-1386"> * Adds a new entry to this block index chunk.</span> |
| <span class="source-line-no">1387</span><span id="line-1387"> * @param firstKey the first key in the block pointed to by this entry</span> |
| <span class="source-line-no">1388</span><span id="line-1388"> * @param blockOffset the offset of the next-level block pointed to by this entry</span> |
| <span class="source-line-no">1389</span><span id="line-1389"> * @param onDiskDataSize the on-disk data of the block pointed to by this entry,</span> |
| <span class="source-line-no">1390</span><span id="line-1390"> * including header size</span> |
| <span class="source-line-no">1391</span><span id="line-1391"> * @param curTotalNumSubEntries if this chunk is the root index chunk under construction, this</span> |
| <span class="source-line-no">1392</span><span id="line-1392"> * specifies the current total number of sub-entries in all</span> |
| <span class="source-line-no">1393</span><span id="line-1393"> * leaf-level chunks, including the one corresponding to the</span> |
| <span class="source-line-no">1394</span><span id="line-1394"> * second-level entry being added.</span> |
| <span class="source-line-no">1395</span><span id="line-1395"> */</span> |
| <span class="source-line-no">1396</span><span id="line-1396"> @Override</span> |
| <span class="source-line-no">1397</span><span id="line-1397"> public void add(byte[] firstKey, long blockOffset, int onDiskDataSize,</span> |
| <span class="source-line-no">1398</span><span id="line-1398"> long curTotalNumSubEntries) {</span> |
| <span class="source-line-no">1399</span><span id="line-1399"> // Record the offset for the secondary index</span> |
| <span class="source-line-no">1400</span><span id="line-1400"> secondaryIndexOffsetMarks.add(curTotalNonRootEntrySize);</span> |
| <span class="source-line-no">1401</span><span id="line-1401"> curTotalNonRootEntrySize += SECONDARY_INDEX_ENTRY_OVERHEAD + firstKey.length;</span> |
| <span class="source-line-no">1402</span><span id="line-1402"></span> |
| <span class="source-line-no">1403</span><span id="line-1403"> curTotalRootSize += Bytes.SIZEOF_LONG + Bytes.SIZEOF_INT</span> |
| <span class="source-line-no">1404</span><span id="line-1404"> + WritableUtils.getVIntSize(firstKey.length) + firstKey.length;</span> |
| <span class="source-line-no">1405</span><span id="line-1405"></span> |
| <span class="source-line-no">1406</span><span id="line-1406"> blockKeys.add(firstKey);</span> |
| <span class="source-line-no">1407</span><span id="line-1407"> blockOffsets.add(blockOffset);</span> |
| <span class="source-line-no">1408</span><span id="line-1408"> onDiskDataSizes.add(onDiskDataSize);</span> |
| <span class="source-line-no">1409</span><span id="line-1409"></span> |
| <span class="source-line-no">1410</span><span id="line-1410"> if (curTotalNumSubEntries != -1) {</span> |
| <span class="source-line-no">1411</span><span id="line-1411"> numSubEntriesAt.add(curTotalNumSubEntries);</span> |
| <span class="source-line-no">1412</span><span id="line-1412"></span> |
| <span class="source-line-no">1413</span><span id="line-1413"> // Make sure the parallel arrays are in sync.</span> |
| <span class="source-line-no">1414</span><span id="line-1414"> if (numSubEntriesAt.size() != blockKeys.size()) {</span> |
| <span class="source-line-no">1415</span><span id="line-1415"> throw new IllegalStateException("Only have key/value count " + "stats for "</span> |
| <span class="source-line-no">1416</span><span id="line-1416"> + numSubEntriesAt.size() + " block index " + "entries out of " + blockKeys.size());</span> |
| <span class="source-line-no">1417</span><span id="line-1417"> }</span> |
| <span class="source-line-no">1418</span><span id="line-1418"> }</span> |
| <span class="source-line-no">1419</span><span id="line-1419"> }</span> |
| <span class="source-line-no">1420</span><span id="line-1420"></span> |
| <span class="source-line-no">1421</span><span id="line-1421"> /**</span> |
| <span class="source-line-no">1422</span><span id="line-1422"> * The same as {@link #add(byte[], long, int, long)} but does not take the key/value into</span> |
| <span class="source-line-no">1423</span><span id="line-1423"> * account. Used for single-level indexes.</span> |
| <span class="source-line-no">1424</span><span id="line-1424"> * @see #add(byte[], long, int, long)</span> |
| <span class="source-line-no">1425</span><span id="line-1425"> */</span> |
| <span class="source-line-no">1426</span><span id="line-1426"> @Override</span> |
| <span class="source-line-no">1427</span><span id="line-1427"> public void add(byte[] firstKey, long blockOffset, int onDiskDataSize) {</span> |
| <span class="source-line-no">1428</span><span id="line-1428"> add(firstKey, blockOffset, onDiskDataSize, -1);</span> |
| <span class="source-line-no">1429</span><span id="line-1429"> }</span> |
| <span class="source-line-no">1430</span><span id="line-1430"></span> |
| <span class="source-line-no">1431</span><span id="line-1431"> @Override</span> |
| <span class="source-line-no">1432</span><span id="line-1432"> public void clear() {</span> |
| <span class="source-line-no">1433</span><span id="line-1433"> blockKeys.clear();</span> |
| <span class="source-line-no">1434</span><span id="line-1434"> blockOffsets.clear();</span> |
| <span class="source-line-no">1435</span><span id="line-1435"> onDiskDataSizes.clear();</span> |
| <span class="source-line-no">1436</span><span id="line-1436"> secondaryIndexOffsetMarks.clear();</span> |
| <span class="source-line-no">1437</span><span id="line-1437"> numSubEntriesAt.clear();</span> |
| <span class="source-line-no">1438</span><span id="line-1438"> curTotalNonRootEntrySize = 0;</span> |
| <span class="source-line-no">1439</span><span id="line-1439"> curTotalRootSize = 0;</span> |
| <span class="source-line-no">1440</span><span id="line-1440"> }</span> |
| <span class="source-line-no">1441</span><span id="line-1441"></span> |
| <span class="source-line-no">1442</span><span id="line-1442"> /**</span> |
| <span class="source-line-no">1443</span><span id="line-1443"> * Finds the entry corresponding to the deeper-level index block containing the given</span> |
| <span class="source-line-no">1444</span><span id="line-1444"> * deeper-level entry (a "sub-entry"), assuming a global 0-based ordering of sub-entries.</span> |
| <span class="source-line-no">1445</span><span id="line-1445"> * <p></span> |
| <span class="source-line-no">1446</span><span id="line-1446"> * <i> Implementation note. </i> We are looking for i such that numSubEntriesAt[i - 1] <= k <</span> |
| <span class="source-line-no">1447</span><span id="line-1447"> * numSubEntriesAt[i], because a deeper-level block #i (0-based) contains sub-entries #</span> |
| <span class="source-line-no">1448</span><span id="line-1448"> * numSubEntriesAt[i - 1]'th through numSubEntriesAt[i] - 1, assuming a global 0-based ordering</span> |
| <span class="source-line-no">1449</span><span id="line-1449"> * of sub-entries. i is by definition the insertion point of k in numSubEntriesAt.</span> |
| <span class="source-line-no">1450</span><span id="line-1450"> * @param k sub-entry index, from 0 to the total number sub-entries - 1</span> |
| <span class="source-line-no">1451</span><span id="line-1451"> * @return the 0-based index of the entry corresponding to the given sub-entry</span> |
| <span class="source-line-no">1452</span><span id="line-1452"> */</span> |
| <span class="source-line-no">1453</span><span id="line-1453"> @Override</span> |
| <span class="source-line-no">1454</span><span id="line-1454"> public int getEntryBySubEntry(long k) {</span> |
| <span class="source-line-no">1455</span><span id="line-1455"> // We define mid-key as the key corresponding to k'th sub-entry</span> |
| <span class="source-line-no">1456</span><span id="line-1456"> // (0-based).</span> |
| <span class="source-line-no">1457</span><span id="line-1457"></span> |
| <span class="source-line-no">1458</span><span id="line-1458"> int i = Collections.binarySearch(numSubEntriesAt, k);</span> |
| <span class="source-line-no">1459</span><span id="line-1459"></span> |
| <span class="source-line-no">1460</span><span id="line-1460"> // Exact match: cumulativeWeight[i] = k. This means chunks #0 through</span> |
| <span class="source-line-no">1461</span><span id="line-1461"> // #i contain exactly k sub-entries, and the sub-entry #k (0-based)</span> |
| <span class="source-line-no">1462</span><span id="line-1462"> // is in the (i + 1)'th chunk.</span> |
| <span class="source-line-no">1463</span><span id="line-1463"> if (i >= 0) return i + 1;</span> |
| <span class="source-line-no">1464</span><span id="line-1464"></span> |
| <span class="source-line-no">1465</span><span id="line-1465"> // Inexact match. Return the insertion point.</span> |
| <span class="source-line-no">1466</span><span id="line-1466"> return -i - 1;</span> |
| <span class="source-line-no">1467</span><span id="line-1467"> }</span> |
| <span class="source-line-no">1468</span><span id="line-1468"></span> |
| <span class="source-line-no">1469</span><span id="line-1469"> /**</span> |
| <span class="source-line-no">1470</span><span id="line-1470"> * Used when writing the root block index of a multi-level block index. Serializes additional</span> |
| <span class="source-line-no">1471</span><span id="line-1471"> * information allowing to efficiently identify the mid-key.</span> |
| <span class="source-line-no">1472</span><span id="line-1472"> * @return a few serialized fields for finding the mid-key</span> |
| <span class="source-line-no">1473</span><span id="line-1473"> * @throws IOException if could not create metadata for computing mid-key</span> |
| <span class="source-line-no">1474</span><span id="line-1474"> */</span> |
| <span class="source-line-no">1475</span><span id="line-1475"> @Override</span> |
| <span class="source-line-no">1476</span><span id="line-1476"> public byte[] getMidKeyMetadata() throws IOException {</span> |
| <span class="source-line-no">1477</span><span id="line-1477"> ByteArrayOutputStream baos = new ByteArrayOutputStream(MID_KEY_METADATA_SIZE);</span> |
| <span class="source-line-no">1478</span><span id="line-1478"> DataOutputStream baosDos = new DataOutputStream(baos);</span> |
| <span class="source-line-no">1479</span><span id="line-1479"> long totalNumSubEntries = numSubEntriesAt.get(blockKeys.size() - 1);</span> |
| <span class="source-line-no">1480</span><span id="line-1480"> if (totalNumSubEntries == 0) {</span> |
| <span class="source-line-no">1481</span><span id="line-1481"> throw new IOException("No leaf-level entries, mid-key unavailable");</span> |
| <span class="source-line-no">1482</span><span id="line-1482"> }</span> |
| <span class="source-line-no">1483</span><span id="line-1483"> long midKeySubEntry = (totalNumSubEntries - 1) / 2;</span> |
| <span class="source-line-no">1484</span><span id="line-1484"> int midKeyEntry = getEntryBySubEntry(midKeySubEntry);</span> |
| <span class="source-line-no">1485</span><span id="line-1485"></span> |
| <span class="source-line-no">1486</span><span id="line-1486"> baosDos.writeLong(blockOffsets.get(midKeyEntry));</span> |
| <span class="source-line-no">1487</span><span id="line-1487"> baosDos.writeInt(onDiskDataSizes.get(midKeyEntry));</span> |
| <span class="source-line-no">1488</span><span id="line-1488"></span> |
| <span class="source-line-no">1489</span><span id="line-1489"> long numSubEntriesBefore = midKeyEntry > 0 ? numSubEntriesAt.get(midKeyEntry - 1) : 0;</span> |
| <span class="source-line-no">1490</span><span id="line-1490"> long subEntryWithinEntry = midKeySubEntry - numSubEntriesBefore;</span> |
| <span class="source-line-no">1491</span><span id="line-1491"> if (subEntryWithinEntry < 0 || subEntryWithinEntry > Integer.MAX_VALUE) {</span> |
| <span class="source-line-no">1492</span><span id="line-1492"> throw new IOException("Could not identify mid-key index within the "</span> |
| <span class="source-line-no">1493</span><span id="line-1493"> + "leaf-level block containing mid-key: out of range (" + subEntryWithinEntry</span> |
| <span class="source-line-no">1494</span><span id="line-1494"> + ", numSubEntriesBefore=" + numSubEntriesBefore + ", midKeySubEntry=" + midKeySubEntry</span> |
| <span class="source-line-no">1495</span><span id="line-1495"> + ")");</span> |
| <span class="source-line-no">1496</span><span id="line-1496"> }</span> |
| <span class="source-line-no">1497</span><span id="line-1497"></span> |
| <span class="source-line-no">1498</span><span id="line-1498"> baosDos.writeInt((int) subEntryWithinEntry);</span> |
| <span class="source-line-no">1499</span><span id="line-1499"></span> |
| <span class="source-line-no">1500</span><span id="line-1500"> if (baosDos.size() != MID_KEY_METADATA_SIZE) {</span> |
| <span class="source-line-no">1501</span><span id="line-1501"> throw new IOException("Could not write mid-key metadata: size=" + baosDos.size()</span> |
| <span class="source-line-no">1502</span><span id="line-1502"> + ", correct size: " + MID_KEY_METADATA_SIZE);</span> |
| <span class="source-line-no">1503</span><span id="line-1503"> }</span> |
| <span class="source-line-no">1504</span><span id="line-1504"></span> |
| <span class="source-line-no">1505</span><span id="line-1505"> // Close just to be good citizens, although this has no effect.</span> |
| <span class="source-line-no">1506</span><span id="line-1506"> baos.close();</span> |
| <span class="source-line-no">1507</span><span id="line-1507"></span> |
| <span class="source-line-no">1508</span><span id="line-1508"> return baos.toByteArray();</span> |
| <span class="source-line-no">1509</span><span id="line-1509"> }</span> |
| <span class="source-line-no">1510</span><span id="line-1510"></span> |
| <span class="source-line-no">1511</span><span id="line-1511"> /** Returns the size of this chunk if stored in the non-root index block format */</span> |
| <span class="source-line-no">1512</span><span id="line-1512"> @Override</span> |
| <span class="source-line-no">1513</span><span id="line-1513"> public int getNonRootSize() {</span> |
| <span class="source-line-no">1514</span><span id="line-1514"> return Bytes.SIZEOF_INT // Number of entries</span> |
| <span class="source-line-no">1515</span><span id="line-1515"> + Bytes.SIZEOF_INT * (blockKeys.size() + 1) // Secondary index</span> |
| <span class="source-line-no">1516</span><span id="line-1516"> + curTotalNonRootEntrySize; // All entries</span> |
| <span class="source-line-no">1517</span><span id="line-1517"> }</span> |
| <span class="source-line-no">1518</span><span id="line-1518"></span> |
| <span class="source-line-no">1519</span><span id="line-1519"> @Override</span> |
| <span class="source-line-no">1520</span><span id="line-1520"> public int getCurTotalNonRootEntrySize() {</span> |
| <span class="source-line-no">1521</span><span id="line-1521"> return curTotalNonRootEntrySize;</span> |
| <span class="source-line-no">1522</span><span id="line-1522"> }</span> |
| <span class="source-line-no">1523</span><span id="line-1523"></span> |
| <span class="source-line-no">1524</span><span id="line-1524"> @Override</span> |
| <span class="source-line-no">1525</span><span id="line-1525"> public List<byte[]> getBlockKeys() {</span> |
| <span class="source-line-no">1526</span><span id="line-1526"> return blockKeys;</span> |
| <span class="source-line-no">1527</span><span id="line-1527"> }</span> |
| <span class="source-line-no">1528</span><span id="line-1528"></span> |
| <span class="source-line-no">1529</span><span id="line-1529"> @Override</span> |
| <span class="source-line-no">1530</span><span id="line-1530"> public List<Integer> getSecondaryIndexOffsetMarks() {</span> |
| <span class="source-line-no">1531</span><span id="line-1531"> return secondaryIndexOffsetMarks;</span> |
| <span class="source-line-no">1532</span><span id="line-1532"> }</span> |
| <span class="source-line-no">1533</span><span id="line-1533"></span> |
| <span class="source-line-no">1534</span><span id="line-1534"> /** Returns the size of this chunk if stored in the root index block format */</span> |
| <span class="source-line-no">1535</span><span id="line-1535"> @Override</span> |
| <span class="source-line-no">1536</span><span id="line-1536"> public int getRootSize() {</span> |
| <span class="source-line-no">1537</span><span id="line-1537"> return curTotalRootSize;</span> |
| <span class="source-line-no">1538</span><span id="line-1538"> }</span> |
| <span class="source-line-no">1539</span><span id="line-1539"></span> |
| <span class="source-line-no">1540</span><span id="line-1540"> /** Returns the number of entries in this block index chunk */</span> |
| <span class="source-line-no">1541</span><span id="line-1541"> public int getNumEntries() {</span> |
| <span class="source-line-no">1542</span><span id="line-1542"> return blockKeys.size();</span> |
| <span class="source-line-no">1543</span><span id="line-1543"> }</span> |
| <span class="source-line-no">1544</span><span id="line-1544"></span> |
| <span class="source-line-no">1545</span><span id="line-1545"> public byte[] getBlockKey(int i) {</span> |
| <span class="source-line-no">1546</span><span id="line-1546"> return blockKeys.get(i);</span> |
| <span class="source-line-no">1547</span><span id="line-1547"> }</span> |
| <span class="source-line-no">1548</span><span id="line-1548"></span> |
| <span class="source-line-no">1549</span><span id="line-1549"> public long getBlockOffset(int i) {</span> |
| <span class="source-line-no">1550</span><span id="line-1550"> return blockOffsets.get(i);</span> |
| <span class="source-line-no">1551</span><span id="line-1551"> }</span> |
| <span class="source-line-no">1552</span><span id="line-1552"></span> |
| <span class="source-line-no">1553</span><span id="line-1553"> public int getOnDiskDataSize(int i) {</span> |
| <span class="source-line-no">1554</span><span id="line-1554"> return onDiskDataSizes.get(i);</span> |
| <span class="source-line-no">1555</span><span id="line-1555"> }</span> |
| <span class="source-line-no">1556</span><span id="line-1556"></span> |
| <span class="source-line-no">1557</span><span id="line-1557"> public long getCumulativeNumKV(int i) {</span> |
| <span class="source-line-no">1558</span><span id="line-1558"> if (i < 0) return 0;</span> |
| <span class="source-line-no">1559</span><span id="line-1559"> return numSubEntriesAt.get(i);</span> |
| <span class="source-line-no">1560</span><span id="line-1560"> }</span> |
| <span class="source-line-no">1561</span><span id="line-1561"></span> |
| <span class="source-line-no">1562</span><span id="line-1562"> }</span> |
| <span class="source-line-no">1563</span><span id="line-1563"></span> |
| <span class="source-line-no">1564</span><span id="line-1564"> public static int getMaxChunkSize(Configuration conf) {</span> |
| <span class="source-line-no">1565</span><span id="line-1565"> return conf.getInt(MAX_CHUNK_SIZE_KEY, DEFAULT_MAX_CHUNK_SIZE);</span> |
| <span class="source-line-no">1566</span><span id="line-1566"> }</span> |
| <span class="source-line-no">1567</span><span id="line-1567"></span> |
| <span class="source-line-no">1568</span><span id="line-1568"> public static int getMinIndexNumEntries(Configuration conf) {</span> |
| <span class="source-line-no">1569</span><span id="line-1569"> return conf.getInt(MIN_INDEX_NUM_ENTRIES_KEY, DEFAULT_MIN_INDEX_NUM_ENTRIES);</span> |
| <span class="source-line-no">1570</span><span id="line-1570"> }</span> |
| <span class="source-line-no">1571</span><span id="line-1571">}</span> |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| </pre> |
| </div> |
| </main> |
| </body> |
| </html> |
