I'm not a GAE expert, but using the GAE memcache clone wouldn't be a good idea in this case? The low latency requirement should be met and it looks like that his data structure would fit well in a k/v store.