Garin
Garin
Operational Transformation(OT)是一个应用于协同编辑领域的并发控制和冲突解决系统,要解决的是“多个用户对同一个文本域的同一个版本进行编辑时如何处理”的问题。下文中简称**冲突问题**。 整体来看,OT解决并发编辑冲突问题的思路有以下几步: 1. 定义原子操作类型:将用户在UI上触发的基于Event的操作抽象成由可枚举的N个原子操作类型组成的操作序列,这样一来复杂的UI界面操作的冲突就转换成了原子操作之间的冲突,同时也为多端数据同步定义了基本数据结构。 2. 设计冲突解决算法:在**冲突问题**发生时,通过冲突解决算法解决冲突。冲突解决算法要完成以下任务: - 通过算法能将冲突的2个操作序列**转换**成2个可以和原来冲突的操作序列**串行**执行的**新操作序列**。 - 可串行的两组操作序列作用在文本后,产生的影响相同。 - 串行后的操作需要保持原有语义 3. 多端冲突解决:通过向各端同步新的**可串行操作序列**完成冲突解决 接下来我使用ot.js的实现来详细解释一下冲突解决的思路 ## 定义原子操作类型 我们先来看看没有原子操作的世界。对有状态的UI Component来说其实并没有操作类型的概念,每次UI操作只会生成newValue在浏览器端通过`e.target.value`获取。如果进行粗略的oldValue和newValue的diff,在浏览器文本框中,用户可以进行以下UI操作: - 头部插入:`"a" => "ba"` - 尾部插入:`"a" => "ab"` - 中间插入:`"ab"...
点开文章的朋友们可以先看看讲的是不是你要的效果 初始数据:假设我们的表如下所示,时间戳(ts)我简化成了1到5的数字。 | ts | amount | | --- | ------ | | 1 | 10 | | 2 | 5 | | 3 | 3 | | 4 |...
在日常工作中,可能经常会遇到切“数据快照”的需求。所谓“数据快照”是在某一个时间点将数据库中的某些表转储到另一个地方,就像对当时的数据拍了照片存起来。对于数据一致性要求不高的场景可以直接在凌晨的某个时间点执行一次类似`select * from xx`的转储任务就可以满足需求。但是如果遇到对数据一致性有严格要求场景应该怎么做呢?本文就“日结余额快照”这个具体问题介绍一下**强一致性场景下**数据快照任务的实现思路。 ### 背景介绍 在每个广告投放系统中,都需要一个报表来为广告主按天级别展示花费、转入、转出和余额数据。其中余额这一项就依赖一个“数据快照“任务在每一天结束前对广告主余额做一个快照存储起来,作为当天的结束时候的余额,我们称它为“日结余额快照”。 我们开头提到日结余额快照有强一致性要求,那么什么是**强一致性**要求?那么就是在问“强在哪”和“跟谁一致”? **跟谁一致**:我们既然说一致性,那就必须有另外一些数据需要和目标数据保持一致。在日结余额的计算中,需要和日结余额保持一致性的关联数据包括:花费、转入、转出。 **强在哪**:这几项数据需要在产出的数据快照中要满足以下一致性公式: ![](https://garinzhang-blog.oss-cn-beijing.aliyuncs.com/2022-02-18-075910.png) 简单来说就是“前一天的日结余额 - 当天花的钱 + 当天转入的钱 - 当天转出的钱 = 当天日结余额”。只有满足了这个公式才能达到财务层面和平台报表的要求。 理解了强一致性“强在哪”和“跟谁一致”之后。我们需要从工程角度出发,考虑实现方式。 为了简化理解假设我们现在有三张表,均为MySQL存储,分别是:广告主余额表、广告主天级花费表、广告主转入/转出记录表。其中广告主天级花费表、广告主转入/转出记录表中均包含准确字段标识数据发生的日期因此不需要额外的数据快照,而广告主余额表存储的是广告主余额的实时状态。 ### 如何计算日结余额 #### 方案一: select * 我们先考虑最简单的方案,直接通过一个0点的定时任务执行类似`select *...
## Operational Transformation ### 开源实现 - [quilljs/quill: Quill is a modern WYSIWYG editor built for compatibility and extensibility.](https://github.com/quilljs/quill) - [Operational-Transformation](https://github.com/Operational-Transformation) - [SharedPen 之 Operational Transformation | Deng's Blog](http://objcer.com/2018/03/05/SharePen-Operational-Transformation/) - [OT...
> 原文:[How we fortified Twitter's real time ad spend architecture](https://blog.twitter.com/engineering/en_us/topics/infrastructure/2020/how_we_fortified_twitters_real_time_ad_spend_architecture.html) 推特是广告商与受众接触的一个热门平台。当广告商发起一个新的计划(campaign)时,他们会指定一个广告预算(budget),限制他们将花费多少钱。Twitter的Ad Server校验计划的预算,以确定是否继续出广告。如果没有这种校验,我们可能会在计划达到其预算限制后继续出广告,但却无法对账户扣费(charged)。这种情况我们称为超支或超投(overspend)。 超支可能导致Twitter的收入损失(因为机会成本,比如:本来我们可以在这个广告位(slot)显示其他广告),所以建立可靠的系统来防止超支是非常重要的 ## 名词解释 - campaing - 计划层级 - budget - 预算,指的是广告主在campaign(计划)中设置的预算 - spend - 消耗,指的是一个广告事件触发后广告平台应该收取广告主的费用,消耗并不完全等于实际消费 - engagement -...
想要系统了解文件系统,还是得先从硬盘这个硬件说起 ## 硬盘 ### 机械硬盘 机械硬盘由盘片、主轴、磁头臂组成。无论是否有IO操作,盘片都需要由主轴带动盘片高速旋转,目的是靠磁盘旋转时带动的气流,让磁头在进行IO时能够**悬浮**在盘片上方。悬浮的目的是为了避免磁头和盘片接触导致磁头与磁盘损坏。它的存储原理就是,数据存储在具有磁性特质的盘片上。 那为什么都说机械硬盘慢,因为机械硬盘在做IO操作时,磁头臂移动到盘片的磁道上,通过磁头读取磁道上的数据。而移动磁头是一个机械动作,需要花费数毫秒时间,因此机械硬盘慢一些。 其实在说机械磁盘慢的时候,必须要考虑IO是顺序还是随机读写,随机读写也就是硬盘数据在硬盘上不连续,那么磁头就需要来回移动,就会花费更长的时间。而顺序读写,说明文件数据连续,比如日志文件,那么磁头就可以减少移动,读写时间就会很短 ### 固态硬盘 固态硬盘由主控芯片、闪存、外置缓存颗粒、PCB板、外壳组成 - 主控芯片:相当于固态硬盘的CPU,控制内部运算 - 闪存:存储内容 - 外置缓存:有些有、有些没有。有的集成在主控中 - SLC缓存:提供固态硬盘爆发速度的技术 - PCB板:类似于主板,用于集成主控、闪存、外置缓存。 - 外壳:铁壳或塑料壳 #### 固态硬盘的物理原理 SLC 闪存有 0 和 1...
## 核心概念 同步/异步、阻塞/非阻塞 ## 如何理解 `同步/异步,阻塞/非阻塞`这两组概念是在应用(用户进程)角度考虑的,考虑通信的双方是用户进程和内核进程。 同步/异步描述的是**进程间**的协作方式,强调内核提供了什么方式和用户线程通信,或者说用户进程选择使用什么内核提供的IO API进行系统调用 阻塞/非阻塞描述的是**用户进程内部**的处理方式,只涉及用户进程自己怎么做。 ## 通过类比理解 去书店买书,涉及两方我和书店老板,还有一份数据就是书。 #### 同步和异步 同步:我要买一本书,老板**要求我**在这等着,直到书拿过来。 异步:我要买一本书,老板说你可以先干别的。但是书准备好以后有两种方式你可以选: 方式1:好了我不告诉你,你过段时间来店里问问 方式2:好了我给你打电话 总之,这里强调的都是老板提供的方式 #### 阻塞和非阻塞 阻塞:我下定决心,无论老板是要求我在这等着(同步)还是告诉我可以回去(异步),我就是在这死等,一直等到老板告诉我书准备好了。 非阻塞:我下定决心,无论老板是要求我在这等着(同步)还是告诉我可以回去(异步),我就是要想办法不等着。 将以上两种概念组合: 同步阻塞:我要买一本书,老板要求我在这等着,直到书拿过来。我也准备就在这等着,然后再干别的。 同步非阻塞:我要买一本书,老板要求我在这等着,直到书拿过来。我就知道会有这种情况,所以我让我小弟来,让他等着。 异步阻塞:我我要买一本书,老板说你可以回去了。我也准备就在这等着。 异步非阻塞:我我要买一本书,老板说你可以先干别的,但这时候我有两种选择: 选择方式一:我当人肉复读机,过段时间就来问老板“书准备好了没有” 选择方式二:我先做别的了,等着老板告诉我结果...
## 数据类型 在概念上Neo4j有两个实体概念:Node和Relationship ### Node - 节点 类似于Entity,包含: - **Property**:KV对,用于存储数据 - **Label**:用于标记类型 ### Relationship - 关系 - First Node:起始节点 - Second Node:终止节点 - **Label**:标签 - **Property**:属性 ## 逻辑存储结构 免索引邻接(Index Free...
## Overview ``` - 性能 - 吞吐量 - TPS - QPS - BPS - 响应时间 - 完成时间 - 资源占用 - 空资源占用 - 满资源占用 - 可用性 - 系统可用概率 - 功能可用概率 -...
## 开始之前 在开始介绍分布式系统之前,我们需要对软件所做的事情进行一个抽象,将其处理的请求、执行的命令称为**任务**,而完成一个任务需要读取数据 - 处理数据 - 写入数据。这个过程我们在抽象出两个概念:**计算**和**数据**。所以我们可以这样理解: > 任务 = 计算 + 数据 单机应用程序角度来看: - 计算,是使用CPU和内存进行运行时数据处理的过程 - 数据,是使用磁盘、网络进行数据读写的操作 分布式应用程序角度来看: - 计算,是应用程序整体的处理过程,比如一个用户管理模块的应用代码处理部分就是计算 - 数据,是应用程序依赖的各种数据库处理的部分 如果仅从应用程序的视角来看,对数据的读取就是对不同数据源的IO,这个概念模型也可以转换为: > 任务 = 计算 + IO...