proki (proki) wrote in programmer_il,
proki
proki
programmer_il

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

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 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М , и так до очередного полного бэкапа