FSTCompiler.Builder should have an option to stream the FST bytes directly to Directory

[mikemccand]

Description

[Spinoff from this comment inspired by Tantivy's FST implementation]

The building of an FST is inherently streamable: the way the FST freezes states as it processes inputs is a write-once, roughly append-only operation. Today, Lucene holds this growing byte[] entirely in RAM, and once done, writes the whole thing to disk.

Yet at search time, Lucene searches the FST off-heap, doing nearly random backwards IO through IndexInput.

Let's fix Lucene to stream the FST byte[] directly to IndexOutput? This would reduce the RAM required to build so that it is constant regardless of how large an FST you are building / how many input/output pairs you are adding to it.

[mikemccand]

Copying the comment from #10520 that's really about this issue:

I'm planning to refactor the BytesStore into an interface that can be chosen from the FST builder. And one can decide whether on-heap or off-heap or on-heap without blocks is best suited.

Awesome, thanks @dungba88!

But, at write time, can we avoid BytesStore entirely, maybe? Just write to a DataOutput? But we would need to first refactor FST#addNode to not use this reverse method on BytesStore, and do its own byte[] buffering/reversal before writing? If possible, can we do this as a first step, which we test/merge before making the change to move to DataOutput?

[mikemccand]

Copying another comment from #10520:

Maybe we could first allow FSTCompiler to specify its own DataOutput even when building the tree on-the-fly, instead of always relying on BytesStore? And we are free to choose an appropriate implementation, whether off-heap, or growing byte, etc.

Ahh, yes, exactly! (Sorry, catching up and reading comments out-of-order!).

As our use case are building and using FST at runtime, there might be (some, I'm not sure) penalty we would have if we are to read/write entirely with filesystem. In some of my previous experience with Java I/O, using FileChannel would be much faster than InputStream/OutputStream when writing to filesystem, but even so they are still slower than main memory.

Well, Lucene's DataOutput abstraction can be backed by heap too, e.g. ByteBufferDataOutput or ByteArrayDataOutput (there may be others!). An application could even easily make its own "double the byte[]" to grow custom DataOutput.

I'm curious if Lucene also has a benchmark for comparison of off-heap and heap mode? (Also by off-heap, I assume you mean filesystem, instead of the direct memory, e.g with ByteBuffer.allocateDirect()?)

I think in the original issue that introduced off-heap FST reading, luceneutil benchmarks were run? Not certain though. I don't know of other benchys.

[mikemccand]

@dungba88 raised a good point -- FST construction also needs to read prior bytes it wrote even as it is appending new bytes to the end of the file.

Lucene's IndexInput/Output don't support this usage ... so that's a wrinkle we'd need to somehow overcome to have true off-heap writing.

[dungba88]

Thanks @mikemccand ! Let's continue the discuss in this issue instead.

[dungba88]

I put together a PR at #12624.

I also verified with a custom dictionary (~1MB in size) that position does not go backward to previously written input, so I think it would not be a problem to create a new FSTWriter that flush to disk on every add and only use the in-mem buffer for processing the current input. That is assuming we have shouldShareSuffix set to false.

[dungba88]

One of the thing I think is missing is that those byte manipulation methods should not be called after calling #finish(), but currently there is no such enforcement.

[dungba88]

Copied from the PR:

It seems Tantivy segregate the building and the traverse of FST as 2 different entity. The FST Builder will just write the FST to a DataOutput and not allow it to be read directly. I was thinking of this too, as currently we are mixing up the writing and reading:

• Load a previously saved FST from a DataInput. This is read-only and is fine, and it's how Tantivy FST is created as well.
• Construct a FST on-the-fly and use it right away. This is both read & write and it uses BytesStore.

I'm kind of favoring the way Tantivy is doing, it's cleaner and more "facade pattern". Maybe we could create an experimental FST Builder, that only save the FST into DataOutput?

For suffix sharing, Tantivy seems to use LRU cache in write-through mode: write the new node to both the DataOutput and the cache, and read from there. It will not result in a perfectly minimal FST though.

[dungba88]

I put a new revision with support for DataOutput and FileChannel.

When using DataOutput, if suffix sharing is enabled one also needs to pass a RandomAccessInput for reading. Otherwise it can be left null. So one can pass a IndexOutput, and RandomAccessInput can be created from IndexInput.

When using FileChannel, one only needs to pass the FileChannel as that already allows both read & write at the same time. This FileChannel implementation is just for demonstration of feasibility.

Some stuffs I'd like to discuss:

• Should we write the rootNode + numBytes to the end of the FST instead of the front? We only have them after constructing the FST and we can't prepend a DataOutput (that's costly). Otherwise we would need to save the metadata separately from the main body. That's why I added a new method saveMetadata()
• Should we move to value-based LRU cache? It has pros and cons:
  • Pros: We make NodeHash independent of FST completely. It would allow the suffix sharing without the need of RandomAccessInput, and thus without the need for IndexOutput & IndexInput to be open at the same time. Also accessing from RAM is much faster than accessing from disk.
  • Cons: More RAM required than the address-based cache. For truly minimal FST it would require the same (or more) RAM needed for the entire FST.

[dungba88]

@mikemccand I think this is done. Can we close it.

[mikemccand]

Ahh yes I will close it, and attach milestone label. Hmm which 9.x did we release this in ...

[mikemccand]

Looks like 9.10.0, from the CHANGES.txt.

[dungba88]

Yeah we released in 9.10. Thank you!