View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase.codec.prefixtree.encode.row;
20  
21  import java.io.IOException;
22  import java.io.OutputStream;
23  import java.util.ArrayList;
24  
25  import org.apache.commons.logging.Log;
26  import org.apache.commons.logging.LogFactory;
27  import org.apache.hadoop.classification.InterfaceAudience;
28  import org.apache.hadoop.hbase.codec.prefixtree.PrefixTreeBlockMeta;
29  import org.apache.hadoop.hbase.codec.prefixtree.encode.PrefixTreeEncoder;
30  import org.apache.hadoop.hbase.codec.prefixtree.encode.tokenize.TokenizerNode;
31  import org.apache.hadoop.hbase.util.ByteRangeUtils;
32  import org.apache.hadoop.hbase.util.CollectionUtils;
33  import org.apache.hadoop.hbase.util.vint.UFIntTool;
34  import org.apache.hadoop.hbase.util.vint.UVIntTool;
35  
36  /**
37   * Serializes the fields comprising one node of the row trie, which can be a branch, nub, or leaf.
38   * Please see the write() method for the order in which data is written.
39   */
40  @InterfaceAudience.Private
41  public class RowNodeWriter{
42    protected static final Log LOG = LogFactory.getLog(RowNodeWriter.class);
43  
44    /********************* fields ******************************/
45  
46    protected PrefixTreeEncoder prefixTreeEncoder;
47    protected PrefixTreeBlockMeta blockMeta;
48    protected TokenizerNode tokenizerNode;
49  
50    protected int tokenWidth;
51    protected int fanOut;
52    protected int numCells;
53  
54    protected int width;
55  
56  
57    /*********************** construct *************************/
58  
59    public RowNodeWriter(PrefixTreeEncoder keyValueBuilder, TokenizerNode tokenizerNode) {
60      reconstruct(keyValueBuilder, tokenizerNode);
61    }
62  
63    public void reconstruct(PrefixTreeEncoder prefixTreeEncoder, TokenizerNode tokenizerNode) {
64      this.prefixTreeEncoder = prefixTreeEncoder;
65      reset(tokenizerNode);
66    }
67  
68    public void reset(TokenizerNode node) {
69      this.blockMeta = prefixTreeEncoder.getBlockMeta();// changes between blocks
70      this.tokenizerNode = node;
71      this.tokenWidth = 0;
72      this.fanOut = 0;
73      this.numCells = 0;
74      this.width = 0;
75      calculateOffsetsAndLengths();
76    }
77  
78  
79    /********************* methods ****************************/
80  
81    protected void calculateOffsetsAndLengths(){
82      tokenWidth = tokenizerNode.getTokenLength();
83      if(!tokenizerNode.isRoot()){
84        --tokenWidth;//root has no parent
85      }
86      fanOut = CollectionUtils.nullSafeSize(tokenizerNode.getChildren());
87      numCells = tokenizerNode.getNumOccurrences();
88    }
89  
90    public int calculateWidth(){
91      calculateWidthOverrideOffsetWidth(blockMeta.getNextNodeOffsetWidth());
92      return width;
93    }
94  
95    public int calculateWidthOverrideOffsetWidth(int offsetWidth){
96      width = 0;
97      width += UVIntTool.numBytes(tokenWidth);
98      width += tokenWidth;
99  
100     width += UVIntTool.numBytes(fanOut);
101     width += fanOut;
102 
103     width += UVIntTool.numBytes(numCells);
104 
105     if(tokenizerNode.hasOccurrences()){
106       int fixedBytesPerCell = blockMeta.getFamilyOffsetWidth()
107         + blockMeta.getQualifierOffsetWidth()
108         + blockMeta.getTagsOffsetWidth()
109         + blockMeta.getTimestampIndexWidth()
110         + blockMeta.getMvccVersionIndexWidth()
111         + blockMeta.getKeyValueTypeWidth()
112         + blockMeta.getValueOffsetWidth()
113         + blockMeta.getValueLengthWidth();
114       width += numCells * fixedBytesPerCell;
115     }
116 
117     if( ! tokenizerNode.isLeaf()){
118       width += fanOut * offsetWidth;
119     }
120 
121     return width;
122   }
123 
124 
125   /*********************** writing the compiled structure to the OutputStream ***************/
126 
127   public void write(OutputStream os) throws IOException{
128     //info about this row trie node
129     writeRowToken(os);
130     writeFan(os);
131     writeNumCells(os);
132 
133     //UFInt indexes and offsets for each cell in the row (if nub or leaf)
134     writeFamilyNodeOffsets(os);
135     writeQualifierNodeOffsets(os);
136     writeTagNodeOffsets(os);
137     writeTimestampIndexes(os);
138     writeMvccVersionIndexes(os);
139     writeCellTypes(os);
140     writeValueOffsets(os);
141     writeValueLengths(os);
142     //offsets to the children of this row trie node (if branch or nub)
143     writeNextRowTrieNodeOffsets(os);
144   }
145 
146 
147   /**
148    * Row node token, fan, and numCells. Written once at the beginning of each row node. These 3
149    * fields can reproduce all the row keys that compose the block.
150    */
151 
152   /**
153    * UVInt: tokenWidth
154    * bytes: token
155    */
156   protected void writeRowToken(OutputStream os) throws IOException {
157     UVIntTool.writeBytes(tokenWidth, os);
158     int tokenStartIndex = tokenizerNode.isRoot() ? 0 : 1;
159     ByteRangeUtils.write(os, tokenizerNode.getToken(), tokenStartIndex);
160   }
161 
162   /**
163    * UVInt: numFanBytes/fanOut
164    * bytes: each fan byte
165    */
166   public void writeFan(OutputStream os) throws IOException {
167     UVIntTool.writeBytes(fanOut, os);
168     if (fanOut <= 0) {
169       return;
170     }
171     ArrayList<TokenizerNode> children = tokenizerNode.getChildren();
172     for (int i = 0; i < children.size(); ++i) {
173       TokenizerNode child = children.get(i);
174       os.write(child.getToken().get(0));// first byte of each child's token
175     }
176   }
177 
178   /**
179    * UVInt: numCells, the number of cells in this row which will be 0 for branch nodes
180    */
181   protected void writeNumCells(OutputStream os) throws IOException {
182     UVIntTool.writeBytes(numCells, os);
183   }
184 
185 
186   /**
187    * The following methods write data for each cell in the row, mostly consisting of indexes or
188    * offsets into the timestamp/column data structures that are written in the middle of the block.
189    * We use {@link UFIntTool} to encode these indexes/offsets to allow random access during a binary
190    * search of a particular column/timestamp combination.
191    * <p/>
192    * Branch nodes will not have any data in these sections.
193    */
194 
195   protected void writeFamilyNodeOffsets(OutputStream os) throws IOException {
196     if (blockMeta.getFamilyOffsetWidth() <= 0) {
197       return;
198     }
199     for (int i = 0; i < numCells; ++i) {
200       int cellInsertionIndex = PrefixTreeEncoder.MULITPLE_FAMILIES_POSSIBLE ? tokenizerNode
201           .getFirstInsertionIndex() + i : 0;
202       int sortedIndex = prefixTreeEncoder.getFamilySorter().getSortedIndexForInsertionId(
203         cellInsertionIndex);
204       int indexedFamilyOffset = prefixTreeEncoder.getFamilyWriter().getOutputArrayOffset(
205         sortedIndex);
206       UFIntTool.writeBytes(blockMeta.getFamilyOffsetWidth(), indexedFamilyOffset, os);
207     }
208   }
209 
210   protected void writeQualifierNodeOffsets(OutputStream os) throws IOException {
211     if (blockMeta.getQualifierOffsetWidth() <= 0) {
212       return;
213     }
214     for (int i = 0; i < numCells; ++i) {
215       int cellInsertionIndex = tokenizerNode.getFirstInsertionIndex() + i;
216       int sortedIndex = prefixTreeEncoder.getQualifierSorter().getSortedIndexForInsertionId(
217         cellInsertionIndex);
218       int indexedQualifierOffset = prefixTreeEncoder.getQualifierWriter().getOutputArrayOffset(
219         sortedIndex);
220       UFIntTool.writeBytes(blockMeta.getQualifierOffsetWidth(), indexedQualifierOffset, os);
221     }
222   }
223 
224   protected void writeTagNodeOffsets(OutputStream os) throws IOException {
225     if (blockMeta.getTagsOffsetWidth() <= 0) {
226       return;
227     }
228     for (int i = 0; i < numCells; ++i) {
229       int cellInsertionIndex = tokenizerNode.getFirstInsertionIndex() + i;
230       int sortedIndex = prefixTreeEncoder.getTagSorter().getSortedIndexForInsertionId(
231         cellInsertionIndex);
232       int indexedTagOffset = prefixTreeEncoder.getTagWriter().getOutputArrayOffset(
233         sortedIndex);
234       UFIntTool.writeBytes(blockMeta.getTagsOffsetWidth(), indexedTagOffset, os);
235     }
236   }
237 
238   protected void writeTimestampIndexes(OutputStream os) throws IOException {
239     if (blockMeta.getTimestampIndexWidth() <= 0) {
240       return;
241     }
242     for (int i = 0; i < numCells; ++i) {
243       int cellInsertionIndex = tokenizerNode.getFirstInsertionIndex() + i;
244       long timestamp = prefixTreeEncoder.getTimestamps()[cellInsertionIndex];
245       int timestampIndex = prefixTreeEncoder.getTimestampEncoder().getIndex(timestamp);
246       UFIntTool.writeBytes(blockMeta.getTimestampIndexWidth(), timestampIndex, os);
247     }
248   }
249 
250   protected void writeMvccVersionIndexes(OutputStream os) throws IOException {
251     if (blockMeta.getMvccVersionIndexWidth() <= 0) {
252       return;
253     }
254     for (int i = 0; i < numCells; ++i) {
255       int cellInsertionIndex = tokenizerNode.getFirstInsertionIndex() + i;
256       long mvccVersion = prefixTreeEncoder.getMvccVersions()[cellInsertionIndex];
257       int mvccVersionIndex = prefixTreeEncoder.getMvccVersionEncoder().getIndex(mvccVersion);
258       UFIntTool.writeBytes(blockMeta.getMvccVersionIndexWidth(), mvccVersionIndex, os);
259     }
260   }
261 
262   protected void writeCellTypes(OutputStream os) throws IOException {
263     if (blockMeta.isAllSameType()) {
264       return;
265     }
266     for (int i = 0; i < numCells; ++i) {
267       int cellInsertionIndex = tokenizerNode.getFirstInsertionIndex() + i;
268       os.write(prefixTreeEncoder.getTypeBytes()[cellInsertionIndex]);
269     }
270   }
271 
272   protected void writeValueOffsets(OutputStream os) throws IOException {
273     for (int i = 0; i < numCells; ++i) {
274       int cellInsertionIndex = tokenizerNode.getFirstInsertionIndex() + i;
275       long valueStartIndex = prefixTreeEncoder.getValueOffset(cellInsertionIndex);
276       UFIntTool.writeBytes(blockMeta.getValueOffsetWidth(), valueStartIndex, os);
277     }
278   }
279 
280   protected void writeValueLengths(OutputStream os) throws IOException {
281     for (int i = 0; i < numCells; ++i) {
282       int cellInsertionIndex = tokenizerNode.getFirstInsertionIndex() + i;
283       int valueLength = prefixTreeEncoder.getValueLength(cellInsertionIndex);
284       UFIntTool.writeBytes(blockMeta.getValueLengthWidth(), valueLength, os);
285     }
286   }
287 
288   /**
289    * If a branch or a nub, the last thing we append are the UFInt offsets to the child row nodes.
290    */
291   protected void writeNextRowTrieNodeOffsets(OutputStream os) throws IOException {
292     ArrayList<TokenizerNode> children = tokenizerNode.getChildren();
293     for (int i = 0; i < children.size(); ++i) {
294       TokenizerNode child = children.get(i);
295       int distanceToChild = tokenizerNode.getNegativeIndex() - child.getNegativeIndex();
296       UFIntTool.writeBytes(blockMeta.getNextNodeOffsetWidth(), distanceToChild, os);
297     }
298   }
299 }