как вручную замепить триллион строк на целые числа?

Какой вид нагрузки на базу нужен - один раз записал и далее только чтение, или смешанные запись-чтения?

смешанные

Петабайтная мапка? Пффф... Фигня. Тут на лоре все таким в старших классах школы занимались.

cast superhackkiller1997

Если операций чтения достаточно мало, то можно сделать просто сортированный файл. Если примерно поровну, то файл с записями + индекс.

Хотя в любом случае лучше не изобретать велосипед, а взять, например, реализацию dbf или sqlite или berkeley DB.

Тогда лучше забить, ибо всё будет не очень просто. В первом приближении будет распределённый хеш

hash(blob) -> storage
hash(blob) -> (hash, value, blob)

Уже на конкретной ноде можно взять готовое k/v хранилище вроде gdbm или leveldb.

Или делать самому если всё нужно своими руками. Например, импровизированную хеш таблицу на файлах + отдельное хранилище блобов на локальной машине с индексом. Тогда

hash2(hash(blob)) -> [ (hash, key, seq, offset, size) ]
+ большой файл с конкатенированными строками

В обратном направлении всё примерно тоже самое:

key -> [ (storage, hash, seq) ]

Проблемы начинаются когда нужно будет собирать мусор (обрабатывать операции удаления - периодически компактить блоб со строками), делать перебалансировку (менять разбиение хеша по нодам) и обеспечивать избыточность. Кластер получится не очень маленьким, на сотни машин, потому без избыточности будет относительно часто находиться в поломанном виде. Либо придётся выкладывать много $ на хорошое SAN.

ок а как ты предлагаешь получить отсортированный файл на таких числах?

Уже на конкретной ноде можно взять готовое k/v хранилище вроде gdbm или leveldb.

интересен собственно опыт создания велосипедов

ок а как ты предлагаешь получить отсортированный файл на таких числах

Когда у меня была похожая задача (правда у меня было всего гигов 30-40), то я просто делал каталоги на каждый префикс (1-2 буквы). Если какой-то файл дорастал до гигабайта, то файл разбивался на пачку каталогов аналогичной структуры.

Далее два прохода:

1. Раскидывание по файлам по префиксам, разбивка файлов на подкаталоги

2. Сортировка каждого файла в памяти обычным quicksort'ом

Если надо возможность быстрой вставки, то единственной, что приходит в голову: под запись изначально выделять по 10Кб. И хранить там несколько элементов. Тогда перезапись файла (одного) будет требоваться только если блок заполнится полностью. Но неэффективно расходуется место.

Ну или единицу дробления по файлам сделать в десяток мегабайт и для вставки перезаписывать файл целиком.

hm. ok. над этим нужно подумать

интересен собственно опыт создания велосипедов

Все эти либы с открытым кодом и некоторые даже с документацией и описанием принципов работы - бери и смотри. Есть ещё книжка The Architecture of Open Source Applications, там есть раздел про Berkeley DB.

это будет то что нужно

http://fallabs.com/kyotocabinet/

тож благодарность - интересно