lucene中的docValue实现源码解读（六）——SortedDocValue的写入

 之前写了NumericDocValue（存储数字的）和BinaryDocValue（存储byte[]的），今天看看存储带有排序的byte[]的docValue，也就是SortedDocValue，这里没有写为SortedBinaryDocValue，可能是为了省略吧，SortedDocValue特指的就排是序的byte[]。注意，之前在写NumericDocValue和BinaryDocValue的时候，忘了说一个事情，就是他们要求每个doc只能存储一个值，即一个数字或者一个byte[]，这里SotedDocValue也是一样，每个doc只能有一个byte[]。这里说的排序是指每个doc的byte[]在所有的doc中的排序，在SotedDocValue中要保留这个排序，也就是我们可以从索引中马上得到这个doc的某个值的排序值，比如id是5的doc的排序是1，id是6的排序是3等，所以SortedDocValue特别适合排序，还有一个好处是，SortedDocValue提供了查询指定排序的byte[]的方法，即如果想查询排序是第几的doc的值，也可以快速的查找；还有一个优点就是如果在不建立索引的情况下，也可以查看某个byte[]存在与否。好了，好处慢慢再说，看下他是如何存储的吧。

和前面一样，写入的方法入口仍然是在DefaultIndexingChain的indexDocValue方法里面，里面会创建一个SortedDocValueWriter来写docValue，

//上面是一些属性，
/**这个属性是记录所有添加的byte[]的，在添加每个byte[]后，会给其一个id，我们这里叫做termId，如果这个byte[]已经存在了，则返回负值，否则返回其id。其实这个类就是创建索引的时候保存所有的term使用的   */
final BytesRefHash hash;
/**记录每个doc的termId的对象，每个doc都有一个termid，并且是按照顺序存放的，所以如果读取id是5的doc的值，则直接读取第五个值就可以。*/
private PackedLongValues.Builder pending;

public SortedDocValuesWriter(FieldInfo fieldInfo, Counter iwBytesUsed) {
	this.fieldInfo = fieldInfo;
	this.iwBytesUsed = iwBytesUsed;
	hash = new BytesRefHash(new ByteBlockPool(new ByteBlockPool.DirectTrackingAllocator(iwBytesUsed)),
			BytesRefHash.DEFAULT_CAPACITY, new DirectBytesStartArray(BytesRefHash.DEFAULT_CAPACITY, iwBytesUsed));
	pending = PackedLongValues.deltaPackedBuilder(PackedInts.COMPACT);
	bytesUsed = pending.ramBytesUsed();
	iwBytesUsed.addAndGet(bytesUsed);
}

 看看他的添加docValue方法，当然这里还是在内存中保存着，

public void addValue(int docID, BytesRef value) {
	if (value.length > (BYTE_BLOCK_SIZE - 2)) {//太大会报错
		throw new IllegalArgumentException("DocValuesField \"" + fieldInfo.name + "\" is too large, must be <= " + (BYTE_BLOCK_SIZE - 2));
	)
	// Fill in any holes:，因为有的doc没有值，所以要填窟窿，这样在读取的时候，直接按照doc的id读取即可，更加快速
	while (pending.size() < docID) {
		pending.add(EMPTY_ORD);
	}
	addOneValue(value);
}

private void addOneValue(BytesRef value) {
	int termID = hash.add(value);//添加到内存中，返回其termid
	if (termID < 0) {//已经存在了
		termID = -termID - 1;
	} else {//第一次出现，增加使用的内存		
		iwBytesUsed.addAndGet(2 * RamUsageEstimator.NUM_BYTES_INT);
	}
	pending.add(termID);//将这个termid记录起来，每个doc都有一个termid，这样在查找某个doc的termid的时候，直接根据doc的id查找即可。
	updateBytesUsed();
}

看了代码，就知道，在保存到内存的时候，其实最重要的就是两个属性，一个是用来保存byte[]的hash对象，他用来根据byte[]生成一个id，第二个就是记录每个doc的termid的pending对象。

下面看当提交索引的时候操作：

 

 

