jingtao8a's blog

应用场景：

• 只读负载
• 读写负载，但是数据分布变化不大（即CDF随着key的插入删除变化较小）

问题描述：

之前的学习索引通过设计更好的启发式方法来划分key空间，使得每一份被分割的sub key空间可以更好地被线性模型拟合。
缺点：

• 为了达到这个目的，学习索引必须构建更深的层次结构，从而产生更多的遍历时间和预测数量
  （类似于用一个分段线性函数去拟合数据分布CDF）。

难点和分析过程：

本文提出了学习索引NFL（包括两个结构Normalizing Flow 和 Learned Index ）

思想： 先用分布转换模型将复杂key分布转换为近似均匀的分布，然后利用转换的key构建学习索引

难点

（1）Efficacy of Normalizing flow:

• 由于key的数字数据特征有限，分布转换模型表现不佳
• 均匀分布很难作为训练目标（我们设计了一个具有丰富特征空间的分布转换模型和一个易于操作的训练目标）

（2）Efficiency of normalizing flow

• 分布转化必须是高效的在线步骤，这样就限制了NF的复杂性。但是直接减少参数数量标准化流程可能会降低转换质量（这样会导致学习索引需要更深的层次结构和更多的模型来近似CDF），（我们设计了一套效率优化方案，并且保证NF的功效）

（3）Lack of proper indexes for transformed keys：

• numerica NF的转换使线性模型拟合地更好，学习索引应该以新的视角重新思考。（我们提出了After-Flow Learned Index（AFLI），充分利用转换后的key）

方法

以下两个是评价模型转换质量的指标

Tail conflict degree：

Numerical Normalizing Flow:
Feature Space Expansion:现有的NF大多用在cv和nlp领域，用于处理高纬的图片和文本，这些数据都有丰富的特征。然而keys都是数值数据，含有的特征较少。
使用Algorithm 3.1分布转换算法（对keys的数值特征进行扩展）

特征扩展的时间复杂度为O（n x d）

Structure of AFLI：

Model node:
Empty Slot：unused slot
Data Slot：key payload
Bucket Pointer: 指向一个bucket
Node Pointer：指向一个model node或者dense node
Bucket:
a short data array.它的size由tail conflict degree决定，但将保持在预设阈值范围内。我们提供两种桶，线性桶（默认）和有序桶

Dense node：
Also a data array，比bucket大一点，但是比Model node小很多，是一个ordered and gapped array, gap的最大值由tail conflict degree

Analysis:
当索引无法建立模型节点时，因为节点中的所有键都太近（即拟合线性模型的斜率为0），索引会分配一个dense array

Queries:
（1）从root node开始查找，如果是model node，先用linear model预测position，判断它的类型，如果是empty slot，表示不存在；如果是data slot，比较是否是相同的key；如果是bucket pointer，在bucket中查找；如果是node pointer，递归操作
（2）如果node是dense node，使用二分查找查找这个结果。

Insertions:
（1）如果key-payload pair被插入model node，先用linear model预测position

• 如果是empty slot，直接存储key-payload
• 如果是data slot，表明发生冲突，创建一个bucket来存储这两个key
• 如果是bucket pointer或者node pointer，插入key-payload到bucket或者child node中
  （2）插入到bucket中时，将key-payload会直接被加到sorted data的末尾；如果bucket是一个ordered mode，将会执行一次插入排序。
  （3）插入到dense node中时，先在array上执行二分查找，如果那个position是一个empty slot，我们会直接插入key-payload pair；，否则会移动到最近的empty slot再插入。

如果bucket或者dense node没有empty slots，我们尽量通过一个modeling operation将它转换为model node

我们首先一个使用线性回归创建线性模型（Line 1）
如果slope 为0（所有key被映射到一个相同的position），我们为创建一个dense node（Line 2 - 4）
否则如果我们成功创建一个linear model，就计算model node所有位置的conflict degree（Line 6）
然后我们遍历所有预测的位置，决定每个pos的entry type。如果conflict degree为1，我们直接在data slot存储该key；如果conflict degree大于1但是比bucket的tail confict degree小，存储在一个bucket中（Line 14 - 17）；
否则，如果某个position的confict degree比bucket的tail conflict degree大，找到下一个conflict degree也大于tail conflict degree的position或者到末尾，并将经过的position的key都收集起来，并分配一个新的节点来处理它们（第18 - 21行）
BulkLoad：首先计算tail conflict degree. The returned result is the root node.
Update: lookup + in-place update
Delete

