Some of you have noticed that I'm not writing much in this blog lately.
But fear not: exciting changes are still happening in Lucene, and I am still writing about them!
It's just that most of what I write is now appearing at either the Elastic blogs or on my Google+ feed, so please head over to those two sources to keep reading about the fun changes in Apache Lucene and Elasticsearch.
There are no promises for the exact timing (it's done when it's done!), but we already have a volunteer release manager (thank you Anshum!).
A major release in Lucene means all deprecated APIs (as of 4.10.x) are dropped, support for 3.x indices is removed while the numerous 4.x index formats are still supported for index backwards compatibility, and the 4.10.x branch becomes our bug-fix only release series (no new features, no API changes).
5.0.0 already contains a number of exciting changes, which I describe below, and they are still rolling in with ongoing active development.
Stronger index safety
Many of the 5.0.0 changes are focused on providing stronger protection against index corruption.
All file
access now uses
Java's
NIO.2 APIs, giving us better error handling
(e.g., Files.delete returns a meaningful exception) along
with atomic rename for
safer
commits, reducing the risk of hideous "your entire index is gone"
bugs
like this
doozie.
Lucene's replication module, along with distributed servers on top of Lucene such as Elasticsearch or Solr, must copy index files from one place to another. They do this for backup purposes (e.g., snapshot and restore), for migrating or recovering a shard from one node to another or when adding a new replica. Such replicators try to be incremental, so that if the same file name is present, with the same length and checksum, it will not be copied again.
Unfortunately, these layers sometimes have subtle bugs (they are complex!). Thanks to checksums (added in 4.8.0), Lucene already detects if the replicator caused any bit-flips while copying, and this revealed a long standing nasty bug in the compression library Elasticsearch uses.
With 5.0.0 we take this even further and now detect if whole files
were copied to the wrong file name, by assigning
a unique
id to every segment and commit (segments_N file).
Each index file now records
the segment
id in its header, and then these ids are cross-checked when the
index is opened.
The new Lucene50Codec also includes further index corruption detection.
Even CorruptIndexException itself is improved! It will
now always refer to the file or resource where the corruption was
detected, as this is now a required argument to its constructors.
When corruption is detected higher up (e.g., a bad field number in the
field infos file), the resulting CorruptIndexException
will now state whether there was also a checksum mismatch in the file,
helping to narrow the possible source of the corruption.
Finally, during merge, IndexWriter now always checks the
incoming segments for corruption before merging. This can mean, on
upgrading to 5.0.0, that merging may uncover long-standing latent
corruption in an older 4.x index.
Reduced heap usage
5.0.0 also includes several changes to reduce heap usage during indexing and searching.
If your index has 1B docs, then caching a
single FixedBitSet-based filter in 4.10.2
costs a non-trivial 125 MB of heap! But with 5.0.0, Lucene now
supports random-writable and advance-able sparse bitsets
(RoaringDocIdSet
and SparseFixedBitSet),
so the heap required is in proportion to how many bits are set, not how
many total documents exist in the index. These bitsets also greatly
simplify how MultiTermQuery is rewritten (no
more CONSTANT_SCORE_AUTO_REWRITE_METHOD), and they
provide faster advance implementations than FixedBitSet's
linear scan. Finally, they provide a more
accurate cost() implementation, allowing Lucene to make
better choices about how to drive the intersection at query time.
Heap usage during IndexWriter merging is
also much
lower with the new Lucene50Codec, since doc values and norms for
the segments being merged are no longer fully loaded into heap for all
fields; now they are loaded for the one field currently being merged, and then
dropped.
The default norms format now uses sparse encoding when appropriate, so indices that enable norms for many sparse fields will see a large reduction in required heap at search time.
An explain API for heap usage
If you still find Lucene using more heap than you expected, 5.0.0 has a new API to print a tree structure showing a recursive breakdown of which parts are using how much heap. This is analogous to Lucene's explain API, used to understand why a document has a certain relevance score, but applied to heap usage instead.
It produces output like this:
_cz(5.0.0):C8330469: 28MB
postings [...]: 5.2MB
...
field 'latitude' [...]: 678.5KB
term index [FST(nodes=6679, ...)]: 678.3KB
This is a much faster way to see what is using up your heap than trying to stare
at a Java heap dump.
Further changes
There is a long tail of additional 5.0.0 changes; here are some of them:
Sep/Fixed/VariableIntPostingsFormat) have been
removed. PulsingPostingsFormat has also been removed,
since the default postings format already pulses unique terms.
FieldCache is gone (moved to a
dedicated UninvertingReader in the misc
module). This means when you intend to sort on a field, you
should index that field using doc values, which is much faster and
less heap consuming than FieldCache.
Tokenizers and Analyzers no longer require Reader on init.
NormsFormat now gets its own dedicated NormsConsumer/Producer
FieldInfo (Lucene's "low schema"): no more normType
(it is always a DocValuesType.NUMERIC), no more isIndexed (just check
IndexOptions)
SortedSetSortField, used to sort on a multi-valued
field, is promoted from sandbox to Lucene's core
PostingsFormat now uses a "pull" API when writing
postings, just like doc values. This is powerful because you can
do things in your postings format that require making more than one
pass through the postings such as iterating over all postings for
each term to decide which compression format it should use.
IndexWriterConfig and analysis components.
TermQuery, matches any document that contains the specified term, regardless of where the term occurs inside each document. Using BooleanQuery you can combine multiple TermQuerys, with full control over which terms
are optional (SHOULD) and which are required (MUST) or required not to be present (MUST_NOT), but still the matching ignores the relative positions of each term inside the document.
PhraseQuery, to match a specific sequence of tokens such as "Barack Obama". Seen as a graph, a PhraseQuery is a simple linear chain:
*) transition to match an arbitrary token. (Note: while the graph cannot properly express it, this query would also match a document that had the tokens Barack and Obama on top of one another, at the same position, which is a little bit strange!)
MultiPhraseQuery is another proximity query. It generalizes PhraseQuery by allowing more than one token at each position, for example:
domain name system or domain name service. MultiPhraseQuery also accepts a slop factor to allow for non-precise matches.
SpanNearQuery, SpanFirstQuery) go even further, allowing you to build up a complex compound query based on positions where each clause matched. What makes them unique is that you can arbitrarily nest them. For example, you could first build a SpanNearQuery matching Barack Obama with slop=1, then another one matching George Bush, and then make another SpanNearQuery, containing both of those as sub-clauses, matching if they appear within 10 terms of one another.
MultiPhraseQuery and the span queries: it allows you to directly build an arbitrary automaton expressing how the terms must occur in sequence, including any transitions to handle slop. Here's an example:
QueryParser support yet, patches welcome!). Once that's done, the query determinizes the automaton and then uses the same infrastructure (e.g. CompiledAutomaton) that queries like FuzzyQuery use for fast term matching, but applied to term positions instead of term bytes. The query is naively scored like a phrase query, which may not be ideal in some cases.
TokenStreamToTermAutomatonQuery, that provides loss-less translation of any graph TokenStream into the equivalent TermAutomatonQuery. This is powerful because it means even arbitrary token stream graphs will be correctly represented at search time, preserving the PositionLengthAttribute that some tokenizers now set.
PositionLengthAttribute, index-time synonyms are still not fully correct. That said, it would be simple to build a TokenFilter that writes the position length into a payload, and then to extend the new TermAutomatonQuery to read from the payload and apply that length during matching (patches welcome!).
getFiniteStrings API to do this for any automaton) and construct a boolean query from those phrase queries. This would match the same set of documents, also correctly preserving PositionLengthAttribute, but would assign different scores.
docFreq, totalTermFreq, 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.
UUID.randomUUID().
UUID.randomUUID()) is ~4X slower.
IndexWriter.commit, even if the OS or JVM crashes or power is lost, or you kill -KILL your JVM process, after rebooting, the index will be intact (not corrupt) and will reflect the last successful commit before the crash.
CheckIndex. This is similar to the ZFS file system's block-level checksums, but not everyone uses ZFS yet (heh), and so Lucene now does its own checksum verification on top of the file system.
IndexWriterConfig.setCheckIntegrityAtMerge. In the future we'd like to remove that option and always validate checksums on merge, and we've already done so for the default stored fields format in LUCENE-5580 and (soon) term vectors format in LUCENE-5602, as well as set up the low-level IO APIs so other codec components can do so as well, with LUCENE-5583, for Lucene 4.8.0.
IndexWriter.commit, Lucene gathers up all newly written filenames since the last commit, and invokes FileDescriptor.sync on each one to ensure all changes are moved to stable storage.
FSDirectory implementations is able to bring new 0-byte files into existence. This normally isn't a problem by itself, because IndexWriter shouldn't fsync a file that it didn't create. However, it exacerbates debugging when there is a bug in IndexWriter or in the application using Lucene (e.g., directly deleting index files that it shouldn't). In these cases it's confusing to discover these 0-byte files so much later, versus hitting a FileNotFoundException at the point when IndexWriter tried to fsync them.
segments_N files), and of course also opens files by their names.
fdatasync if the file length has changed, which is always the case in Lucene since we only append to files when writing (we removed Indexoutput.seek in LUCENE-4399).
IndexWriter.commit, will IndexWriter then re-open the newly created files in order to obtain a FileDescriptor so we can fsync them.
IndexWriter.commit and the laws of physics ensuring little magnets were flipped or a few electrons were moved into a tiny floating gate in a NAND cell, how can we reliably test that the whole series of abstractions is actually working?
Directory implementation called MockDirectoryWrapper. It can do all sorts of nasty things like throw random exceptions, sometimes slow down opening, closing and writing of some files, refuse to delete still-open files (like Windows), refuse to close when there are still open files, etc. This has helped us find all sorts of fun bugs over time.
FSDirectory classes, such as the frustrating LUCENE-3418 (first appeared in Lucene 3.1 and finally fixed in Lucene 3.4).
WordDelimiterFilter so that
CamelCaseTokens are split. For example,
try searching
on infix and note the highlights. As Rober Muir reminded
me, WordDelimiterFilter corrupts offsets, which will
mess up highlighting in some cases, so I'm going to try to set
up ICUTokenizer, which I'm already using, to do this
splitting instead.
FieldComparator to achieve
the same functionality, but expressions is more compact and powerful
and lets me remove that custom FieldComparator.
commit once per day. Previously I never
committed, and simply relied on near-real-time searching. This
works just fine, except when I need to bring the server down
(e.g. to push new changes out), it required full reindexing, which
was very fast but a poor user experience for those users who
happened to do a search while it was happening. Now, when I bounce
the server it comes back to the last commit and then the
near-real-time indexing quickly catches up on any changed issues
since that last commit.
WFSTCompletionLookup compiles all suggestions and their weights into a compact Finite State Transducer, enabling fast prefix lookup for basic suggestions.
AnalyzingSuggester improves on this by using an Analyzer to normalize both the suggestions and the user's query so that trivial differences in whitespace, casing, stop-words, synonyms, as determined by the analyzer, do not prevent a suggestion from matching.
AnalyzingInfixSuggester goes further by allowing infix matches so that words inside each suggestion (not just the prefix) can trigger a match. You can see this one action at the Lucene/Solr Jira search application (e.g., try "python") that I recently created to eat our own dog food. It is also the only suggester implementation so far that supports highlighting (this has proven challenging for the other suggesters).
FreeTextSuggester, can help! It uses the approach described in this Google blog post.
FreeTextSuggester will see "3d" and the "p" prefix for the next token and predict printer, even though "flashforge 3d printer" was never explicitly added as a suggestion.
FreeTextSuggester will be as a fallback: you would first use one of the existing exact match suggesters, but when those suggesters fail to find any suggestions for a given query, because it's "unusual" and has crossed over into the long tail, you then fall back to FreeTextSuggester.
< 1 km (147) < 2 km (579) < 5 km (2775)Such distance facets, which allow the user to quickly filter their search results to those that are close to their location, has become especially important lately since most searches are now from mobile smartphones.
ValueSource, not just a numeric doc values field from the index. Thanks to the recently added expressions module, this means you can offer dynamic range facets computed from an arbitrary JavaScript expression, since the expression is compiled on-the-fly to a ValueSource using custom generated Java bytecodes with ASM. Lucene's range faceting is also faster now, using segment trees to quickly assign each value to the matching ranges.
DoubleDocValuesFields in each document, and you know the user's latitude/longitude location for each request, you can easily compute facet counts and offer drill-downs by any set of chosen distances.
1 2 3 4 | Document doc = new Document();
doc.add(new DoubleField("latitude", 40.759011, Field.Store.NO));
doc.add(new DoubleField("longitude", -73.9844722, Field.Store.NO));
writer.addDocument(doc);
|
ValueSource by building a dynamic expression that invokes the Haversine function:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | private ValueSource getDistanceValueSource() {
Expression distance;
try {
distance = JavascriptCompiler.compile(
"haversin(40.7143528,-74.0059731,latitude,longitude)");
} catch (ParseException pe) {
// Should not happen
throw new RuntimeException(pe);
}
SimpleBindings bindings = new SimpleBindings();
bindings.add(new SortField("latitude", SortField.Type.DOUBLE));
bindings.add(new SortField("longitude", SortField.Type.DOUBLE));
return distance.getValueSource(bindings);
}
|
ValueSource, compute the dynamic facet counts like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 | FacetsCollector fc = new FacetsCollector();
searcher.search(new MatchAllDocsQuery(), fc);
Facets facets = new DoubleRangeFacetCounts(
"field",
getDistanceValueSource(), fc,
ONE_KM,
TWO_KM,
FIVE_KM,
TEN_KM);
return facets.getTopChildren(10, "field");
|
MatchAllDocsQuery.
Finally, once the user picks a distance for drill-down, use the Range.getFilter method and add that to a DrillDownQuery using ConstantScoreQuery:
1 2 3 4 5 6 7 8 9 10 | public TopDocs drillDown(DoubleRange range) throws IOException {
// Passing no baseQuery means we drill down on all
// documents ("browse only"):
DrillDownQuery q = new DrillDownQuery(null);
q.add("field", new ConstantScoreQuery(
range.getFilter(getDistanceValueSource())));
return searcher.search(q, 10);
}
|
lucene/demo module.
Updated drill-down in the
Lucene/Solr
issue search application uses range facets. Another
example is distance facets (< 1 km, < 2 km, etc.), where the distance
is dynamically computed based on the user's current location. Price
faceting might also use range facets, if the ranges cannot be
established during indexing.
O(N) cost, where N is the number of ranges.
O(log(N) + M) cost per lookup, where
M is the number of ranges that match the given value. I
chose to explore segment trees, as Lucene only requires looking up by
a single value (interval trees can also efficiently look up
all ranges overlapping a provided range) and also because all
the ranges are known up front (interval trees also support dynamically
adding or removing ranges).
ImmutableRangeSet takes this approach. However,
Lucene's range faceting allows overlapping ranges so we can't do
that.
0: 0 – 10 1: 0 – 20 2: 10 – 30 3: 15 – 50 4: 40 – 70The elementary intervals (think Venn diagram!) are:
-∞ – 0 0 – 10 10 – 15 15 – 20 20 – 30 30 – 40 40 – 50 50 – 70 70 – ∞Finally, you build a binary tree on top of the elementary ranges, and then add output range indices to both internal nodes and the leaves of that tree, necessary to prevent adversarial cases that would require too much (
O(N^2)) space. During lookup, as you walk down
the tree, you gather up the output ranges (indices) you encounter; for
our example, each elementary range is assigned the follow range
indices as outputs:
-∞ – 0 → 0 – 10 → 0 10 – 15 → 1, 2 15 – 20 → 1, 2, 3 20 – 30 → 2, 3 30 – 40 → 3 40 – 50 → 3, 4 50 – 70 → 4 70 – ∞ →Some ranges correspond to 1 elementary interval, while other ranges correspond to 2 or 3 or more, in general. Some, 2 in this example, may have no matching input ranges.
SimpleLongRangeMultiSet;
here's the recursive lookup method:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | private int lookup(Node node, long v, int[] answers, int upto) {
if (node.outputs != null) {
for(int range : node.outputs) {
answers[upto++] = range;
}
}
if (node.left != null) {
if (v <= node.left.end) {
upto = lookup(node.left, v, answers, upto);
} else {
upto = lookup(node.right, v, answers, upto);
}
}
return upto;
}
|
if statements, specialized to the specific ranges, to do the binary
search and record the range indices. Here's the resulting specialized
code, compiled from the above ranges:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | void lookup(long v, int[] answers) {
int upto = 0;
if (v <= 19) {
if (v <= 9) {
if (v >= 0) {
answers[upto++] = 0;
answers[upto++] = 1;
}
} else {
answers[upto++] = 1;
answers[upto++] = 2;
if (v >= 15) {
answers[upto++] = 3;
}
}
} else {
if (v <= 39) {
answers[upto++] = 3;
if (v <= 29) {
answers[upto++] = 2;
}
} else {
if (v <= 49) {
answers[upto++] = 3;
answers[upto++] = 4;
} else {
if (v <= 69) {
answers[upto++] = 4;
}
}
}
}
}
|
LinearLongRangeMultiSet;
as long as you don't have too many ranges (say 10 or less), its
performance is often better than the Java segment tree.
Updated drill-down, then it should be faster to use a
slightly unbalanced tree, by first checking if the value is less
than the maximum range. However, in testing, while there are some
cases where this "training" is a bit faster, often it's slower; I'm
not sure why.
O(N*log(N)) in size), which may cause other
problems. On balance I'm not sure the sizable performance gains
(on a micro-benchmark) warrant using ASM in Lucene's range faceting.
rtsp://admin:000000@<hostname>/PSIA/Streaming/channels/1.
testRTSPClient.cpp example, that seems to work
well.
example.py
Python program, that shows how to load H264 video frames from the
camera and save them to a local file. You could start from this
example and modify it to do other things, for example use the
ffmpeg H264 codec to decode
individual frames, use a motion detection library to trigger recording,
parse each frame's metadata to find the keyframes, etc. Here's the current example.py:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | import time
import sys
import live555
import threading
# Shows how to use live555 module to pull frames from an RTSP/RTP
# source. Run this (likely first customizing the URL below:
# Example: python3 example.py 10.17.4.118 1 10 out.264
if len(sys.argv) != 5:
print()
print('Usage: python3 example.py cameraIP channel seconds fileOut')
print()
sys.exit(1)
cameraIP = sys.argv[1]
channel = sys.argv[2]
seconds = float(sys.argv[3])
fileOut = sys.argv[4]
# NOTE: the username & password, and the URL path, will vary from one
# camera to another! This URL path works with the Lorex LNB2153:
url = 'rtsp://admin:000000@%s/PSIA/Streaming/channels/%s' % (cameraIP, channel)
fOut = open(fileOut, 'wb')
def oneFrame(codecName, bytes, sec, usec, durUSec):
print('frame for %s: %d bytes' % (codecName, len(bytes)))
fOut.write(b'\0\0\0\1' + bytes)
# Starts pulling frames from the URL, with the provided callback:
useTCP = False
live555.startRTSP(url, oneFrame, useTCP)
# Run Live555's event loop in a background thread:
t = threading.Thread(target=live555.runEventLoop, args=())
t.setDaemon(True)
t.start()
endTime = time.time() + seconds
while time.time() < endTime:
time.sleep(0.1)
# Tell Live555's event loop to stop:
live555.stopEventLoop()
# Wait for the background thread to finish:
t.join()
|
README.txt.
I've only tested on Linux with Python3.2 and with the Lorex LNB2151
cameras.