A system, comprising: one or more computing devices configured to: establish, to implement respective rates of provisioned workloads, respective sets of admission control parameters (130A, 130B, 130C, 130D) for each of a plurality of block-level storage devices (120A, 120B, 120C, 120D) implemented at a multi-tenant storage service; generate an estimate, by a client-side component of the multi-tenant storage service, of a particular rate of work requests expected to be directed during a particular time period to at least a portion of a first block-level storage device implemented at a first storage server, wherein the particular rate exceeds a first provisioned rate, wherein the estimate of the particular rate of work requests is generated according to an anticipated access pattern of work requests predicted based on temporal and/or spatial patterns in read and write requests issued from the client side, and wherein the temporal and/or spatial patterns are detected based on workload-related metrics collected from one or more of: logs of read/write requests handled at the client-side component on behalf of one or more compute instances to which the plurality of block-level storage devices are attached, information collected from other client-side components at other instance hosts or the same instance host, and/or information collected from one or more storage servers; identify, by the client-side component, one or more other storage servers, including a second storage server, at which respective rates of work requests are anticipated to be less than respective provisioned rates during the particular time period; verify that the first storage server has a sufficient workload capacity during the particular time period to complete work requests at a rate higher than the first provisioned rate; modify at least one admission control parameter of the first block-level storage device to enable the first storage server to accept work requests at up to a rate higher than the first provisioned rate during the particular time period; and modify at least one admission control parameter of at least a particular block-level storage device at the second storage server to enable the second storage server to accept work requests at a rate no greater than a provisioned rate of the second storage server during the particular time period. establish, to implement respective rates of provisioned workloads, respective sets of admission control parameters (130A, 130B, 130C, 130D) for each of a plurality of block-level storage devices (120A, 120B, 120C, 120D) implemented at a multi-tenant storage service; generate an estimate, by a client-side component of the multi-tenant storage service, of a particular rate of work requests expected to be directed during a particular time period to at least a portion of a first block-level storage device implemented at a first storage server, wherein the particular rate exceeds a first provisioned rate, wherein the estimate of the particular rate of work requests is generated according to an anticipated access pattern of work requests predicted based on temporal and/or spatial patterns in read and write requests issued from the client side, and wherein the temporal and/or spatial patterns are detected based on workload-related metrics collected from one or more of: logs of read/write requests handled at the client-side component on behalf of one or more compute instances to which the plurality of block-level storage devices are attached, information collected from other client-side components at other instance hosts or the same instance host, and/or logs of read/write requests handled at the client-side component on behalf of one or more compute instances to which the plurality of block-level storage devices are attached, information collected from other client-side components at other instance hosts or the same instance host, and/or information collected from one or more storage servers; identify, by the client-side component, one or more other storage servers, including a second storage server, at which respective rates of work requests are anticipated to be less than respective provisioned rates during the particular time period; verify that the first storage server has a sufficient workload capacity during the particular time period to complete work requests at a rate higher than the first provisioned rate; modify at least one admission control parameter of the first block-level storage device to enable the first storage server to accept work requests at up to a rate higher than the first provisioned rate during the particular time period; and modify at least one admission control parameter of at least a particular block-level storage device at the second storage server to enable the second storage server to accept work requests at a rate no greater than a provisioned rate of the second storage server during the particular time period.