Yeah, 36k per instance (especially on an xlarge or 2xlarge EC2 instance) is well within the serving capacity of memcached. While it depends a lot on the workload profile for a specific cluster, some clusters serve on the order of ~5k/instance while others are as high as ~100k/instance. We've done a lot of experimentation with extstore as well; it certainly eats up more compute cycles on average than an equivalent in-memory only cluster, but is still quite efficient.