Додумается до чего, лок за тебя сделать? Конечно, не «додумается» додумывать за тебя через libastral желаемые операции. Лучше файл немного перестроить и корень держать вначале, т.е. примерно как обычно дерево кучи хранят.

Додумается до чего, лок за тебя сделать?

Вдруг у него какой-то профилировщик будет что мол, страницу выгрузил уже 100500 раз, а она нужна сразу же. Ну я понял короче, многого хочу и будет накладно такое содержать.

Думаю перестроить именно так тяжеловато будет, так как файлы громадные и формируются потоками, сливаются через merge двух отсортированых тоже солидного размера. Проще mlockов натыкать. А собственно если я натыкаю mlockов на какую-то часть верхушки дерева, то чем это хуже heap-подобной структуры с одним mlock?

А собственно если я натыкаю mlockов на какую-то вершину, то чем это хуже?

mlock на вершину может захватить с собой не только вершину, но ещё и ненужные куски если их много помещается на страницу. Память будет расходоваться менее эффективно, чем больше кусков влезает на страницу тем менее полезно. А так можно было бы залочить несколько десятков-сотен мегабайт подряд и был бы 100% профит от этого.

$getconf PAGESIZE
4096

Не, да у меня наверное и один блок побольше будет

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

Да я все в cgroup запихну, чтобы память ограничивать, так вот там кеш заполнится очень быстро на ура. Хотелось бы верхушку держать в памяти. Да, буду пробовать

До mlock ОС, естественно, не додумается. Но, если страница с корнем дерева будет достаточно горячей, она постоянно будет в кэше.

Где описаны критерии приоритезации вытеснения страниц кроме сорцов ядра?

Конкретно Linux - ХЗ, общие принципы - в учебнике по системному программированию. Очень подозреваю, что «приоритезация» страниц сведется к обычному LRU.

Конкретно Linux - ХЗ

Я тоже :D

Очень подозреваю, что «приоритезация» страниц сведется к обычному LRU.

Если так, то ее кроме всяких memory pressure corner case никогда не вытеснят. Думал есть статейка. Думаю лучше таки пробовать

Не, да у меня наверное и один блок побольше будет

Ну тогда нет особого смысла перестраивать. Мб есть смысл через posix_fadvise() сказать что будешь рандомно читать.

Можно верхушку (ключи) в памяти кешировать. Так делают с корневым узлом b-tree. LRU удобно заимплементить с помощью boost::bimap.

Да я если я прото тупо влеплю mlock, то оно и так его закеширует, зачем что-то городить?

Такой подход будет работать везде. Даже на виндоуз.

Будет п-ц тормозить. Индекс отдельно хранить можешь?

Согласно Роберту Лаву и mm/filemap.c (см. add_to_page_cache_lru()), там LRU.

Круто, спасибо

Это и есть индекс, просто ключи большие. Он еще двухярусный, там отдельный binary (или linear prefix compressed) search внутри блока. Данные - отдельный файл и mmap.

А чего вдруг будет тормозить?

Очевидно что поиск будет бить в средину всегда.

ага. Один раз. А дальше рандом.

Не взлетит.

Хотелось бы верхушку держать в памяти.

она и так будет в памяти, забей. Я пробовал, не осилил. Системе виднее.

ага. Один раз. А дальше рандом.

Есть основание полагать что один поиск полностью влезет в память. Может быть даже 10 поисков. Но циркулировать могут только низы, с верхушки поиск будет начинаться всегда, вот и обсуждаем mlock

Если поиск на HDD, то нужно будет logN позиционирований головки в среднем на 1 случайный поиск. Интерполяционный бинарный поиск снизит до константы.

А что конкретно неосилил? Предлагаемый подход очевидный как пень. Взять центр, потом четверти, потом 1/8 и так до определенного лимита все скормить в mlock. Если я так mlockну например 20 MB памяти, то можешь представить насколько дохрена это 5000 pagesize. А это неслабый кусок верхушки может быть

Можно его попробовать когда выскочишь с верхушки в памяти. А верхушка может быть обычным binary, так как нужна предсказуемость позиций

Есть основание полагать что один поиск полностью влезет в память.

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

Но циркулировать могут только низы, с верхушки поиск будет начинаться всегда, вот и обсуждаем mlock

в бинарном дереве только низы и есть (50% на нижнем уровне, 75% на двух нижних, 87.5% на трёх нижних уровнях, и т.д.). Т.ч. если в дереве больше пяти уровней(>32 узлов), то кеширование не имеет смысла. Т.к. всё внизу.

