KVS _update_user_token_list can be more efficient

[Billy Olsen]

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).

[Steve Martinelli (stevemar)]

consider using fernet tokens to avoid persisting tokens at all

[Billy Olsen (billy-olsen)]

I understand that the SQL backend is recommended over KVS, but running some tests in which I created 20K tokens for a user using the current linear implementation vs an ordered implementation yields some interesting results. I created 20k tokens (without reuse) and measured the duration it took from the API CURL command for creating each token. This measures the API/User perceived token creation time:

* A graph and data can be found at: https://plot.ly/~wolsen/10/unordered-vs-ordered-list-token-creation-times/ (I will also attach a .png of the graph)

From the data we can see that in general, the token creation time with an ordered list is (in general) about 80% faster than the unordered list implementation (mean time is 0.54s vs 0.11s).

[Billy Olsen (billy-olsen)]

Yep, fernet tokens will avoid persistence problems and that's great, but this isn't about fernet tokens - this is about improving the kvs provider under memcache, which is still used from time to time.

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: master
Review: https://review.openstack.org/348040

[Steve Martinelli (stevemar)]

See comments in patch set. We are actively trying to remove KVS code from keystone since it is so very rarely used in production, and alternatives are easily setup for testing.

[OpenStack Infra (hudson-openstack)]

Change abandoned by Billy Olsen (<email address hidden>) on branch: master
Review: https://review.openstack.org/348040
Reason: No interest in improving the KVS store as its being deprecated anyways. Let's move on to bigger and better things

[Billy Olsen (billy-olsen)]

After discussion with Keystone core, there's no interest in fixing this in current Keystone as the KVS is deprecated in favor of fernet tokens. I think its reasonable to mark this as won't fix. There's some performance gains that could be had, but they aren't worth it at this point.

[Steve Martinelli (stevemar)]

Thanks Billy! I'll mark this as WONTFIX since it doesn't align with project plans.