A request for a session identifier for a particular client is transmitted from an access subsystem of a storage service to a metadata subsystem of the service. A session identifier based on a persistent session storage location at which metadata of the client session are stored is received at the access subsystem. The session identifier is cached at the access subsystem prior to its transmission to the client. A lock state indicator generated by the metadata subsystem in response to a particular request from the client during the client session may also be cached at the access subsystem. Subsequent storage requests from the client during the session may be handled by the access subsystem using the cached session identifier and lock state indicator.