Here is a full working example using py-redis:
from redis import StrictRedis
cache = StrictRedis()
def clear_ns(ns):
    """
    Clears a namespace
    :param ns: str, namespace i.e your:prefix
    :return: int, cleared keys
    """
    count = 0
    ns_keys = ns + '*'
    for key in cache.scan_iter(ns_keys):
        cache.delete(key)
        count += 1
    return count
You can also do scan_iter to get all the keys into memory, and then pass all the keys to delete for a bulk delete but may take a good chunk of memory for larger namespaces. So probably best to run a delete for each key.
Cheers! 
UPDATE:
Since writing the answer, I started using pipelining feature of redis to send all commands in one request and avoid network latency:
from redis import StrictRedis
cache = StrictRedis()
def clear_cache_ns(ns):
    """
    Clears a namespace in redis cache.
    This may be very time consuming.
    :param ns: str, namespace i.e your:prefix*
    :return: int, num cleared keys
    """
    count = 0
    pipe = cache.pipeline()
    for key in cache.scan_iter(ns):
        pipe.delete(key)
        count += 1
    pipe.execute()
    return count
UPDATE2 (Best Performing): 
If you use scan instead of scan_iter, you can control the chunk size and iterate through the cursor using your own logic. This also seems to be a lot faster, especially when dealing with many keys. If you add pipelining to this you will get a bit of a performance boost, 10-25% depending on chunk size, at the cost of memory usage since you will not send the execute command to Redis until everything is generated. So I stuck with scan:
from redis import StrictRedis
cache = StrictRedis()
CHUNK_SIZE = 5000
def clear_ns(ns):
    """
    Clears a namespace
    :param ns: str, namespace i.e your:prefix
    :return: int, cleared keys
    """
    cursor = '0'
    ns_keys = ns + '*'
    while cursor != 0:
        cursor, keys = cache.scan(cursor=cursor, match=ns_keys, count=CHUNK_SIZE)
        if keys:
            cache.delete(*keys)
    return True
Here are some benchmarks:
5k chunks using a busy Redis cluster:
Done removing using scan in 4.49929285049
Done removing using scan_iter in 98.4856731892
Done removing using scan_iter & pipe in 66.8833789825
Done removing using scan & pipe in 3.20298910141
5k chunks and a small idle dev redis (localhost):
Done removing using scan in 1.26654982567
Done removing using scan_iter in 13.5976779461
Done removing using scan_iter & pipe in 4.66061878204
Done removing using scan & pipe in 1.13942599297