Telegram Group & Telegram Channel
Wide LRC codes

Я как-то писал в канале про Erasure Codes, в том числе про LRC, который в какой-то степени стал стандартом. Напомню, что про Erasure Codes можно думать как redundancy technique -- если у вас есть данные, их можно поделить на 2 части, посчитать xor, теперь при выпадении любой из 3 получившихся частей, мы можем восстановить данные полностью. В итоге потратили 1.5x места, но redundancy 2 (при выпадении любого 1 куска данные восстанавливаются). Если копать глубже, то дополнительные k частей получаются умножением на матрицу (n + k) x n над полем F_2 или F_256, а при выпадении любых k, матрицу можно обратить и восстановить данные. Вопрос в нахождении матрицы, но так получается, что k можно брать достаточно маленьким по сравнению с n и фактически можно достигнуть любой практической redundancy k потратив (1+eps) места. LRC идут дальше, они стараются группировать некоторые из n частей вместе, чтобы обращение матрицы было частичным -- скажем, поделим всё на 12 частей, у первых 6 посчитаем XOR, у вторых 6 посчитаем XOR, попробуем найти матрицу 16 x 12, где две строки это такие линейные преобразование и ещё 2, чтобы матрица была полностью обратима. Теперь если выпал один чанк данных, то можно скачать 6 других восстановить по XOR, если два чанка в двух разных группах, то тоже всё сработает, а если выпало 3 или 2 в одной группе, ну что ж поделать, скачаем всё и обратим матрицу. Но такие случаи реже случаются, поэтому инженерия любит такое дело. Такие группы называют локальными группами, а дополнительные чанки у локальных групп -- локальные чанки, а дополнительные чанки для всей операции -- глобальные чанки.

На FAST'23 вышла статья в Google про широкие LRC коды. Это такие коды, которые делят на очень много частей, чтобы получить большую redundancy и потратить поменьше места. Холодный storage может делить данные на сотни частей и делать всего десятки дополнительных чанков получая redundancy в 6-7 c оверхедом на весь сторадж процентов в 10% (например, (96, 4, 5) делит на 96 частей, бьёт на 4 локальные группы с 5 глобальными чанками). Хоть и теория кодов очень хорошо изучена, на практике становится слегка сложно с балансом двух вещей

* Находить обратимые матрицы с свойствами локальных чанков
* Сделать операции локальных чанков достаточно простыми, скажем, обычный XOR ок, но что-то сложнее уже слегка путает инженеров. Простота также полезна для миграций -- можно ли как можно больше посчитанных чанков сохранить

Обычно LRC коды изучают как сделать операции над локальными чанками. Статья от Google показывает, что можно сделать слегка лучше -- смотреть на локальные группы как функцию не только от изначальных данных, но и от глобальных чанков, а можно также смотреть как на функцию от данных, глобальных и локальных. Так становится чуть проще размазать локальные чанки по всем данным. Определение и трюк слегка self-referential в том плане, что локальные чанки определяются через локальные, но статья считает некоторую математику, которая сходится.

Зачем это надо?

В статье можно увидеть только слегка лучше результаты по метриками redundancy, average cost of repair и тд. Цифры не ахти в сравнении и никакой супер революции этот LRC метод не привносит. Он рассказывает историю как продвинуть рисёрч слегка дальше по достаточно практичной теме как LRC коды.

Keep on pushing, статья рассказывает хорошую историю.

https://www.usenix.org/system/files/fast23-kadekodi.pdf
https://www.youtube.com/watch?v=pfnSYWEf5q4



group-telegram.com/experimentalchill/244
Create:
Last Update:

Wide LRC codes