public void flush(SegmentWriteState state, DocValuesConsumer dvConsumer) throws IOException {
	final int maxDoc = state.segmentInfo.getDocCount();

	assert pending.size() == maxDoc;
	final int valueCount = hash.size();//term的个数
	final PackedLongValues ords = pending.build();//可以通过这个对象找到每个doc含有的byte[]的id
	// 获得所有的termid，按照文本值从小到大排序
	final int[] sortedValues = hash.sort(BytesRef.getUTF8SortedAsUnicodeComparator());
	final int[] ordMap = new int[valueCount];//每个term的排序，数组的下标是termid，value是排序。
	for (int ord = 0; ord < valueCount; ord++) {
		ordMap[sortedValues[ord]] = ord;//
	}
	dvConsumer.addSortedField(fieldInfo,
			// ord -> value，返回所有的byte[]，已经是排好序的。这样就可以使用前缀压缩。这个对象可以通过每个byte[]的排序找到对应的byte[].因为sortedValues的下标就是排序，而值就是id，所以根据排序就能找到id，再根据id就能从hash中找到byte[]
			new Iterable<BytesRef>() {
				public Iterator<BytesRef> iterator() {
					return new ValuesIterator(sortedValues, valueCount, hash);//第一个参数是已经排序的termid的数组，第二个是所有的byte[]的数量，第三个是所有的byte[]。
				}
			},
			// doc -> ord，返回每个doc的byte[]的id，可以通过ords找到每个doc的byte[]的id，然后通过ordMap根据id找到排序.
			new Iterable<Number>() {
				public Iterator<Number> iterator() {
					return new OrdsIterator(ordMap, maxDoc, ords);
				}
			});
}

通过上面的两个Iterator就可以 快速的得到每个doc含有的byte[]的排序（通过ordMap），并且能根据排序找到对应的byte[]的id（通过sortedValues），然后根据id快速的找到对应的byte[]（通过hash）。再看一下这两个iterable的具体实现：

private static class ValuesIterator implements Iterator<BytesRef> {
	final int sortedValues[];//次序到byte[]的id的映射
	final BytesRefHash hash;//从byte[]的id到byte[]的映射
	final BytesRef scratch = new BytesRef();
	final int valueCount;//byte[]的数量
	int ordUpto;//当前的指针

	ValuesIterator(int sortedValues[], int valueCount, BytesRefHash hash) {
		this.sortedValues = sortedValues;
		this.valueCount = valueCount;
		this.hash = hash;
	}

	@Override
	public boolean hasNext() {
		return ordUpto < valueCount;
	}

	@Override
	public BytesRef next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		hash.get(sortedValues[ordUpto], scratch);//sortedValues[ordUpto]求出的是byte[]的id，然后hash.get是根据id求出byte[]来，然后放入到scratch中。
		ordUpto++;
		return scratch;
	}
}

 可以总结，这个valueSourceIterator很简单，就是按照已经排好顺序的byte[]依次返回。再看看下一个iterator

private static class OrdsIterator implements Iterator<Number> {
	final PackedLongValues.Iterator iter;//这个是记录的每个doc的byte[]的id
	final int ordMap[];//记录的是每个byte[]的次序
	final int maxDoc;//一共多少个doc
	int docUpto;

	OrdsIterator(int ordMap[], int maxDoc, PackedLongValues ords) {
		this.ordMap = ordMap;
		this.maxDoc = maxDoc;
		assert ords.size() == maxDoc;
		this.iter = ords.iterator();
	}

	@Override
	public boolean hasNext() {
		return docUpto < maxDoc;
	}

	@Override
	public Number next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		int ord = (int) iter.next();
		docUpto++;
		return ord == -1 ? ord : ordMap[ord];//返回的是次序。即每个doc的byte[]的次序
	}
}

 从代码中可以看出，这个iterable返回的是每个doc的byte[] 的次序。

 

再看下到底是如何使用者两个iterable的，代码在Lucene410DocValuesConsumer.addSortedField(FieldInfo, Iterable<BytesRef>, Iterable<Number>)中：

