泽民博客 ☰ Menu

sparl_ml_pipline

Posted by 夏泽民 Nov 16, 2017
inspired by the scikit-learn project.
DataFrame: This ML API uses DataFrame from Spark SQL as an ML dataset, which can hold a variety of data types. E.g., a DataFrame could have different columns storing text, feature vectors, true labels, and predictions.
Transformer: A Transformer is an algorithm which can transform one DataFrame into another DataFrame. E.g., an ML model is a Transformer which transforms a DataFrame with features into a DataFrame with predictions.
Estimator: An Estimator is an algorithm which can be fit on a DataFrame to produce a Transformer. E.g., a learning algorithm is an Estimator which trains on a DataFrame and produces a model.Technically, an Estimator implements a method fit(), which accepts a DataFrame and produces a Model, which is a Transformer.
Pipeline: A Pipeline chains multiple Transformers and Estimators together to specify an ML workflow.
Parameter: All Transformers and Estimators now share a common API for specifying parameters. 参考：http://spark.apache.org/docs/latest/ml-pipeline.html
一句话概括：管道（Pipeline）是运用数据（DataFrame）训练算法模型（Estimator）调整参数（Parameter）得到一个最优的算法模型（Transformer）,转换数据（DataFrame）的流程。 For Transformer stages, the transform() method is called on the DataFrame. For Estimator stages, the fit() method is called to produce a Transformer (which becomes part of the PipelineModel, or fitted Pipeline), and that Transformer’s transform() method is called on the DataFrame.
阅读全文

mysql 的排序

Posted by 夏泽民 Nov 16, 2017
用户通过Order by语句即能达到将指定的结果集排序的目的，其实不仅仅是Order by语句，Group by语句，Distinct语句都会隐含使用排序
阅读全文

mysql_maneager

Posted by 夏泽民 Nov 16, 2017

