proki (proki) wrote in programmer_il,
proki
proki
programmer_il

задача на оптимизацию

Что то я отупел, не могу решить практическую задачку.
Условия следующие: резервное копирование (גיבוי) базы данных можно делать 2 способами - полностью и только дельту относительно последнего полного копирования. Надо оптимизировать процесс, чтобы объём копирования был минимальным.
Например сейчас объём базы (В) 3000М, объём дельты (D) - 100М. Т.е. объём D1 - 100M, D2 - 200M, D3 - 300M и.т.д. до очередного полного копирования. Понятно, что чем больше делать дельт то тем меньше будет полных копирований, но при этом одна и та же инфа копируется многократно (с каждой дельтой) поскольку дельта берётся относительно последнего полного копирования.
Несколько замечаний:
1. интервал между дельтами неважен, поскольку даётся её объём
2. советы по поводу изменения системы копирования нерелевантны
Tags: math
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

  • 8 comments
можно, к примеру, создать временную таблицу для хранения ключей всех временных дельт, созданных после создания очередной полной копии. И для каждой последующей дельты делать лефт джойн с этой таблицей, брать в новую дельту только записи, которых еще нет во временной таблице.
Смотрите замечание №2.
К этой задаче надо отнестись исключительно в математической плоскости.

d_ohrenelli

March 29 2016, 09:38:21 UTC 1 year ago Edited:  March 29 2016, 09:42:23 UTC

Это арифметическая прогрессия.

Пусть F= полный бекап
Пусть D = дельта.
Пусть M = количество циклов бекапа за, допустим, год.
Пусть N = количество инкрементальных апдейтов в одном цикле бекапа.

Тогда сумма скопированных данных за один цикл инкрементального апдейта и один начальный будет
F + D*(2*0 + N - 1)/2 (по формуле суммы арифметической прогрессии)

Тогда за год мы перетащим M * (F+D*(2*0 + N -1)/2)

Очевидно, что M зависит от N. Выразите M через N, получите полином второй степени с которым можно работать.

Нечто подобное я уже сделал, но ответа не получил, вернее получил что нет корней уравнения. Между тем, из общих соображений минимум должен быть достижим и зависит от параметров. Для этого я и дал примерные параметры. Так что, если вам интересно - попытайтесь решить, мне не удалось.
Замечание: я использовал также условие что М * N = const

d_ohrenelli

March 29 2016, 10:52:02 UTC 1 year ago Edited:  March 29 2016, 11:00:53 UTC

В том то и дело, что М*N - не константа. Константа это М+N. ( и я забыл в сумме прогрессии умножить на количество членов, позор мне)


Допустим, что мы делаем 1000 бэкапов за какой-то промежуток времени и каждый раз можем выбирать - инкрементальный это бэкап или нет.Так же допустим, что мы хотим, чтобы во всех наших циклах n было одинаковым.

Тогда получаем M+N = 1000 --> М = 1000 - N

Имеем, подставляя: (1000 - N) * (3000+N * 100*(N -1)/2) это сумма переданных данных.

Найдем размер средней передачи, который мы, собственно, и пытаемся минимизировать (поделим на н) и заменим н на х чтобы гугл нам все нарисовал сам,
получим
y = ((1000 - x)* (3000 + x*(x-1)*100/2)) /x

И получим минимум около х = 8.


Edit: Интуитивно это логично: 100 * 8 * 7/2 = 400* 7 = 2800 - это сумма всех инкрементальных бэкапов в серии, после этого инкрементальные бэкапы передавать нет смысла, следующий все равно будем размером с полный..
Забавно, вы идёте моим путём, но это не тот ответ что надо.
1. Допустим гибуй делается 1 раз в неделю, каждая серия состоит из 1-го полного копирования и n дельт.
Тогда к примеру если n=4, и серия - m - занимает 5 недель, за 1000 недель будет 200 серий.
Если n=9 то m = 100. В общем случае (n+1) * m = С - постоянная - количество недель - параметр оптимизации.
Т.о. m = C / (n+1)
2. Нам надо минимизировать среднеарифметический объём копирования для ВСЕХ копирований (полных и дельт) для выбранного параметра, скажем 1000
Попробуйте посчитать с учётом этих замечаний.
P.S. вы конечно понимаете, что полное копирование имеет объём равный предыдущему полному копированию + объём последней дельты
ОК, сначала.

Для начала решим простой случай - общий размер полного бэкапа не меняется со временем.

d = размер дельты
f = размер полного бэкапа
n = количество инкрементальных бэкапов в серии, сумма всех инкрементальных бэкапов = n*(n-1)*d/2, то есть, размер данных переданных за одну серию = n*(n-1)*d/2 + f, 1 полная серия занимает n + 1 единиц времени.

Размер среднего бэкапа за серию = (n*(n-1)*d/2 +f)/(n + 1) .

Заменяем n --> x, подставляем размеры и запихиваем в гугл: y=(x*(x-1)*100/2 +3000)/(x + 1)
Гугл рисует график с минимумом в районе 7 (в предыдущем графике было 8 потому что я делил на n а не на n+1).

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

По поводу более сложного случая, когда общий размер полного бэкапа растет со временем есть вопрос:
растет ли со временем размер дельты тоже ?
общий размер полного бэкапа не меняется со временем - это невозможно, полный бэкап с каждым копированием увеличивается на дельту. Сама дельта прирастает всегда на одинаковую величину, но поскольку дельта берётся от последенго полного бэкапа, то она соответственно пропорциональна порядковому номеру: 1-я - 100М, 2-я - 200М , и так до очередного полного бэкапа