注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

和申的个人主页

专注于java开发,1985wanggang

 
 
 

日志

 
 

Choosing a fast unique identifier (UUID) for Lucene  

2014-05-15 11:28:10|  分类: nutch搜索引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Choosing a fast unique identifier (UUID) for Lucene

Most search applications using Apache Lucene assign a unique id, or primary key, to each indexed document. While Lucene itself does not require this (it could care less!), the application usually needs it to later replace, delete or retrieve that one document by its external id. Most servers built on top of Lucene, such as Elasticsearch and Solr, require a unique id and can auto-generate one if you do not provide it. 

Sometimes your id values are already pre-defined, for example if an external database or content management system assigned one, or if you must use a URI, but if you are free to assign your own ids then what works best for Lucene? 

One obvious choice is Java's UUID class, which generates version 4 universally unique identifiers, but it turns out this is the worst choice for performance: it is 4X slower than the fastest. To understand why requires some understanding of how Lucene finds terms. 

BlockTree terms dictionary 

The purpose of the terms dictionary is to store all unique terms seen during indexing, and map each term to its metadata (de>docFreqde>, de>totalTermFreqde>, etc.), as well as the postings (documents, offsets, postings and payloads). When a term is requested, the terms dictionary must locate it in the on-disk index and return its metadata. 

The default codec uses the BlockTree terms dictionary, which stores all terms for each field in sorted binary order, and assigns the terms into blocks sharing a common prefix. Each block contains between 25 and 48 terms by default. It uses an in-memory prefix-trie index structure (an FST) to quickly map each prefix to the corresponding on-disk block, and on lookup it first checks the index based on the requested term's prefix, and then seeks to the appropriate on-disk block and scans to find the term. 

