I tried using Memorystore for Redis with the VPC connector and I'm still seeing the same issue. If I try running the same commands from the cloud console I have no issue. Something is going wrong inside the App Engine environment for me.
Here is the psuedo code:
# see if data is cached
cached = redis_client.get('my_key')
if cached is not None:
return cached
# data not cached, query from datastore
q = datastore_client.query(kind='MyKind')
result = list(q.fetch())
# cache data for next query
t = time.time()
success = redis_client.set('my_key', result, ex=7200)
logging.info(f'redis.set took {time.time() - t} seconds') # this takes 35 seconds with memorystore for redis, <1 s from cloud console