PHP isn’t a language I have much experience with, but as I understand it both loops are trying to filter the set of keys, so you can extract the structure of the loop into another method that accepts the conditions for filtering as an argument in the form of a function:

private function getKeysWhere($entity, $allKeys, $condition)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY ||
                    $key_type == self::CUSTOM_KEY ||
                    $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

This requires you use PHP 5.3 or above, in order to do things like pass functions as arguments and declare anonymous functions.

This is much more general and powerful than a boolean flag, because instead of picking between two set conditions, you can move the logic for whether to include the key into a separate function and separate the concern of filtering the keys from the concern of what conditions to filter them by.

Now, we define what the conditions for a key to invalidate on modification and on creation are as private helper methods:

private function keyIsInvalidOnCreation($key) {
    return strpos($key, 'id:') === false;
}

private function keyIsInvalidOnModification($key, $modifiedId) {
    return strpos($key, 'id:') === false || strpos($key, 'id:'.$modifiedId) !== false;
}

And finally, we can define our two methods to get invalid keys in terms of this general method and these two predicates:

public function getKeysToInvalidateOnCreation($entity, $allKeys) {
    return getKeysWhere($entity, $allKeys, 'keyIsInvalidOnCreation');
}

public function getKeysToInvalidateOnModification($entity, $allKeys, $modifiedId) {
    return getKeysWhere($entity, $allKeys, function($key) use ($modifiedId) {
        return keyIsInvalidOnModification($key, $modifiedId)
    });
}

The case for modification needs to be wrapped in an anonymous function in order to properly pass in $modifiedId to the predicate and turn it into a function of one argument to work with getKeysWhere. If you’re using a library with support for common functional programming tools such as currying and partial application, you can use that here as a cleaner alternative to the anonymous function wrapper. Not sure how possible some of that stuff is in PHP though.

This is fairly heavily decomposed and may be difficult to grok if you’re not familiar with functional programming patterns, but it cuts down on the duplication and generalizes well.

So just for other PHP guys that may be struggling with functional programming I want to register here the steps I did following Jack’s answer.

First I refactored each method to extract the condition so I could have an identical code base in both (note how the condition was extracted in both):

public function getKeysToInvalidateOnCreation($entity, $allKeys)
{
    $condition = function($key) {
        return strpos($key, 'id:') === false;
    };
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

public function getKeysToInvalidateOnModification($entity, $modifiedId, $allKeys)
{
    $condition = function($key) use ($modifiedId) {
        return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
    };
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

private function keyIsInvalidOnModification($modifiedId, $key)
{
    return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
}

private function keyIsInvalidOnCreation($key)
{
    return strpos($key, 'id:') === false;
}

At these moment, all tests are still green, so I can proceed to extract the common code to a private method:

public function getKeysToInvalidateOnCreation($entity, $allKeys)
{
    $condition = function($key) {
        return strpos($key, 'id:') === false;
    };
    return $this->getKeysToInvalidate($entity, $allKeys, $condition);
}

public function getKeysToInvalidateOnModification($entity, $modifiedId, $allKeys)
{
    $condition = function($key) use ($modifiedId) {
        return strpos($key, 'id:') === false || strpos($key, 'id:' . $modifiedId) !== false;
    };
    return $this->getKeysToInvalidate($entity, $allKeys, $condition);
}

private function getKeysToInvalidate($entity, $allKeys, callable $condition)
{
    $result = [];
    foreach ($allKeys as $key) {
        $entities_in_key = explode('+', substr($key, 0, strpos($key, '_')));
        $key_type = substr($key, strrpos($key, '_'));
        foreach ($entities_in_key as $entity_in_key) {
            if ($entity_in_key == $entity) {
                if ($key_type == self::GET_ALL_KEY || $key_type == self::CUSTOM_KEY || $condition($key)) {
                    $result[] = $key;
                }
            }
        }
    }
    return $result;
}

And everything still green. Thanks Jack