Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Что я придумал

Краткое содержание предыдущих серий:

Есть функция multiColor :: [Key] -> [Color], которую надо мемоизировать, используя дисковое хранилище. Ключей оч много и они не помещаются в память.
data Color = Red | Black

keyValue :: Key -> Value
keyChildren :: Key -> [Key]
valueColor :: (Key, Value) -> Color

keyColor :: Key -> Color
keyColor x = valueColor (x, keyValue x)

treeColor :: Key -> Color
treeColor x | keyColor x == Red = Red
treeColor x | any (\x -> treeColor x == Red) $ keyChildren x = Red
treeColor _ = Black

multiColor :: [Key] -> [Color]
multiColor = map treeColor
Теперь решение:

Никакие Рекстеры нам не нужны, лепим из говна и палок.

Берем key-value store. Я взял Berkeley DB, because I can.

multiColor :: [Key] -> IO [Color] - хуй с ними с IOPS (тем более что BDB не утилизирует NCQ нихуя, судя по бенчмаркам), хуячим секвенциально mapM как первоклашки.

treeColor :: Key -> IO Color - делаем в виде BDB hash store. Основная масса запросов будет хитами в таблице treeColor. В будущем можно какие-нибудь блумфильтры прикрутить, т.к. битик храним, может в память (говнокластера) влезет.

Если у нас мисс - самое интересное.
data Rose a = Rose a [Rose a]
data KV = KV Key (Maybe Value)
Делаем таблицу keyTree :: Key -> Rose KV, в которой лежит сериализованное дерево Key, Value.

А также таблицу secondaryKey :: Key -> Key, в которой для каждого ключа указан корень дерева, в котором он лежит.

Теперь если у нас значения нет - значит, либо его вообще нет (т.е. надо вычислять keyChildren, keyValue, обновлять текущее дерево и secondaryKey, вычислять цвет и если красный - то останавливаться), либо оно лежит в соседнем блобе.
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    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.
  • 0 comments