客户端管理器 客户端管理器是处理客户端通信的。客户端可以是一个（网站）服务器或者一个最终用户或最终应用。客户端管理器通过一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式来访问数据库。客户端管理器也提供专有的数据库访问API。 当你连接到数据库时： 管理器首先检查你的验证信息（用户名和密码），然后检查你是否有访问数据库的授权。这些权限由DBA分配。 然后，管理器检查是否有空闲进程（或线程）来处理你对查询。 管理器还会检查数据库是否负载很重。 管理器可能会等待一会儿来获取需要的资源。如果等待时间达到超时时间，它会关闭连接并给出一个可读的错误信息。 然后管理器会把你的查询送给查询管理器来处理。 因为查询处理进程不是『不全则无』的，一旦它从查询管理器得到数据，它会把部分结果保存到一个缓冲区并且开始给你发送。 如果遇到问题，管理器关闭连接，向你发送可读的解释信息，然后释放资源。 查询管理器 这部分是数据库的威力所在，在这部分里，一个写得糟糕的查询可以转换成一个快速执行的代码，代码执行的结果被送到客户端管理器。这个多步骤操作过程如下：查询首先被解析并判断是否合法 然后被重写，去除了无用的操作并且加入预优化部分 接着被优化以便提升性能，并被转换为可执行代码和数据访问计划。 然后计划被编译 最后，被执行 查询解析器每一条SQL语句都要送到解析器来检查语法，如果你的查询有错，解析器将拒绝该查询。比如，如果你写成”SLECT …” 而不是 “SELECT …”，那就没有下文了。但这还不算完，解析器还会检查关键字是否使用正确的顺序，比如 WHERE 写在 SELECT 之前会被拒绝。然后，解析器要分析查询中的表和字段，使用数据库元数据来检查：表是否存在 表的字段是否存在 对某类型字段的 运算 是否 可能（比如，你不能将整数和字符串进行比较，你不能对一个整数使用 substring() 函数） 接着，解析器检查在查询中你是否有权限来读取（或写入）表。再强调一次：这些权限由DBA分配。在解析过程中，SQL 查询被转换为内部表示（通常是一个树）。如果一切正常，内部表示被送到查询重写器。查询重写器在这一步，我们已经有了查询的内部表示，重写器的目标是：预优化查询 避免不必要的运算 帮助优化器找到合理的最佳解决方案 重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则，查询就会按照这条规则来重写。下面是（可选）规则的非详尽的列表：视图合并：如果你在查询中使用视图，视图就会转换为它的 SQL 代码。 子查询扁平化：子查询是很难优化的，因此重写器会尝试移除子查询去除不必要的运算符：比如，如果你用了 DISTINCT，而其实你有 UNIQUE 约束（这本身就防止了数据出现重复），那么 DISTINCT 关键字就被去掉了。 排除冗余的联接：如果相同的 JOIN 条件出现两次，比如隐藏在视图中的 JOIN 条件，或者由于传递性产生的无用 JOIN，都会被消除。 常数计算赋值：如果你的查询需要计算，那么在重写过程中计算会执行一次。比如 WHERE AGE > 10+2 会转换为 WHERE AGE > 12 ， TODATE(“日期字符串”) 会转换为 datetime 格式的日期值。 （高级）分区裁剪（Partition Pruning）：如果你用了分区表，重写器能够找到需要使用的分区。 （高级）物化视图重写（Materialized view rewrite）：如果你有个物化视图匹配查询谓词的一个子集，重写器将检查视图是否最新并修改查询，令查询使用物化视图而不是原始表。 （高级）自定义规则：如果你有自定义规则来修改查询（就像 Oracle policy），重写器就会执行这些规则。 （高级）OLAP转换：分析/加窗 函数，星形联接，ROLLUP 函数……都会发生转换（但我不确定这是由重写器还是优化器来完成，因为两个进程联系很紧，必须看是什么数据库）。当你要求数据库收集统计信息，数据库会计算下列值：表中行和页的数量 表中每个列中的： 唯一值 数据长度（最小，最大，平均） 数据范围（最小，最大，平均） 表的索引信息 这些统计信息会帮助优化器估计查询所需的磁盘 I/O、CPU、和内存使用对每个列的统计非常重要。 比如，如果一个表 PERSON 需要联接 2 个列： LAST_NAME, FIRST_NAME。 根据统计信息，数据库知道FIRST_NAME只有 1,000 个不同的值，LAST_NAME 有 1,000,000 个不同的值。 因此，数据库就会按照 LAST_NAME, FIRST_NAME 联接。 因为 LAST_NAME 不大可能重复，多数情况下比较 LAST_NAME 的头 2 、 3 个字符就够了，这将大大减少比较的次数。所有的现代数据库都在用基于成本的优化（即CBO）来优化查询。道理是针对每个运算设置一个成本，通过应用成本最低廉的一系列运算，来找到最佳的降低查询成本的方法。为了理解成本优化器的原理，我觉得最好用个例子来『感受』一下这个任务背后的复杂性。这里我将给出联接 2 个表的 3 个方法，我们很快就能看到即便一个简单的联接查询对于优化器来说都是个噩梦。之后，我们会了解真正的优化器是怎么做的。对于这些联接操作，我会专注于它们的时间复杂度，但是，数据库优化器计算的是它们的 CPU 成本、磁盘 I/O 成本、和内存需求。时间复杂度和 CPU 成本的区别是，时间成本是个近似值（给我这样的懒家伙准备的）。而 CPU 成本，我这里包括了所有的运算，比如：加法、条件判断、乘法、迭代……还有呢：每一个高级代码运算都要特定数量的低级 CPU 运算。 对于 Intel Core i7、Intel Pentium 4、AMD Opteron…等，（就 CPU 周期而言）CPU 的运算成本是不同的，也就是说它取决于 CPU 的架构。 使用时间复杂度就容易多了（至少对我来说），用它我也能了解到 CBO 的概念。由于磁盘 I/O 是个重要的概念，我偶尔也会提到它。请牢记，大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用。索引在研究 B+树的时候我们谈到了索引，要记住一点，索引都是已经排了序的。仅供参考：还有其他类型的索引，比如位图索引，在 CPU、磁盘I/O、和内存方面与B+树索引的成本并不相同。另外，很多现代数据库为了改善执行计划的成本，可以仅为当前查询动态地生成临时索引。存取路径在应用联接运算符（join operators）之前，你首先需要获得数据。以下就是获得数据的方法。 全扫描如果你读过执行计划，一定看到过『全扫描』（或只是『扫描』）一词。简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言，很明显全表扫描的成本比索引全扫描要高昂。范围扫描其他类型的扫描有索引范围扫描，比如当你使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 的时候它就会发生。当然，你需要在 AGE 字段上有索引才能用到索引范围扫描。在第一部分我们已经知道，范围查询的时间成本大约是 log(N)+M，这里 N 是索引的数据量，M 是范围内估测的行数。多亏有了统计我们才能知道 N 和 M 的值（注： M 是谓词 “ AGE > 20 AND AGE < 40 ” 的选择率）。另外范围扫描时，你不需要读取整个索引，因此在磁盘 I/O 方面没有全扫描那么昂贵。唯一扫描如果你只需要从索引中取一个值你可以用唯一扫描。根据 ROW ID 存取多数情况下，如果数据库使用索引，它就必须查找与索引相关的行，这样就会用到根据 ROW ID 存取的方式。 其它路径我没有列举所有的存取路径，如果你感兴趣可以读一读 Oracle文档。其它数据库里也许叫法不同但背后的概念是一样的。联接运算符那么，我们知道如何获取数据了，那现在就把它们联接起来！我要展现的是3个个常用联接运算符：合并联接（Merge join），哈希联接（Hash Join）和嵌套循环联接（Nested Loop Join）。但是在此之前，我需要引入新词汇了：内关系和外关系（ inner relation and outer relation） 【译者注： “内关系和外关系” 这个说法来源不明，跟查询的”内联接（INNER JOIN） 、外联接（OUTER JOIN） ” 不是一个概念 。只查到百度百科词条：关系数据库 里提到”每个表格（有时被称为一个关系）……” 。 其他参考链接 “Merge Join” “Hash Join” “Nested Loop Join” 】 。 一个关系可以是：一个表 一个索引 上一个运算的中间结果（比如上一个联接运算的结果） 当你联接两个关系时，联接算法对两个关系的处理是不同的。在本文剩余部分，我将假定：外关系是左侧数据集 内关系是右侧数据集 比如， A JOIN B 是 A 和 B 的联接，这里 A 是外关系，B 是内关系。多数情况下， A JOIN B 的成本跟 B JOIN A 的成本是不同的。在这一部分，我还将假定外关系有 N 个元素，内关系有 M 个元素。要记住，真实的优化器通过统计知道 N 和 M 的值。注：N 和 M 是关系的基数。【译者注： 基数 】嵌套循环联接嵌套循环联接是最简单的哈希联接哈希联接更复杂，不过在很多场合比嵌套循环联接成本低哈希联接的道理是：1) 读取内关系的所有元素 2) 在内存里建一个哈希表 3) 逐条读取外关系的所有元素 4) （用哈希表的哈希函数）计算每个元素的哈希值，来查找内关系里相关的哈希桶内 5) 是否与外关系的元素匹配。 在时间复杂度方面我需要做些假设来简化问题：内关系被划分成 X 个哈希桶 哈希函数几乎均匀地分布每个关系内数据的哈希值，就是说哈希桶大小一致。 外关系的元素与哈希桶内的所有元素的匹配，成本是哈希桶内元素的数量。 时间复杂度是 (M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N 。 如果哈希函数创建了足够小规模的哈希桶，那么复杂度就是 O(M+N)。还有个哈希联接的版本，对内存有利但是对磁盘 I/O 不够有利。 这回是这样的：1) 计算内关系和外关系双方的哈希表 2) 保存哈希表到磁盘 3) 然后逐个哈希桶比较（其中一个读入内存，另一个逐行读取）。 合并联接合并联接是唯一产生排序的联接算法。注：这个简化的合并联接不区分内表或外表；两个表扮演同样的角色。但是真实的实现方式是不同的，比如当处理重复值时。1.（可选）排序联接运算：两个输入源都按照联接关键字排序。2.合并联接运算：排序后的输入源合并到一起。排序我们已经谈到过合并排序，在这里合并排序是个很好的算法（但是并非最好的，如果内存足够用的话，还是哈希联接更好）。然而有时数据集已经排序了，比如：如果表内部就是有序的，比如联接条件里一个索引组织表 【译者注： index-organized table 】 如果关系是联接条件里的一个索引 如果联接应用在一个查询中已经排序的中间结果 空闲内存：没有足够的内存的话就跟强大的哈希联接拜拜吧（至少是完全内存中哈希联接）。 两个数据集的大小。比如，如果一个大表联接一个很小的表，那么嵌套循环联接就比哈希联接快，因为后者有创建哈希的高昂成本；如果两个表都非常大，那么嵌套循环联接CPU成本就很高昂。 是否有索引：有两个 B+树索引的话，聪明的选择似乎是合并联接。 结果是否需要排序：即使你用到的是未排序的数据集，你也可能想用成本较高的合并联接（带排序的），因为最终得到排序的结果后，你可以把它和另一个合并联接串起来（或者也许因为查询用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或显式地要求一个排序结果）。 关系是否已经排序：这时候合并联接是最好的候选项。 联接的类型：是等值联接（比如 tableA.col1 = tableB.col2 ）？ 还是内联接？外联接？笛卡尔乘积？或者自联接？有些联接在特定环境下是无法工作的。 数据的分布：如果联接条件的数据是倾斜的（比如根据姓氏来联接人，但是很多人同姓），用哈希联接将是个灾难，原因是哈希函数将产生分布极不均匀的哈希桶。 如果你希望联接操作使用多线程或多进程。 动态规划，贪婪算法和启发式算法关系型数据库会尝试我刚刚提到的多种方法，优化器真正的工作是在有限时间里找到一个好的解决方案。多数时候，优化器找到的不是最佳的方案，而是一个『不错』的对于小规模的查询，采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴的方式，我们有办法避免不必要的计算，这就是动态规划。动态规划这几个字背后的理念是，很多执行计划是非常相似的。 贪婪算法但是，优化器面对一个非常大的查询，或者为了尽快找到答案（然而查询速度就快不起来了），会应用另一种算法，叫贪婪算法。原理是按照一个规则（或启发）以渐进的方式制定查询计划。在这个规则下，贪婪算法逐步寻找最佳算法，先处理一条JOIN，接着每一步按照同样规则加一条新的JOIN。我们来看个简单的例子。比如一个针对5张表（A,B,C,D,E）4次JOIN 的查询，为了简化我们把嵌套JOIN作为可能的联接方式，按照『使用最低成本的联接』规则。直接从 5 个表里选一个开始（比如 A） 计算每一个与 A 的联接（A 作为内关系或外关系） 发现 “A JOIN B” 成本最低 计算每一个与 “A JOIN B” 的结果联接的成本（”A JOIN B” 作为内关系或外关系） 发现 “(A JOIN B) JOIN C” 成本最低 计算每一个与 “(A JOIN B) JOIN C” 的结果联接的成本 …… 最后确定执行计划 “( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )” 因为我们是武断地从表 A 开始，我们可以把同样的算法用在 B，然后 C，然后 D, 然后 E。最后保留成本最低的执行计划。顺便说一句，这个算法有个名字，叫『最近邻居算法』。抛开细节不谈，只需一个良好的模型和一个 Nlog(N) 复杂度的排序，问题就轻松解决了。这个算法的复杂度是 O(Nlog(N)) ，对比一下完全动态规划的 O(3^N)。如果你有个20个联接的大型查询，这意味着 26 vs 3,486,784,401 ，天壤之别！这个算法的问题是，我们做的假设是：找到 2 个表的最佳联接方法，保留这个联接结果，再联接下一个表，就能得到最低的成本。但是：即使在 A, B, C 之间，A JOIN B 可得最低成本 (A JOIN C) JOIN B 也许比 (A JOIN B) JOIN C 更好。 为了改善这一状况，你可以多次使用基于不同规则的贪婪算法，并保留最佳的执行计划。其他算法[ 如果你已经受够了算法话题，就直接跳到下一部分。这部分对文章余下的内容不重要。] 【译者注：我也很想把这段跳过去 -_- 】很多计算机科学研究者热衷于寻找最佳的执行计划，他们经常为特定问题或模式探寻更好的解决方案，比如：如果查询是星型联接（一种多联接查询），某些数据库使用一种特定的算法。 如果查询是并行的，某些数据库使用一种特定的算法。 …… 其他算法也在研究之中，就是为了替换在大型查询中的动态规划算法。贪婪算法属于一个叫做启发式算法的大家族，它根据一条规则（或启发），保存上一步找到的方法，『附加』到当前步骤来进一步搜寻解决方法。有些算法根据特定规则，一步步的应用规则但不总是保留上一步找到的最佳方法。它们统称启发式算法。比如，基因算法就是一种：一个方法代表一种可能的完整查询计划 每一步保留了 P 个方法（即计划），而不是一个。 0) P 个计划随机创建 1) 成本最低的计划才会保留 2) 这些最佳计划混合在一起产生 P 个新的计划 3) 一些新的计划被随机改写 4) 1，2，3步重复 T 次 5) 然后在最后一次循环，从 P 个计划里得到最佳计划。 循环次数越多，计划就越好。我们来看看 SQLite 优化器 是怎么工作的。这是个轻量化数据库，它使用一种简单优化器，基于带有附加规则的贪婪算法，来限制可能性的数量。SQLite 在有 CROSS JOIN 操作符时从不给表重新排序 使用嵌套联接 外联接始终按顺序评估 …… 3.8.0之前的版本使用『最近邻居』贪婪算法来搜寻最佳查询计划 等等……我们见过这个算法！真是巧哈！ 从3.8.0版本（发布于2015年）开始，SQLite使用『N最近邻居』贪婪算法来搜寻最佳查询计划 我们再看看另一个优化器是怎么工作的。IBM DB2 跟所有企业级数据库都类似，我讨论它是因为在切换到大数据之前，它是我最后真正使用的数据库。看过官方文档后，我们了解到 DB2 优化器可以让你使用 7 种级别的优化：对联接使用贪婪算法 0 – 最小优化，使用索引扫描和嵌套循环联接，避免一些查询重写 1 – 低级优化 2 – 完全优化 对联接使用动态规划算法 3 – 中等优化和粗略的近似法 5 – 完全优化，使用带有启发式的所有技术 7 – 完全优化，类似级别5，但不用启发式 9 – 最大优化，完全不顾开销，考虑所有可能的联接顺序，包括笛卡尔乘积 可以看到 DB2 使用贪婪算法和动态规划算法。当然，他们不会把自己的启发算法分享出来的，因为查询优化器是数据库的看家本领。DB2 的默认级别是 5，优化器使用下列特性： 【译者注：以下出现的一些概念我没有做考证，因为[ 这段不重要，可以跳过 ]】使用所有可用的统计，包括线段树（frequent-value）和分位数统计（quantile statistics）。 使用所有查询重写规则（含物化查询表路由，materialized query table routing），除了在极少情况下适用的计算密集型规则。 使用动态规划模拟联接 有限使用组合内关系（composite inner relation） 对于涉及查找表的星型模式，有限使用笛卡尔乘积 考虑宽泛的访问方式，含列表预取（list prefetch，注：我们将讨论什么是列表预取），index ANDing（注：一种对索引的特殊操作），和物化查询表路由。 默认的，DB2 对联接排列使用受启发式限制的动态规划算法。其它情况 (GROUP BY, DISTINCT…) 由简单规则处理。 查询计划缓存由于创建查询计划是耗时的，大多数据库把计划保存在查询计划缓存，来避免重复计算。这个话题比较大，因为数据库需要知道什么时候更新过时的计划。办法是设置一个上限，如果一个表的统计变化超过了上限，关于该表的查询计划就从缓存中清除。查询执行器在这个阶段，我们有了一个优化的执行计划，再编译为可执行代码。然后，如果有足够资源（内存，CPU），查询执行器就会执行它。计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行，这取决于执行器。为了获得和写入数据，查询执行器与数据管理器交互，本文下一部分来讨论数据管理器在这一步，查询管理器执行了查询，需要从表和索引获取数据，于是向数据管理器提出请求。但是有 2 个问题：关系型数据库使用事务模型，所以，当其他人在同一时刻使用或修改数据时，你无法得到这部分数据。 数据提取是数据库中速度最慢的操作，所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。 在这一部分，我没看看关系型数据库是如何处理这两个问题的。我不会讲数据管理器是怎么获得数据的，因为这不是最重要的（而且本文已经够长的了！）。 缓存管理器我已经说过，数据库的主要瓶颈是磁盘 I/O。为了提高性能，现代数据库使用缓存管理器。查询执行器不会直接从文件系统拿数据，而是向缓存管理器要。缓存管理器有一个内存缓存区，叫做缓冲池，从内存读取数据显著地提升数据库性能。对此很难给出一个数量级，因为这取决于你需要的是哪种操作：顺序访问（比如：全扫描） vs 随机访问（比如：按照row id访问） 读还是写 以及数据库使用的磁盘类型：7.2k/10k/15k rpm的硬盘 SSD RAID 1/5/… 要我说，内存比磁盘要快100到10万倍。然而，这导致了另一个问题（数据库总是这样…)，缓存管理器需要在查询执行器使用数据之前得到数据，否则查询管理器不得不等待数据从缓慢的磁盘中读出来。预读这个问题叫预读。查询执行器知道它将需要什么数据，因为它了解整个查询流，而且通过统计也了解磁盘上的数据。道理是这样的：当查询执行器处理它的第一批数据时 会告诉缓存管理器预先装载第二批数据 当开始处理第二批数据时 告诉缓存管理器预先装载第三批数据，并且告诉缓存管理器第一批可以从缓存里清掉了。 …… 缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用，缓存管理器给缓存的数据添加了额外的信息（叫闩锁）。有时查询执行器不知道它需要什么数据，有的数据库也不提供这个功能。相反，它们使用一种推测预读法（比如：如果查询执行器想要数据1、3、5，它不久后很可能会要 7、9、11），或者顺序预读法（这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据）。为了监控预读的工作状况，现代数据库引入了一个度量叫缓冲/缓存命中率，用来显示请求的数据在缓存中找到而不是从磁盘读取的频率。注：糟糕的缓存命中率不总是意味着缓存工作状态不佳。更多信息请阅读Oracle文档。缓冲只是容量有限的内存空间，因此，为了加载新的数据，它需要移除一些数据。加载和清除缓存需要一些磁盘和网络I/O的成本。如果你有个经常执行的查询，那么每次都把查询结果加载然后清除，效率就太低了。现代数据库用缓冲区置换策略来解决这个问题。 缓冲区置换策略多数现代数据库(至少 SQL Server, MySQL, Oracle 和 DB2)使用 LRU 算法。LRULRU代表最近最少使用（Least Recently Used）算法，背后的原理是：在缓存里保留的数据是最近使用的，所以更有可能再次使用。 图解： 为了更好的理解，我假设缓冲区里的数据没有被闩锁锁住（就是说是可以被移除的）。在这个简单的例子里，缓冲区可以保存 3 个元素：1：缓存管理器（简称CM）使用数据1，把它放入空的缓冲区 2：CM使用数据4，把它放入半载的缓冲区 3：CM使用数据3，把它放入半载的缓冲区 4：CM使用数据9，缓冲区满了，所以数据1被清除，因为它是最后一个最近使用的，数据9加入到缓冲区 5：CM使用数据4，数据4已经在缓冲区了，所以它再次成为第一个最近使用的。 6：CM使用数据1，缓冲区满了，所以数据9被清除，因为它是最后一个最近使用的，数据1加入到缓冲区 …… 这个算法效果很好，但是有些限制。如果对一个大表执行全表扫描怎么办？换句话说，当表/索引的大小超出缓冲区会发生什么？使用这个算法会清除之前缓存内所有的数据，而且全扫描的数据很可能只使用一次。改进为了防止这个现象，有些数据库增加了特殊的规则，比如Oracle文档中的描述：『对非常大的表来说，数据库通常使用直接路径来读取，即直接加载区块[……]，来避免填满缓冲区。对于中等大小的表，数据库可以使用直接读取或缓存读取。如果选择缓存读取，数据库把区块置于LRU的尾部，防止清空当前缓冲区。』 还有一些可能，比如使用高级版本的LRU，叫做 LRU-K。例如，SQL Server 使用 LRU-2。这个算法的原理是把更多的历史记录考虑进来。简单LRU（也就是 LRU-1），只考虑最后一次使用的数据。LRU-K呢：考虑数据最后第K次使用的情况 数据使用的次数加进了权重 一批新数据加载进入缓存，旧的但是经常使用的数据不会被清除（因为权重更高） 但是这个算法不会保留缓存中不再使用的数据 所以数据如果不再使用，权重值随着时间推移而降低 计算权重是需要成本的，所以SQL Server只是使用 K=2，这个值性能不错而且额外开销可以接受。其他算法当然还有其他管理缓存的算法，比如：2Q（类LRU-K算法） CLOCK（类LRU-K算法） MRU（最新使用的算法，用LRU同样的逻辑但不同的规则） LRFU（Least Recently and Frequently Used，最近最少使用最近最不常用） …… 写缓冲区我只探讨了读缓存 —— 在使用之前预先加载数据。用来保存数据、成批刷入磁盘，而不是逐条写入数据从而造成很多单次磁盘访问。要记住，缓冲区保存的是页（最小的数据单位）而不是行（逻辑上/人类习惯的观察数据的方式）。缓冲池内的页如果被修改了但还没有写入磁盘，就是脏页。有很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联，下面我们就谈谈事务。 事务管理器最后但同样重要的，是事务管理器，我们将看到这个进程是如何保证每个查询在自己的事务内执行的。但开始之前，我们需要理解ACID事务的概念。现代数据库不会使用纯粹的隔离作为默认模式，因为它会带来巨大的性能消耗。SQL一般定义4个隔离级别：串行化(Serializable，SQLite默认模式）：最高级别的隔离。两个同时发生的事务100%隔离，每个事务有自己的『世界』。 可重复读（Repeatable read，MySQL默认模式）：每个事务有自己的『世界』，除了一种情况。如果一个事务成功执行并且添加了新数据，这些数据对其他正在执行的事务是可见的。但是如果事务成功修改了一条数据，修改结果对正在运行的事务不可见。所以，事务之间只是在新数据方面突破了隔离，对已存在的数据仍旧隔离。 举个例子，如果事务A运行”SELECT count(1) from TABLE_X” ，然后事务B在 TABLE_X 加入一条新数据并提交，当事务A再运行一次 count(1)结果不会是一样的。 这叫幻读（phantom read）。 读取已提交（Read committed，Oracle、PostgreSQL、SQL Server默认模式）：可重复读+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（或删除）并提交，事务A再次读取数据D时数据的变化（或删除）是可见的。 这叫不可重复读（non-repeatable read）。 读取未提交（Read uncommitted）：最低级别的隔离，是读取已提交+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（但并未提交，事务B仍在运行中），事务A再次读取数据D时，数据修改是可见的。如果事务B回滚，那么事务A第二次读取的数据D是无意义的，因为那是事务B所做的从未发生的修改（已经回滚了嘛）。 这叫脏读（dirty read）。 多数数据库添加了自定义的隔离级别（比如 PostgreSQL、Oracle、SQL Server的快照隔离），而且并没有实现SQL规范里的所有级别（尤其是读取未提交级别）。默认的隔离级别可以由用户/开发者在建立连接时覆盖（只需要增加很简单的一行代码）。 并发控制确保隔离性、一致性和原子性的真正问题是对相同数据的写操作（增、更、删）：如果所有事务只是读取数据，它们可以同时工作，不会更改另一个事务的行为。 如果（至少）有一个事务在修改其他事务读取的数据，数据库需要找个办法对其它事务隐藏这种修改。而且，它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除。 这个问题叫并发控制。最简单的解决办法是依次执行每个事务（即顺序执行），但这样就完全没有伸缩性了，在一个多处理器/多核服务器上只有一个核心在工作，效率很低。理想的办法是，每次一个事务创建或取消时：监控所有事务的所有操作 检查是否2个（或更多）事务的部分操作因为读取/修改相同的数据而存在冲突 重新编排冲突事务中的操作来减少冲突的部分 按照一定的顺序执行冲突的部分（同时非冲突事务仍然在并发运行） 考虑事务有可能被取消 用更正规的说法，这是对冲突的调度问题。更具体点儿说，这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时，来寻找每个新事务活动最好的调度，因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。 锁管理器为了解决这个问题，多数数据库使用锁和/或数据版本控制。这是个很大的话题，我会集中探讨锁，和一点点数据版本控制。悲观锁原理是：如果一个事务需要一条数据 它就把数据锁住 如果另一个事务也需要这条数据 它就必须要等第一个事务释放这条数据 这个锁叫排他锁。 但是对一个仅仅读取数据的事务使用排他锁非常昂贵，因为这会迫使其它只需要读取相同数据的事务等待。因此就有了另一种锁，共享锁。共享锁是这样的：如果一个事务只需要读取数据A 它会给数据A加上『共享锁』并读取 如果第二个事务也需要仅仅读取数据A 它会给数据A加上『共享锁』并读取 如果第三个事务需要修改数据A 它会给数据A加上『排他锁』，但是必须等待另外两个事务释放它们的共享锁。 同样的，如果一块数据被加上排他锁，一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。锁管理器是添加和释放锁的进程，在内部用一个哈希表保存锁信息（关键字是被锁的数据），并且了解每一块数据是：被哪个事务加的锁 哪个事务在等待数据解锁 死锁但是使用锁会导致一种情况，2个事务永远在等待一块数据： 在本图中： 事务A 给 数据1 加上排他锁并且等待获取数据2 事务B 给 数据2 加上排他锁并且等待获取数据1 这叫死锁。在死锁发生时，锁管理器要选择取消（回滚）一个事务，以便消除死锁。这可是个艰难的决定：杀死数据修改量最少的事务（这样能减少回滚的成本）？ 杀死持续时间最短的事务，因为其它事务的用户等的时间更长？ 杀死能用更少时间结束的事务（避免可能的资源饥荒）？ 一旦发生回滚，有多少事务会受到回滚的影响？ 在作出选择之前，锁管理器需要检查是否有死锁存在。哈希表可以看作是个图表（见上文图），图中出现循环就说明有死锁。由于检查循环是昂贵的（所有锁组成的图表是很庞大的），经常会通过简单的途径解决：使用超时设定。如果一个锁在超时时间内没有加上，那事务就进入死锁状态。锁管理器也可以在加锁之前检查该锁会不会变成死锁，但是想要完美的做到这一点还是很昂贵的。因此这些预检经常设置一些基本规则。两段锁实现纯粹的隔离最简单的方法是：事务开始时获取锁，结束时释放锁。就是说，事务开始前必须等待确保自己能加上所有的锁，当事务结束时释放自己持有的锁。这是行得通的，但是为了等待所有的锁，大量的时间被浪费了。更快的方法是两段锁协议（Two-Phase Locking Protocol，由 DB2 和 SQL Server使用），在这里，事务分为两个阶段：成长阶段：事务可以获得锁，但不能释放锁。 收缩阶段：事务可以释放锁（对于已经处理完而且不会再次处理的数据），但不能获得新锁。 这两条简单规则背后的原理是：释放不再使用的锁，来降低其它事务的等待时间 防止发生这类情况：事务最初获得的数据，在事务开始后被修改，当事务重新读取该数据时发生不一致。 这个规则可以很好地工作，但有个例外：如果修改了一条数据、释放了关联的锁后，事务被取消（回滚），而另一个事务读到了修改后的值，但最后这个值却被回滚。为了避免这个问题，所有独占锁必须在事务结束时释放。多说几句当然了，真实的数据库使用更复杂的系统，涉及到更多类型的锁（比如意向锁，intention locks）和更多的粒度（行级锁、页级锁、分区锁、表锁、表空间锁），但是道理是相同的。我只探讨纯粹基于锁的方法，数据版本控制是解决这个问题的另一个方法。版本控制是这样的：每个事务可以在相同时刻修改相同的数据 每个事务有自己的数据拷贝（或者叫版本） 如果2个事务修改相同的数据，只接受一个修改，另一个将被拒绝，相关的事务回滚（或重新运行） 这将提高性能，因为：读事务不会阻塞写事务 写事务不会阻塞读 没有『臃肿缓慢』的锁管理器带来的额外开销 除了两个事务写相同数据的时候，数据版本控制各个方面都比锁表现得更好。只不过，你很快就会发现磁盘空间消耗巨大。数据版本控制和锁机制是两种不同的见解：乐观锁和悲观锁。两者各有利弊，完全取决于使用场景（读多还是写多）。关于数据版本控制，我推荐这篇非常优秀的文章，讲的是PostgreSQL如何实现多版本并发控制的。一些数据库，比如DB2（直到版本 9.7）和 SQL Server（不含快照隔离）仅使用锁机制。其他的像PostgreSQL, MySQL 和 Oracle 使用锁和鼠标版本控制混合机制。我不知道是否有仅用版本控制的数据库（如果你知道请告诉我）。[2015-08-20更新]一名读者告诉我：Firebird 和 Interbase 用不带锁的版本控制。版本控制对索引的影响挺有趣的：有时唯一索引会出现重复，索引的条目会多于表行数，等等。 如果你读过不同级别的隔离那部分内容，你会知道，提高隔离级别就会增加锁的数量和事务等待加锁的时间。这就是为什么多数数据库默认不会使用最高级别的隔离（即串行化）。当然，你总是可以自己去主流数据库（像MySQL, PostgreSQL 或 Oracle）的文档里查一下。 日志管理器我们已经知道，为了提升性能，数据库把数据保存在内存缓冲区内。但如果当事务提交时服务器崩溃，崩溃时还在内存里的数据会丢失，这破坏了事务的持久性。你可以把所有数据都写在磁盘上，但是如果服务器崩溃，最终数据可能只有部分写入磁盘，这破坏了事务的原子性。事务作出的任何修改必须是或者撤销，或者完成。有 2 个办法解决这个问题：影子副本/页（Shadow copies/pages）：每个事务创建自己的数据库副本（或部分数据库的副本），并基于这个副本来工作。一旦出错，这个副本就被移除；一旦成功，数据库立即使用文件系统的一个把戏，把副本替换到数据中，然后删掉『旧』数据。 事务日志（Transaction log）：事务日志是一个存储空间，在每次写盘之前，数据库在事务日志中写入一些信息，这样当事务崩溃或回滚，数据库知道如何移除或完成尚未完成的事务。 WAL（预写式日志）影子副本/页在运行较多事务的大型数据库时制造了大量磁盘开销，所以现代数据库使用事务日志。事务日志必须保存在稳定的存储上，我不会深挖存储技术，但至少RAID磁盘是必须的，以防磁盘故障。多数数据库（至少是Oracle, SQL Server, DB2, PostgreSQL, MySQL 和 SQLite) 使用预写日志协议（Write-Ahead Logging protocol ，WAL）来处理事务日志。WAL协议有 3 个规则：1) 每个对数据库的修改都产生一条日志记录，在数据写入磁盘之前日志记录必须写入事务日志。 2) 日志记录必须按顺序写入；记录 A 发生在记录 B 之前，则 A 必须写在 B 之前。 3) 当一个事务提交时，在事务成功之前，提交顺序必须写入到事务日志。 这个工作由日志管理器完成。简单的理解就是，日志管理器处于缓存管理器（cache manager）和数据访问管理器（data access manager，负责把数据写入磁盘）之间，每个 update / delete / create / commit / rollback 操作在写入磁盘之前先写入事务日志。简单，对吧？回答错误！ 我们研究了这么多内容，现在你应该知道与数据库相关的每一件事都带着『数据库效应』的诅咒。好吧，我们说正经的，问题在于，如何找到写日志的同时保持良好的性能的方法。如果事务日志写得太慢，整体都会慢下来。 1992年，IBM 研究人员『发明』了WAL的增强版，叫 ARIES。ARIES 或多或少地在现代数据库中使用，逻辑未必相同，但AIRES背后的概念无处不在。我给发明加了引号是因为，按照MIT这门课的说法，IBM 的研究人员『仅仅是写了事务恢复的最佳实践方法』。AIRES 论文发表的时候我才 5 岁，我不关心那些酸溜溜的科研人员老掉牙的闲言碎语。事实上，我提及这个典故，是在开始探讨最后一个技术点前让你轻松一下。我阅读过这篇 ARIES 论文 的大量篇幅，发现它很有趣。在这一部分我只是简要的谈一下 ARIES，不过我强烈建议，如果你想了解真正的知识，就去读那篇论文。ARIES 代表『数据库恢复原型算法』（Algorithms for Recovery and Isolation Exploiting Semantics）。这个技术要达到一个双重目标：1) 写日志的同时保持良好性能 2) 快速和可靠的数据恢复 有多个原因让数据库不得不回滚事务：因为用户取消 因为服务器或网络故障 因为事务破坏了数据库完整性（比如一个列有唯一性约束而事务添加了重复值） 因为死锁 有时候（比如网络出现故障），数据库可以恢复事务。这怎么可能呢？为了回答这个问题，我们需要了解日志里保存的信息。 日志 事务的每一个操作（增/删/改）产生一条日志，由如下内容组成：LSN：一个唯一的日志序列号（Log Sequence Number）。LSN是按时间顺序分配的 * ，这意味着如果操作 A 先于操作 B，log A 的 LSN 要比 log B 的 LSN 小。 TransID：产生操作的事务ID。 PageID：被修改的数据在磁盘上的位置。磁盘数据的最小单位是页，所以数据的位置就是它所处页的位置。 PrevLSN：同一个事务产生的上一条日志记录的链接。 UNDO：取消本次操作的方法。 比如，如果操作是一次更新，UNDO将或者保存元素更新前的值/状态（物理UNDO），或者回到原来状态的反向操作（逻辑UNDO） 。 REDO：重复本次操作的方法。 同样的，有 2 种方法：或者保存操作后的元素值/状态，或者保存操作本身以便重复。 …：（供您参考，一个 ARIES 日志还有 2 个字段：UndoNxtLSN 和 Type）。 进一步说，磁盘上每个页（保存数据的，不是保存日志的）都记录着最后一个修改该数据操作的LSN。*LSN的分配其实更复杂，因为它关系到日志存储的方式。但道理是相同的。 ARIES 只使用逻辑UNDO，因为处理物理UNDO太过混乱了。注：据我所知，只有 PostgreSQL 没有使用UNDO，而是用一个垃圾回收服务来删除旧版本的数据。这个跟 PostgreSQL 对数据版本控制的实现有关。为了更好的说明这一点，这有一个简单的日志记录演示图，是由查询 “UPDATE FROM PERSON SET AGE = 18;” 产生的，我们假设这个查询是事务18执行的。【译者注： SQL 语句原文如此，应该是作者笔误 】每条日志都有一个唯一的LSN，链接在一起的日志属于同一个事务。日志按照时间顺序链接（链接列表的最后一条日志是最后一个操作产生的）。日志缓冲区为了防止写日志成为主要的瓶颈，数据库使用了日志缓冲区。 当查询执行器要求做一次修改： 1) 缓存管理器将修改存入自己的缓冲区； 2) 日志管理器将相关的日志存入自己的缓冲区； 3) 到了这一步，查询执行器认为操作完成了（因此可以请求做另一次修改）； 4) 接着（不久以后）日志管理器把日志写入事务日志，什么时候写日志由某算法来决定。 5) 接着（不久以后）缓存管理器把修改写入磁盘，什么时候写盘由某算法来决定。 当事务提交，意味着事务每一个操作的 1 2 3 4 5 步骤都完成了。写事务日志是很快的，因为它只是『在事务日志某处增加一条日志』；而数据写盘就更复杂了，因为要用『能够快速读取的方式写入数据』。STEAL 和 FORCE 策略出于性能方面的原因，第 5 步有可能在提交之后完成，因为一旦发生崩溃，还有可能用REDO日志恢复事务。这叫做 NO-FORCE策略。数据库可以选择FORCE策略（比如第 5 步在提交之前必须完成）来降低恢复时的负载。另一个问题是，要选择数据是一步步的写入（STEAL策略），还是缓冲管理器需要等待提交命令来一次性全部写入（NO-STEAL策略）。选择STEAL还是NO-STEAL取决于你想要什么：快速写入但是从 UNDO 日志恢复缓慢，还是快速恢复。总结一下这些策略对恢复的影响：STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高，但是日志和恢复过程更复杂 (比如 ARIES)。多数数据库选择这个策略。 注：这是我从多个学术论文和教程里看到的，但并没有看到官方文档里显式说明这一点。 STEAL/ FORCE 只需要 UNDO. NO-STEAL/NO-FORCE 只需要 REDO. NO-STEAL/FORCE 什么也不需要: 性能最差，而且需要巨大的内存。 关于恢复Ok，有了不错的日志，我们来用用它们！假设新来的实习生让数据库崩溃了（首要规矩：永远是实习生的错。），你重启了数据库，恢复过程开始了。ARIES从崩溃中恢复有三个阶段：1) 分析阶段：恢复进程读取全部事务日志，来重建崩溃过程中所发生事情的时间线，决定哪个事务要回滚（所有未提交的事务都要回滚）、崩溃时哪些数据需要写盘。 2) Redo阶段：这一关从分析中选中的一条日志记录开始，使用 REDO 来将数据库恢复到崩溃之前的状态。 在REDO阶段，REDO日志按照时间顺序处理（使用LSN）。对每一条日志，恢复进程需要读取包含数据的磁盘页LSN。如果LSN（磁盘页）>= LSN（日志记录），说明数据已经在崩溃前写到磁盘（但是值已经被日志之后、崩溃之前的某个操作覆盖），所以不需要做什么。如果LSN（磁盘页）< LSN（日志记录），那么磁盘上的页将被更新。即使将被回滚的事务，REDO也是要做的，因为这样简化了恢复过程（但是我相信现代数据库不会这么做的）。3) Undo阶段：这一阶段回滚所有崩溃时未完成的事务。回滚从每个事务的最后一条日志开始，并且按照时间倒序处理UNDO日志（使用日志记录的PrevLSN）。 恢复过程中，事务日志必须留意恢复过程的操作，以便写入磁盘的数据与事务日志相一致。一个解决办法是移除被取消的事务产生的日志记录，但是这个太困难了。相反，ARIES在事务日志中记录补偿日志，来逻辑上删除被取消的事务的日志记录。当事务被『手工』取消，或者被锁管理器取消（为了消除死锁），或仅仅因为网络故障而取消，那么分析阶段就不需要了。对于哪些需要 REDO 哪些需要 UNDO 的信息在 2 个内存表中：事务表（保存当前所有事务的状态） 脏页表（保存哪些数据需要写入磁盘） 当新的事务产生时，这两个表由缓存管理器和事务管理器更新。因为是在内存中，当数据库崩溃时它们也被破坏掉了。分析阶段的任务就是在崩溃之后，用事务日志中的信息重建上述的两个表。为了加快分析阶段，ARIES提出了一个概念：检查点（check point），就是不时地把事务表和脏页表的内容，还有此时最后一条LSN写入磁盘。那么在分析阶段当中，只需要分析这个LSN之后的日志即可。

阅读全文

mysql_index

Posted by 夏泽民 Nov 16, 2017

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

阅读全文

MySQL的表类型的（存储引擎）

Posted by 夏泽民 Nov 16, 2017

查看数据库支持的存储引擎： \G或者分号表示命令结束 MySQL>show engines \G or show variables like ‘have%’; mysql -h localhost -u root -p123 show databases; use database; show tables;

阅读全文

Search

Blog Categories

jekyll (35)
web (334)
technology (2)
php (201)
linux (415)
spark (51)
deep_learning (2)
storage (290)
golang (1081)
cryptology (15)
lang (74)
docker (100)
zookeeper (11)
elasticsearch (86)
java (7)
algorithm (134)
hadoop (2)
slug (1)
architect (46)
k8s (107)
node (82)
python (18)
mysql (42)
rust (4)
elasticSearch (1)
arch (1)
Javascript (1)
kafka (2)
nginx (7)

Popular posts

Anything in here will be replaced on browsers that support the canvas element

Recent posts

Tags

This blog is maintained by 夏泽民

Get in touch with me at 465474307@qq.com

Subscribe to our mailing list

* indicates required