А это неслабый кусок верхушки может быть

ну говорю же — не взлетит. Число узлов дерева растёт экспоненциально, потому закешировать можно только несколько процентов пути. Смысл? Т.е. если у тебя 20 прыжков, ну закешируешь ты 5 прыжков, а 15 у тебя так и будут тупить. HDD на рандоме тупит не по детски, потому толку от кеширования верхушки никакого. Ну закешируй конечно, если не веришь.

Но лучше сначала посчитай. Сколько у тебя уровней в бинарном дереве?

Ответ на комментарий:

Быть троллем на самом деле очень просто и легко.

Да какой ты тролль, ты просто хронический школьник и долбоёб. Забавно смотреть как ты свою глупость пытаешься оправдать троллингом.

Взять центр, потом четверти, потом 1/8 и так до определенного лимита все скормить в mlock

...и пускать программу от рута

Обижаешь, в cgroups

...и пускать программу от рута

или открыть для себя capabilities

или открыть для себя capabilities

никто не станет их открывать

Обижаешь, в cgroups

В cgroups mlock разрешен всем подряд?

Вот это я не проверил, кстати схрена ли non-root юзеры не могут лочить страницы? Я конечно понимаю сценарии когда это может помешать, но вроде можно было бы придумать решение получше, чем просто не давать использовать mlock

Если не будет работать, то таки прийдется руками кешировать

кстати схрена ли non-root юзеры не могут лочить страницы?

ЕМНИП, они могут лочить немного, но сомневаюсь, что по дефолту это 20М.

Ну если есть CAP_IPC_LOCK, то это же true/false, не?

Можно ещё заоптимизячить лукап последних мегабайт 1-8 последовательным чтением. При блоке около 4к это будет ещё минус 8-11 уровней. И если ещё забить в память 1гб (~16-18 уровей), то 28 сиков снизятся до 3-4

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

Ну короче если там LRU, то я думаю бояться не стоит. Damage от простого mlock по мере возможности с игнором ошибки будет минимальный

Ну если есть CAP_IPC_LOCK, то это же true/false, не?

есть ещё ulimit -l, хз как оно будет работать в твоём случае

Это и есть индекс, просто ключи большие. Он еще двухярусный, там отдельный binary (или linear prefix compressed) search внутри блока. Данные - отдельный файл и mmap.

Ну вот чем лучше локальность данных индекса у тебя будет, тем быстрей будет работать поиск.

А чего вдруг будет тормозить?

TLB порвёт, pipeline будет стоять. Если ещё и код не влезает в iTLB, то ваще катастрофа.

Если индекс, в основном, read only, то лучше вообще его метнуть на hugetlbfs и ммапить там. Если надо время от времени индекс сохранять в более надёжное место, чем оперативка, то делаешь форк процессу, и сохраняешь индекс в чайлде. Только ммап приватный должен быть.

А что собственно мешает явно _скопировать_ эти блоки в память?

Можно и так

верхушка дерева в памяти-то осядет...

...но таки будь мужиком, запили b-tree.

лишнее копирование?

можно и линейным поиском

но для случая невлезания индекса в память бородатые дядьки ещё лет 40 взад придумали b-tree.

бородатые дядьки ещё лет 40 взад придумали b-tree

ТС же не полностью описал задачу. Для некоторых паттернов - много обновлений, мало вставок и совсем мало чтений, btree не очень. LSM-tree предпочтительнее. Да вон даже в SQLite4 бэкенд уже на LSM, не на btree

Можно предположить что 1Т индексов это от каких-то социальных/телекоммуникационных данных (после map/reduce), то есть как раз такой паттерн и есть. Если ТС-а устраивает не очень быстрое чтение в обмен на быстрое обновление, почему бы иногда и не похрустеть жестким диском?

Это lsm. Я говорю о одной sstable

Обновление ключей индекса? 8-0

Новое слово в информатике...

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

Я говорю в не первом in-memory дереве, а о последующих иммутабельных

LSM-tree придумали для быстрой вставки/обновления/удаления, если что. Рандомное чтение - худший случай для этой структуры данных.

Индекс на диске плохо хранить в отсортированном массиве — b-tree значительно лучше.

Допустим, размер ключа — 128 байт. Каждое чтение с диска поднимает 128КБ (наверное, это где-то можно подкрутить — не специалист в линуксах). Постепенно 124КБ может вытесниться, но из-за одного «горячего» ключа рядом в памяти будет болтаться ещё 4КБ предположительно ненужных.

В SSTable предполагается, что *все* индексы находятся в памяти.