Небольшой отчет о статусе akumuli. Итак, я реализовал всю основную функциональность.
Запись - работает, пропускную способность по записи я особо изощренно не тестировал, на моем старом ноутбуке, akumuli может прожевать порядка 3х миллионов insert-ов в секунду (и прочитать их потом назад, что немаловажно). На нормальном железе - заметно больше. Это все благодаря тому, что akumuli трансформирует случайную запись в последовательную запись, с которой у современных железок все очень хорошо и замечательно. В будущем производительность будет ниже, так как ей придется немного пожертвовать ради повышения отказоустойчивости. До сих пор не реализованы некоторые важные вещи, например синхронизация чтения и записи при перезаписи старых данных.
Поиск - тоже работает. Он требует оптимизаций (оптимизация с помощью mincore еще не реализована), но корректно ищет все что нужно. Возможно стоит реализовать простой планировщик запросов, например, на основе алгоритма FSCAN.
Я серьезно переработал in-memory индекс для данных, не вышедших за пределы sliding window. Теперь он основан не на B-tree, а на алгоритме patience sort. Подробно с алгоритмом можно ознакомиться в википедии. Если коротко, то все работает примерно так - в начале у нас есть пустой массив, элементами которого являются sorted runs - отсортированные в порядке увеличения меток времени массивы. Когда записывается первый элемент, в этот массив добавляется единственный sorted run из одного, только что добавленного, элемента. Далее, при записи следующего элемента, мы смотрим на его метку времени и, если она больше или равна метке времени предыдущего элемента, то этот элемент добавляется в тот же sorted run, если она меньше - то создается еще один sorted run. Далее, процесс повторяется для каждого последующего элемента, в результате чего, мы получаем набор отсортированных массивов. Их не может быть очень много, так как глубина записи ограничена sliding window. Эти массивы и есть индекс. Когда нужно слить всю информацию на диск (данные вышли за пределы sliding window), они сливаются с помощью простого k-way merge-а, очень быстро и эффективно. В этих массивах можно легко искать простым бинарным поиском, запись в такой индекс происходит быстрее чем запись в b-tree, даже на самых неудобных данных.
В ближайшее время я планирую реализовать синхронизацию между чтением и записью и оптимизировать поиск. После этого, возможно, у меня дойдут руки до whitepaper-а по системе.
Запись - работает, пропускную способность по записи я особо изощренно не тестировал, на моем старом ноутбуке, akumuli может прожевать порядка 3х миллионов insert-ов в секунду (и прочитать их потом назад, что немаловажно). На нормальном железе - заметно больше. Это все благодаря тому, что akumuli трансформирует случайную запись в последовательную запись, с которой у современных железок все очень хорошо и замечательно. В будущем производительность будет ниже, так как ей придется немного пожертвовать ради повышения отказоустойчивости. До сих пор не реализованы некоторые важные вещи, например синхронизация чтения и записи при перезаписи старых данных.
Поиск - тоже работает. Он требует оптимизаций (оптимизация с помощью mincore еще не реализована), но корректно ищет все что нужно. Возможно стоит реализовать простой планировщик запросов, например, на основе алгоритма FSCAN.
Я серьезно переработал in-memory индекс для данных, не вышедших за пределы sliding window. Теперь он основан не на B-tree, а на алгоритме patience sort. Подробно с алгоритмом можно ознакомиться в википедии. Если коротко, то все работает примерно так - в начале у нас есть пустой массив, элементами которого являются sorted runs - отсортированные в порядке увеличения меток времени массивы. Когда записывается первый элемент, в этот массив добавляется единственный sorted run из одного, только что добавленного, элемента. Далее, при записи следующего элемента, мы смотрим на его метку времени и, если она больше или равна метке времени предыдущего элемента, то этот элемент добавляется в тот же sorted run, если она меньше - то создается еще один sorted run. Далее, процесс повторяется для каждого последующего элемента, в результате чего, мы получаем набор отсортированных массивов. Их не может быть очень много, так как глубина записи ограничена sliding window. Эти массивы и есть индекс. Когда нужно слить всю информацию на диск (данные вышли за пределы sliding window), они сливаются с помощью простого k-way merge-а, очень быстро и эффективно. В этих массивах можно легко искать простым бинарным поиском, запись в такой индекс происходит быстрее чем запись в b-tree, даже на самых неудобных данных.
В ближайшее время я планирую реализовать синхронизацию между чтением и записью и оптимизировать поиск. После этого, возможно, у меня дойдут руки до whitepaper-а по системе.
Комментариев нет:
Отправить комментарий