随意的世界 - 数据库
type: channel
link: http://1.117.140.145/数据库
items: LSM基础
items: Faster笔记
items: Megastore: Providing Scalable, Highly Available Storage for Interactive Services（1）
items: Dynamo：亚马逊的高可用键值对存储
items: Cassandra 一个去中心化的结构化存储
items: Percolator
items: Bigtable解读
items: Bigtable：面向结构化数据的分布式存储系统
items: Mysql成本计算规则Optimizer trace
items: Redis特性

LSM基础
type: item
date: 2025-08-01T12:46:19+08:00
description: LSM‍‌‌‍⁠‌‬⁠⁠‍‍‬‌﻿‌⁠⁠‬‌‌‍‬‬‍‌‬‍⁠wiscKey论文精读 - 飞书云文档经典LSM实现-LevelDB适合磁盘索引的结构通常有俩中，一种是就地更新B+，一种是就地更新LSM。B+树读取性能更好，B+树随机写入很差，LSM写入性能更好。接下来内容都讨论LSM Tree。最直观的想法是将随机写入改成顺序写入，最简答的方法就是假设一个无限大小的文件，每次kv为一组，一直向后追加。这样会引出几个问题。同一个key可能被写入多次，更早的key就无效了，会浪费磁盘空间。读取的性能是不可接受的，读取一个数据可能要扫描全部文件。一个简单的优化想法就是合并这个无限大的文件，将被覆盖的key清理掉，只保留最新的key，但这样就不能在一个文件中操作（不能将压缩过程变成更新，类似GC），因此需要将文件分段。每次合并本质上就是一个归并排序的过程（为了支持范围查询，以及空间压缩），那么就需要找到所有分段文件中有重合范围的文件，进行合并。而且不能合并一个正在写入的文件。为了降低读取的复杂度，第一个想法就是使用内存，将最近新写入的kv存储在内存数据结构中，红黑树，跳表等。那么问题是合适将数据结构dump到磁盘？最简单的是根据其大小的区别，然而在dump之前我们不能继续向其中写数据。为了更好的确定内存中的数据结构什么时候应该被写入，我们应该在内存中维护一个不变内存表和活跃内存表，周期性的将不变内存表dump到内存中形成一个文件。这些都没有解决最先写入且从未更新的key尧都区全量数据的问题，为解决这个问题LSM结构引入了分层的思想。由于我们区分了不变内存，因此从内存dump到磁盘的文件一定是有序的。L0中每个文件内是不会出现重复的现象，但是文件之间可能是乱序的。从L1开始，每个层级内的SSTable文件必须保证Key范围有序且不重叠。这是通过compaction实现的。我们假设直接从内存写入磁盘的文件为第0层，从第0层合并数据到第二层。那么从c1-ck层，他们的数据只会出现一次。而c1-ck是发生过合并的文件。由于ci+1 是ci中具有重叠部分的文件合并的产物，因此可以说在同一层内是不存在重叠key的，因为重叠key已经在其上一层被合并了。那么只有c0层是可能存在重叠的文件的。所以当要读取磁盘上的数据时，最坏情况下只需要读取c0的所有文件以及c1-ck每一层中的一个文件即c0+k个文件即可找到key的位置，分层合并思想使得非就地更新索引在常数次的IO中读取数据。L1 的每个文件负责的 Key 范围是 由 Compaction 动态划分的，而非预先固定。例如：如果 L0 和 L1 的合并数据覆盖 [a, z]，Compaction 可能将其拆分为多个文件（如 [a, g]、[h, m]、[n, z]），每个文件大小接近 target_file_size（默认 2MB）。LSM tree中，文件更新完全通过原子替换实现。L1和L2的归并步骤选择 L1 层的所有 SSTable 文件选择 L2 层中与 L1 层有键范围重叠的 SSTable 文件对这些文件进行多路归并排序生成新的 L2 层 SSTable 文件删除旧的 L1 和 L2 层参与合并的文件leveldb最多有8层，假设第0层最多6个文件，我们只需要读取14个文件就能找到一个key。用户在读取同一个key的时候，只要读取最上面的最新版本即可。简单来说，同一层只有一个相同的key，但是不同层可能有多个相同的key的（不同版本）。在一个巨大的日志文件中找一个key也是很难的，leveldb中有三个模块，元数据区，索引区，数据表。元数据区存在布隆过滤器，可以直接判断key是不是在当前文件。布隆过滤器存在假阳，当假阳发生时，需要读取索引块。这个索引存储了key和对应value的偏移量，可以直接在内存中进行二分查找。实际上存储数据的结构叫做sstable。为了标记哪些SStable属于哪一层，因此要存在一个sstable的元数据管理文件，在levelDB中叫做MANIFEST文件。其中存储每一个sstable的文件名，所属的级别，最大与最小的key的前缀。LSM树中，一层有多个文件，这允许多个文件进行并行写入操作，小文件可以独立合并，避免每次合并都要重写整个层的数据。小规模更新对系统影响小，且每个层都可以维护自己的布隆过滤器。LSM tree优化方向LSM 是牺牲读取性能和空间利用率为代价，换取写入性能的。因此，对LSM的结构优化目标就是想办法提高读取性能和空间录用率。KV分离对SSD的优化SSD上引用LSM技术带来俩个问题，第一写放大缩短了SSD寿命，第二传统LSM无法充分发挥SSD的并行写入特性。相较于机械硬盘，随机读取与顺序读取的性能在固态上没有那么显著。意味着过分追求顺序读取而进行…

