You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "mikemccand (via GitHub)" <gi...@apache.org> on 2023/09/07 14:09:16 UTC
[GitHub] [lucene] mikemccand opened a new issue, #12543: `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory
mikemccand opened a new issue, #12543:
URL: https://github.com/apache/lucene/issues/12543
### Description
[Spinoff from [this comment](https://github.com/apache/lucene/issues/12513#issuecomment-1710091688) 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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-1761024337
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?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-1746403380
Thanks @mikemccand ! Let's continue the discuss in this issue instead.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-1749982744
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-1748001631
I put together a PR at https://github.com/apache/lucene/pull/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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-2029834118
Looks like 9.10.0, from the `CHANGES.txt`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-2029832839
Ahh yes I will close it, and attach milestone label. Hmm which 9.x did we release this in ...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-1745049853
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-2029126851
@mikemccand I think this is done. Can we close it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand closed issue #12543: `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory
URL: https://github.com/apache/lucene/issues/12543
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-2034162204
Yeah we released in 9.10. Thank you!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-1782469977
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-1745389156
@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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] `FSTCompiler.Builder` should have an option to stream the FST bytes directly to Directory [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12543:
URL: https://github.com/apache/lucene/issues/12543#issuecomment-1744945237
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?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org