Может быть я становлюсь тупой, но я задачи не понимаю:
авторЕсть кэш, элементы в нем запрашиваются с разной частотой, и элементы устаревают.
Например по ключу "А" идет 100 запросов в минуту, а по ключу "Б" всего 2.

понятно

авторКаждый раз когда кэш возвращает устаревшее (неверное) значение - мы засчитываем ему ошибку.

Понятно наполовину, "кэш возвращает устаревшее (неверное) значение" - предполагаю, что понимаю
"неверное значение - мы засчитываем ему ошибку" - не понимаю. Откуда мы знаем, что значение не верное? Для этого мы должны знать оба значения и то, которое вернул кэш и правильное, что бы их сравнить. Он если мы знаем правильное, то почему-бы его и не возврашать?

авторПоэтому если оба ключа устареют - по "А" будет засчитано 100 ошибок в минуту, а по ключу "Б"
всего 2 ошибки.

Вот это уже вне моего понимания, обычно кэш обновляет се6я (на то он и кэш). Если кэш понимает, что данные "устарели" или "неверные", то кол-во "ошибок" / "промахов" ни как не связано с частотой запроса данных

Запросили элемент A, вернули старый, обновили элемент A - одна ошибка
Запросили элемент B, Вернули старый, обновли элемент B - одна ошибка
Еще 99 раз запросили элемент A, вернули обновленную версию - ошибки нет

IMHO & AFAIK

P.S. вроде исходный вопрос при первом прочтении и понятен, но при втором - становится не понятно совершенно. Попытаюсь погадать на хрустальном шаре.

1) Т.к. если кеш и получатель результата имеет доступ к внешним данным (можем их сравнить и понять факт ошибки) - то по самой природе кеша, что обычно под этим понимается, проблемы нет.

2) Частота ошибок никак не связана с кол-вом запросов, максимум с частотой обновления информации в БД.

3) Если у нас не стандартный кеш, а некоторый Read Ahead Buffer ))) и у нас отсутвует или усложнен доступ к внешним данным (например внешний поставшик, у которого данные купили/воруем через I-net), то совершенно не понятно, как мы определяем факт "ошибки"

3.1. факт ошибки мы определить НЕ можем. Только "эмперически" отдельными эксперементами не связанными с эксплуатацией, но это вроде противоречит описанию проблемы в исходном посте
3.2. понятно, что должны найти некоторый баланс между двумя взаимо исключающими ситуациями:
a) уменьшить объем данных получаемых с внешнего источника. Можно уменьшить частоту опроса. Но здесь мы должны базироваться не на "частоте запросов/статистику кеша", а на "кол-во обновлений данных в БД/статистику источника данных"
b) уменьшить объем ситуаций (увеличить актуальность), когда мы выдаем получателю некорректные данные. Те данные, которые запрашивают чаще, так же чаще обновлять.
Но здесь принципиально, что мы НЕ можем в момент отдачи понять, актуальные у нас данные или ошибка. Т.к. если бы могли, то и проблемы бы не было )))

c) Объединяя a+b вмести, уменьшить "убытки" от выдачи неактуальной информации.

Чисто арифметически, если у нас есть 101 пользователь, 100 пользователей запрашивающие информацию A и 1 запрашивающий информацию B ==> то выгоднее вообще B послать лесом ))) т.к. уменьшив кол-во пользователей на < 1%, мы сэкономим затраты на 50%. Если все "платят" одинаково, то чистая прибыл вырастит так же практически в 2 раза ))) Но это чисто арифметически ))) Практически, возможно, что именно информация B и является "бизнес критикал", "ценной" и "know how". Т.ч. исключив ее, мы потеряем ни одного пользователя, а всех ))).

В общем, в универсальный алгортм не верю. А проблема баланса, выглядит бизнес моделью, чем каким либо програмным алгоритмом.

Общую формулу вывести легко. На уровне арифметики 3-4 класса средней школы:

прибыл = доходы /удовлетворенные клиенты/ - расходы /запросы данных/ - убытки, штрафы за неправильный ответ от не удовлетворенных клиентов
собрав статистику ошибок и обращений - можно понять процент ошибок по разным ГРУППАМ товаров / данным. См. ABC анализ в складской деятельностью.
рентабельность = оборот / прибыл
ну и некоторая показатель качества бизнеса. Качество = все возможные доходы (удовлетворенные клиенты + возможная прибыль от если бы неудовлетворенных клиентов считать удовлетворенными) / реальные доходы (удовлетворенные клиента - убытки от неудовлетворенных клиентов).

Задача максимизировать рентабельность и качество услуг )))

IMHO & AFAIK

privateХмм, никто не понял..., может я действительно неверно описал... :)

Мы создали зеркало (копию) википедии. В википедии есть страница про "Бритни Спирс" с посещаемостью 100хитов/мин, и про "Садоводство" с посещаемостью 2хита/мин....
Я понял.

См. мой ответ. Разделить все странички по группам в соответствие с ABC-анализом.

Нужно оперировать предположениями о бизнес-ценности информации + желательно оперативно получать информацию о частоте изменении информации на википедии.

Предположим, что просмотр Бритни Спирс приносит кучу дохода, а Садоводство мало. То первую отправляем в группу A, вторую в группу B. НО если страничка о садоводстве меняется раз в день, а о Бритни Спирс меняется раз в год - то несмотря на принадлежность к группе A, ее можно проверять реже.

Пример про бизнес-ценность:

privateВ яндексе и гугле должны знать как это делать, они-же тоже планируют обход сайтов по времени, у них тоже задача минимизировать ошибки. :)
У них задача - заработать бабла. БАБЛА КАРЛ. Уверяю Вас, на ошибки - им глубоко пофиг.