Faster笔记
type: item
date: 2025-07-07T16:51:00+08:00
description: Faster笔记Epochepoch框架Faster是基于一个关键的设计原则，旨在实现可伸缩性：避免在线程和公共的访问路径之间的昂贵协调开销。更快的线程在大多数情况下独立执行操作，不需要同步。与此同时，他们需要就共享系统整天同步的通用机制达成一致。为了实现这个目标我们扩展了多线程访问 epoch安全到一个框架中在任意全局操作上启用异步延迟。Epoch basics是Faster用于协调多线程并发访问的轻量级同步机制。以下是核心组件线程记作$T$全局当前epoch（E）一个原子计数器，由系统维护，记为当前的epoch。线程本地epoch$E_T$：每个线程维护自己本地版本的E，线程会定期刷新本地的E。安全epoch$E_s$：全局变量，表示所有线程以观察到的最小epoch值。即本地所有线程的epoch大于$E_s$时，$E_s$才会更新为那个新值。所有线程本地的$E_T$被存储在epoch table中每个线程占用一个缓存行（应该是为了防止缓存行伪共享）。对于任意的epoch $c$如果所有的线程本地的epoch都大于$c$，那么这个c就是安全的。系统保持对于任意的$T$, $E_s<E_T \leq E$Trigger action当把当前的线程从$c$增加到$c+1$,线程可以额外关联一个操作这个操作在将来系统epoch$c$为安全时进行触发。这是通过drain-list实现的，一个<epoch,action>pairs的列表，其中的action是回调代码。这通过使用小的数组来实现的，每当$E_s$更新时，该数组会被扫描以寻找触发的动作。我们在数组上使用原子的比较并交换来确保每个操作只被执行一次。使用epoch框架我们使用四个操作来暴露epoch保护框架，它可以被任意线程调用。Acquire：为$T$保留一个条目并且设置$E_T$为$E$。Refresh：更新$E_T$为$E$, $E_s$更新为当前最大的安全epoch并且触发在drain-list中就绪的操作。BumpEpoch(Action)：将计数器E从当前值c增加到c+1，并且添加到drain-list当中。Release：从epoch table中删除T。具有延迟触发动作的epoch可用于简化并行系统中的延迟同步。考虑一个典型案例，当共享变量状态更新为active时，必须调用active-now函数。线程将自动的将状态更新为active，并以active-now作为触发动作来触发epoch。并不是所有线程都会立即观察到状态的变化。然而他们都保证在刷新它们的epoch的时候观察到它，（由于使用内存屏障的顺序内存一致性）因此active-now只有在所有线程看到状态为活动状态后才会被调用，因此是安全的。我们使用epoch框架在faster中协调系统操作，比如内存安全的垃圾收集，索引改变，循环缓冲维护和页刷新，共享日志页边界维护和检查点。同时在短时间内为用户操作（如读取和更新提供更快的线程不收锁限制地访问共享内存位置）。Faster线程的生命周期我们使用faster实现了一个计数器存储（counter store），其中一组faster用户线程会传递与传入请求关联的计数器。线程首先调用Acquire向epoch机制注册自身，随后发起一系列的用户操作，并定期调用Refresh（例如没256次操作调用一次）以将线程移至当前epoch，同时调用completePending（例如没64K操作调用一次）来处理所有先前待处理操作。最后线程调用release来注销Faster的调用。Faster的哈希索引Faster的关键构建块是哈希索引，一个并发的无延迟可扩展以及可变的基于哈希的索引。为了便于说明，我们假设一个64位的机器，有64个字节的缓存行。在大的架构中我们期望有更大的原子操作，从而允许我们的设计可扩展。在4,5,6章中，我们把这个索引与不同的分配器配对，以创建功能不断增强的键值对存储。3.1 索引组织faster索引是一个缓存对其的$2^k$大小的哈希桶，其中每个桶的大小和缓存行对其（图2）。因此，一个64字节的同由7个8字节的哈希桶项和一个8字节的条目。每个溢出的桶（每个桶包含7个条目+1个溢出指针）也具有缓存行的大小和对其方式，并使用内存分配器按需分配。选择8字节的条目是关键的，因为它允许我们使用64位原子比较并交换操作对条目进行无锁操作。在64位机器上，物理地址通常占用不到64位，例如因特尔机器通常使用48位指针。因此我们可以偷窃这些额外的比特来进行索引操作（Faster至少需要一个bit）。在本文的其余部分中，我们使用48位指针，但请注意，我们可以支持63位长度的指针。每个哈希桶（图2）包含了三个部分：tag（15bit），tentative bit和地址。0值的条…