结果：

数据集：
选取了7个不同的数据集进行评估
（Key的类型为double payload的类型是int64）

对每种类型的数据集构建了四种类型的工作负载

每种工作负载包括 批量加载和运行阶段
我们使用批量加载操作来加载数据集的50%的key；在运行阶段，根据不同的操作比率生成请求

• 只读
• 读80% 写20%
• 写 20% 读80%
• 只写

将NFL与LIPP、ALEX、PGM-index、B-Tree、an efficient B-Tree对比

平均吞吐量

• 只读：NFL与LIPP、ALEX、PGM、B-Tree相比，平均吞吐量分别提高了2.34倍、2.46倍、3.82倍、7.45倍；对于具有大冲突程度的工作负载（即LLT和FB），可以分别实现比LIPP、ALEX高2.41x和3.70x的吞吐量。
• 重读：与LIPP、ALEX、PGM、B-Tree相比，NFL在吞吐量上分别提高72.22%、101.05%、611.48%、389.45%
• 重写：与LIPP、ALEX、PGM、B-Tree相比，NFL在吞吐量上分别提高29.10%、39.28%、50.88%、162.92%
• 只写：与LIPP、ALEX、B-Tree相比，NFL在吞吐量上分别提高22.65%、28.30%和131.58%

延迟

• 只读：与LIPP、ALEX、PGM index、B-Tree相比，NFL可以将延迟分别降低58.68%、32.89%、62.73%和80.77%
• 读写：与LIPP、ALEX、PGM index和B-Tree相比，NFL可以将延迟分别降低26.64%、45.05%、59.49%、65.31%
• 只写：与LIPP、ALEX、B-Tree相比，NFL可以将延迟减少2.26%、27.92%、50.48%

批量加载时间

与LIPP、ALEX、B-Tree相比，NFL需要2.25倍、0.86倍、2.81倍的大容量加载时间，其中77%的时间是用来转换key的

索引大小：

NFL的指数大小分别是ALEX和PGM的2.26倍和3.1倍；然而，NFL的大小仅为LIPP大小的0.51

应用场景

读写负载

问题描述

Learned Index：只能在只读数据集上查找，无法处理索引结构中必不可少的更新操作
ALEX和PGM：它们对更新的支持是以查找操作的额外搜索为代价的；并且这些索引的更新操作也会导致大量元素的移动

需要一种索引可以解决“最后一英里问题”

方法

每个Node包含一个model、一个entries array、一个bit数组，
每个bit表示array中一个entry的类型，
类型有
NULL（空entry），
DATA(entry包含一个键值对，如果键值对太大，保存一个指向payload的指针)，
NODE（该entry指向下一层中的一个子节点，将一个新元素插入DATA entry时，创建一个子节点保存这两个entry，该entry指向这个新的节点）

三种类型的entry的大小都为16byte，其中DATA类型的entry由8byte的key和8byte的payload组成
对于第i个entry，bit数组的第2i位表示该entry是不是NULL,第2i + 1位表示entry的type

LIPP不区分leaf node和internal node

各种操作的算法：
FMCD算法：

给定一组key和数组长度L，计算最小的冲突度T及相应的linear model

INTRODUCTION

ReadOnly
对字符串的学习索引最重要的问题是 last-mile-search,并且这种搜索在字符串场景中特别昂贵。

两个原因

1. 由于难以建模真实世界的数据（许多真实世界的数据集具有很长的共同前缀以及每个字节相对较低的鉴别内容，CDF似乎是循序渐近的，这样传统的学习模型很难准确捕获和预测），这些场景的平均模型误差往往很高
2. 最后一英里的搜索是很慢的，每次比较是昂贵的，字符串的大尺寸减少了适合在缓存中的键的数量

这项研究的基础： Bounded Error（这样就可以使用二分查找代替指数搜索）

