[jira] Created: (LUCENE-2575) Concurrent byte and int block implementations

classic Classic list List threaded Threaded
51 messages Options
123
Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12913403#action_12913403 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

A further question for this issue, in regards to copy-on-write
of the 1st dimension of the byte[][] array, will we want to keep
a count of references to the byte array, in the case of, lets
say multiple readers keeping references to each individual byte
array (the one with the bytes data). Assuming we will want to
continue to pool the byte[]s, I think we'll need to use
reference counting, or simply not pool the byte[]s after
flushing, in order to avoid overwriting of arrays.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12913597#action_12913597 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

The reference counting described above is a common pattern throughout Lucene, one similarly used place is IR reopen and clone.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914607#action_12914607 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

The current MultiLevelSkipList* system relies on writing out
fixed length skip list buffers before they are readable. This
obviously will not work for RT so I'm working on modifying MLSL
into new class(es) that writes and reads from the concurrent-ish
BBP.

In trunk, each level is a RAMOutputStream, that'll nee to
changechange, and each level will likely be a stream keyed into
the BBP. A question is whether we will statically assign the
number of levels prior to the creation of the MLSL, or will we
need to somehow make the number of levels dynamic, in which case
using streams becomes slightly more complicated.



> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Issue Comment Edited: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914607#action_12914607 ]

Jason Rutherglen edited comment on LUCENE-2575 at 9/24/10 3:28 PM:
-------------------------------------------------------------------

The current MultiLevelSkipList* system relies on writing out
fixed length skip list buffers before they are readable. This
obviously will not work for RT so I'm working on modifying MLSL
into new class(es) that writes and reads from the concurrent-ish
BBP.

In trunk, each level is a RAMOutputStream, that'll need to
change, and each level will likely be a stream keyed into
the BBP. A question is whether we will statically assign the
number of levels prior to the creation of the MLSL, or will we
need to somehow make the number of levels dynamic, in which case
using streams becomes slightly more complicated.



      was (Author: jasonrutherglen):
    The current MultiLevelSkipList* system relies on writing out
fixed length skip list buffers before they are readable. This
obviously will not work for RT so I'm working on modifying MLSL
into new class(es) that writes and reads from the concurrent-ish
BBP.

In trunk, each level is a RAMOutputStream, that'll nee to
changechange, and each level will likely be a stream keyed into
the BBP. A question is whether we will statically assign the
number of levels prior to the creation of the MLSL, or will we
need to somehow make the number of levels dynamic, in which case
using streams becomes slightly more complicated.


 

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914624#action_12914624 ]

Michael McCandless commented on LUCENE-2575:
--------------------------------------------

Maybe we can get an initial version of this working, without the skipping?  Ie skipping is implemented as scanning.

My guess is for in-RAM postings we don't need as aggressive skipping as we do on-disk, and it's possible single level skipping, with a larger skip interval, is fine for even large RAM buffers.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914626#action_12914626 ]

Michael McCandless commented on LUCENE-2575:
--------------------------------------------

{quote}
I think we'll need to use
reference counting, or simply not pool the byte[]s after
flushing, in order to avoid overwriting of arrays.
{quote}

Can we just have IW allocate a new byte[][] after flush?  So then any open readers can keep using the one they have?

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914630#action_12914630 ]

Michael McCandless commented on LUCENE-2575:
--------------------------------------------

bq. This issue is blocked because the change made to ByteBlockPool to add the level of the slice, to the beginning of the slice, moves all of the positions forward by one.

Hmm so does this waste that byte?  Ie when the next slice is allocated, today, we overwrite the level byte w/ the 4 bytes forwarding address.  Ie the level byte is only needed when the slice isn't full yet.

But if you move the level byte to the start, does that mean it's never re-used?

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914631#action_12914631 ]

Michael McCandless commented on LUCENE-2575:
--------------------------------------------

Since we now have parallel arrays, we could also store the level byte in a separate parallel array, ie outside of the pool?

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914634#action_12914634 ]

Michael McCandless commented on LUCENE-2575:
--------------------------------------------

Maybe we can not skip until we've hit the max slice?  This way skipping would always know it's on the max slice.  This works out to 429 bytes into the stream... likely this is fine.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914684#action_12914684 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

{quote}Maybe we can not skip until we've hit the max slice? This
way skipping would always know it's on the max slice. This works
out to 429 bytes into the stream... likely this is fine. {quote}

Me like-y. I'll implement the skip list to point to the largest
level slices.

