<div dir="ltr">Adam Young shared a patch to convert the tree back to a linear list:<div><br></div><div>  <a href="https://review.openstack.org/#/c/205266/">https://review.openstack.org/#/c/205266/</a></div><div><br></div><div>This shouldn't be merged without benchmarking as it's purely a performance-oriented change.<br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 23, 2015 at 11:40 AM, Matt Fischer <span dir="ltr"><<a href="mailto:matt@mattfischer.com" target="_blank">matt@mattfischer.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Morgan asked me to post some of my numbers here. From my staging environment:<div><br></div><div>With 0 revocations:</div><div><div>Requests per second:    104.67 [#/sec] (mean)</div><div>Time per request:       191.071 [ms] (mean)</div></div><div><br></div><div>With 500 revocations:</div><div><div>Requests per second:    52.48 [#/sec] (mean)</div><div>Time per request:       381.103 [ms] (mean)</div></div><div><br></div><div>I have some more numbers up on my blog post about this but that's from a virtual test environment and focused on throughput.</div><div><br></div><div>Thanks for the attention on this.</div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 23, 2015 at 8:45 AM, Lance Bragstad <span dir="ltr"><<a href="mailto:lbragstad@gmail.com" target="_blank">lbragstad@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote"><span>On Wed, Jul 22, 2015 at 10:06 PM, Adam Young <span dir="ltr"><<a href="mailto:ayoung@redhat.com" target="_blank">ayoung@redhat.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000"><span>
    <div>On 07/22/2015 05:39 PM, Adam Young
      wrote:<br>
    </div>
    <blockquote type="cite">
      
      <div>On 07/22/2015 03:41 PM, Morgan
        Fainberg wrote:<br>
      </div>
      <blockquote type="cite">
        
        <div>This is an indicator that the bottleneck is not the db
          strictly speaking, but also related to the way we match. This
          means we need to spend some serious cycles on improving both
          the stored record(s) for revocation events and the matching
          algorithm. <br>
        </div>
      </blockquote>
      <br>
      The simplest approach to revocation checking is to do a linear
      search through the events.  I think the old version of the code
      that did that is in a code review, and I will pull it out.<br>
      <br>
      If we remove the tree, then the matching will have to run through
      each of the records and see if there is a match;  the test will be
      linear with the number of records (slightly shorter if a token is
      actually revoked).<br>
    </blockquote>
    <br></span>
    This was the origianal, linear search version of the code.<br>
    <br>
