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 -- Mailing list: https://launchpad.net/~yahoo-eng-team Post to : yahoo-eng-team@lists.launchpad.net Unsubscribe : https://launchpad.net/~yahoo-eng-team More help : https://help.launchpad.net/ListHelp