SPLING STRINGS

问题描述：对于字符串而言，需要满足两种操作

1. 确定性查找，找到完全匹配的字符
2. 模糊匹配，找到第一个满足匹配条件的元素（下届）

RADIX STRING SPLINE

RSS是一棵树，每个节点包含三个部分：

• bounds: 可操作的数据下标范围
• 重定向map(指针):包含并指向了一些key，这些key因为不满足当前节点的error bound，因而被分配到了其他节点
• 一个使用K个byte作为前缀，错误范围为E的RadixSpline模型

如何构建？

1. 首先，对数据集中所有字符串构建一个RadixSpline(使用前k个字节)。然后，遍历所有唯一的k字节前缀，并检查估计的位置是否在前缀的第一次出现和最后一次出现时都在规定的误差范围内。
2. 对于每个测试失败的前缀，我们将其添加到重定向表中，并在有问题前缀的所有字符串中构建一个新的RSS，从字节k开始而不是0
3. 这个过程递归地继续进行，直到每个key都得到满足为止。

如何查询

首先提取字符串的前k个字节，然后对重定向器进行二分查找，如果找到重定向新的RSS节点，就重新开始对下一个k字节进行操作；如果没有找到，那么就在当前节点使用适当的字符串前缀查找并返回结果。

HASH CORRECTOR

待更新

INTRODUCTION

PGM == PieceWise Geometric Model 分段几何模型
关键词：dynamic(表示PGM-index除了支持查询还支持插入和删除)、compressed(表示还对模型进行了压缩，达到更好的空间效率)

本文的注意力集中在解决所谓的全动态可索引字典问题。这个问题要求存储多重集S，以便有效支持以下查询和更新操作

1. member (x) = true if x ∈ S, false otherwise;
2. lookup(x) returns the satellite data of x ∈ S (if any), nil otherwise;
3. predecessor (x) = max{y ∈ S | y < x};
4. range(x, y) = S ∩ [x, y];
5. insert(x) adds x to S, i.e. S ← S ∪ {x};
6. delete(x) removes x from S, i.e. S ← S \ {x}.

• member(x)，判断关键字x是否属于多重集S
• lookup(x)，给定一个key，若该key已被插入，则返回其value
• predecessor(x)，翻译软件叫“前任”，返回所有小于x的数据中最大的那个，其实可以简单理解为排好序的数组中，x的前一个数据
• range(x, y)，范围查询，给出[x, y]关键字x和y之间的所有对应的value
• insert和delete很好理解，插入和删除对应的（K, V）

本文将 member,lookup,predecessor称为点查询，range称为范围查询
对于点查询和范围查询只要实现rank(x)
member(x) <–> A[rank(x)] == x
predecessor(x) <–>A[rank(x) - 1]
range(x, y) <–> 从rank(x)对应的A数组的位置开始向后查找直到key大于y为止

现存的解决上述问题的经典索引数据结构：（1）哈希索引（2）B树（3）位图索引（4）字典树trie索引
哈希索引不支持predecesor和range，位图索引维护成本过高，字典树空间消耗过大，主流数据库还是使用B树及其变种作为存储引擎

本文提出的PGM-Index不像RMI和FITing-Tree那样混合了传统的索引和学习型索引。(RMI的最后一个stage中的模型若error超过阈值，则将模型替换为B+树，FITing-Tree在确定segment时也是查找B+树)

PGM-Index

两个关键点：

1.PLA-Model(Piecewise Linear Approximation model, 分段线性近似模型)

这里使用了多个线性模型(segment, FITing-Tree中的分段线性模型)组成了一个PLA-Model(PGM-Index中的一层)，一个segment包含了三部分(start key, slope, intercept)

2.recursive index structure (递归索引结构)

为了适应key的分布，PGM-Index使用了多层PLA-Model，我们先使用所有的key来构建最底层的PLA-Model，然后提取Segment中的key形成新的集合，然后对该集合再次构建PLA-Model，如此递归直到最高层的PLA-Model只有一个segment

下图包含了PGM-Index的构建伪代码，查找伪代码和查找示意图

Optimal PLA-model