public void addSortedField(FieldInfo field, Iterable<BytesRef> values, Iterable<Number> docToOrd)
		throws IOException {
	meta.writeVInt(field.number);
	meta.writeByte(Lucene410DocValuesFormat.SORTED);//记录格式。
	addTermsDict(field, values);//添加那些byte[]，按照前缀压缩的格式，
	addNumericField(field, docToOrd, false);//添加数字，也就是每个doc对应的排序
}

从名字上大概 可以看到，他是采取了两块来存储的，第一步存储的是byte[]，第二步存储的是每个doc的次序。事实上就是这么做的，先看第一个代码，即存储所有的byte[]。

private void addTermsDict(FieldInfo field, final Iterable<BytesRef> values) throws IOException {
	// first check if its a "fixed-length" terms dict
	int minLength = Integer.MAX_VALUE;
	int maxLength = Integer.MIN_VALUE;
	long numValues = 0;
	for (BytesRef v : values) {
		minLength = Math.min(minLength, v.length);
		maxLength = Math.max(maxLength, v.length);
		numValues++;
	}
	if (minLength == maxLength) {
		addBinaryField(field, values);//如果所有的byte[]的长度都相等，则直接向存储普通的binaryDocValue那样存储就可以了，不错这个条件几乎不会实现的
	} else if (numValues < REVERSE_INTERVAL_COUNT) {
		addBinaryField(field, values);//同上
	} else {
		// header
		meta.writeVInt(field.number);
		meta.writeByte(Lucene410DocValuesFormat.BINARY);
		meta.writeVInt(BINARY_PREFIX_COMPRESSED);//写入存储格式，是基于前缀压缩的。
		meta.writeLong(-1L);
		final long startFP = data.getFilePointer();
//刚上来可能不好看懂，所以我直接说一下是怎么存储的吧，在存储所有的byte[]的时候，是按照前缀压缩匹配的，就像在词典表中存放到格式一样。
//每16个byte[]作为一个块来存储，在一个块中又分为两部分，第一部分是记录的这个快的第一个byte[]以及后面的15个byte的除了共享前缀意外的长度。这一部分叫做headBuffer
//在第二个块中记录的是另外15个byte[]的除了共享前缀意外的部分以及共享前缀的长度。这个部分叫做bytesBuffer
		RAMOutputStream addressBuffer = new RAMOutputStream();
		MonotonicBlockPackedWriter termAddresses = new MonotonicBlockPackedWriter(addressBuffer, BLOCK_SIZE);//记录每个block的开始位置在data中的位置，也就是每个块的索引的
		RAMOutputStream bytesBuffer = new RAMOutputStream();//记录第二部分
		// buffers up block header
		RAMOutputStream headerBuffer = new RAMOutputStream();//第一部分，每隔16个则记录一次。
		BytesRefBuilder lastTerm = new BytesRefBuilder();//刚刚写入第一部分的byte[]。
		lastTerm.grow(maxLength);
		long count = 0;
		int suffixDeltas[] = new int[INTERVAL_COUNT];//记录第二部分的byte[]在刨除了和对应的第一部分的byte[]的共享前缀意外的长度
		for (BytesRef v : values) {
			int termPosition = (int) (count & INTERVAL_MASK);//每隔interval_mask+1 个，也就是16个
			if (termPosition == 0) {//每隔16个，记录一个到第一部分中
				termAddresses.add(data.getFilePointer() - startFP);//记录一个小块的开始位置，也就是索引
				headerBuffer.writeVInt(v.length);//在第一部分中记录当前的byte[]的长度
				headerBuffer.writeBytes(v.bytes, v.offset, v.length);//记录当前的byte[]的内容
				lastTerm.copyBytes(v);//保留当前的byte[]，
			} else {
				// 基于前缀压缩的，最大共享前缀是255个
				int sharedPrefix = Math.min(255, StringHelper.bytesDifference(lastTerm.get(), v));//当前的byte[]和刚刚写入上层跳表的byte[]的前缀的数量，最大255个。
				bytesBuffer.writeByte((byte) sharedPrefix);//在第二部分中写入前缀的长度
				bytesBuffer.writeBytes(v.bytes, v.offset + sharedPrefix, v.length - sharedPrefix);//将刨除了前缀以外的部分写入到第二部分中
				suffixDeltas[termPosition] = v.length - sharedPrefix - 1;//记录当前的byte[]刨除了共享前缀意外的部分的长度，这个值将来写在第一部分里面，比如这个块的第一层记录的byte[]是a,而当前的byte[]记录的是ab，则这个值就是1，当然我这里用的是字符数组，不是byte[]。
			}
			count++;
			if ((count & INTERVAL_MASK) == 0) {//每够16个，写入到硬盘
				flushTermsDictBlock(headerBuffer, bytesBuffer, suffixDeltas);
			}
		}
		// flush trailing crap
		int leftover = (int) (count & INTERVAL_MASK);
		if (leftover > 0) {//写入最后的部分，因为上面只有到16的倍数才会写入到data中。
			Arrays.fill(suffixDeltas, leftover, suffixDeltas.length, 0);
			flushTermsDictBlock(headerBuffer, bytesBuffer, suffixDeltas);
		}
		final long indexStartFP = data.getFilePointer();//索引部分，也就是上面的addressBuffer在data中的开始位置。
		// write addresses of indexed terms，接下来要写的是每个块在data中的开始位置
		termAddresses.finish();
		addressBuffer.writeTo(data);
		addressBuffer = null;
		termAddresses = null;
		meta.writeVInt(minLength);
		meta.writeVInt(maxLength);
		meta.writeVLong(count);
		meta.writeLong(startFP);//记录byte[]数据的开始位置，
		meta.writeLong(indexStartFP);//记录索引的开始位置
		meta.writeVInt(PackedInts.VERSION_CURRENT);
		meta.writeVInt(BLOCK_SIZE);
		addReverseTermIndex(field, values, maxLength);
	}
}

 还有一个方法是flushTermDictBlock方法，也就是当每个16个byte[]的时候，要把第一部分，第二部分写入到硬盘，看看他是如何操作的：