Я как-то писал в канале про Erasure Codes, в том числе про LRC, который в какой-то степени стал стандартом. Напомню, что про Erasure Codes можно думать как redundancy technique -- если у вас есть данные, их можно поделить на 2 части, посчитать xor, теперь при выпадении любой из 3 получившихся частей, мы можем восстановить данные полностью. В итоге потратили 1.5x места, но redundancy 2 (при выпадении любого 1 куска данные восстанавливаются). Если копать глубже, то дополнительные k частей получаются умножением на матрицу (n + k) x n над полем F_2 или F_256, а при выпадении любых k, матрицу можно обратить и восстановить данные. Вопрос в нахождении матрицы, но так получается, что k можно брать достаточно маленьким по сравнению с n и фактически можно достигнуть любой практической redundancy k потратив (1+eps) места. LRC идут дальше, они стараются группировать некоторые из n частей вместе, чтобы обращение матрицы было частичным -- скажем, поделим всё на 12 частей, у первых 6 посчитаем XOR, у вторых 6 посчитаем XOR, попробуем найти матрицу 16 x 12, где две строки это такие линейные преобразование и ещё 2, чтобы матрица была полностью обратима. Теперь если выпал один чанк данных, то можно скачать 6 других восстановить по XOR, если два чанка в двух разных группах, то тоже всё сработает, а если выпало 3 или 2 в одной группе, ну что ж поделать, скачаем всё и обратим матрицу. Но такие случаи реже случаются, поэтому инженерия любит такое дело. Такие группы называют локальными группами, а дополнительные чанки у локальных групп -- локальные чанки, а дополнительные чанки для всей операции -- глобальные чанки.

На FAST'23 вышла статья в Google про широкие LRC коды. Это такие коды, которые делят на очень много частей, чтобы получить большую redundancy и потратить поменьше места. Холодный storage может делить данные на сотни частей и делать всего десятки дополнительных чанков получая redundancy в 6-7 c оверхедом на весь сторадж процентов в 10% (например, (96, 4, 5) делит на 96 частей, бьёт на 4 локальные группы с 5 глобальными чанками). Хоть и теория кодов очень хорошо изучена, на практике становится слегка сложно с балансом двух вещей

* Находить обратимые матрицы с свойствами локальных чанков
* Сделать операции локальных чанков достаточно простыми, скажем, обычный XOR ок, но что-то сложнее уже слегка путает инженеров. Простота также полезна для миграций -- можно ли как можно больше посчитанных чанков сохранить

Обычно LRC коды изучают как сделать операции над локальными чанками. Статья от Google показывает, что можно сделать слегка лучше -- смотреть на локальные группы как функцию не только от изначальных данных, но и от глобальных чанков, а можно также смотреть как на функцию от данных, глобальных и локальных. Так становится чуть проще размазать локальные чанки по всем данным. Определение и трюк слегка self-referential в том плане, что локальные чанки определяются через локальные, но статья считает некоторую математику, которая сходится.

Зачем это надо?

В статье можно увидеть только слегка лучше результаты по метриками redundancy, average cost of repair и тд. Цифры не ахти в сравнении и никакой супер революции этот LRC метод не привносит. Он рассказывает историю как продвинуть рисёрч слегка дальше по достаточно практичной теме как LRC коды.

Keep on pushing, статья рассказывает хорошую историю.

https://www.usenix.org/system/files/fast23-kadekodi.pdf
https://www.youtube.com/watch?v=pfnSYWEf5q4

BY Experimental chill


Warning: Undefined variable $i in /var/www/group-telegram/post.php on line 260

Share with your friend now:
group-telegram.com/experimentalchill/244

View MORE
Open in Telegram


Telegram | DID YOU KNOW?

Date: |

Apparently upbeat developments in Russia's discussions with Ukraine helped at least temporarily send investors back into risk assets. Russian President Vladimir Putin said during a meeting with his Belarusian counterpart Alexander Lukashenko that there were "certain positive developments" occurring in the talks with Ukraine, according to a transcript of their meeting. Putin added that discussions were happening "almost on a daily basis." Such instructions could actually endanger people — citizens receive air strike warnings via smartphone alerts. On December 23rd, 2020, Pavel Durov posted to his channel that the company would need to start generating revenue. In early 2021, he added that any advertising on the platform would not use user data for targeting, and that it would be focused on “large one-to-many channels.” He pledged that ads would be “non-intrusive” and that most users would simply not notice any change. Oleksandra Matviichuk, a Kyiv-based lawyer and head of the Center for Civil Liberties, called Durov’s position "very weak," and urged concrete improvements. Ukrainian President Volodymyr Zelensky said in a video message on Tuesday that Ukrainian forces "destroy the invaders wherever we can."
from us


Telegram Experimental chill
FROM American