A computer-implemented method, comprising: receiving a request through a web services interface to create a table in a non-relational data store, wherein the request specifies an identifier of the table, a primary key by which to index items stored in the table, and a throughput parameter for the scalable table; in response to said receiving: creating a scalable table in the non-relational data store, wherein the creating comprises creating one or more partitions for the scalable table according to the throughput parameter for the scalable table, wherein the scalable table is configured to store a plurality of items each of which comprises a value for the primary key, and wherein the scalable table does not have a pre-determined size limit; monitoring the throughput for the scalable table, where the throughput is specified in terms of a measure of normalized logical work units over time; determining whether the scalable table should be partitioned based on a change in the monitored throughput for the scalable table; and programmatically performing partitioning the scalable table in response to determining that the scalable table should be partitioned, wherein the partitioning is made according to values of the primary key for the items stored in the scalable table. receiving a request through a web services interface to create a table in a non-relational data store, wherein the request specifies an identifier of the table, a primary key by which to index items stored in the table, and a throughput parameter for the scalable table; in response to said receiving: creating a scalable table in the non-relational data store, wherein the creating comprises creating one or more partitions for the scalable table according to the throughput parameter for the scalable table, wherein the scalable table is configured to store a plurality of items each of which comprises a value for the primary key, and wherein the scalable table does not have a pre-determined size limit; monitoring the throughput for the scalable table, where the throughput is specified in terms of a measure of normalized logical work units over time; determining whether the scalable table should be partitioned based on a change in the monitored throughput for the scalable table; and programmatically performing partitioning the scalable table in response to determining that the scalable table should be partitioned, wherein the partitioning is made according to values of the primary key for the items stored in the scalable table. creating a scalable table in the non-relational data store, wherein the creating comprises creating one or more partitions for the scalable table according to the throughput parameter for the scalable table, wherein the scalable table is configured to store a plurality of items each of which comprises a value for the primary key, and wherein the scalable table does not have a pre-determined size limit; monitoring the throughput for the scalable table, where the throughput is specified in terms of a measure of normalized logical work units over time; determining whether the scalable table should be partitioned based on a change in the monitored throughput for the scalable table; and programmatically performing partitioning the scalable table in response to determining that the scalable table should be partitioned, wherein the partitioning is made according to values of the primary key for the items stored in the scalable table.