<a href="https://review.openstack.org/#/c/55908/50/keystone/contrib/revoke/model.py,cm" target="_blank">https://review.openstack.org/#/c/55908/50/keystone/contrib/revoke/model.py,cm</a><div><div><br>
    <br></div></div></div></blockquote><div><br></div></span><div>What initially landed for Revocation Events was the tree-structure, right? We didn't land a linear approach prior to that and then switch to the tree, did we?  </div><div><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><div><div>
    <blockquote type="cite"> <br>
      <br>
      <br>
      <br>
      <br>
      <blockquote type="cite">
        <div><br>
          Sent via mobile</div>
        <div><br>
          On Jul 22, 2015, at 11:51, Matt Fischer <<a href="mailto:matt@mattfischer.com" target="_blank">matt@mattfischer.com</a>>

          wrote:<br>
          <br>
        </div>
        <blockquote type="cite">
          <div>
            <div dir="ltr">Dolph,
              <div><br>
              </div>
              <div>Per our IRC discussion, I was unable to see any
                performance improvement here although not calling DELETE
                so often will reduce the number of deadlocks when we're
                under heavy load especially given the globally
                replicated DB we use.</div>
              <div><br>
              </div>
              <div><br>
              </div>
            </div>
            <div class="gmail_extra"><br>
              <div class="gmail_quote">On Tue, Jul 21, 2015 at 5:26 PM,
                Dolph Mathews <span dir="ltr"><<a href="mailto:dolph.mathews@gmail.com" target="_blank">dolph.mathews@gmail.com</a>></span>
                wrote:<br>
                <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
                  <div dir="ltr">Well, you might be in luck! Morgan
                    Fainberg actually implemented an improvement that
                    was apparently documented by Adam Young way back in
                    March: 
                    <div><br>
                        <a href="https://bugs.launchpad.net/keystone/+bug/1287757" target="_blank">https://bugs.launchpad.net/keystone/+bug/1287757</a><br>
                    </div>
                    <div><br>
                    </div>
                    <div>There's a link to the stable/kilo backport in
                      comment #2 - I'd be eager to hear how it performs
                      for you!</div>
                    <div>
                      <div>
                        <div>
                          <div class="gmail_extra"><br>
                            <div class="gmail_quote">On Tue, Jul 21,
                              2015 at 5:58 PM, Matt Fischer <span dir="ltr"><<a href="mailto:matt@mattfischer.com" target="_blank">matt@mattfischer.com</a>></span>
                              wrote:<br>
                              <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
                                <div dir="ltr">
                                  <div class="gmail_extra">Dolph,</div>
                                  <div class="gmail_extra"><br>
                                  </div>
                                  <div class="gmail_extra">Excuse the
                                    delayed reply, was waiting for a
                                    brilliant solution from someone.
                                    Without one, personally I'd prefer
                                    the cronjob as it seems to be the
                                    type of thing cron was designed for.
                                    That will be a painful change as
                                    people now rely on this behavior so
                                    I don't know if its feasible. I will
                                    be setting up monitoring for the
                                    revocation count and alerting me if
                                    it crosses probably 500 or so. If
                                    the problem gets worse then I think
                                    a custom no-op or sql driver is the
                                    next step.</div>
                                  <div class="gmail_extra"><br>
                                  </div>
                                  <div class="gmail_extra">Thanks.</div>
                                  <div>
                                    <div>
                                      <div class="gmail_extra"><br>
                                      </div>
                                      <div class="gmail_extra"><br>
                                        <div class="gmail_quote">On Wed,
                                          Jul 15, 2015 at 4:00 PM, Dolph
                                          Mathews <span dir="ltr"><<a href="mailto:dolph.mathews@gmail.com" target="_blank">dolph.mathews@gmail.com</a>></span>
                                          wrote:<br>
                                          <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
                                            <div dir="ltr"><br>
                                              <div class="gmail_extra"><br>
                                                <div class="gmail_quote"><span>On

                                                    Wed, Jul 15, 2015 at
                                                    4:51 PM, Matt
                                                    Fischer <span dir="ltr"><<a href="mailto:matt@mattfischer.com" target="_blank">matt@mattfischer.com</a>></span>
                                                    wrote:<br>
                                                    <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
                                                      <div dir="ltr">I'm
                                                        having some
                                                        issues with
                                                        keystone
                                                        revocation
                                                        events. The
                                                        bottom line is
                                                        that due to the
                                                        way keystone
                                                        handles the
                                                        clean-up of
                                                        these events[1],
                                                        having more than
                                                        a few leads to:
                                                        <div><br>
                                                        </div>
                                                        <div> - bad
                                                          performance,
                                                          up to 2x
                                                          slower token
                                                          validation
                                                          with about 600
                                                          events based
                                                          on my perf
                                                          measurements.</div>
                                                        <div> - database
                                                          deadlocks,
                                                          which cause
                                                          API calls to
                                                          fail, more
                                                          likely with
                                                          more events it
                                                          seems</div>
                                                        <div><br>
                                                        </div>
                                                        <div>I am seeing
                                                          this behavior
                                                          in code from
                                                          trunk on June
                                                          11 using
                                                          Fernet tokens,
                                                          but the token
                                                          backend does
                                                          not seem to
                                                          make a
                                                          difference.</div>
                                                        <div><br>
                                                        </div>
                                                        <div>Here's what
                                                          happens to the
                                                          db in terms of
                                                          deadlock:</div>
                                                        <div>2015-07-15
                                                          21:25:41.082
                                                          31800 TRACE
                                                          keystone.common.wsgi
                                                          DBDeadlock:
                                                          (OperationalError)
                                                          (1213,
                                                          'Deadlock
                                                          found when
                                                          trying to get
                                                          lock; try
                                                          restarting
                                                          transaction')
                                                          'DELETE FROM
                                                          revocation_event
                                                          WHERE
                                                          revocation_event.revoked_at
                                                          < %s'
                                                          (datetime.datetime(2015,
                                                          7, 15, 18, 55,
                                                          41, 55186),)<br>
                                                        </div>
                                                        <div><br>
                                                        </div>
                                                        <div>When this
                                                          starts
                                                          happening, I
                                                          just go
                                                          truncate the
                                                          table, but
                                                          this is not
                                                          ideal. If [1]
                                                          is really true
                                                          then the
                                                          design is not
                                                          great, it
                                                          sounds like
                                                          keystone is
                                                          doing a
                                                          revocation
                                                          event clean-up
                                                          on every token
                                                          validation
                                                          call. Reading
                                                          and
                                                          deleting/locking
                                                          from my db
                                                          cluster is not
                                                          something I
                                                          want to do on
                                                          every validate
                                                          call.</div>
                                                      </div>
                                                    </blockquote>
                                                    <div><br>
                                                    </div>
                                                  </span>
                                                  <div>Unfortunately,
                                                    that's *exactly*
                                                    what keystone is
                                                    doing. Adam and I
                                                    had a conversation
                                                    about this problem
                                                    in Vancouver which
                                                    directly resulted in
                                                    opening the bug
                                                    referenced on the
                                                    operator list:<br>
                                                    <br>
                                                      <a href="https://bugs.launchpad.net/keystone/+bug/1456797" target="_blank">https://bugs.launchpad.net/keystone/+bug/1456797</a><br>
                                                    <br>
                                                  </div>
                                                  <div>Neither of us
                                                    remembered the
                                                    actual implemented
                                                    behavior, which is
                                                    what you've run into
                                                    and Deepti verified
                                                    in the bug's
                                                    comments.<br>
                                                  </div>
                                                  <span>
                                                    <div> </div>
                                                    <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
                                                      <div dir="ltr">
                                                        <div><br>
                                                        </div>
                                                        <div>So, can I
                                                          turn of token
                                                          revocation for
                                                          now? I didn't
                                                          see an obvious
                                                          no-op driver.</div>
                                                      </div>
                                                    </blockquote>
                                                    <div><br>
                                                    </div>
                                                  </span>
                                                  <div>Not sure how,
                                                    other than writing
                                                    your own no-op
                                                    driver, or perhaps
                                                    an extended driver
                                                    that doesn't try to
                                                    clean the table on
                                                    every read?<br>
                                                  </div>
                                                  <span>
                                                    <div> </div>
                                                    <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
                                                      <div dir="ltr">
                                                        <div>And in the
                                                          long-run can
                                                          this be fixed?
                                                          I'd rather do
                                                          almost
                                                          anything else,
                                                          including
                                                          writing a
                                                          cronjob than
                                                          what happens
                                                          now.</div>
                                                      </div>
                                                    </blockquote>
                                                    <div><br>
                                                    </div>
                                                  </span>
                                                  <div>If anyone has a
                                                    better solution than
                                                    the current one,
                                                    that's also better
                                                    than requiring a
                                                    cron job on
                                                    something like
                                                    keystone-manage
                                                    revocation_flush I'd
                                                    love to hear it.<br>
                                                  </div>
                                                  <div><br>
                                                  </div>
                                                  <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><span>
                                                      <div dir="ltr">
                                                        <div><br>
                                                        </div>
                                                        <div>[1] - <a href="http://lists.openstack.org/pipermail/openstack-operators/2015-June/007210.html" target="_blank">http://lists.openstack.org/pipermail/openstack-operators/2015-June/007210.html</a></div>
                                                      </div>
                                                      <br>
                                                    </span>__________________________________________________________________________<br>
                                                    OpenStack
                                                    Development Mailing
                                                    List (not for usage
                                                    questions)<br>
                                                    Unsubscribe: <a href="http://OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" rel="noreferrer" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a><br>
                                                    <a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" rel="noreferrer" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a><br>
                                                    <br>
                                                  </blockquote>
                                                </div>
                                                <br>
                                              </div>
                                            </div>
                                            <br>
__________________________________________________________________________<br>
                                            OpenStack Development
                                            Mailing List (not for usage
                                            questions)<br>
                                            Unsubscribe: <a href="http://OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" rel="noreferrer" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a><br>
                                            <a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" rel="noreferrer" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a><br>
                                            <br>
                                          </blockquote>
                                        </div>
                                        <br>
                                      </div>
                                    </div>
                                  </div>
                                </div>
                                <br>
__________________________________________________________________________<br>
                                OpenStack Development Mailing List (not
                                for usage questions)<br>
                                Unsubscribe: <a href="http://OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" rel="noreferrer" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a><br>
                                <a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" rel="noreferrer" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a><br>
                                <br>
                              </blockquote>
                            </div>
                            <br>
                          </div>
                        </div>
                      </div>
                    </div>
                  </div>
                  <br>
__________________________________________________________________________<br>
                  OpenStack Development Mailing List (not for usage
                  questions)<br>
                  Unsubscribe: <a href="http://OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" rel="noreferrer" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a><br>
                  <a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" rel="noreferrer" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a><br>
                  <br>
                </blockquote>
              </div>
              <br>
            </div>
          </div>
        </blockquote>
        <blockquote type="cite">
          <div><span>__________________________________________________________________________</span><br>
            <span>OpenStack Development Mailing List (not for usage
              questions)</span><br>
            <span>Unsubscribe: <a href="mailto:OpenStack-dev-request@lists.openstack.org" target="_blank">OpenStack-dev-request@lists.openstack.org</a>?subject:unsubscribe</span><br>
            <span><a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a></span><br>
          </div>
        </blockquote>
        <br>
        <fieldset></fieldset>
        <br>
        <pre>__________________________________________________________________________
OpenStack Development Mailing List (not for usage questions)
Unsubscribe: <a href="mailto:OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a>
<a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a>
</pre>
      </blockquote>
      <br>
      <br>
      <fieldset></fieldset>
      <br>
      <pre>__________________________________________________________________________
OpenStack Development Mailing List (not for usage questions)
Unsubscribe: <a href="mailto:OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a>
<a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a>
</pre>
    </blockquote>
    <br>
  </div></div></div>

<br>__________________________________________________________________________<br>
OpenStack Development Mailing List (not for usage questions)<br>
Unsubscribe: <a href="http://OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" rel="noreferrer" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a><br>
<a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" rel="noreferrer" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a><br>
<br></blockquote></div></div></div><br></div></div>
<br>__________________________________________________________________________<br>
OpenStack Development Mailing List (not for usage questions)<br>
Unsubscribe: <a href="http://OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" rel="noreferrer" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a><br>
<a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" rel="noreferrer" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a><br>
<br></blockquote></div><br></div>
</div></div><br>__________________________________________________________________________<br>
OpenStack Development Mailing List (not for usage questions)<br>
Unsubscribe: <a href="http://OpenStack-dev-request@lists.openstack.org?subject:unsubscribe" rel="noreferrer" target="_blank">OpenStack-dev-request@lists.openstack.org?subject:unsubscribe</a><br>
<a href="http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev" rel="noreferrer" target="_blank">http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev</a><br>
<br></blockquote></div><br></div></div></div>