yahoo-eng-team team mailing list archive

[Billy Olsen <billy.olsen@xxxxxxxxxxxxx>]

Public bug reported:

Maintaining the user token list and the revocation list in the memcached
persistence backend (kvs) is inefficient for larger amounts of tokens
due to the use of a linear algorithm for token list maintenance.

Since the list is unordered, each token within the list must be checked
first to ensure whether it has expired or not, secondly to determine if
it has been revoked or not. By changing to an ordered list and using a
binary search, expired tokens can be found with less computational
overhead.

The current algorithm means that the insertion of a new token into the
list is O(n) since token expiration validity is done when the list is
updated. By using an ordered list, the insertion and validation of the
expiration can be reduced to O(log n).

** Affects: keystone
     Importance: Undecided
         Status: New


** Tags: sts

-- 
You received this bug notification because you are a member of Yahoo!
Engineering Team, which is subscribed to OpenStack Identity (keystone).
https://bugs.launchpad.net/bugs/1607039

Title:
  KVS _update_user_token_list can be more efficient

Status in OpenStack Identity (keystone):
  New

Bug description:
  Maintaining the user token list and the revocation list in the
  memcached persistence backend (kvs) is inefficient for larger amounts
  of tokens due to the use of a linear algorithm for token list
  maintenance.

  Since the list is unordered, each token within the list must be
  checked first to ensure whether it has expired or not, secondly to
  determine if it has been revoked or not. By changing to an ordered
  list and using a binary search, expired tokens can be found with less
  computational overhead.

  The current algorithm means that the insertion of a new token into the
  list is O(n) since token expiration validity is done when the list is
  updated. By using an ordered list, the insertion and validation of the
  expiration can be reduced to O(log n).

To manage notifications about this bug go to:
https://bugs.launchpad.net/keystone/+bug/1607039/+subscriptions