Oops, you're right! Here's a fixed version (just prefixing the timestamp to the value to make sure it's always unique). Of course, this entire class makes the assumption that you never write twice with the same timestamp. (That's hard to guarantee if you're actually using time instead of something strictly increasing.)

    class TimeStore:
        def __init__(self, redis_client):
            self.redis_client = redis_client

        @staticmethod
        def timestamp(time): return (time-datetime.datetime(1970,1,1)).total_seconds()

        def set_value(self, key, value, time=None):
            if time is None: time = datetime.datetime.utcnow()

            timestamp = self.timestamp(time)

            self.redis_client.zadd(key, timestamp, '%d:%s' % (timestamp, value))

        def get_value(self, key, time=None):
            if time is None: time = datetime.datetime.utcnow()

            for item in self.redis_client.zrevrangebyscore(key, self.timestamp(time), 0, start=0, num=1):
                return item.partition(':')[2]
            return None

        def cleanup_before(self, key, time):
            self.redis_client.zremrangebyscore(key, 0, self.timestamp(time))