Uploaded image for project: 'Couchbase Server'
  1. Couchbase Server
  2. MB-46614

Planner: Better stopping criteria

    XMLWordPrintable

Details

    • Improvement
    • Resolution: Unresolved
    • Major
    • Neo.next
    • CheshireCat.Next
    • secondary-index
    • None
    • 1

    Description

      Planner currently stops iterating when one of the following is achieved:

      1. Estimated cost falls below a fixed threshold t, or
      2. A fixed maximum number of iterations i is reached

      There are some problems with this approach. Let c be the (unknown) optimal cost.

      • If c << t, Planner will stop too early based on reaching t, even though much improvement is still possible.
      • If c > t, Planner will iterate the full i iterations even if it is no longer making progress.

      A better stopping criterion is to calculate a trailing average proportional cost improvement per iteration p over the last 1,000 iterations (= sample size for "how much improvement is still being achieved") and replacing t with an "epsilon" value e based on this metric, so Planner would instead stop when one of the following is achieved:

      1. p for the last 1,000 iterations falls below e
      2. A fixed maximum number of iterations i is reached

      Using this approach, Planner would not stop too early if it was still making good progress, nor would it continue to iterate futilely if only minimal or no progress was still being made.

      Attachments

        Activity

          People

            kevin.cherkauer Kevin Cherkauer (Inactive)
            kevin.cherkauer Kevin Cherkauer (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

              Created:
              Updated:

              PagerDuty