A system, comprising: one or more computing devices configured to: receive, at an access subsystem of a distributed multi-tenant file storage service, a request to establish a client session for file store operations on behalf of a particular client; transmit, from the access subsystem to a metadata subsystem of the file storage service, a request for a session identifier to be associated with the client session; provide, to the access subsystem, from the metadata subsystem, a session identifier based at least in part on a persistent session storage location at which one or more elements of metadata of the client session are stored, wherein the one or more elements include an indication of a lease associated with the client session; cache, at the access subsystem, the session identifier and an indication of the lease, prior to a transmission of the session identifier to the particular client; determine, at the metadata subsystem, a persistent lock storage location at which to store a lock state indicator associated with a particular file store object, wherein the lock state indicator is generated in response to a different request from the client, wherein the different request comprises the session identifier and wherein the lock state indicator comprises the session identifier; cache, at the access subsystem, the lock state indicator; utilize, at the access subsystem, the cached session identifier, the cached indication of the lease, and the cached lock state indicator to respond to a service request from the client directed to the particular file store object; and in response to a determination that a timeout associated with the lease has expired, delete (a) the lock state indicator from the persistent lock storage location, and (b) the session identifier from the persistent session storage location. receive, at an access subsystem of a distributed multi-tenant file storage service, a request to establish a client session for file store operations on behalf of a particular client; transmit, from the access subsystem to a metadata subsystem of the file storage service, a request for a session identifier to be associated with the client session; provide, to the access subsystem, from the metadata subsystem, a session identifier based at least in part on a persistent session storage location at which one or more elements of metadata of the client session are stored, wherein the one or more elements include an indication of a lease associated with the client session; cache, at the access subsystem, the session identifier and an indication of the lease, prior to a transmission of the session identifier to the particular client; determine, at the metadata subsystem, a persistent lock storage location at which to store a lock state indicator associated with a particular file store object, wherein the lock state indicator is generated in response to a different request from the client, wherein the different request comprises the session identifier and wherein the lock state indicator comprises the session identifier; cache, at the access subsystem, the lock state indicator; utilize, at the access subsystem, the cached session identifier, the cached indication of the lease, and the cached lock state indicator to respond to a service request from the client directed to the particular file store object; and in response to a determination that a timeout associated with the lease has expired, delete (a) the lock state indicator from the persistent lock storage location, and (b) the session identifier from the persistent session storage location.