{quote}Can we just have IW allocate a new byte[][] after flush?
So then any open readers can keep using the one they have?{quote}

This means the prior byte[]s will still be recycled after all
active previous flush readers are closed? If there are multiple
readers from the previous flush, we'd probably still need
reference counting (ala bitvector and norms)? Unfortunately a
reference count parallel array will not quite work because we're
copy-on-writing the byte[]s, eg, there's nothing consistent for
the index numeral to point to. A hash map of byte[]s would
likely be too heavyweight? We may need to implement a ByteArray
object composed of a byte[] and a refcount. This is somewhat
counter to our parallel array memory savings strategy, though it
is directly analogous to the way norms are implemented in
SegmentReader.

{quote}it's possible single level skipping, with a larger skip
interval, is fine for even large RAM buffers.{quote}

True, I'll implement a default of one level, and a default
large-ish skip interval.

{quote}Maybe we can get an initial version of this working,
without the skipping? Ie skipping is implemented as scanning.
{quote}

How many scorers, or how often is skipping used? It's mostly for
disjunction queries? If we limit the skip level to one, and not
implement the BBP level byte at the beginning of the slice, the
MLSL will be a lot easier (ie faster) to implement and test.

I'd like to see BytesHash get out of THPF (eg, LUCENE-2662), get
deletes working in the RT branch, and merge the flush by DWPT to
trunk. Concurrently I'll work on the search on the RAM buffer
which is most of the way completed. I'd prefer to test a more
complete version of LUCENE-2312 with skip lists (which can
easily be turned off), so that when we do take it through the
laundromat of testing, we won't need to retrofit anything back
in, re-test, and possibly re-design.

On a side note related to testing: One naive way I've tested is
to do the copy-on-write of the BBP when the segment needs to be
flushed to disk, and write the segment from the read-only copy
of the BBP. If the segment is correct, then at least we know the
copy worked properly and nothing's missing.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914802#action_12914802 ]

Michael McCandless commented on LUCENE-2575:
--------------------------------------------

{quote}
bq. Can we just have IW allocate a new byte[][] after flush?  So then any open readers can keep using the one they have?

This means the prior byte[]s will still be recycled after all
active previous flush readers are closed?
{quote}

Probably we should stop reusing the byte[] with this change?  So when all readers using a given byte[] are finally GCd, is when that byte[] is reclaimed.

{quote}
bq. it's possible single level skipping, with a larger skip interval, is fine for even large RAM buffers.

True, I'll implement a default of one level, and a default
large-ish skip interval.
{quote}

Well, I was thinking only implement the single-level skip case (since it ought to be alot simpler than the MLSLW/R)....

{quote}
How many scorers, or how often is skipping used? It's mostly for
disjunction queries?
{quote}

Actually, conjunction (AND) queries, and also PhraseQuery (which is really an AND query followed by positions checking).  One thing to remember is that skipping is *costly* (especially, the first time you use it) -- I think we over-use it today, ie, in many cases we should do a spin loop (.next()) instead, if your target "is not that far away".  PhraseQuery (the exact case) has a heuristic to do this, but really this ought to be implemented in the codec.

bq. get deletes working in the RT branch,

Do we have a design thought out for this?  The challenge is because every doc state now has its own private docID stream, we need a global sequence ID to track "when" a deletion arrived, to know whether or not that deletion applies to each docID, right?  (And, each added doc must also record the sequenceID when it was added).


> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914803#action_12914803 ]

Michael McCandless commented on LUCENE-2575:
--------------------------------------------

Can you explain what's the "copy on write ByteBlockPool"?  Exactly when do we make a copy....?

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914838#action_12914838 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

{quote}Can you explain what's the "copy on write ByteBlockPool"?
Exactly when do we make a copy....? {quote}

A copy of the byte[][] refs is made when getReader is called.
Each DWPT is locked, eg, writes stop, a copy of the byte[][] is
made (just the refs) for that reader. I think the issue at the
moment is I'm using a boolean[] to signify if a byte[] needs to
be copied before being written to. As with BV and norms cloning,
read-only references are carried forward, which would imply
making copies of the boolean[] as well. In other words, as with
BV and norms, I think we need ref counts to the individual
byte[]s so that read-only references to byte[]s are carried
forward properly. However this implies creating a BytesRefCount
object because a parallel array cannot point back to the same
underlying byte[] if the byte[] in the byte[][] can be replaced
when a copy is made.

{quote}Do we have a design thought out for this? The challenge
is because every doc state now has its own private docID
stream{quote}