Megastore: Providing Scalable, Highly Available Storage for Interactive Services（1）
type: item
date: 2025-05-23T13:28:40+08:00
description: Megastore: Providing Scalable, Highly Available Storage for Interactive ServicesMegastore.pdfINTRODUCTIONMegastore Blends the scalability of a NOSQL data storage with the convenience of a traditional RDBMS. It uses synchronous replication to achieve high availability and a consistent view of data. It provide fully serializable ACID semantics over distant replicas with low enough latencies to support iterative application.We accomplish this by taking a middle ground in the RDBMS vs. NoSQL design space: we partition the data-store and replicate each partition separately, providing full ACID semantics within partitions, but only limited consistency guarantees across them. We believe that megastore is the largest system deployed that uses Paxos to replicate primary user data across datacenters on every write. Megastore has been widely deployed within Google for several years. It handles more than three billion write and 20 billion read transactions daily and stores nearly a petabyte of primary data across many global datacenters.The key contribution of this paper are:the design of a data model and storage system that allows rapid development of interactive applications where high availability and scalability are built-in from the start;an implementation of the Paxos replication and consensus algorithm optimized for low-latency operation across geographically distributed datacenters to provide high availability for the system;a report on our experience with a large-scale deployment of Megastore at Google.2 Toward Availability and scalefor availability, we implemented a synchronous ,fault-tolerant log replicator optimized for long distance-links.for scale, we partitioned data into a vast space of small databases, each with its own replicated log stored in a per-replica NoSQL datastore.2.1common strategies for with-area replication:Asynchronous Master/slave: a master node replicates write-ahead log entries to at least one slave. Log appends are acknowledged at the master i…

Dynamo：亚马逊的高可用键值对存储
type: item
date: 2024-12-02T16:39:00+08:00
description: Dynamo：亚马逊的高可用键值对存储概要在大规模下的可靠性是我们在亚马逊一个大的挑战，一个世界上最大的电商系统。即便是轻微的中断也会明显的财务影响并且影响了客户的信任。亚马逊平台提供了给世界尺度的很多网站提供服务，在成千上万台基础设施上实现的，并且网络组件位于许多遍布世界的数据中心。在这个规模下，小或者大的组件连续不断的故障，面对这些故障时管理持久化状态的方式驱动了可靠的可扩展的软件系统。这个paper提出了设计和Dynamo的实现，一个高可用的键值对存储系统，亚马逊的一些核心服务就是用它来提供永远的在线体验的。为了达到这种级别的可用性，Dynamo牺牲了在某些故障场景下的一致性。它以一种为开发人员提供新颖接口的方式，广泛使用了对象版本控制应用辅助的冲突解决，1 介绍亚马逊运行着世界范围的电商平台，在高峰时段为数以千万的客户提供服务，使用上万台服务器位于世界的许多数据中心。在亚马逊平台上的操作对于性能，可靠性，有效性方面有严格的要求，为了支持持续增长，平台需要具有高度可扩展性。可靠性是一个最重要的需求，因为即便是小的中断也会导致明显的经济后果和影响客户的信任。此外，为了支持持续的增长平台徐亚高扩展性。我们团队组织从运营亚马逊平台中学到的经验之一，系统的可靠性可扩展性依赖于如何管理应用程序状态。亚马逊使用了高度去中心化的，松耦合的，面向服务体系结构，由数百个服务组成。在这个环境特别需要强大的永远可用的存储技术。例如客户有能查看和添加项目到购物车即便磁盘故障。网络线路不稳定，数据中心被龙卷风摧毁。因此，服务负责管理购物车他可以永远被读取和写入在数据存储，数据需要跨多个数据中心高可用。处理由百万个组件组成的基础设施中的故障是我们标注的操作模式；总会有几个小的但是显著数量的服务和网络组件在一些给定时间内故障。因此亚马逊软件系统需要构建一种方式，他将异常视为正常情况而不影响可用性和性能。为了应对可靠性和扩展性需求，亚马逊开发了几个存储技术，其中Amazon Simple storage Service (也可以在亚马逊之外访问到，被称为Amazon S3)，可能是最有名的。这篇论文提出了Dynamo的实现和设计。在亚马逊平台上构建的另一种高可用的可靠的可扩展的分布式数据存储。Dynamo被用来管理服务状态，它们对可靠性的需求非常高并且需要严格的控制，可用性，一致性成本效益和性能。amazon平台有非常多样的应用在不同的存储需求。选择一组应用需要一种存储技术，他足够弹性，以让应用设计人员根据这些权衡适当的配置数据存储以实现高可用，使用最划算的方式保证性能 。许多在亚马逊平台上的服务他们只需要键值对访问。对于许多服务，比如提供畅销排行榜的，购物车，客户偏好，会话管理，销售排名和产品目录，使用关系型数据库的常见模式会导致低效率以及限制了规模和可用性。Dynamo提供了简单的键值对接口，以应对这些应用的需要。Dynamo使用了一些工作的良好的技术综合以达到可扩展性和可靠性：数据被通过一致性哈希进行分区和复制。通过在更新期间保持副本的一致性通过法定人数技术和去中心化的复制同步协议。Dynamo使用了基于gossip的故障探测和成员协议。Dynamo是一个完全去中心化的系统并且最小化手动管理的需求。存储节点可以在Dynamo添加或者删除而不需要任何手动分区或者重分布。在过去的一年中，Dynamo已经成为了亚马逊贸易平台中的几个核心服务的底层存储技术。它能够在节假日扩展到极端的峰值负载而无需任何停机时间。例如，维护购物车的服务服务于数千万的请求在同一天就有超过300万的结账，管理会话状态的服务处理数十万的活动会话。这项工作对于学术届的主要贡献是评估了如何结合不同的技术来提供单一的高可用性系统。他展示了最终一致性的存储系统可以被用在对于有着高要求的应用。他也提供了对这些技术调优的深入理解以应对生产系统非常严苛的性能需求。背景亚马逊的电商平台由几百项服务组成，这些协同功能从推荐到订单履行到欺诈检测的各种功能。每个服务都通过良好定义的接口进行暴露可通过网络访问。这些服务被托管于由上万个服务谓语世界范围内的数据中心。其中的一些服务是无状态的（服务聚合从其他服务的影响）一些是有状态的（即服务在他存储在持久化系统的状态上执行业务逻辑，生成它的相应）。传统的生成系统存储他们的状态在关系型数据库中。然而， 对于许多常见的状态持久化的使用模式，关系系数据库是非理想的解决方案。他么中的大部分服务只存储并检索数据，不需要关系型数据库管理系统提供的功能复杂的查询和管理。这种多余的功能需要昂贵的硬件和高技能的操作人员，这是一个非常低效的方案。此外，可用的复制技术是有限的，通常选择一致性而不是可用性。虽然尽管近年来取得了许多进展，横向扩展数据库依然不简单，或者使用智能的分区模…

