以下是论文Workload-Driven Fragment Allocation for Partially Replicated Databases Using Linear Programming的笔记。
LP模型 (Linear Programming)
[1] 目的：计算具有最低总内存容量的部分副本(partial replicas)集，同时均衡查询负载
[2] 用于：scale-out方式，常见如Master replication，单个主节点(master node)处理所有OLTP工作负载，而OLAP查询在副本节点(replica nodes)上负载均衡
[3] 部分复制(partial replication)的步骤：
- 第一步：数据集被水平和/或垂直划分为不相交的数据片段
- 第二步：将各个片段分配给一个或多个数据库节点
优化片段分配的计算为NP-hard / NP-complete问题。
NP-hard指所有NP问题都能在多项式时间复杂度内归约到的问题。
NP是指非确定性多项式non-deterministic polynomial，所谓的非确定性是指可用一定数量的运算去解决多项式时间内可解决的问题。
NP-Complete（NP完全或NP完备，缩写为 NP-C 或 NPC)，是NP中最难的决定性问题。因此NP完备问题应该是最不可能被化简为P多项式时间可决定)的决定性问题的集合。一个决定性问题C若是为NPC，则代表它对NP是完备的，这表示：它是一个NP问题，且其他属于NP的问题都可归约成它。
已有方法及改进
[1] Ozsu et al: 启发式方法与系统的特定假设相关，因此仅适用于特定分配问题
[2] Rabl et al: (部分复制) 最优分配的LP模型，贪婪的启发式算法仅适用于小规模问题
原因：如果数据被晚分配，会导致最高的数据复制
启发式缺点：
- 在选择下一个要分配的查询时，不考虑访问的查询片段（只考虑大小）
- 不考虑关于剩余查询的信息，这些查询必须在以后分配
[3] 与基于规则的启发式方法相比，分解方法保留了问题的结构，因此能够找到耦合数据放置和负载分配问题的近似最优解
最优解
[1] 符号：
xi,k 取值0/1，表示片段i是够分配给节点k
yj,k 取值0/1，表示查询j是否可以在节点k进行
zj,k 取值0..1，表示在节点k处执行的查询j的工作负载共享。对于所有查询，份额总和规范化为1
不考虑查询频率和成本，z可以为离散值
[2] 选择x、y和z，以使目标最小化并满足以下约束：
约束(2)保证在所有相关片段都可用的情况下，查询j仅可以在节点k执行。|qj|表示查询j中使用到的片段数量)；
约束(3)保证如果查询j可以在节点k上执行，j只能有正的工作负载份额 (yj,k = 0，zj,k = 0；yj,k = 1，zj,k不限制)，以线性方式结合了二进制变量y和连续变量z；
约束(4)保证所有节点k不超过特定工作负载L，0 <= L <= 1。使用C表示的总工作负载成本(fj * cj的和)规范每个节点的工作负荷；
约束(5)保证查询的工作负载份额总和为1：
[3] 目标和约束的相关变量均为线性，分别根据片段数N、查询数Q、节点数K增加
变量的总数：N * K + Q * K 离散，Q * K连续
约束的总数：2 * Q * K + K + Q
因此可以使用已有方案（如NEOS solver）解决
启发式分解算法
分解算法解决方法
[1] 目的：可扩展(scalable)，计算更大问题的解决方案
[2] 通过使用带有K个叶子的树结构迭代地将工作负载分成不同的份额(shares)/块(chunks)来解决较小的子问题
一个节点的工作负载份额分割给B个子节点，每个字节点b包含nb个最终节点 b = 1…B
因此每个子节点b有wb = nb / K的工作份额
[3] 示例：K = 2 * 2 = 4节点，Q = 5个查询，N = 10个片段的工作负载，两个级别上B = 2子节点
透明片段表示节省内存
对于一个给定的特定工作负载(查询和片段)，有一个额外的分解级别（左上角）：
分解算法模型
[1] 约束(10)中，L可作为固定参数L或作为在目标(7)中加上罚项α * L的连续变量
如果α选择足够大(α >> V)，根据V的计算，会达到目标工作负载限制
下一级上每个子节点B的剩余工作负载x, y, z*
[2] 从一个层次到另一个层次，相关片段和查询的数量都会减少，变量和约束的数量会减少；
在每个层次上，对于每个节点，可以任意选择子节点的数B及其工作负载权重wb；
一个最优的解决方案也保证了工作负载的均匀分布L = 1 / K。
[3] 子节点B的数量可以用来控制问题的复杂性：
B越小，每一层的计算越快，但是启发式的总体数据复制可能会多于最优分配；
为了获得最小的计算时间，从最高层次以B = 2开始。
[4] 如果片段和查询的数量很大，即使块的数量很小，LP方法也会花费长时间
解决方案：相应简化子问题
- 对相似的查询进行聚类
- 只考虑较大的片段
- 只考虑具有较大工作负载份额的最昂贵的查询
利用TPC-H基准分析评估
最优解
[1] 条件：垂直分割，关系模型，Q = 22，N = 61
查询成本：
假设：
- LINEITEM表包含6M个tuple
- date、identifier和integer需要4个字节
- decimal需要8个字节
- 变量和固定文本需要最大长度字节。
[2] 复制因子(replication factor) = W / V
W为使用数据总量，V为最小使用数据量：
[3] 对于不同数量节点K，结果如下：
最佳分配实现了完美的工作负载分布L* = 1 / K；复制因子W* / V < K (完全复制的复制因子)。
k >= 9的最优分配不能在合理的时间内计算
分解算法
在惩罚公式中使用（标准化）因子α = 1000 * V。 W / V仅比W* / V大1%～5%，且实现完美的工作负载分布L = 1 / K