It sounded easy when I first heard it, however, I needed to
write it down to fully understand and work through what's going
on. That process is located in LUCENE-2558.

{quote}Well, I was thinking only implement the single-level skip
case (since it ought to be alot simpler than the
MLSLW/R)....{quote}

I started on this, eg, implementing a single-level skip list
that reads and writes from the BBP. It's a good lesson in how to
use the BBP.

{quote}Actually, conjunction (AND) queries, and also
PhraseQuery{quote}

Both very common types of queries, so we probably need some type
of skipping, which we will, it'll just be single-level.

{quote}Probably we should stop reusing the byte[] with this
change? So when all readers using a given byte[] are finally
GCd, is when that byte[] is reclaimed.{quote}

I have a suspicion we'll change our minds about pooling byte[]s.
We may end up implementing ref counting anyways (as described
above), and the sudden garbage generated *could* be a massive
change for users? Of course ref counting was difficult to
implement the first time around in LUCENE-1314, perhaps however
it'll be easier the 2nd time.

As a side note, there is still an issue in my mind around the
term frequencies parallel array (introduced in these patches),
in that we'd need to make a copy of it for each reader (because
if it changes, the scoring model becomes inaccurate?). However,
we could in fact use a 2 dimensional PagedBytes (in this case,
PagesInts) for this purpose. Or is the garbage of an int[] the
size of the number of docs OK per reader? There is also the
lookup cost to consider.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914860#action_12914860 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

Further thoughts on ref counting the byte[]s.  If we add a BytesRefCount (or some other similarly named class that I want to call BytesRef, though I can't use because that's taken), then I think adding 4 bytes for the int count variable, 8 bytes for the byte[] pointer, is 12 bytes total added to a 32k (ie, 32768 len) byte[] really too much?  I don't think so.  

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914863#action_12914863 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

In regards to the performance effects on writes of obtaining the reader from each DWPT, there should not be any, because it is the thread calling getReader that will wait for the lock on the DWPT in between doc adds.  The copy-on-write is it's most primitive form, is a copy of object references, eg, the cost is extremely low.  And so I do not think indexing performance will be affected whatsoever by the copy-on-write approach.  Of course we'll need to benchmark to verify.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12914902#action_12914902 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

The RAM buffer single-level skip list writer probably requires two additional parallel arrays.  One for the beginning address into the skip list BBP.  The second for the address upto, where the last skip list entry that was written left off.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12915130#action_12915130 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

Here are the new parallel arrays.  It seems like something went wrong and there are too many, however I think each is required.

{code}
final int[] skipStarts; // address where the term's skip list starts (for reading)
final int[] skipAddrs; // where writing left off
final int[] sliceAddrs; // the start addr of the last posting slice
final byte[] sliceLevels; // posting slice levels
final int[] skipLastDoc; // last skip doc written
final int[] skipLastAddr; // last skip addr written
{code}