Cassandra 一个去中心化的结构化存储
type: item
date: 2024-11-13T14:45:00+08:00
description: Cassandra 一个去中心化的结构化存储概要cassandra是一个分布式存储系统已管理大量的结构化数据分布在许多商用服务器上，同时允许在单点故障的情况下提供高可用。Cassandra的目标是运行在上百台节点的基础设施之上（可能分割到不同的数据中心）。在这个尺度下，大的和小的组件故障连续不断。Cassandra在面对这些故障管理持久状态的方式驱动了一来该软件服务的软件系统的可靠性和伸缩性。在很多封面Cassandra类似一个数据库，并与之贡献很多实现策略Cassandra不知此完全的关系模型；作为替代他提供给客户端一个简单的数据模型以支持对数据布局和格式的动态控制。Cassandra的系统被设计为运行在廉价的通用硬件。在处理高吞吐量的同时不影响读取的效率。1 介绍Facebook运行最大的社交网络平台，服务于上亿的用户在峰值时段使用上万台服务器其遍布整个世界。这是一个严格的操作要求facebook的平台的性能，可靠性，有效性有严格的要求，并且支持持续的增长，平台需要高可缩放性。处理包括上千个组件的故障是我们标准运作模式。总会有小的但是明显的服务和网络组件在给定的事件故障。因此，软件系统需要结构化的管理者将失败视为日常而不是意外。为了应对上述的可用性和可缩放需求facebook开发了Cassandra。Cassandra总和使用了知名的技术一达到可缩放和可用性。Cassandra被设计为实现Inbox serch 问题。Inbox是一项功能允许用户搜索他们的facebook收件箱。在facebook中这意味着系统需要处理非常高的写入量，每天上百万的写入，并且随着用户数量的扩大。由于用户从地理分布的数据中心获得服务，允许副本数据穿过数据中心是保证低延迟的关键。Inbox 查询在2008年6月启动服务于大约1亿用户如今我们有超过2.5亿的用户，并且Cassandra还在保持增长。Cassandra现在被部署在后端存储系统为facebook的多个服务服务。2 相关工作分布式数据的可靠性可用性和持久性在文件系统和数据库已经有了广泛的研究。对于只支持平面空间的p2p存储，分布式文件系统特别支持了分级的命名空间。文件系统类似Ficus和Coda 以牺牲一致性为代价来获得高可用性。更新冲突通常使用专门 打冲突解决程序进行管理。Farsite是一个分布式文件系统他不使用任何中心化服务。Farsite使用复制达到了高可用和可缩放。GFS是另一个文件系统以托管谷歌内部的应用状态。GFS使用了简单的单个主设计以托管整个元数据，其数据被切分为chunk并且存储在chunk服务上。然而，GFSmaster使用Chubby的抽象处理容错。Bayou是一个分布式关系型数据库允许不连贯的操作并且提供数据的最终一致性。在这些系统中，Coda和Ficus 允许断开操作并对网络分区和中断问题具有弹性。这些系统在解决冲突上的过程有所不同。例如coda和Ficus执行文件级别的冲突决议，Bayou允许应用级别的解决。然而，他们都保证最终一致性，Dynamo允许读取和写入操作连续，即便是在网络分区的情况下别去使用不同的由客户端驱动的冲突解决机制来解决冲突。传统的复制的关系数据聚焦于保证副本数据的强一致性。虽然强一致性提供了应用写入方便的模型，这写系统限制了可缩放性和可用性。这些系统没有处理网络分区的能力，因为他通常提供强一致性保证。向量时钟（Vector Clock）是一种用于解决分布式系统中并发更新冲突的问题的机制。它通过记录每个节点（或副本）在某个数据项上的修改历史，来追踪这些数据项的状态变化，以便在多个副本并行修改时能够检测到哪些修改是冲突的。在分布式系统中，通常会有多个节点（或副本）处理同一数据项的不同副本。为了确保数据一致性，需要一种机制来判断这些副本是否有冲突，尤其是在它们的更新是并行进行的情况下。向量时钟就提供了一种解决方法。每个节点有一个时钟：系统中的每个节点维护一个向量，记录该节点对数据项的修改历史。向量中的每个元素对应一个节点的时钟，通常是一个整数，表示该节点的修改次数。例如，系统中有三个节点 A、B 和 C，那么每个节点会维护一个三维向量 [A, B, C]，每个维度的值代表该节点对数据项的修改次数。每次修改都会更新时钟：当某个节点修改数据时，它会增加自己的时钟值，同时将这个更新传播到其他节点。例如，假设节点 A 修改了数据，它的向量时钟会变成 [1, 0, 0]（假设初始时钟为 [0, 0, 0]），表示节点 A 对数据进行了第一次修改。向量时钟的传播：当节点 A 将数据更新发送给节点 B 和节点 C 时，它会把自己的向量时钟一并发送过去。接收到更新的节点会更新自己的时钟，确保自己的向量时钟包含其他节点的历史修改。检测冲突：向量时钟的核心在于它…