/**参数的意义可以在上面的方法中查找到*/
private void flushTermsDictBlock(RAMOutputStream headerBuffer, RAMOutputStream bytesBuffer, int suffixDeltas[])	throws IOException {
	boolean twoByte = false;//这个的意思是记录每一个块的长度的时候（长度说的是每个byte[]在刨除了共享前缀的byte[]以外的长度），可能会超过254，如果超过了就用short，否则用byte。
	for (int i = 1; i < suffixDeltas.length; i++) {
		if (suffixDeltas[i] > 254) {
			twoByte = true;
		}
	}
	if (twoByte) {//随便看一种即可。可以发现是将每个byte[]的除了共享前缀意外的部分的长度写在了head里面，即第一部分里面。
		headerBuffer.writeByte((byte) 255);
		for (int i = 1; i < suffixDeltas.length; i++) {
			headerBuffer.writeShort((short) suffixDeltas[i]);
		}
	} else {
		for (int i = 1; i < suffixDeltas.length; i++) {
			headerBuffer.writeByte((byte) suffixDeltas[i]);
		}
	}
	headerBuffer.writeTo(data);//将head写入到data中，
	headerBuffer.reset();
	bytesBuffer.writeTo(data);//将bytes写入到data中
	bytesBuffer.reset();
}

 看完了上面的两个方法，我们可以总结下载存储具体的byte[]的时候是怎么存储的。所有的byte[]经过排序后，按照从小到大的顺序保存，然后每16个存储为一个块，这个块中分为两个部分，第一个部分叫做header，存储了 这个块的第一个byte[]，以及剩下的15个byte[]的除了前缀意外的部分的长度，第二个块存储的是每个byte[]的共享前缀的长度，以及自己的byte[]。还有存储了termAddress，也就是记录了每个块在data中的开始位置，这样当我们要查找某个排序的byte[]的时候，就可以先计算其所属的块，然后直接根据termAddress找到对应的开始位置再从16个byte[]中查找就可以了。我们还忘记了一个方法，也即是上面的addReverseTermIndex方法，看一下：