In regards to writing into the skip list the start address of
the first level 9 posting slice: Because we're writing vints
into the posting slices, and vints may span more than 1 byte, we
may (and this has happened in testing) write a vint that spans
slices, so if we record the last slice address and read a vint
from that point, we'll get an incorrect vint. If we start 1+
bytes into a slice, we will not know where the slice ends
(because we are assuming they're 200 bytes in length). Perhaps
in the slice address parallel array we can somehow encode the
first slice's length, or add yet another parallel array for the
length of the first slice.  Something to think about.

We can't simply read
ahead 200 bytes (ie, level 9), nor can

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Issue Comment Edited: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12915130#action_12915130 ]

Jason Rutherglen edited comment on LUCENE-2575 at 9/27/10 1:44 AM:
-------------------------------------------------------------------

Here are the new parallel arrays.  It seems like something went wrong and there are too many, however I think each is required.

{code}
final int[] skipStarts; // address where the term's skip list starts (for reading)
final int[] skipAddrs; // where writing left off
final int[] sliceAddrs; // the start addr of the last posting slice
final byte[] sliceLevels; // posting slice levels
final int[] skipLastDoc; // last skip doc written
final int[] skipLastAddr; // last skip addr written
{code}

In regards to writing into the skip list the start address of
the first level 9 posting slice: Because we're writing vints
into the posting slices, and vints may span more than 1 byte, we
may (and this has happened in testing) write a vint that spans
slices, so if we record the last slice address and read a vint
from that point, we'll get an incorrect vint. If we start 1+
bytes into a slice, we will not know where the slice ends
(because we are assuming they're 200 bytes in length). Perhaps
in the slice address parallel array we can somehow encode the
first slice's length, or add yet another parallel array for the
length of the first slice.  Something to think about.

      was (Author: jasonrutherglen):
    Here are the new parallel arrays.  It seems like something went wrong and there are too many, however I think each is required.

{code}
final int[] skipStarts; // address where the term's skip list starts (for reading)
final int[] skipAddrs; // where writing left off
final int[] sliceAddrs; // the start addr of the last posting slice
final byte[] sliceLevels; // posting slice levels
final int[] skipLastDoc; // last skip doc written
final int[] skipLastAddr; // last skip addr written
{code}

In regards to writing into the skip list the start address of
the first level 9 posting slice: Because we're writing vints
into the posting slices, and vints may span more than 1 byte, we
may (and this has happened in testing) write a vint that spans
slices, so if we record the last slice address and read a vint
from that point, we'll get an incorrect vint. If we start 1+
bytes into a slice, we will not know where the slice ends
(because we are assuming they're 200 bytes in length). Perhaps
in the slice address parallel array we can somehow encode the
first slice's length, or add yet another parallel array for the
length of the first slice.  Something to think about.

We can't simply read
ahead 200 bytes (ie, level 9), nor can
 

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12915137#action_12915137 ]

Jason Rutherglen commented on LUCENE-2575:
------------------------------------------

There's a little error in thinking of the last comment.  Also, the best solution is probably to store the length of the posting slice into the skip list byte pool.  This'll mean a slight modification to byte slice reader, however I think it'll work.

> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (LUCENE-2575) Concurrent byte and int block implementations

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/LUCENE-2575?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12915685#action_12915685 ]

Michael McCandless commented on LUCENE-2575:
--------------------------------------------

bq. A copy of the byte[][] refs is made when getReader is called.

Hmm why can't the reader just use the current byte[][]?  The writer only adds in new blocks to this array (doesn't overwrite the already written blocks, until flush)?  (And then allocates a new byte[][] once that array is full).

{quote}
I think the issue at the
moment is I'm using a boolean[] to signify if a byte[] needs to
be copied before being written to
{quote}
Hmm so we also copy-on-write a given byte[] block?  Is this because JMM can't make the guarantees we need about other threads reading the bytes written?

{quote}
I have a suspicion we'll change our minds about pooling byte[]s.
We may end up implementing ref counting anyways (as described
above), and the sudden garbage generated could be a massive
change for users?
{quote}

But even if we do reuse, we will cause tons of garbage, until the still-open readers are closed?  Ie we cannot re-use the byte[] being "held open" by any NRT reader that's still referencing the in-RAM segment after that segment had been flushed to disk.

Also the garbage shouldn't be that bad since each object is large.  It's not like 3.x's situation with FieldCache or terms dict index, for example....

I would start simple by dropping reuse.  We can then add it back if we see perf issues?

{quote}
Both very common types of queries, so we probably need some type
of skipping, which we will, it'll just be single-level.
{quote}
I would start simple, here, and make skipping stupid, ie just scan.  You can get everything working, all tests passing, etc., and then adding in skipping is much more isolated change.  You need all the isolation you can get here!  This stuff is *hairy*.

{quote}
As a side note, there is still an issue in my mind around the
term frequencies parallel array (introduced in these patches),
in that we'd need to make a copy of it for each reader (because
if it changes, the scoring model becomes inaccurate?).
{quote}

Hmm your'e right that each reader needs a private copy, to remain truly "point in time".  This (4 bytes per unique term X number of readers reading that term) is a non-trivial addition of RAM.

BTW I'm assuming IW will now be modal?  Ie caller must tell IW up front if NRT readers will be used?  Because non-NRT users shouldn't have to pay all this added RAM cost?


> Concurrent byte and int block implementations
> ---------------------------------------------
>
>                 Key: LUCENE-2575
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2575
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>    Affects Versions: Realtime Branch
>            Reporter: Jason Rutherglen
>             Fix For: Realtime Branch
>
>         Attachments: LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch, LUCENE-2575.patch
>
>
> The current *BlockPool implementations aren't quite concurrent.
> We really need something that has a locking flush method, where
> flush is called at the end of adding a document. Once flushed,
> the newly written data would be available to all other reading
> threads (ie, postings etc). I'm not sure I understand the slices
> concept, it seems like it'd be easier to implement a seekable
> random access file like API. One'd seek to a given position,
> then read or write from there. The underlying management of byte
> arrays could then be hidden?

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

123