For checking an entry in revocation_event table, keystone builds a tree comprising all the entries in the table and searches for a matching token by traversing the tree. Every validate token call rebuilds the tree - this includes getting all entries from the db, converting them into dict objects for manipulation and then building the tree. We observed that the conversion of db entries to objects is what causes the increase in latency and not the building of the tree or the tree traversal. This conversion and subsequent rebuilds are unnecessary and can be avoided. With this patch, the first call to the get_revoke_tree method will build the tree and subsequent calls will not rebuild the tree unless the tree has been invalidated by a new addition to the revocation_event table.
Related bugs - 1287757 & 1456797. The fix for 1287757 addresses the issue partially by removing the purge on validate, but we still see deadlocks and a huge increase in latency with an increase in revocation table entries due to the time taken for db entries to objects conversion as mentioned in the Bug description.