找到最优的PLA-model的方法是动态规划，但它所需要的O(n^3)是禁止的。FITing-Tree的作者通过收缩锥的方式来在线性时间内解决这个问题但无法保证是最优的PLA-model

然而我们发现这个问题在时间序列的有损压缩和相似性搜索中得到了广泛的研究，并且它允许采用O(n)最优时间和空间的流媒体算法。这类方法的关键思想是将分段线性近似问题简化为构造一组点的凸包在我们的情况下，这是集合{(ki，rank(ki))}为i = 0，…，n−1。只要凸包可以被封闭在一个高度不超过2ε的（可能是旋转的）矩形中，索引i就会递增，集合就会被扩展。一旦包围凸壳的矩形高于2ε，我们就停止构造，通过取将矩形分成两个等尺寸的半的线来确定pla模型的一部分。然后，清空当前的处理元素集，算法从其余的输入点重新启动。这种贪婪方法可以被证明在pla模型的大小上是最优的，并且具有线性的时间和空间复杂度。

DYNAMIC PGM-INDEX

插入和删除操作

现有学习型索引插入操作的实现方案是，将元素按序插入到相应段的缓存中，当缓存满了，将缓存与主索引合并，合并需要重新训练。这个方案在key非常多时，效率较低。本文提出两个插入策略：（1）面向时序数据（2）面向一般数据

• 如果是时间序列的数据，插入的数据肯定是在数组A的最后面，那么如果最后一个段能够存放这个数据，且满足ε的条件，就直接放在最后一个段；否则新建一个段，然后向上层一层一层更新Segment。在这种策略下，每层更新最多只涉及到一个Segment的添加，因此需要的I/O少。
• 如果是一般的数据，即插入的位置可以是任意的。这里则采用LSM-Tree更新数据的思想。

COMPRESSED PGM-INDEX

Introduction

1. 一种新的索引结构，它使用分段线性函数紧凑地捕捉数据中的趋势，并通过此减少索引的内存大小
2. 这个索引结构的核心是一个参数error(查找key的预测position和实际position之间的最大距离)
3. 为了实现查找性能和空间之间的trade-off，我们提出了一种cost model在给定查找延迟需求(eg 500ns)和存储预算(eg 100MB)的情况下帮助DBA选择合适的error参数

与最初的提出的技术相比，有以下优点：
(1)绑定最坏的查找性能
(2)有效地支持插入
(3)启动分页(所有数据不必驻留在一个连续的内存区域)

另一个有趣的点：
由于FITing-Tree的内部节点是树形结构，仍然可以应用前缀和后缀截断的技术来进一步减少索引的大小

OverView

Function Representation

使用分段线性函数拟合数据相比于更复杂的函数的优点
(分段线性函数近似的计算成本要低得多)
(1) 初始索引构建成本低
(2) 插入新的key延迟低

分段线性函数仍然存在误差error

通过以上公式，我们可以定义一个segment(一组排序好的数据)
分割过程结束后，FITing-Tree将每个segment的边界和斜率存储在叶子节点中，减少了索引的总体内存占用

FITing-Tree Design

Clusted Indexes

Non-clusted Indexes

SEGMENTATION

Design Choices

下图是我们分段算法需要实现的目标，使得分段后满足最大的error

为了高效地构建索引和支持插入，需要一个高效地one-pass linear algorithm

Segment Definition

当一个segment添加一个key时，违反了这个max-error，则定义这个segment已经达到最大了

定理:最大segment所覆盖的最小位置数为max-error + 1

Segmentation Algorithm (思考: 可以不以用一个新的分段算法,或者在这个分段算法之上对这个进行改进)

如图5所示，说明了圆锥体的更新方式:点1时圆锥体的原点。点2更新了高斜坡和低斜坡。点3在原锥内，但是它只更新圆锥的上界（点3的小于下界之上的误差）。点4在更新锥的外部，因此将是新段的第一个点

Algorithm Analysis

虽然以上收缩锥体算法的运行时间复杂度为O(n),但是它不是最优的。

INDEX LOOKUPS

Point Queries

Range Queries

INDEX INSERTS

In-place Insert Strategy