Percolator
type: item
date: 2024-10-31T19:30:00+08:00
description: Percolator思考Google的三驾马车提供了Google的搜索引擎功能。建立网页我过程如下爬取互联网的内容进行解析提取出关键字确认反向索引对反向索引的URL进行整理形成了搜索引擎所需的网页引擎在构建网页索引的过程中，我们初始状态是由大量URL到页面内容这个键值对。我们把它处理成从关键字到URL这样一个反向的键值对（倒排索引）。reduce函数合并共同的反向索引。如果多个URL的内容一样，那么只有pageRank高的网页才会进行展示。但是一旦有网页更新，新的网页产生。我们需要更新到索引库中。网页之间的关系非常复杂。加入在新URL产生后需要内容去重然后重新pagerank。但是MapReduce这套生成网页索引的机制是全量的。没办法单独为新增的网页跑一套这个流程。MapReduce只能权利生成不能增量更新。Google长期采用的方法是通过MapReduce批处理过程，定期重新生成一个新的索引库。假设原来索引库索引了1000个页面，这时候五个页面新加入。MapReduce需要重新处理10005个页面才能得到新索引库。那么能不能只处理5个新增页面通过一个增量的更新呢？其实增量这个操作就是select+insert/update的过程。还需要保证整个过程的一致性和隔离性。如果这个索引库支持事务就能解决我们的问题了。那么如何让Bigtable支持事务呢？我们需要一个支持事务的DBMS来索引存储库。因此出现了percolator，在Bigtable上面做了一层封装。支持事务解决了问题并成为了分布式数据库。也就是newSQL的雏形。原论文中说：percolator是专门为了增量处理而构建的，并不是为了取代大多数数据任务处理的解决方案，MapReduce可以更好地处理无法将结果分解为小更新。此外计算应该有强烈的一致性要求不然Bigtable就足够了。计算在某些维度上应该非常大。传统的DBMS可以处理不适合Mapreduce或Bigtable的较小计算。但后续的Spanner到现在的各种newsql数据库已经在现有的解决方案商越走越远了。在性能差异不大的情况下，NewSQL能支持近乎无限容量的数据。提供强大的扩展性，又能弥补原有分布式的种种限制。（变得all in one）基本原理percolator是基于俩阶段提交的改进版本。prepare阶段：协调器向各个节点发送paepare消息，各节点决定该节点事务部分是提交还是中止。commit阶段：协调者收到各节点的ready或不能提交响应。所有节点都ready则提交成功，任一阶段无法提交就回滚。俩阶段提交的特点是强一致性失去了并发能力：不能使用MVCC需要一个特殊实现的协调者，这个协调者需要单独实现并存储一些日志和锁内容。（这个协调者是脱离bigtable的，所以更难控制）需要付出更大的性能。percolator基于此做了最核心的俩个改造提交过程中的第一个参与者设计为一个类似俩阶段提交协调者的角色，整个事务的原子性状态也以它为准。由此，借用Bigtable的高可用存储能力，免去了特殊设计协调者的麻烦和风险。percolator采用全局授时机制，通过全局时间戳实现多版本的管理，从而实现了snapshot isolation（快照隔离），具有一定的并发能力和first-commiter-win的特性。percolator存储了四个列：key，data，lock（锁状态），write（提交状态）字段前5或6是时间戳（我们用一个简单的自增整数来代替，时间戳由Bigtable负责存储）write下时间戳为data@5表示时间戳为5已经提交data字段的写入不表示这个事务已经提交了，没有提交的数据是不可以读的。读的流程为先查询write字段，找到最近的一个提交记录。再按照这个时间戳找到已提交的数据进行读取。接下里Bob给Joe转账7元。我们首先扣除Bob账户的7元。并在Bob账户上加锁。因为这是分布式事务的第一把锁，所以我们设定它为primary锁。这里最新的write字段还是时间戳6，只能查询到时间戳5的数据。所以现在Bob的余额还是10（MVCC）然后给Joe账户增加7元，余额变为9，并在Joe的账户上加锁。因为这是分布式事务的第二把锁，它指向primary锁的位置。这是为了让分布式事务的提交与成功有一个原子性的标志。一个事务中除了第一个锁是Primary锁其他的锁都是secondary锁。这样我们的prepare阶段就完成。事务进入commit阶段，事务释放掉primary锁，并申请时间戳8，在时间戳8写入write列。时间戳8就是这个事务的提交时间戳。底层实现我们可以简单把Bigtable当做一个整体来看待，Bigtable上面就是运行percolator程序的服务器了。percolator其实…