private void addReverseTermIndex(FieldInfo field, final Iterable<BytesRef> values, int maxLength) throws IOException { 
		long count = 0;
		BytesRefBuilder priorTerm = new BytesRefBuilder();
		priorTerm.grow(maxLength);
		BytesRef indexTerm = new BytesRef();
		long startFP = data.getFilePointer();//第三部分的开始的位置
		PagedBytes pagedBytes = new PagedBytes(15);//用来记录生成的每个字符串
		MonotonicBlockPackedWriter addresses = new MonotonicBlockPackedWriter(data, BLOCK_SIZE);//因为下面的每次的indexTerm的长度都是不同的，要使用这个对象记录每个indexTerm在data中的开始位置，这样在查找的时候能更快速的定位到第n个字符串的位置
		for (BytesRef b : values) {
			int termPosition = (int) (count & REVERSE_INTERVAL_MASK);
			if (termPosition == 0) {//每隔1024个，记录一个term，第0个或者是第1024个，进入
				int len = StringHelper.sortKeyLength(priorTerm.get(), b);//找到能够判断出两个byte[]大小所需要的最小的长度。
				indexTerm.bytes = b.bytes;
				indexTerm.offset = b.offset;
				indexTerm.length = len;//只记录最开始的一些。
				addresses.add(pagedBytes.copyUsingLengthPrefix(indexTerm));//记录添加前的位置，也就是开始位置，最终写入到data中去
			} else if (termPosition == REVERSE_INTERVAL_MASK) {//第1023个进入
				priorTerm.copyBytes(b);
			}
			count++;
		}
		addresses.finish();//将所有的新的字符串的位置写入到data中
		long numBytes = pagedBytes.getPointer();//使用的byte的个数
		pagedBytes.freeze(true);
		PagedBytesDataInput in = pagedBytes.getDataInput();
		meta.writeLong(startFP);//第三部分的开始位置写入到索引中
		data.writeVLong(numBytes);//记录pagedBytess使用的长度
		data.copyBytes(in, numBytes);//写入pagedBytes，也就是所有的字符串（每隔1024个term计算一个字符串）。
	}

 这个方法很简单，他是对于所有的byte[]，每1024个记录一些最短的byte[]的前缀（也就是上面说的产生一个新的字符串），使得所有的byte[]能够区别出大小来就可以，他的目的是对于某些查询，比如要查询abc这个byte[]存不存在（这个方法在SortedDocValues里面就存在），如果没有这个功能的话，我们并不知道他是哪一个块，只能尝试所有的块，而如果有了这个记录，我们就能快速定位他的大致的范围，然后再查找的话，就快的多了。这个功能是后来新家的，我看4.9就没有，4.10就有了。

 

再次总结一下sortedBinary的存储吧，一共分为三块，第一块是记录所有的byte[]的，按照每16个一个小块记录，每个小块分为两部分，header和bytes（详细的不再重复）；第二块是记录了每个小块在data中的索引，方便快速的找到块的位置；第三部分就是每个2014个记录一个尽可能小的byte[]，是为了查找某个byte[]存不存在而存放的，使用二分查找，快速的找到其大概位置，然后在从小块中查找，也可以看做是byte[]的索引吧。不过期效率不是很高。

 

还有一个方法就是addSortedField中的addNumericField，这个方法很简单，目的就是记录每个doc的byte[]的排序的，方便根据doc查找到排序后，再查找具体的byte[]值。这个方法就是之前写NumericDocValue时的方法。不再重复了。

算法上面的addNumeircField方法，我们可以将所有的sortedBinaryDocValue分为两个部分，一个是binary部分，一个是numeric部分，前面的部分负责保存byte[]，是分为三个部分存放的额，第二个部分用来存放每个doc的byte[]的排序。 知道了这个存储格式，我们就能猜想sortedDocValue的功能的实现，比如查找排序是n的docValue，可以直接根据n找到binary部分的第一部分的第n%16+1个小块，根据第二小块的索引快速定位到开始位置，然后再16个小块中查找；如果想查找docid是n的doc的排序，则直接查找numeric部分即可，如果再想查找byte[]，则再根据排序查找即可。