类似于页面的填充因子，我们将指定的误差分成两个部分：分割误差e和插入预算x
通过为每个segment保留插入预算x，可以确保插入新元素不会违反页面的错误

更具体地说，给定一个段，页面的总大小为|s| + 2*x(|s|为该段中的位置数,数据被放置在新页面的中间)，在页面的开始和结束处产生x个空位置。在插入过程中如果所有的空白都被填满，那么就需要重新执行分割算法

Delta Insert Algorithm

• 就地插入策略的成本可能很高
• 为了减小插入时页面内数据移动的开销，每个segment包含一个额外的固定大小的缓冲区，此缓冲区保持排序，以实现有效的搜索和合并操作，一旦缓冲区达到预定的大小(buff)，它与段中的数据进行合并，再次执行分割算法
• 另外，由于为每个段添加缓冲区可能违反FITing-Tree的max-error，我们透明地将缓冲区地大小合并到分割过程地错误阐述中，即分割过程中地错误阈值为(error -buff)
  

COST MODEL

由于指定的错误阈值error会影响查找和插入的性能以及索引的大小
提供cost model的目的就是帮助DBA在不同的工作负载下选择合适的错误阈值error

Latency Guarantee

查找延迟保证

由于查找需要找到相关的segment,然后搜索segment(数据+缓冲区)，并且error的值会影响创建的段的数量(即更小的error会产生更多的段),我们使用一个函数，它返回为给定数据集创建的segment数量和error值。我们使用Se来表示指定数据集在给定错误阈值e下生成的segment的数量。

error值为e的总估计查找延迟可以用以下表达式来建模,其中b是tree的fanout,buff是segment的最大buffer大小

满足给定延迟要求并且存储占用最小的索引由以下表达式给出,其中E表示一组可能的错误值

Space Budget

空间预算
可以用以下函数来估计给定的错误阈值e下的只读聚类索引的大小(byte)

因此满足给定存储预算的最小误差阈值由以下表达式给出

RadixSpline

组成部分

1. a set of spline points
2. a radix table

构建

1. Build Spline

   首先建立一个Spline Model S
   S(ki) = pi +/- e
   (ki, pi)为要查找的key和真实的position e为error
   模型的计算如下，其中(kleft,pleft)和(kright, pright)为两个spline point
   

2.Build Radix Tablle

作用： 用于所定查找key的附近的两个spline point

过程： 确定使用的key的prefix的长度r，分配2^r长度的数组，遍历所有的spline points，碰到新的prefix，就插入该数组

ALEX：An Updatable Adaptive Learned Index

应用场景：

在DBMS中代替传统的索引结构，类似于B树、B+树之类的变种

问题描述：

ALEX索引需要实现点查找、范围查询、插入、删除和批量载入
ALEX的目标是
1.比B+树写数据更快
2.比B+树和learned index读数据要更快
3.索引大小要比B+树和learned Index要小

难点与分析过程：

• 写数据时：B+树插入到数据节点时需要进行大量的移位操作，对于一个dense Array 它的插入时间复杂度为O(n)
• 写数据时：B+树插入到数据节点时，根据节点是否已满的条件来将数据节点分裂，分裂到根节点会导致树高的增加
• 读数据时：B+树遍历到数据节点后，使用二分查找确定带查找的key的position，它的时间复杂度为O（log2n)
• 读数据时：最初的Learned Index是先将数据排序好之后，再在该数据上创建模型，这样用最后的数据节点来预测key的位置时会有较大出错的概率，并且还需要存储Error Bound

方法：

• 写数据时：ALEX使用一个gap array（间隙数组），这样在插入过程中需要更少的移位操作，它的时间复杂度近似于O（log2n）
• 写数据时：插入已满数据节点时，使用一个intra-node cost model模型来决定将数据节点扩展（如果没有）或者是分裂
  Intra-node cost model根据每个数据节点存储的两个信息（1.平均每次操作指数搜索的迭代次数 2.平均每次插入时的移位操作次数）计算经验成本，再和数据节点的预期成本（节点创建时预期的成本）比较
  如果经验成本与预期成本没有较大的偏离（超过50%）则执行节点扩展（不会超过节点最大大小限制），否则执行节点分裂