Bigtable解读
type: item
date: 2024-10-31T16:07:00+08:00
description: Bigtable解读基本Bigtable 是在GFS上的结构化的系统。很多人也把它称之为分布式表格系统。Bigtable在GFS和Chubby的基础上首次实现了可用的LSM树。bigtable的key由三部分组成，关键字，列关键字+时间戳(row:string,column:string,time:int64)->string它的key由三部分组成，行关键字+列关键字+时间戳。它的value是一个bute数组。分别对应行主键，列名。value从业务角度理解可以是一个未解析的byte数组。在谷歌给出的例子中url就是行关键字，anchor和内容就是列关键字。url 列名时间戳形成了多个键值对，比如途中就有6个k-v对其中t是数据版本。为什么要把各列的值拆成多个k-v对呢？而不是一整行数据放在一起呢。因为对于网页索引来说网页内容非常大，读取也比较慢。而对于anchor这样的小字段读取就非常的快。并且俩者的查询往往不是一个业务场景。常见的是先用anchor索引确定网页后在读取完整的页面内容。这样吧他们放在一起对于读取anchor的场景就非常不利了。所以虽然他们有相同的url但还是分开存储好。然后谷歌还提出了列族的概念，就是吧一些有共性的字段整合到一起，在存储访问等方面统一管理。API：bigtable提供的功能包括建表、删表DDL对单行数据增删查功能，不支持修改范围扫描功能（弱化的where）。bigtable只支持单行的事务。因此bigtable只能用在宽松的场景。结构在最底层bigtable把数据按照字典序排列之后以range划分。bigtable把这样一个range的数据称为一个tablet一个tablet对应一个GFS中的文件。有一个全局唯一的文件名。并且一个tablet相当于一个LSM树。要注意GFS支持append不支持update。而LSM树的所有操作都是append操作。对于Bigtable来说只需要一个tablet的文件名就可以直接从GFS中进行读写了。但是这里我们需要一个手段把我们要查询的key值和tablet文件名联系起来。为了解决这个问题Bigtable设计了三层的类似B+树结构的结构来存储tablet的位置信息。这里的三层结构是存储位置信息不要和存储具体kv的lsm树搞混。LSM树是一个tablet内部的概念。Chubby file，负责选择出Root tabletroot tablet 包含一个特殊的METADATA表；记录METADATA例所有的TABLET位置信息METADATA，其中的每个tablet包含了一个usertablet的集合多个usertablet存储数据的最终项。经过计算能存储2048PB的数据整个bigtable还需要client来提供服务。为了避免tablet服务器出现宕机的情况需要master服务器来检测各tablet服务器的状态。查找流程为通过client项chubby查找key访问到chubby指向的tablet开始。逐层向下找到自自己要找到tablet在找到tablet的lsm树中进行查找每次都进行这样的流程会有些慢，可以加上路径缓存。把路径上第一层的RootTablet，第二层的MetaDATA和第三层的Tablet位置都加入缓存。Bigtable把这个缓存存储在客户端称为客户端缓存。

