Lucene/Solr（5.0） 源码初探- Lucene Facet SortedSetDocValues (二）

//SortedSetDocValuesWriter
 public void addValue(int docID, BytesRef value) {
    if (value == null) {
      throw new IllegalArgumentException("field \"" + fieldInfo.name + "\": null value not allowed");
    }
    if (value.length > (BYTE_BLOCK_SIZE - 2)) {
      throw new IllegalArgumentException("DocValuesField \"" + fieldInfo.name + "\" is too large, must be <= " + (BYTE_BLOCK_SIZE - 2));
    }
    
    /**由于所有的文档是按照顺序index，如果docid变化，表示前面文档index结束要做一些后期操作*
    if (docID != currentDoc) {
      finishCurrentDoc();
    }

    // Fill in any holes:
    while(currentDoc < docID) {
      pendingCounts.add(0); // no values
      currentDoc++;
    }
   // 这里讲field 值加入内存
    addOneValue(value);
    updateBytesUsed();
  }


 private void addOneValue(BytesRef value) {

    /** 这里维护了一个hash表用来生成term id， 同时可以判定此term是够已经存在（去重）*/
    int termID = hash.add(value);
    if (termID < 0) {
      termID = -termID-1;
    } else {
      // reserve additional space for each unique value:
      // 1. when indexing, when hash is 50% full, rehash() suddenly needs 2*size ints.
      //    TODO: can this same OOM happen in THPF?
      // 2. when flushing, we need 1 int per value (slot in the ordMap).
      iwBytesUsed.addAndGet(2 * RamUsageEstimator.NUM_BYTES_INT);
    }
    
    if (currentUpto == currentValues.length) {
      currentValues = ArrayUtil.grow(currentValues, currentValues.length+1);
      // reserve additional space for max # values per-doc
      // when flushing, we need an int[] to sort the mapped-ords within the doc
      iwBytesUsed.addAndGet((currentValues.length - currentUpto) * 2 * RamUsageEstimator.NUM_BYTES_INT);
    }
   /** currentValues 是一个writer的全局数组，用来记录每个文档所包含的term Id
currentUpto 表示现在数组占用边界，对每个文档具体的统计在finishCurrentDoc 方法操作*/
    currentValues[currentUpto] = termID;
    currentUpto++;
  }

// finalize currentDoc: this deduplicates the current term ids
  private void finishCurrentDoc() {
    Arrays.sort(currentValues, 0, currentUpto);
    int lastValue = -1;
    int count = 0;
   /** currentValues termid 排序后，用pending 来做统计，pendingCounts 表示当前文档包含几个term,pending 维护一个termid数组，而且对于其中每个文档其包含的termid 必定唯一。*/
    for (int i = 0; i < currentUpto; i++) {
      int termID = currentValues[i];
      // if it's not a duplicate
      if (termID != lastValue) {
        pending.add(termID); // record the term id
        count++;
      }
      lastValue = termID;
    }
    // record the number of unique term ids for this doc
    pendingCounts.add(count);
    maxCount = Math.max(maxCount, count);
    currentUpto = 0;
    currentDoc++;
  }

做好每个文档的term统计以后，在最后flush操作中，生成几个关键数组，完成DocValues的存储。

//SortedSetDocValuesWriter
 public void flush(SegmentWriteState state, DocValuesConsumer dvConsumer) throws IOException {
    final int maxDoc = state.segmentInfo.getDocCount();
    final int maxCountPerDoc = maxCount;
    assert pendingCounts.size() == maxDoc;
    //由于hash是全局，并且去重，那么valuecount就是真正存储的term的数量
    final int valueCount = hash.size();
    //pending 数组表示文档包含哪些具体term id，每个文档之间已经按照termid 排序
    final PackedLongValues ords = pending.build();
    // 每个文档包含几个term
    final PackedLongValues ordCounts = pendingCounts.build();
    
    //sortedValues 是hash所有存储的term排序后term id 排列组合
    final int[] sortedValues = hash.sort(BytesRef.getUTF8SortedAsUnicodeComparator());
    final int[] ordMap = new int[valueCount];
   
    /**ordMap是数据索引表，可以根据termid 查找在sortedValues 中具体位置，挺tricky的行列转换代码*/
    for(int ord=0;ord<valueCount;ord++) {
      ordMap[sortedValues[ord]] = ord;
    }
    
    // 具体将各个数据字典写入segment,dvd,dvm文件中。
    dvConsumer.addSortedSetField(fieldInfo,

                              // ord -> value
                              new Iterable<BytesRef>() {
                                @Override
                                public Iterator<BytesRef> iterator() {
                                  return new ValuesIterator(sortedValues, valueCount, hash);
                                }
                              },
                              
                              // doc -> ordCount
                              new Iterable<Number>() {
                                @Override
                                public Iterator<Number> iterator() {
                                  return new OrdCountIterator(maxDoc, ordCounts);
                                }
                              },

                              // ords
                              new Iterable<Number>() {
                                @Override
                                public Iterator<Number> iterator() {
                                  return new OrdsIterator(ordMap, maxCountPerDoc, ords, ordCounts);
                                }
                              });
  }

由于看代码抽象，用上章的例子做为解释对象，上章例子中有如下SortedSetDocValuesFacetField：

Doc0:
  doc.add(new SortedSetDocValuesFacetField("Author", "Bob"));
  doc.add(new SortedSetDocValuesFacetField("Publish Year", "2010"));
Doc1:
  doc.add(new SortedSetDocValuesFacetField("Author", "Lisa"));
  doc.add(new SortedSetDocValuesFacetField("Publish Year", "2010"));
Doc2:
  doc.add(new SortedSetDocValuesFacetField("Author", "Lisa"));
  doc.add(new SortedSetDocValuesFacetField("Publish Year", "2012"));
Doc3:
  doc.add(new SortedSetDocValuesFacetField("Author", "Susan"));
  doc.add(new SortedSetDocValuesFacetField("Publish Year", "2012"));
Doc4:
  doc.add(new SortedSetDocValuesFacetField("Author", "Frank"));
  doc.add(new SortedSetDocValuesFacetField("Publish Year", "1999"));

根据上章分析所有的dim,label 将会拼接在一起，而且生成termid, 其term id 与term对应关系如下:
(注lucene存贮字符串是用utf8存储为了便于理解这里还是用字符串显示但是中间分隔符是1f)
0 ----- "Author1fBob"
1 ----- "Publish Year1f2010"
2 ----- "Author1fLisa"
3 ----- "Publish Year1f2012"
4 ----- "Author1fSusan"
5 ----- "Author1fFrank"
6 ----- "Publish Year1f1999"

pendingCounts(ordCounts) 在flush时候：
[2, 2, 2, 2, 2]
每个数组下标表示docid,这个数组表示0-4号文档，每个文档包括2个term

pending ords 在flush时候：
[0, 1, 1, 2, 2, 3, 3, 4, 5, 6]

结合ordCounts再看，对于文档1，查找pendingCounts 知道其包含2个term，其前一个文档也是包含2个term，那么查找文档1包含的term是从pending 数组下标2开始，到4 结束（不包含4），也就是包含term 1和2。

sortedValues 在flush时候:  [0, 5, 2, 4, 6, 1, 3]

很明显这是根据要存储的term按照字符串排序后，term id 的排列

ordMap 在flush时候: [0, 5, 2, 6, 3, 1, 4]

初看是和sortedValues 很类似，其实这是一个数组索引数组，我们根据文档号查找到其包含的term id 时候，我们遇到另外一个问题，因为term 存储不是按照termid或者term索引顺序存储的，而是按照term字符串的大小排列的，即使知道termid ，并不意味着顺序访问就能得到真正的term，所以ordMap 就是这个数据索引，假设我们知道文档1包含term 1,2，那么我们根据ordMap的下标（其就是term id ） 查找term1 的位置是5，也就是在sortvalues 存储在第5个term 位置，同理term2在第2个位置。

有意思的是在生成OrdMap中用的代码：

for(int ord=0;ord<valueCount;ord++) {
      ordMap[sortedValues[ord]] = ord;
   }

做到生成代码为O(n),而不是O(n*n)。到此可以回答前面的问题，所有的term都是单独去重排序存储（sortedValues），另外为所有文档维护term 信息pending ords，pendingCounts(ordCounts)，同时便于根据termid 查找具体term内容提供索引数组ordMap 查找。

评论

1 楼 q133662517 2018-02-28  

谢谢