Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 2.1
    • Fix Version/s: 2.1
    • Component/s: core/index
    • Labels:
      None
    • Lucene Fields:
      Patch Available

      Description

      This is a patch based on discussion a while back on lucene-dev:

      http://mail-archives.apache.org/mod_mbox/lucene-java-dev/200608.mbox/%3c44E5B16D.4010805@mikemccandless.com%3e

      The approach is a small modification over the original discussion (see
      Retry Logic below). It works correctly in all my cross-machine test
      case, but I want to open it up for feedback, testing by
      users/developers in more diverse environments, etc.

      This is a small change to how lucene stores its index that enables
      elimination of the commit lock entirely. The write lock still
      remains.

      Of the two, the commit lock has been more troublesome for users since
      it typically serves an active role in production. Whereas the write
      lock is usually more of a design check to make sure you only have one
      writer against the index at a time.

      The basic idea is that filenames are never reused ("write once"),
      meaning, a writer never writes to a file that a reader may be reading
      (there is one exception: the segments.gen file; see "RETRY LOGIC"
      below). Instead it writes to generational files, ie, segments_1, then
      segments_2, etc. Besides the segments file, the .del files and norm
      files (.sX suffix) are also now generational. A generation is stored
      as an "_N" suffix before the file extension (eg, _p_4.s0 is the
      separate norms file for segment "p", generation 4).

      One important benefit of this is it avoids files contents caching
      entirely (the likely cause of errors when readers open an index
      mounted on NFS) since the file is always a new file.

      With this patch I can reliably instantiate readers over NFS when a
      writer is writing to the index. However, with NFS, you are still forced to
      refresh your reader once a writer has committed because "point in
      time" searching doesn't work over NFS (see LUCENE-673 ).

      The changes are fully backwards compatible: you can open an old index
      for searching, or to add/delete docs, etc. I've added a new unit test
      to test these cases.

      All units test pass, and I've added a number of additional unit tests,
      some of which fail on WIN32 in the current lucene but pass with this
      patch. The "fileformats.xml" has been updated to describe the changes
      to the files (but XXX references need to be fixed before committing).

      There are some other important benefits:

      • Readers are now entirely read-only.
      • Readers no longer block one another (false contention) on
        initialization.
      • On hitting contention, we immediately retry instead of a fixed
        (default 1.0 second now) pause.
      • No file renaming is ever done. File renaming has caused sneaky
        access denied errors on WIN32 (see LUCENE-665 ). (Yonik, I used
        your approach here to not rename the segments_N file(try
        segments_(N-1) on hitting IOException on segments_N): the separate
        ".done" file did not work reliably under very high stress testing
        when a directory listing was not "point in time").
      • On WIN32, you can now call IndexReader.setNorm() even if other
        readers have the index open (fixes a pre-existing minor bug in
        Lucene).
      • On WIN32, You can now create an IndexWriter with create=true even
        if readers have the index open (eg see
        www.gossamer-threads.com/lists/lucene/java-user/39265) .

      Here's an overview of the changes:

      • Every commit writes to the next segments_(N+1).
      • Loading the segments_N file (& opening the segments) now requires
        retry logic. I've captured this logic into a new static class:
        SegmentInfos.FindSegmentsFile. All places that need to do
        something on the current segments file now use this class.
      • No more deletable file. Instead, the writer computes what's
        deletable on instantiation and updates this in memory whenever
        files can be deleted (ie, when it commits). Created a common
        class index.IndexFileDeleter shared by reader & writer, to manage
        deletes.
      • Storing more information into segments info file: whether it has
        separate deletes (and which generation), whether it has separate
        norms, per field (and which generation), whether it's compound or
        not. This is instead of relying on IO operations (file exists
        calls). Note that this fixes the current misleading
        FileNotFoundException users now see when an _X.cfs file is missing
        (eg http://www.nabble.com/FileNotFound-Exception-t6987.html).
      • Fixed some small things about RAMDirectory that were not
        filesystem-like (eg opening a non-existent IndexInput failed to
        raise IOException; renames were not atomic). I added a stress
        test against a RAMDirectory (1 writer thread & 2 reader threads)
        that uncovered these.
      • Added option to not remove old files when create=true on creating
        FSDirectory; this is so the writer can do its own [more
        sophisticated because it retries on errors] removal.
      • Removed all references to commit lock, COMMIT_LOCK_TIMEOUT, etc.
        (This is an API change).
      • Extended index/IndexFileNames.java and index/IndexFileNameFilter.java
        with logic for computing generational file names.
      • Changed index/IndexFileNameFilter.java to use a HashSet to check
        file extentsions for better performance.
      • Fixed the test case TestIndexReader.testLastModified: it was
        incorrectly (I think?) comparing lastModified to version, of the
        index. I fixed that and then added a new test case for version.

      Retry Logic (in index/SegmentInfos.java)

      If a reader tries to load the segments just as a writer is committing,
      it may hit an IOException. This is just normal contention. In
      current Lucene contention causes a [default] 1.0 second pause then
      retry. With lock-less the contention causes no added delay beyond the
      time to retry.

      When this happens, we first try segments_(N-1) if present, because it
      could be segments_N is still being written. If that fails, we
      re-check to see if there is now a newer segments_M where M > N and
      advance if so. Else we retry segments_N once more (since it could be
      it was in process previously but must now be complete since
      segments_(N-1) did not load).

      In order to find the current segments_N file, I list the directory and
      take the biggest segments_N that exists.

      However, under extreme stress testing (5 threads just opening &
      closing readers over and over), on one platform (OS X) I found that
      the directory listing can be incorrect (stale) by up to 1.0 seconds.
      This means the listing will show a segments_N file but that file does
      not exist (fileExists() returns false).

      In order to handle this (and other such platforms), I switched to a
      hybrid approach (originally proposed by Doron Cohen in the original
      thread): on committing, the writer writes to a file "segments.gen" the
      generation it just committed. It writes 2 identical longs into this
      file. The retry logic, on detecting that the directory listing is
      stale falls back to the contents of this file. If that file is
      consistent (the two longs are identical), and, the generation is
      indeed newer than the dir listing, it will use that.

      Finally, if this approach is also stale, we fallback to stepping
      through sequential generations (up to a maximum # tries). If all 3
      methods fail, we throw the original exception we hit.

      I added a static method SegmentInfos.setInfoStream() which will print
      details of retry attempts. In the patch it's set to System.out right
      now (we should turn off before a real commit) so if there are problems
      we can see what retry logic had done.

      1. lockless-commits-patch2.txt
        113 kB
        Michael McCandless
      2. lockless-commits-patch.txt
        124 kB
        Michael McCandless
      3. index.prelockless.nocfs.zip
        11 kB
        Michael McCandless
      4. index.prelockless.cfs.zip
        4 kB
        Michael McCandless

        Activity

        Hide
        Michael McCandless added a comment -

        Closing all issues that were resolved for 2.1.

        Show
        Michael McCandless added a comment - Closing all issues that were resolved for 2.1.
        Hide
        Michael McCandless added a comment -

        Oooh – I would love to!

        Show
        Michael McCandless added a comment - Oooh – I would love to!
        Hide
        Otis Gospodnetic added a comment -

        Steven - I don't see any issues with this going in before 2.1. As a matter of fact, this may be a sufficiently substantial change that will make us want to make a 2.1 release.

        Maybe Michael should commit this next week.

        Show
        Otis Gospodnetic added a comment - Steven - I don't see any issues with this going in before 2.1. As a matter of fact, this may be a sufficiently substantial change that will make us want to make a 2.1 release. Maybe Michael should commit this next week.
        Hide
        Steven Parkes added a comment -

        I'm all for the patch ... the only thing I'm wondering is about release timing, if that's issue? This changes the on-disk format, which affects more than Lucene Java and, should anyone that's using Lucene out there care (via scripts, etc.), the naming of files on disk.

        I'm just wondering if there's any interest/reason for doing a 2.1 before something with those side effects?

        Show
        Steven Parkes added a comment - I'm all for the patch ... the only thing I'm wondering is about release timing, if that's issue? This changes the on-disk format, which affects more than Lucene Java and, should anyone that's using Lucene out there care (via scripts, etc.), the naming of files on disk. I'm just wondering if there's any interest/reason for doing a 2.1 before something with those side effects?
        Hide
        Yonik Seeley added a comment -

        Looks good Michael, I think this is ready to commit!
        Does anyone have any concerns with this going into the trunk?

        Show
        Yonik Seeley added a comment - Looks good Michael, I think this is ready to commit! Does anyone have any concerns with this going into the trunk?
        Hide
        Michael McCandless added a comment -

        OK, another version of the lockless commits patch with these fixes:

        • Added new unit test (TestIndexFileDeleter) for deleter, caught the
          above bug Yonik found (we can fail to delete orphan'd separate
          del/norm files), fixed it, and unit test now passes.
        • We were also failing to deleted orphan'd .fN files (norm files
          that do get included into CFS file). Fixed that case too.
        • Added version header to segments.gen file.
        • Added static setter/getters for advanced configuration of the
          retry logic. Note: this required making the SegmentInfos class
          public.

        You still need to put those two zip files into
        src/test/org/apache/lucene/index after applying this patch.

        This addresses all feedback/TODOs that I knew about.

        All unit tests pass.

        Show
        Michael McCandless added a comment - OK, another version of the lockless commits patch with these fixes: Added new unit test (TestIndexFileDeleter) for deleter, caught the above bug Yonik found (we can fail to delete orphan'd separate del/norm files), fixed it, and unit test now passes. We were also failing to deleted orphan'd .fN files (norm files that do get included into CFS file). Fixed that case too. Added version header to segments.gen file. Added static setter/getters for advanced configuration of the retry logic. Note: this required making the SegmentInfos class public. You still need to put those two zip files into src/test/org/apache/lucene/index after applying this patch. This addresses all feedback/TODOs that I knew about. All unit tests pass.
        Hide
        Michael McCandless added a comment -

        > > In the future, it might be nice if there was an option to disable
        > > segments.gen to be more friendly to write-once filesystems like
        > > HDFS.
        > I think this makes sense. I will add control over this on the next
        > iteration of the patch.

        > Just to be clear, I didn't mean that I thought it was needed now...
        > there is another place in Lucene that prevents write-once from
        > working (segment file lengths at the beginning IIRC).

        > When this option is added, perhaps the configuration name should be
        > generic and not tied to the implementation specifics that could change
        > more frequently? Something like WRITE_ONCE or setWriteOnce()?

        OK, I see, this is part of a wider context. Maybe it's the creation
        of the compound file you're thinking of? That writes 0's into the
        header, adds the files, then rewinds and puts the actual offsets into
        it. Then let's open a separate issue to track this – I'll do that.
        Don't want to make this patch any bigger!

        Show
        Michael McCandless added a comment - > > In the future, it might be nice if there was an option to disable > > segments.gen to be more friendly to write-once filesystems like > > HDFS. > I think this makes sense. I will add control over this on the next > iteration of the patch. > Just to be clear, I didn't mean that I thought it was needed now... > there is another place in Lucene that prevents write-once from > working (segment file lengths at the beginning IIRC). > When this option is added, perhaps the configuration name should be > generic and not tied to the implementation specifics that could change > more frequently? Something like WRITE_ONCE or setWriteOnce()? OK, I see, this is part of a wider context. Maybe it's the creation of the compound file you're thinking of? That writes 0's into the header, adds the files, then rewinds and puts the actual offsets into it. Then let's open a separate issue to track this – I'll do that. Don't want to make this patch any bigger!
        Hide
        Michael McCandless added a comment -

        Right, this is just normal contention. We do indeed retry around not
        only loading of segments_N but also the loading of the individual
        segments files. There are other places (eg lastModified()) that do
        other things with the segments file. These places also use the retry
        logic.

        In Lucene currently, contention causes a pause (default 1.0 second)
        and then retry to obtain the commit lock. With lockless, we simply
        retry immediately loading the latest segments_N file.

        It's important to note that at any given instant, the index is always
        "consistent" (well, except for issues like LUCENE-702 ).

        But, because a reader takes non-zero time to load the index, you can
        hit contention if a writer's commit spans that time. If a reader
        could load an index in zero time there would never be contention.

        There are several ways that contention will manifest itself. These
        are just the different alignments / convolutions of the series of
        steps that reader goes through "sliding against" the series of steps
        that a writer goes through:

        • Reader opens the segments_N but in reading it hits EOF because
          writer has not finished writing it yet.
        • Reader opens segments_N, fully reads its contents, but then hits
          IOException on loading each segment file because during this team
          writer has committed and is now deleting segments files. This
          case is your example above.
        • Reader opens segments_N, but hits IOException while reading its
          contents because it was deleted by writer before reader could read
          all of its contents (should only happen on fileystems that don't
          do "delete on last close" or "can't delete open files").
        • Reader takes listing of directory, locates segments_N, but fails
          to open that file because writer has now removed it.

        Anyway, on hitting an IOException, we first retry segments_N-1 (if it
        exists). Failing that we recheck the directory for latest segments_N.
        If N has advanced we try that. If N has not advanced we give it one
        more chance to load (since it could be on first try we hit case 1
        above). If it fails that second chance and on re-listing we are still
        at N, we throw the original exception we hit.

        I added a couple of tests cases to TestIndexWriter to verify that a
        messed up index indeed throws an IOException.

        On Yonik's question:

        > Then a question might be, could a writer possibly change the index
        > fast enough to prevent a reader from opening at all? I don't think
        > so (and it would be a mis-configured writer IMO), but maybe Michael
        > could speak to that.

        This is definitely possible. This really is a form of "starvation".
        If a writer is committing too fast, or, readers are constantly
        re-opening too fast, they will starve one another.

        Both current Lucene and lockless will hit starvation under high enough
        rate of commit/opens, but, different things happen. EG LUCENE-307
        issue is exactly this case on the current Lucene. Lockless will retry
        indefinitely though may at some point succeed (but take many
        retries to do so).

        Still, I think the point at which starvation starts to happen is far
        beyond a normal usage of Lucene (ie, committing > ten times / sec).

        Show
        Michael McCandless added a comment - Right, this is just normal contention. We do indeed retry around not only loading of segments_N but also the loading of the individual segments files. There are other places (eg lastModified()) that do other things with the segments file. These places also use the retry logic. In Lucene currently, contention causes a pause (default 1.0 second) and then retry to obtain the commit lock. With lockless, we simply retry immediately loading the latest segments_N file. It's important to note that at any given instant, the index is always "consistent" (well, except for issues like LUCENE-702 ). But, because a reader takes non-zero time to load the index, you can hit contention if a writer's commit spans that time. If a reader could load an index in zero time there would never be contention. There are several ways that contention will manifest itself. These are just the different alignments / convolutions of the series of steps that reader goes through "sliding against" the series of steps that a writer goes through: Reader opens the segments_N but in reading it hits EOF because writer has not finished writing it yet. Reader opens segments_N, fully reads its contents, but then hits IOException on loading each segment file because during this team writer has committed and is now deleting segments files. This case is your example above. Reader opens segments_N, but hits IOException while reading its contents because it was deleted by writer before reader could read all of its contents (should only happen on fileystems that don't do "delete on last close" or "can't delete open files"). Reader takes listing of directory, locates segments_N, but fails to open that file because writer has now removed it. Anyway, on hitting an IOException, we first retry segments_N-1 (if it exists). Failing that we recheck the directory for latest segments_N. If N has advanced we try that. If N has not advanced we give it one more chance to load (since it could be on first try we hit case 1 above). If it fails that second chance and on re-listing we are still at N, we throw the original exception we hit. I added a couple of tests cases to TestIndexWriter to verify that a messed up index indeed throws an IOException. On Yonik's question: > Then a question might be, could a writer possibly change the index > fast enough to prevent a reader from opening at all? I don't think > so (and it would be a mis-configured writer IMO), but maybe Michael > could speak to that. This is definitely possible. This really is a form of "starvation". If a writer is committing too fast, or, readers are constantly re-opening too fast, they will starve one another. Both current Lucene and lockless will hit starvation under high enough rate of commit/opens, but, different things happen. EG LUCENE-307 issue is exactly this case on the current Lucene. Lockless will retry indefinitely though may at some point succeed (but take many retries to do so). Still, I think the point at which starvation starts to happen is far beyond a normal usage of Lucene (ie, committing > ten times / sec).
        Hide
        Yonik Seeley added a comment -

        > > In the future, it might be nice if there was an option to disable
        > > segments.gen to be more friendly to write-once filesystems like
        > > HDFS.
        > I think this makes sense. I will add control over this on the next
        > iteration of the patch.

        Just to be clear, I didn't mean that I thought it was needed now...
        there is another place in Lucene that prevents write-once from working (segment file lengths at the beginning IIRC).

        When this option is added, perhaps the configuration name should be generic and not tied to the implementation specifics that could change more frequently? Something like WRITE_ONCE or setWriteOnce()?

        Show
        Yonik Seeley added a comment - > > In the future, it might be nice if there was an option to disable > > segments.gen to be more friendly to write-once filesystems like > > HDFS. > I think this makes sense. I will add control over this on the next > iteration of the patch. Just to be clear, I didn't mean that I thought it was needed now... there is another place in Lucene that prevents write-once from working (segment file lengths at the beginning IIRC). When this option is added, perhaps the configuration name should be generic and not tied to the implementation specifics that could change more frequently? Something like WRITE_ONCE or setWriteOnce()?
        Hide
        Ning Li added a comment -

        > That wouldn't be considered a failure because it's part of the retry logic. At that point, an attempt would be made to open seg_2.

        From the description of the retry logic, I thought the retry logic only applies to the loading of the "segments_N" file, but not to the entire process of loading all the files of an index.

        You are right, it wouldn't be a failure if the retry logic is applied to the loading of all the files of an index.

        Show
        Ning Li added a comment - > That wouldn't be considered a failure because it's part of the retry logic. At that point, an attempt would be made to open seg_2. From the description of the retry logic, I thought the retry logic only applies to the loading of the "segments_N" file, but not to the entire process of loading all the files of an index. You are right, it wouldn't be a failure if the retry logic is applied to the loading of all the files of an index.
        Hide
        Yonik Seeley added a comment -

        > 3 The reader tries to load seg_1 and fails.

        That wouldn't be considered a failure because it's part of the retry logic. At that point, an attempt would be made to open seg_2.
        To minimize the possibility of this happening, the segments are opened in reverse order (since the last segments change the most often).

        Then a question might be, could a writer possibly change the index fast enough to prevent a reader from opening at all? I don't think so (and it would be a mis-configured writer IMO), but maybe Michael could speak to that.

        Show
        Yonik Seeley added a comment - > 3 The reader tries to load seg_1 and fails. That wouldn't be considered a failure because it's part of the retry logic. At that point, an attempt would be made to open seg_2. To minimize the possibility of this happening, the segments are opened in reverse order (since the last segments change the most often). Then a question might be, could a writer possibly change the index fast enough to prevent a reader from opening at all? I don't think so (and it would be a mis-configured writer IMO), but maybe Michael could speak to that.
        Hide
        Ning Li added a comment -

        Can the following scenario happen with lock-less commits?

        1 A reader reads segments.1, which says the index contains seg_1.
        2 A writer writes segments.2, which says the index now contains seg_2, and deletes seg_1.
        3 The reader tries to load seg_1 and fails.

        Show
        Ning Li added a comment - Can the following scenario happen with lock-less commits? 1 A reader reads segments.1, which says the index contains seg_1. 2 A writer writes segments.2, which says the index now contains seg_2, and deletes seg_1. 3 The reader tries to load seg_1 and fails.
        Hide
        Michael McCandless added a comment -

        Good questions!

        > In the future, it might be nice if there was an option to disable
        > segments.gen to be more friendly to write-once filesystems like
        > HDFS.

        I think this makes sense. I will add control over this on the next
        iteration of the patch.

        > As far as performance goes, I was personally interested in the
        > contentionless case since that's what processes that coordinate
        > everything (like Solr) will see.

        Ahh got it, OK. That's fair.

        > I'm not sure I understand the "segments.gen" logic of writing two
        > longs that are identical. Looking at the code, it doesn't seem like
        > you are implementing this:
        > http://www.nabble.com/Re%3A-Lock-less-commits-p5978090.html
        > Are there two longs instead of one in order to leave "space" for
        > that implementation if needed, w/o having to change the file format?

        Right, I settled on a simplification of that approach. I write two
        longs so that reader can read both & compare and only trust them if they
        are identical. With one long I was worried eg that perhaps 3 bytes
        from the writer were written but not yet the remaining 5 bytes, and
        then reader would get the wrong value. I don't think IO systems
        guarantee atomicity of eg 8 byte chunks (though in practice it's
        probably often the case).

        One thing I will also add is a version header to this file.

        > The file deleting code does much more than in the past, and that's a
        > good thing IMO. For example it looks like leftover non-compound
        > segment files from a failed CFS merge (say the JVM dies) will now be
        > cleaned up!

        Oh, right! In fact any time an index crashes not having committed its
        segments file, there is potential for leftover (unreferenced) files
        now. This separate IndexFileDeleter class should correctly reclaim in
        such cases. And even other potential future situations like the
        discussion in LUCENE-702 would be reclaimed correctly with this
        approach.

        > I'm having a hard time figuring out how older delete files are
        > removed (since they contain the current segment name, it looks like
        > findDeletableFiles would skip them).

        Oooh – you are correct. I do record this file for deleting at the
        point it becomes unreferenced (ie, as a reader is committing its
        separate norms/deletes), and then I delete this file after the commit
        is done. But if JVM crashes after the new del file was written and
        before the commit, then you're right on restarting I don't correctly
        delete the unreferenced old _X_N.del files, nor I believe the separate
        norms _X_N.sM files. I will add a unit test to verify this bug and
        then fix it – good catch!

        Show
        Michael McCandless added a comment - Good questions! > In the future, it might be nice if there was an option to disable > segments.gen to be more friendly to write-once filesystems like > HDFS. I think this makes sense. I will add control over this on the next iteration of the patch. > As far as performance goes, I was personally interested in the > contentionless case since that's what processes that coordinate > everything (like Solr) will see. Ahh got it, OK. That's fair. > I'm not sure I understand the "segments.gen" logic of writing two > longs that are identical. Looking at the code, it doesn't seem like > you are implementing this: > http://www.nabble.com/Re%3A-Lock-less-commits-p5978090.html > Are there two longs instead of one in order to leave "space" for > that implementation if needed, w/o having to change the file format? Right, I settled on a simplification of that approach. I write two longs so that reader can read both & compare and only trust them if they are identical. With one long I was worried eg that perhaps 3 bytes from the writer were written but not yet the remaining 5 bytes, and then reader would get the wrong value. I don't think IO systems guarantee atomicity of eg 8 byte chunks (though in practice it's probably often the case). One thing I will also add is a version header to this file. > The file deleting code does much more than in the past, and that's a > good thing IMO. For example it looks like leftover non-compound > segment files from a failed CFS merge (say the JVM dies) will now be > cleaned up! Oh, right! In fact any time an index crashes not having committed its segments file, there is potential for leftover (unreferenced) files now. This separate IndexFileDeleter class should correctly reclaim in such cases. And even other potential future situations like the discussion in LUCENE-702 would be reclaimed correctly with this approach. > I'm having a hard time figuring out how older delete files are > removed (since they contain the current segment name, it looks like > findDeletableFiles would skip them). Oooh – you are correct. I do record this file for deleting at the point it becomes unreferenced (ie, as a reader is committing its separate norms/deletes), and then I delete this file after the commit is done. But if JVM crashes after the new del file was written and before the commit, then you're right on restarting I don't correctly delete the unreferenced old _X_N.del files, nor I believe the separate norms _X_N.sM files. I will add a unit test to verify this bug and then fix it – good catch!
        Hide
        Yonik Seeley added a comment -

        Thanks for all the details Michael! A few more random comments and questions:

        In the future, it might be nice if there was an option to disable segments.gen to be more friendly to write-once filesystems like HDFS.

        As far as performance goes, I was personally interested in the contentionless case since that's what processes that coordinate everything (like Solr) will see.

        I'm not sure I understand the "segments.gen" logic of writing two longs that are identical.
        Looking at the code, it doesn't seem like you are implementing this:
        http://www.nabble.com/Re%3A-Lock-less-commits-p5978090.html
        Are there two longs instead of one in order to leave "space" for that implementation if needed, w/o having to change the file format?

        The file deleting code does much more than in the past, and that's a good thing IMO. For example it looks like leftover non-compound segment files from a failed CFS merge (say the JVM dies) will now be cleaned up!

        I'm having a hard time figuring out how older delete files are removed (since they contain the current segment name, it looks like findDeletableFiles would skip them).

        Show
        Yonik Seeley added a comment - Thanks for all the details Michael! A few more random comments and questions: In the future, it might be nice if there was an option to disable segments.gen to be more friendly to write-once filesystems like HDFS. As far as performance goes, I was personally interested in the contentionless case since that's what processes that coordinate everything (like Solr) will see. I'm not sure I understand the "segments.gen" logic of writing two longs that are identical. Looking at the code, it doesn't seem like you are implementing this: http://www.nabble.com/Re%3A-Lock-less-commits-p5978090.html Are there two longs instead of one in order to leave "space" for that implementation if needed, w/o having to change the file format? The file deleting code does much more than in the past, and that's a good thing IMO. For example it looks like leftover non-compound segment files from a failed CFS merge (say the JVM dies) will now be cleaned up! I'm having a hard time figuring out how older delete files are removed (since they contain the current segment name, it looks like findDeletableFiles would skip them).
        Hide
        Michael McCandless added a comment -

        > In the absense of contention, have you noticed any performance differences in opening an IndexReader?

        [First one side note: it's during contention that lock-less really
        shines. Because, currently Lucene hits at least a [default] 1.0
        second delay under contention, whereas lockless immediately retries.
        And, readers now have contention with one another, but not with
        lock-less.]

        I ran the following basic performance test. In each case I measure
        avg wall clock time to instantiate readers & writers against the same
        index. A writer creates the index, adding documents as quickly as it
        can, and commits and closes/reopens its writer every 2 seconds. Then,
        a reader reads against the same index, just instantiating a searcher
        then closing it and then pausing for 2 seconds. I skew the writer by
        1 sec to try to minimize contention. Each test is avg of 3 runs,
        where each run is 2 minutes.

        In order to not count contention, I made temporary mods, to both
        current lucene & lockless, to throw IOException on hitting contention.
        Then, I catch that above and discard the time for that one
        instantiation of reader or writer.

        All times are mili-seconds. Each time is formatted as current Lucene
        time followed by lockless in (...)s:

        Local index (Linux): 4.62 (6.04)
        Local index (WIN32): 85.45 (66.37)

        NFS remote index (Linux): 171.26 (11.04)
        SMB remote index (WIN32): 48.91 (31.55)

        The "remote index" case means a writer on that OS, and a reader on
        another machine with the same OS, reading the index on a mount from
        the writer machine (ie, writer is writing locally and reader is
        reading remotely).

        One caveat: I saw quite a bit of variance between runs. I tried to
        eliminate causes (stopped all services, other applications, etc.) but
        still there is variance. Maybe I should be taking the "minumum" time
        seen instead of the average (this was mentioned on the benchmarking
        Jira issue)...

        Anyway, the surprising thing is that lockless is faster in most cases
        In the remote cases (especially NFS) it's quite a bit faster. I think
        this may be because lockless does far fewer "fileExists" calls
        compared to current Lucene. For example, the "openNorms" call
        presently does a "fileExists" call per field that has norms index
        times the number of segments.

        I'm not sure these speedups/differences are all that important in a
        typical Lucene use case, where the cost of instantiating a reader is
        amortized over all the searches that occur during the lifetime of that
        reader. Though, maybe one real difference is: if we can make sure the
        latency is low enough, it's OK to have a single query pay the price of
        reopening the searcher. Ie, it becomes reasonable to have an incoming
        query first check whether the searcher is current and if not, reopen
        it, and then run the query, vs having separate background thread do
        this, which is certainly feasible just more complicated.

        Show
        Michael McCandless added a comment - > In the absense of contention, have you noticed any performance differences in opening an IndexReader? [First one side note: it's during contention that lock-less really shines. Because, currently Lucene hits at least a [default] 1.0 second delay under contention, whereas lockless immediately retries. And, readers now have contention with one another, but not with lock-less.] I ran the following basic performance test. In each case I measure avg wall clock time to instantiate readers & writers against the same index. A writer creates the index, adding documents as quickly as it can, and commits and closes/reopens its writer every 2 seconds. Then, a reader reads against the same index, just instantiating a searcher then closing it and then pausing for 2 seconds. I skew the writer by 1 sec to try to minimize contention. Each test is avg of 3 runs, where each run is 2 minutes. In order to not count contention, I made temporary mods, to both current lucene & lockless, to throw IOException on hitting contention. Then, I catch that above and discard the time for that one instantiation of reader or writer. All times are mili-seconds. Each time is formatted as current Lucene time followed by lockless in (...)s: Local index (Linux): 4.62 (6.04) Local index (WIN32): 85.45 (66.37) NFS remote index (Linux): 171.26 (11.04) SMB remote index (WIN32): 48.91 (31.55) The "remote index" case means a writer on that OS, and a reader on another machine with the same OS, reading the index on a mount from the writer machine (ie, writer is writing locally and reader is reading remotely). One caveat: I saw quite a bit of variance between runs. I tried to eliminate causes (stopped all services, other applications, etc.) but still there is variance. Maybe I should be taking the "minumum" time seen instead of the average (this was mentioned on the benchmarking Jira issue)... Anyway, the surprising thing is that lockless is faster in most cases In the remote cases (especially NFS) it's quite a bit faster. I think this may be because lockless does far fewer "fileExists" calls compared to current Lucene. For example, the "openNorms" call presently does a "fileExists" call per field that has norms index times the number of segments. I'm not sure these speedups/differences are all that important in a typical Lucene use case, where the cost of instantiating a reader is amortized over all the searches that occur during the lifetime of that reader. Though, maybe one real difference is: if we can make sure the latency is low enough, it's OK to have a single query pay the price of reopening the searcher. Ie, it becomes reasonable to have an incoming query first check whether the searcher is current and if not, reopen it, and then run the query, vs having separate background thread do this, which is certainly feasible just more complicated.
        Hide
        Michael McCandless added a comment -

        > > on one platform (OS X) I found that the directory listing can be incorrect (stale) by up to 1.0 seconds.
        >
        > That sucks... (but great job on the very thorough testing).
        > Can it happen with the latest version of OS X? If not, couldn't we just require an upgrade, or do you think that other platforms suffer from this.

        Yes, this was very surprising and annoying! Unfortunately, this
        happens on the latest version of OS X (10.4.8). Other platforms that
        I tested do "the right thing" meaning when you list a directory the
        NFS client on Linux first checks with the server to see if its cache
        is stale and correctly clears the cache. Windows SMB is also always
        correct. But I think it's entirely likely that filesystems do this
        kind of time-based (only) cache validation. I figured better safe than
        sorry here, and Lucene should tolerate stale caching around either
        file contents or directory listing.

        Show
        Michael McCandless added a comment - > > on one platform (OS X) I found that the directory listing can be incorrect (stale) by up to 1.0 seconds. > > That sucks... (but great job on the very thorough testing). > Can it happen with the latest version of OS X? If not, couldn't we just require an upgrade, or do you think that other platforms suffer from this. Yes, this was very surprising and annoying! Unfortunately, this happens on the latest version of OS X (10.4.8). Other platforms that I tested do "the right thing" meaning when you list a directory the NFS client on Linux first checks with the server to see if its cache is stale and correctly clears the cache. Windows SMB is also always correct. But I think it's entirely likely that filesystems do this kind of time-based (only) cache validation. I figured better safe than sorry here, and Lucene should tolerate stale caching around either file contents or directory listing.
        Hide
        Michael McCandless added a comment -

        Thanks Yonik for looking at this!

        > Could you elaborate on how the backward compatibility works w.r.t. modifying an old index?
        > How do versioned norms & del files mix with older unversion files?

        OK, first off, the only file whose contents and name are changed is
        the "segments_N" file. Then, the only files whose name (but not
        contents) is changed are the "_X_N.del" deletes file, and "_X_N.sZ"
        separate norms files). Finally, the only file that is deleted is
        deletable. All other segments files are unchanged.

        The unit test I added for this (TestBackwardsCompatibility) un-zips a
        pre-lockless index (I have one zip file for CFS format and one for
        non-CFS) and then runs various tests: adding docs, deleting a doc,
        setting a norm for a doc, searching, etc., verifying that the results
        are then as expected.

        On opening an pre-lockless index, first we see only a "segments" file
        with no _N extension, and record its generation as 0. Second, since
        that file's contents doesn't lead with format lockless code (-2), we
        know to load the old segments info format that does not contain the
        "del" gen, "separate norm" gen nor the "isCompundFile" marker.

        When loading each Segmentinfo, since the format of the segments files
        was old, we record this with "preLockless = true" and set delGen and
        isCompoundFile to 0 and normGen to null. 0 means "must check
        filesystem for existence". The various methods (hasSeparateNorms,
        hasDeletions, etc.) know to handle these "0" cases as falling back to
        filesystem existence checks of the existing naming (ie, _X.del). I
        tried to capture / contain all of this inside the methods of
        SegmentInfo.

        Now, when a writer commits to this pre-lockless index, we write in the
        new (format lockless) format and to the file "segments_1". (Actually,
        with compound file turned on, we then make a .cfs file and commit
        again to "segments_2"). This file will reference all of the old
        segments (except eg those deleted by a merge) plus the one new
        segment.

        The old segments have written the "0"'s for delGen, normGen (null is
        written as -1 length), isCompoundFile so that on re-loading this
        segments_2 file these segments remain pre-lockless. The SegmentInfo
        for the new segment file will have isCompoundFile=1 (meaning it is a
        compound file), delGen=-1 (there are no separate deletes yet) and
        normGen=null (there are no separate norms yet). When normGen is null,
        we look at "preLockless" to differentiate whether this means there are
        no separate norms at all for any fields, or, this segment is pre
        lockless and therefore we must fallback to the filesystem check.

        If a delete or setNorm call takes place against an old segment format,
        we will at that time create "generation 1" for that file. This means
        you can have an old segment whose separate del file is still
        "generation 0" (you have to check for existence of _X.del) but whose
        separate norms generations are known (or, only certain fields are
        known and the others are "generation 0" and require filesystem check).
        This means an "old" segment file could become "slightly newer" as
        norm/del changes are made against it.

        So an index can have mixed old/new segments. The SegmentInfo for each
        segment keeps track of old/new (and tries to hide these implementation
        details under its methods) with delGen, normGen, isCompoundFile and
        preLockless (which is derived from isCompoundFile).

        Once an optimize is done, or, all old segments have been merged away,
        then all segments are now the lockless format.

        Show
        Michael McCandless added a comment - Thanks Yonik for looking at this! > Could you elaborate on how the backward compatibility works w.r.t. modifying an old index? > How do versioned norms & del files mix with older unversion files? OK, first off, the only file whose contents and name are changed is the "segments_N" file. Then, the only files whose name (but not contents) is changed are the "_X_N.del" deletes file, and "_X_N.sZ" separate norms files). Finally, the only file that is deleted is deletable. All other segments files are unchanged. The unit test I added for this (TestBackwardsCompatibility) un-zips a pre-lockless index (I have one zip file for CFS format and one for non-CFS) and then runs various tests: adding docs, deleting a doc, setting a norm for a doc, searching, etc., verifying that the results are then as expected. On opening an pre-lockless index, first we see only a "segments" file with no _N extension, and record its generation as 0. Second, since that file's contents doesn't lead with format lockless code (-2), we know to load the old segments info format that does not contain the "del" gen, "separate norm" gen nor the "isCompundFile" marker. When loading each Segmentinfo, since the format of the segments files was old, we record this with "preLockless = true" and set delGen and isCompoundFile to 0 and normGen to null. 0 means "must check filesystem for existence". The various methods (hasSeparateNorms, hasDeletions, etc.) know to handle these "0" cases as falling back to filesystem existence checks of the existing naming (ie, _X.del). I tried to capture / contain all of this inside the methods of SegmentInfo. Now, when a writer commits to this pre-lockless index, we write in the new (format lockless) format and to the file "segments_1". (Actually, with compound file turned on, we then make a .cfs file and commit again to "segments_2"). This file will reference all of the old segments (except eg those deleted by a merge) plus the one new segment. The old segments have written the "0"'s for delGen, normGen (null is written as -1 length), isCompoundFile so that on re-loading this segments_2 file these segments remain pre-lockless. The SegmentInfo for the new segment file will have isCompoundFile=1 (meaning it is a compound file), delGen=-1 (there are no separate deletes yet) and normGen=null (there are no separate norms yet). When normGen is null, we look at "preLockless" to differentiate whether this means there are no separate norms at all for any fields, or, this segment is pre lockless and therefore we must fallback to the filesystem check. If a delete or setNorm call takes place against an old segment format, we will at that time create "generation 1" for that file. This means you can have an old segment whose separate del file is still "generation 0" (you have to check for existence of _X.del) but whose separate norms generations are known (or, only certain fields are known and the others are "generation 0" and require filesystem check). This means an "old" segment file could become "slightly newer" as norm/del changes are made against it. So an index can have mixed old/new segments. The SegmentInfo for each segment keeps track of old/new (and tries to hide these implementation details under its methods) with delGen, normGen, isCompoundFile and preLockless (which is derived from isCompoundFile). Once an optimize is done, or, all old segments have been merged away, then all segments are now the lockless format.
        Hide
        Yonik Seeley added a comment -

        Nice job on this very ambitious patch (all 3500 lines of it!) Good tests are certainly important!

        Could you elaborate on how the backward compatibility works w.r.t. modifying an old index?
        How do versioned norms & del files mix with older unversion files?

        In the absense of contention, have you noticed any performance differences in opening an IndexReader?

        > on one platform (OS X) I found that the directory listing can be incorrect (stale) by up to 1.0 seconds.

        That sucks... (but great job on the very thorough testing).
        Can it happen with the latest version of OS X? If not, couldn't we just require an upgrade, or do you think that other platforms suffer from this.

        Show
        Yonik Seeley added a comment - Nice job on this very ambitious patch (all 3500 lines of it!) Good tests are certainly important! Could you elaborate on how the backward compatibility works w.r.t. modifying an old index? How do versioned norms & del files mix with older unversion files? In the absense of contention, have you noticed any performance differences in opening an IndexReader? > on one platform (OS X) I found that the directory listing can be incorrect (stale) by up to 1.0 seconds. That sucks... (but great job on the very thorough testing). Can it happen with the latest version of OS X? If not, couldn't we just require an upgrade, or do you think that other platforms suffer from this.
        Hide
        Michael McCandless added a comment -

        ZIP file that needs to be put in src/test/org/apache/lucene/index (used by backwards compatibility test).

        Show
        Michael McCandless added a comment - ZIP file that needs to be put in src/test/org/apache/lucene/index (used by backwards compatibility test).
        Hide
        Michael McCandless added a comment -

        ZIP file that needs to be put in src/test/org/apache/lucene/index (used by backwards compatibility test).

        Show
        Michael McCandless added a comment - ZIP file that needs to be put in src/test/org/apache/lucene/index (used by backwards compatibility test).

          People

          • Assignee:
            Michael McCandless
            Reporter:
            Michael McCandless
          • Votes:
            4 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development