Ага, именно потому, что это уровень обычной лабораторной работы, так делают pinterest, instagram, tumblr и ещё куча других высоконагруженных систем. Там просто, наверное, парни не осилили уровень "дипломной работы"...
Ой, ну какое нафиг key-value и NoSQL. NoSQL и key-value оно было бы, если бы я как минимум порекомендовал настроить кеширование через redis, memcache и т.д., а тут всё традиционно - ни малейшего шанса нарушить целостность, ни каких противоречий с ACID. На всех узлах стоит обычная реляционная СУБД, просто сервер приложений или прокси или клиент сами раскидывают запросы по ним.

Узнай у руководителя, что он хочет. Я в этой теме отписываться больше не буду, т.к. точку зрения свою уже полностью обозначил.

Ну, короткий ответ - любые. В зависимости от вашей типичной нагрузки и выбирается функция для шардинга. Вот у tumblr пример как это работает в презентации есть (хоть и на MySQL :) ) http://assets.en.oreilly.com/1/event/74/Massively Sharded MySQL at Tumblr Presentation.pdf

Просто, когда всё уже совсем плохо и даже одна таблица больше не помещается на диске, других вариантов особо и нет, кроме как разбить её. И очень часто действительно можно разбить БД на кучу никак не связанных друг с другом подмножеств. Например, есть база каких-нито покупок в интернет магазине. Клиентов куча, у всех есть история, предпочтения, что покупали, что купят и т.д. Можно разбить всё так, что на каждой отдельной машине хранится абсолютно всё, но только по подмножеству клиентов. Когда мы запрос выполняем, мы знаем где данные лежат или будут лежать. Никакие двухфазовые коммиты тут не нужны.
Часто, если есть возможность предвидеть какие нагрузки будут выполняться в системе, можно обойтись таким решением. Тут нет проблем в получении всех пользователей из страны X, покупавших товар B, зарегистрировавшихся после дня Y и т.д. Ну а для запросов, по конкретному пользователю - тут вообще всё ясно.
А вот когда уже нужно какие-то серьёзные аналитические вещи выполнять - например, выбрать топ100 самых "щедрых" покупателей - где есть группировки, сортировки и д.р. люди предпочитают использовать узкоспециализированные NoSQL решения, т.к. иначе придётся свою какую-то логику по слиянию результатов с нескольких узлов писать нетривиальную.

Преимущества такой архитектуры - она shared nothing, т.е. масштабируется вообще на ура. Но, действительно, не всё можно представить в таком виде (особенно, повторюсь, это касается OLAP). Функциональное разбиение, с другой стороны, совсем плохо масштабируется. 1) накладывает определяемое аппаратурой ограничение размера таблиц и 2) намного чаще требует взаимодействия двух и более серверов БД. Хотя это и правда, что если функционально разбить БД, на ней можно без каких-либо хитростей делать более сложные запросы, но они будут проходить очень медленно.

А теперь вернусь к вашему key-value... ну это никак не key-value, тот подход который я описал. Хотя да, сложные запросы требуют более сложной логики. Но большинство OLTP вещей будут нормально работать.
В key-value в понимании NoSQL ссылочная целостность не предусмотрена. А здесь все зависимости, необходимые для подмножества пространства идентификаторов присутствуют на том же узле, т.к. целостность гарантируется уровнем СУБД.

Ладно, уговорили, я верю, что вы все разработали системы, которыми пользуются сотни миллионов человек и спорить с вами на эту тему не имеет смысла. Больше не буду.