TL;DR: Database seems to be the bottleneck.

Placing a timeout in keystone-all has given a traceback:

2015-03-19 07:07:57.741 21373 ERROR keystone.common.wsgi [-] An unexpected error prevented the server from fulfilling your request:  (Disable debug mode to suppress these details.)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi Traceback (most recent call last):
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/keystone/common/wsgi.py", line 223, in __call__
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     result = method(context, **params)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/keystone/token/controllers.py", line 100, in authenticate
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     context, auth)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/keystone/token/controllers.py", line 303, in _authenticate_local
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     user_id, tenant_id)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/keystone/token/controllers.py", line 386, in _get_project_roles_and_ref
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     user_id, tenant_id)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/keystone/assignment/core.py", line 201, in get_roles_for_user_and_project
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     user_role_list = _get_user_project_roles(user_id, project_ref)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/keystone/assignment/core.py", line 182, in _get_user_project_roles
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     tenant_id=project_ref['id'])
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/keystone/assignment/backends/sql.py", line 99, in _get_metadata
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     refs = q.all()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/orm/query.py", line 2300, in all
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     return list(self)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/orm/loading.py", line 66, in instances
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     fetch = cursor.fetchall()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/engine/result.py", line 787, in fetchall
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     self.cursor, self.context)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/engine/base.py", line 1156, in _handle_dbapi_exception
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     util.raise_from_cause(newraise, exc_info)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/util/compat.py", line 199, in raise_from_cause
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     reraise(type(exception), exception, tb=exc_tb)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/engine/result.py", line 782, in fetchall
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     self.close()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/engine/result.py", line 542, in close
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     self.connection.close()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/engine/base.py", line 641, in close
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     conn.close()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/pool.py", line 797, in close
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     self._checkin()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/pool.py", line 681, in _checkin
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     self._pool, None, self._echo, fairy=self)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/pool.py", line 579, in _finalize_fairy
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     connection_record.checkin()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/pool.py", line 468, in checkin
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     pool.dispatch.checkin(connection, self)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/sqlalchemy/event/attr.py", line 260, in __call__
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     fn(*args, **kw)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/oslo/db/sqlalchemy/session.py", line 312, in _thread_yield
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     time.sleep(0)
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/eventlet/greenthread.py", line 32, in sleep
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     hub.switch()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/dist-packages/eventlet/hubs/hub.py", line 293, in switch
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi     return self.greenlet.switch()
2015-03-19 07:07:57.741 21373 TRACE keystone.common.wsgi DBError: An unexpected error prevented the server from fulfilling your request:  (Disable debug mode to suppress these details.)