In certain cases, when the terms in a segment have a predictable pattern, the terms index can know that the requested term cannot exist on-disk. This fast-match test can be a sizable performance gain especially when the index is cold (the pages are not cached by the the OS's IO cache) since it avoids a costly disk-seek. As Lucene is segment-based, a single id lookup must visit each segment until it finds a match, so quickly ruling out one or more segments can be a big win. It is also vital to keep your segment counts as low as possible! 

Given this, fully random ids (like UUID V4) should perform worst, because they defeat the terms index fast-match test and require a disk seek for every segment. Ids with a predictable per-segment pattern, such as sequentially assigned values, or a timestamp, should perform best as they will maximize the gains from the terms index fast-match test. 

Testing Performance 

I created a simple performance tester to verify this; the full source code is here. The test first indexes 100 million ids into an index with 7/7/8 segment structure (7 big segments, 7 medium segments, 8 small segments), and then searches for a random subset of 2 million of the IDs, recording the best time of 5 runs. I used Java 1.7.0_55, on Ubuntu 14.04, with a 3.5 GHz Ivy Bridge Core i7 3770K. 

Since Lucene's terms are now fully binary as of 4.0, the most compact way to store any value is in binary form where all 256 values of every byte are used. A 128-bit id value then requires 16 bytes. 

I tested the following identifier sources:For the UUIDs and Flake IDs I also tested binary encoding in addition to their standard (base 16 or 36) encoding. Note that I only tested lookup speed using one thread, but the results should scale linearly (on sufficiently concurrent hardware) as you add threads.


Choosing a fast unique identifier (UUID) for Lucene - 和申 - 和申的个人主页
 Zero-padded sequential ids, encoded in binary are fastest, quite a bit faster than non-zero-padded sequential ids. UUID V4 (using Java's de>UUID.randomUUID()de>) is ~4X slower. 

But for most applications, sequential ids are not practical. The 2nd fastest is UUID V1, encoded in binary. I was surprised this is so much faster than Flake IDs since Flake IDs use the same raw sources of information (time, node id, sequence) but shuffle the bits differently to preserve total ordering. I suspect the problem is the number of common leading digits that must be traversed in a Flake ID before you get to digits that differ across documents, since the high order bits of the 64-bit timestamp come first, whereas UUID V1 places the low order bits of the 64-bit timestamp first. Perhaps the terms index should optimize the case when all terms in one field share a common prefix. 

I also separately tested varying the base from 10, 16, 36, 64, 256 and in general for the non-random ids, higher bases are faster. I was pleasantly surprised by this because I expected a base matching the BlockTree block size (25 to 48) would be best. 

There are some important caveats to this test (patches welcome)! A real application would obviously be doing much more work than simply looking up ids, and the results may be different as hotspot must compile much more active code. The index is fully hot in my test (plenty of RAM to hold the entire index); for a cold index I would expect the results to be even more stark since avoiding a disk-seek becomes so much more important. In a real application, the ids using timestamps would be more spread apart in time; I could "simulate" this myself by faking the timestamps over a wider range. Perhaps this would close the gap between UUID V1 and Flake IDs? I used only one thread during indexing, but a real application with multiple indexing threads would spread out the ids across multiple segments at once. 

I used Lucene's default TieredMergePolicy, but it is possible a smarter merge policy that favored merging segments whose ids were more "similar" might give better results. The test does not do any deletes/updates, which would require more work during lookup since a given id may be in more than one segment if it had been updated (just deleted in all but one of them). 

Finally, I used using Lucene's default Codec, but we have nice postings formats optimized for primary-key lookups when you are willing to trade RAM for faster lookups, such as this Google summer-of-code project from last year and MemoryPostingsFormat. Likely these would provide sizable performance gains!

6 comments:

  1. Choosing a fast unique identifier (UUID) for Lucene - 和申 - 和申的个人主页
    te style="font-style: normal; font-weight: bold;" >Ashwin Jayaprakashte>May 13, 2014 at 12:54 AM

    The chart/image is not visible in Firefox.

    Reply
    Replies
    1. Choosing a fast unique identifier (UUID) for Lucene - 和申 - 和申的个人主页
      te style="font-style: normal; font-weight: bold;" >Michael McCandlesste>May 13, 2014 at 9:34 AM

      Hmm I can see it with Firefox on OS X and Windows. Which OS/Firefox version are you using?

  2. Choosing a fast unique identifier (UUID) for Lucene - 和申 - 和申的个人主页
    te style="font-style: normal; font-weight: bold;" >Mikhail Khludnevte>May 14, 2014 at 5:52 AM

    Michael, thanks for the informative post!
    I have an off-topic question (as usual). This post provides details about the codec internals: "The default codec uses the...". I'm really interested in it. Is there such detailed explanation already published? 
    Nevertheless, it seems like this datastructure design exploits some sort of "block" pattern, or it's just a common sense? Can you point on any materials about designing such efficient datastructures? I need to design my own one.
    Thanks!

    Reply
    Replies
    1. Choosing a fast unique identifier (UUID) for Lucene - 和申 - 和申的个人主页
      te style="font-style: normal; font-weight: bold;" >Michael McCandlesste>May 14, 2014 at 10:21 AM

      Hi Mikhail,

      Alas, BlockTree is not well described, but it's very similar to burst tries, and I think there's a link to the paper in its javadocs or comments?

    2. Choosing a fast unique identifier (UUID) for Lucene - 和申 - 和申的个人主页
      te style="font-style: normal; font-weight: bold;" >Mikhail Khludnevte>May 14, 2014 at 12:26 PM

      Got it in BlockTreeTermsReader! Thanks!

  3. Choosing a fast unique identifier (UUID) for Lucene - 和申 - 和申的个人主页
    te style="font-style: normal; font-weight: bold;" >Anonymouste>May 14, 2014 at 11:58 AM

    Random UUIDs have another issue, indexing tends to be faster than the random number generator of the box.

    I go with id's applied at indexing gateways a v1 UUID sort64 encoded. https://code.google.com/p/guava-libraries/issues/detail?id=1415. I adapted Cassandra's UUID code which uses timestamp plus sequence plus node id for high frequency events. Then for bucketing / partioning an murmurh hash of the uuid ngram prefix. 

    Actually the reason for not going binary with the ids is because the speed improvement wasn't worth not being able to easily email, share. 

    Good post useful insight, tnx

    Reply
http://blog.mikemccandless.com/2014/05/choosing-fast-unique-identifier-uuid.html
  评论这张
 
阅读(889)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016