Bigtable：面向结构化数据的分布式存储系统
type: item
date: 2024-08-27T14:49:00+08:00
description: Bigtable：面向结构化数据的分布式存储系统概要Bigtable是一个面向管理结构化数据的分布式存储系统，它是被设计为非常大的尺寸：TB的数据在上千个通用服务器。许多项目在Google上将数据存到Bigtable中包括了网站索引，谷歌地图和谷歌财经。这些应用对Bigtable提出了许多不同的要求，包括在数据大小（从URL到网站页面到卫星图像）与延迟要求（从后端批量处理到实时数据服务）。尽管他们有不同的需求，Bigtable很成功的提供了弹性， 高性能解决方案给所有的这些谷歌项目。在这个论文中我们描述Bigtable提供的简单数据模型，它使客户端能够动态控制数据布局和格式，并且我们描述Bigtable的设计和实现。1介绍在过去的俩年半里我们设计实现和开发了分布式存储系统以管理结构化的数据，在谷歌我们叫做Bigtable。Bigtable在谷歌被设计为可靠的的扩展到PB级别的数据和上千台的机器。Bigtable已经达到了几个目标：广泛的应用范围，可扩展性，高性能和高可用性。Bigtable被用在超过60个谷歌的产品和项目上，包括了规格分析，谷歌财经，Orkut，个性化搜索，Writely和规格地球。这些项目使用Bigtable以应对需求多变的工作负载。其范围从吞吐量为导向的批处理工作，到最终用户提供提供延迟敏感的数据服务。在许多方面，Bigtable类似于数据库：他们共享许多数据库的存储策略。并行的数据库和内存数据库已经达到了高可用，但是Bigtable提供了与这些系统不同的接口。Bigtable不支持完整的关系模型；相反，它给客户端提供了简单的数据模型，它支持动态控制数据布局和格式，允许客户端推断底层存储中表示的数据的局部属性。数据索引使用可以为仍以字符串的行名和列名。Bigtable还将数据视作未解释的字符串，尽管客户端经常将各种结构化和半结构化的数据序列化到这些字符串中。通过仔细的选择模式，客户端可以控制数据的位置。最后Bigtable的模式参数让客户端动态控制无论是在磁盘还是内存提供数据。章节2更详细的描述了数据模型，章节3提供了客户端API的总览。章节4描述了谷歌文件系统底层的结构。章节5描述了Bigtable实现的基本原理，章节6描述了一些让我们Bigtable性能提升的改进。章7提供了Bigtable的性能指标。在章节8中我们描述了几个不同的Bigtable在Google中使用的例子。在章节9讨论我们设计和支持Bigtable时学习到的一些经验。最后，章节10描述了相关工作，章节11提出了我们的结论。Bigtable是一个稀疏的，分布式的、持久的多维排序图。这个图通过行和列的key，时间戳进行索引；图中的每个值都是一个为解释的字节数组（行：string，列：string，time：int64）-->string2数据模型我们在检验了多重潜在的使用类似Bigtable的系统，选择了这个数据模型。作为一个确实的例子，它驱动了我们的一些设计决策，假设我们需要保证网页上大量数据和相关数据集的拷贝，这可能被用于许多不同的项目；让我们把这些的表叫做Webtable。在Webtable中，我们可能使用url作为行的键，网页的不同方面作为列名，在内容中存储web页面的内容：在获取的时间戳下面有一列，如图1所示。图1：一个示例表的切片，它存储了web页面。它的行名是倒过来的url。content列族包含了页面内容，锚列族包含了引用该列的任何锚文本。《体育画报》和MY-look主页都引用了CNN的主页，因此，该行包含名为anchor:cnnsi.com和anchor:my.look.ca的列。每个锚单元格都有一个版本；内容列有3个版本，时间戳为t3、t5和t6。在bigtable中表的组成分为行行列key在表中是一个随机字符串（目前最大可达64KB，尽管10-100字节是我们大部分用户的典型大小），每一个对于单行的读和写操作都是原子的（无论在行中读取或写入的不同列的数量如何），在对同一个记录进行更新时，使客户端更容易推断系统行为的设计决策。Bigtable按字典顺序维护数据。表的行范围是动态分区的。每个行的范围被叫做tablet，它是一个分布和负载均衡的单元格。因此，读取短行的范围通常是高效的，通常只修要与几个小数量的机器进行交流。客户端可以通过查询这些行的key来利用这个特性，这样他们就能得更号的数据访问的局部性。例如在Webtable中，通过翻转url的主机名组件将同一域中的页面分组到连续的行中。举个例子，我们将maps.google.com/index.html数据存储到键com.google.maps/index.html下面。将来自同一域的页面存储在彼此相邻的位置，让一些主机和域分析更加有效。列族列键被分组为集合，称为列族…