• 读数据时：ALEX使用指数查找，先用数据节点的线性模型预测一个position，再判断该position上的key是否大于或者小于待查找的key，以此判断指数查找的方向

指数查找的时间复杂度分析如下

并且使用指数查找算法后，也不需要在数据节点模型中存储error bound。

• 读数据时：ALEX在创建数据节点时使用基于模型的插入，先训练好模型之后，再将模型尽量插入预测的位置，这样可以大大减少预测错误的概率

ALEX的节点：
Internal node：
线性模型（slope intercept）、point array
Leaf node：
线性模型（slope intercept）、gap array 、bitmap

查找：

插入：
未满节点: 按照查找逻辑找到应该插入的数据节点，有必要的情况下用指数查找来找到正确的位置。
已满节点： 已满节点的定义（有一个上下限密度dl du）
节点扩展机制：

节点分裂机制：
a.有冗余指针指向数据节点，可以用它分别指向另外两个数据节点

b.如果父节点满了，像B+树那样进行拆分，分类一直可以传播到根节点

删除：
简单删除key和payload，如果Data Node由于删除而达到密度下限dl，那么我们将收缩Data Node避免低空间利用率（思考：是否可以引入合并操作）

更新：
Delete和Insert操作结合

界外插入：
首先，当ALEX检测到现有key空间之外的插入时，将扩展root节点；如果此扩展将导致根节点超过最大节点大小，ALEX则会创建一个新的root节点，并为新root节点的每个其他指针槽创建一个新的数据节点。

其次，ALEX最右边的数据节点通过记录节点中的最大键的值和插入超过该最大值的计数器来检测插入行为。如果多次插入都超过该最大值，这意味着这是一个只追加行为，因此数据节点向右扩展，扩展的空间用来更多类似于追加的插入

批量加载
RMI成本是通过TraverseToLeaf和intra-node cost model来计算的


每个node为internal node或者leaf node由fanout tree决定，
决定每一个node的类型时都独自创建一棵fanout tree

结果

数据集选取：
使用某个数据集的8字节的key运行所有的实验，并随机生成固定大小的payload。
我们在4个数据集上评估了ALEX，其特征和CDF如下所示
经度数据集由Open Street Maps中世界各地的经度组成
Longlat数据集由复合键组成（k=180*floor(longitude)+latitude, 经纬度也是来自Open Street Maps)
Lognormal数据集的值是根据对数正态分布N（0，4）生成的，并乘上10^9，再四舍五入到最接近的整数。
YCSB数据集表示根据YCSB基准生成的用户ID的值，这些值均匀分布在整个64位域中，并使用80字节的有效载荷

工作负载：我们评估ALEX的主要指标是平均吞吐量（指定时间内完成的插入或读取量），评估了5个工作负载的吞吐量
（1）只读工作负载 （2）具有95%的读取和5%插入的读取繁重的工作负载（3）具有50%的读取和50%的插入的写繁重的工作负载（4）具有95%读取和5%插入的读取的短范围查询的工作负载（5）只写工作负载

ALEX和learned Index；B+ Tree；模型增强B+ Tree；ART对比

• 在只读工作负载上，ALEX比B+树、learned index、模型增强B+树和ART在吞吐量上高4.1x、2.2x、2.9x、3.0x和在索引大小上小800x、15x、160x、8000x
• 在读写工作负载上，ALEX比B+树、模型增强B+树和ART在吞吐量上高4.0x、2.7x、2.7x，
  在索引大小上小2000x、475x、36000x

静态链接浪费内存和磁盘空间并且更新困难。动态链接的基本思想： 把链接过程推迟到运行时进行。

-shared

生成动态链接模块时只使用-shared，由于装载时重定位的方法需要修改指令，没有办法做到同一份指令被多个进程共享，因为指令被重定位之后对于每个进程来讲是不同的。

-fPIC 地址无关代码

实现的基本思想就是把指令中那些需要被修改的部分分离出来，跟数据部分放在一起，这样指令部分可以保持不变，而数据部分在每个进程中拥有一个副本。这种方案就是地址无关技术

GOT全局偏移表

