Should implementations of IStorage be thread-safe?

[TheCloudlessSky]

I'm writing a Redis-based IStorage provider (using ServiceStack.Redis) and am running into some funky situations where the Redis client's state becomes inconsistent. I am creating the Redis client using a factory function that queries the IoC container. I was wondering if we need to ensure that the IStorage implementations need to be thread-safe? As soon as I added locks around the Redis client operations, the inconsistencies stopped.