Mysql成本计算规则Optimizer trace
type: item
date: 2024-04-23T16:57:58+08:00
description: Mysql成本计算规则Optimizer tracemysql原理--optimizer trace表的神器功效-CSDN博客MySql5.6之前只能通过Explain语句查看到最后优化器决定使用的执行计划，却无法知道它们为什么做这个决策，在MySql5.6以及之后的版本mysql提出了Optimizer trace（优化跟踪）的功能，它可以让我们看到优化器生成执行计划的整个过程。如果想打开这个功能，必须首先把 enabled 的值改为 on ，就像这样： `SET optimizer_trace="enabled=on"然后我们就可以输入我们想要看优化查询过程的语句，当该语句执行完成后，就可以看到information_schema数据库下的optimizer_trace表中查看完整的优化过程。这个optimizer_trace表有4列，分别是。query：表示我们的查询语句tace表示优化过程的json文本missing_bytes_beyond_max_size：由于优化过程可能会输出很多，如果超过某个限时，多余的文本将会不显示，这个字段展示了被忽略的文本字节数insufficient_privileges：表示是否没有权限查看优化过程，默认值是0，止呕某些特殊情况下才会是1。在我们有一个搜索条件比较多的查询语句，它的执行计划如下：EXPLAIN SELECT * FROM t1 WHERE key1 > 'z' AND key2 < 1000000 AND key3 IN ('a', 'b', 'c') AND common_field = 'abc';可以看到该查询可能使用到的索引有3个，那么为什么优化器最终选择了 idx_key1 而不选择其他的索引或者直接全表扫描呢？这时候就可以通过 otpimzer trace 功能来查看优化器的具体工作过程：SET optimizer_trace="enabled=on";SELECT * FROM t1 WHERE key1 > 'z' AND key2 < 1000000 AND key3 IN ('a', 'b', 'c') AND common_field = 'abc';SELECT * FROM information_schema.OPTIMIZER_TRACEGQUERY: SELECT * FROM t1 WHERE key1 > 'z' AND key2 < 1000000 AND key3 IN ('a', 'b', 'c') AND common_field = 'abc' TRACE: { "steps": [ { "join_preparation": { "select#": 1, "steps": [ { "IN_uses_bisection": true }, { "expanded_query": "/* select#1 */ select `t1`.`id` AS `id`,`t1`.`key1` AS `key1`,`t1`.`key2` AS `key2`,`t1`.`key3` AS `key3`,`t1`.`key_part1` AS `key_part1`,`t1`.`key_part2` AS `key_part2`,`t1`.`key_part3` AS `key_part3`,`t1`.`common_field` AS `common_field` from `t1` where ((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))" } ] } }, { "join_optimization": { "select#": 1, "steps": [ { "condition_processing": { "condition": "WHERE", "original_condition": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b','c')) and (`t1`.`common_field` = 'abc'))", "steps": [ { "transformation": "equality_propagation", "resulting_condition": "((`t1`.`key1` > 'z') and (`t1`.`key2` < 1000000) and (`t1`.`key3` in ('a','b'…

Redis特性
type: item
date: 2024-02-26T13:44:40+08:00
description: Redis特性Stream介绍Redis Stream 是 Redis 5.0 版本新增加的数据类型，Redis 专门为消息队列设计的数据类型。在 Redis 5.0 Stream 没出来之前，消息队列的实现方式都有着各自的缺陷，例如：发布订阅模式，不能持久化也无法可靠的保存消息，并且对于离线重连的客户端不能读取历史的消息的缺陷。List实现消息队列的方式不能重复消费，一个消息消费完就会被删除，而且生产者需要自行实现全局唯一ID基于以上问题，Redis 5.0 便推出了 Stream 类型也是此版本最重要的功能，用于完美地实现消息队列，它支持消息的持久化、支持自动生成全局唯一 ID、支持 ack 确认消息的模式、支持消费组模式等，让消息队列更加的稳定和可靠。常见命令Stream 消息队列操作命令：XADD：插入消息，保证有序，可以自动生成全局唯一 ID；XLEN ：查询消息长度；XREAD：用于读取消息，可以按 ID 读取数据；XDEL ： 根据消息 ID 删除消息；DEL ：删除整个 Stream；XRANGE ：读取区间消息XREADGROUP：按消费组形式读取消息；XPENDING 和 XACK：XPENDING 命令可以用来查询每个消费组内所有消费者「已读取、但尚未确认」的消息；XACK 命令用于向消息队列确认消息处理已完成；应用场景消息队列生产者通过 XADD 命令插入一条消息：# * 表示让 Redis 为插入的数据自动生成一个全局唯一的 ID # 往名称为 mymq 的消息队列中插入一条消息，消息的键是 name，值是 xiaolin > XADD mymq * name xiaolin "1654254953808-0"插入成功后会返回全局唯一的 ID："1654254953808-0"。消息的全局唯一 ID 由两部分组成：第一部分“1654254953808”是数据插入时，以毫秒为单位计算的当前服务器时间；第二部分表示插入消息在当前毫秒内的消息序号，这是从 0 开始编号的。例如，“1654254953808-0”就表示在“1654254953808”毫秒内的第 1 条消息。消费者通过 XREAD 命令从消息队列中读取消息时，可以指定一个消息 ID，并从这个消息 ID 的下一条消息开始进行读取（注意是输入消息 ID 的下一条信息开始读取，不是查询输入ID的消息）。# 从 ID 号为 1654254953807-0 的消息开始，读取后续的所有消息（示例中一共 1 条）。 > XREAD STREAMS mymq 1654254953807-0 1) 1) "mymq" 2) 1) 1) "1654254953808-0" 2) 1) "name" 2) "xiaolin"如果想要实现阻塞读（当没有数据时，阻塞住），可以调用 XRAED 时设定 BLOCK 配置项，实现类似于 BRPOP 的阻塞读取操作。比如，下面这命令，设置了 BLOCK 10000 的配置项，10000 的单位是毫秒，表明 XREAD 在读取最新消息时，如果没有消息到来，XREAD 将阻塞 10000 毫秒（即 10 秒），然后再返回。# 命令最后的“$”符号表示读取最新的消息 > XREAD BLOCK 10000 STREAMS mymq $ (nil) (10.00s)Stream 的基础方法，使用 xadd 存入消息和 xread 循环阻塞读取消息的方式可以实现简易版的消息队列，交互流程如下图所示：前面介绍的这些操作 List 也支持的，接下来看看 Stream 特有的功能。Stream 可以以使用 XGROUP 创建消费组，创建消费组之后，Stream 可以使用 XREADGROUP 命令让消费组内的消费者读取消息。创建两个消费组，这两个消费组消费的消息队列是 mymq，都指定从第一条消息开始读取：# 创建一个名为 group1 的消费组，0-0 表示从第一条消息开始读取。 > XGROUP CREATE mymq group1 0-0 OK # 创建一个名为 group2 的消费组，0-0 表示从第一条消息开始读取。 > XGROUP CREATE mymq group2 0-0 OK消费组 group1 内的消费者 consumer1 从 mymq 消息队列中读取所有消息的命令如下：# 命令最后的参数“>”，表示从第一条尚未被消费的消息开始读取。 > XREADGROUP GROUP group1 consumer1 STREAMS mymq > 1) 1) "mymq" 2) 1) 1) "1654254953808-0" 2) 1) "name" 2) "xiaolin"消息队列中的消息一旦被消费组里的一个消费者读取了，就不能…