对于动态链接模块中,对于外部符号（数据）的访问的机制，当指令需要访问某个外部变量时，程序会先找到GOT，然后根据GOT中变量所对应的项找到变量的目标地址。每个变量都对应一个4个字节的地址，链接器在装载模块的时候会查找每个变量所在的地址，然后填充GOT中的各个项。由于GOT表本身是放在数据段的，所以它可以在模块装载时被修改，并且每个进程都可以有独立的副本。

-fPIE

地址无关代码技术除了可以用在动态链接模块上，它也可以用于可执行文件

共享模块（动态链接模块）的全局变量问题

当一个模块引用了定义在共享对象的全局变量的时候，由于可执行文件在之前链接时就必须确定该全局变量的地址，所以连接器会在创建可执行文件时，在它的.bss段创建一个global变量的副本。导致同一变量同时存在于多个位置
于是解决的办法只有一个，那就是所有的使用这个变量的指令都指向位于可执行文件中的那个副本。ELF共享库在编译时，默认都把定义在模块内部的全局变量当作定义在其他模块的全局变量，也就是说当作前面的类型四，通过GOT来实现变量的访问。当共享模块被装载时，如果某个全局变量在可执行文件中拥有副本，那么动态链接器就会把GOT中的相应地址指向该副本，这样该变量在运行时实际上最终就只有一个实例。如果变量在共享模块中被初始化，那么动态链接器还需要将该初始化值复制到程序主模块中的变量副本；如果该全局变量在程序主模块中没有副本，那么GOT中的相应地址就指向模块内部的该变量副本。

默认情况下，如果可执行文件是动态链接的，那么GCC会使用PIC的方法来产生可执行文件的代码段部分，以便于不同的进程能够共享代码段，节省内存。所以动态链接的可执行文件中存在.got段

延迟绑定

由于动态链接下对于全局数据的访问和跨模块的调用都要进行复杂的GOT定位，然后间接寻址或调用，导致程序的运行速度减慢大概1%~%5。又因为动态链接的链接工作在运行时完成，导致程序的启动速度减慢。
程序运行过程中，会有很多函数没有用到（错误处理函数，没有使用的功能模块等），所以没有必要一开始就把所有函数都链接好，ELF采用延迟绑定的方法，基本思想是当函数第一次被用到时才由动态链接器进行绑定（符号查找，重定位等），没用到的不绑定。这提高了程序的启动速度。
ELF使用PLT（Procedure Linkage Table）来实现延迟绑定,它使用了一些很精巧的指令序列来完成

ELF将GOT拆分成了两个表.got和.got.plt，其中.got用来保存全局变量引用的地址，.got.plt用来保存函数引用的地址
PLT在ELF文件中以独立的段存放，段名通常叫做.plt，因为它本身是一些地址无关代码，所以可以跟代码段合并成同一个可读可写可执行的“Segment”被载入内存
参考链接

连接器采用“两部链接”的方法，将链接过程分为两部：

1.空间和地址分配：扫描所有的输入目标文件，获得各个节的长度、属性、位置并将它们合并，计算合并后各个段的长度与位置，建立映射关系。收集所有输入目标文件中符号表中所有的符号定义和符号引用，统一放到全局符号表中
2.符号解析与重定位：使用第一步中收集到的所有信息，读取输入文件中节的数据、重定位信息，并且进行符号解析与重定位、调整代码中的地址等。

重定位过程是链接过程的核心

符号解析与重定位

符号解析

重定位的过程伴随着符号解析过程，每个目标文件都可能定义一些符号，也可能引用到定义在其他目标文件的符号。重定位过程中，每个重定位的入口都是一个外部符号的引用，当链接器需要对某个符号的引用进行重定位时，他就要确定这个符号的目标地址。这时候链接器会去查找有所有输入目标文件的符号表组成的全局符号表，找到相应的符号后进行重定位，如果没有找到，就会报符号未定义的错误。

重定位

对于32位 x86平台下的ELF文件的重定位入口所修正的指令寻址方式只有两种：

1.绝对近址32位寻址
2.相对近址32为寻址

这两种重定位指令修正方式每个被修正的位置的长度都为32位，即4字节。而且都是近址寻址，不用考虑Intel的段间远址寻址。

X86基本重定位类型：

参考