分布式数据库事务故障恢复的原理与实践
关系数据库中的事务故障恢复并不是一个新问题，自70年代关系数据库诞生之后就一直伴随着数据库技术的发展，并且在分布式数据库的场景下又遇到了一些新的问题。本文将会就事务故障恢复这个问题，分别讲述单机数据库、分布式数据库中遇到的问题和几种典型的解决方案，以及 OceanBase 在事务故障恢复方面的相关实践。
归档
2020
2019
超越不可能
相信所有研究过分布式系统的同学都对大名鼎鼎的FLP不可能性有所耳闻，简单来说，FLP不可能性证明了“在可能有哪怕一个进程故障的异步系统模型中，共识问题无法被解决”。但矛盾的是，现在正当红的很多分布式系统，都依赖于底层的共识算法，比如Multi-Paxos、Raft等，难道是FLP错了么？共识问题已经被解决了？还是...
可串行化（Serializable）：理想和现实
但凡是接触过数据库的同学一定不会对事务（transaction）的概念感到陌生，我第一次接触事务的概念还是在本科的数据库课本上，了解了事务并发控制概念，但在之后多年不严肃的前后台开发经历中，我几乎从来没有考虑过数据库的“隔离级别”，这让我产生了一种”数据库如此好用，世界如此美好“的幻觉…直到现在从事了数据库内核的...
2018
Paxos与“幽灵复现”
Paxos被公认是难度很高的分布式共识算法，一方面是体现在理解其算法正确性的难度上，而另一方，体现在工程实现的复杂度上。在将Paxos算法运用在工程实践的过程会遇到各种各样的问题，本文要探讨的“幽灵复现”问题，就是其中一例。 什么是“幽灵复现” 据我所知，所谓的“幽灵复现”问题是Oceanbase团队在实现M...
[paper note]Megastore & PaxosStore
之前对分布式KV存储关注不多，最近抽时间看了一下Google的Megastore和Wechat的PaxosStore的论文，发现其中很多设计考量的角度都很有趣，值得仔细思考。 Megastore Megastore相对来说是一个比较老的系统了，是在Spanner大规模运用之前构建在Bigtable之上，支持跨...
Paxos revisit
前一段时间借着组里的实习生学习交流的机会，又重新讨论了一次Paxos算法，颇有收获。本文整理记录几个我个人觉得比较有意义的问题，希望通过思考这几个问题，能够加深你对Paxos算法的理解。 本文假定读者已经对Paxos算法有一定了解（包括原理、正确性证明、执行流程），如果你还不了解Paxos，请移步这里。 Pa...
[paper note]Consensus on Transaction Commit
这篇论文的作者实在太吓人了，Jim Gray和Leslie Lamport，两个领域的扛把子。论文介绍的内容叫Paxos Commit，是用分布式共识算法解决分布式事务的原子提交问题，不愧是这两位大佬写出来的文章哈哈。 PS：这篇文章是我的paper note，主要是帮助自己理解和记忆，与其说是文章，其实更像是...
2017
C++实现成员函数检查
最近看到一段代码，感觉非常trick，但也非常有意思，写出来记录一下。 背景是这样的，有一个模板函数 copy_assign ，其作用非常简单，就是将第二参数“拷贝”给第一个参数，但是为了对能够进行深拷贝的类型进行深拷贝，希望的行为是这样的： 如果T有成员函数int assign(const T &am...
并发编程牛刀小试：SeqLock
Sequential lock，简称seq lock，是一种有点特殊的“读写锁”，Linux内核从2.6版本开始引入，是一种非常简单轻量保护共享数据读写的方法。 基本原理 Sequential lock的原理非常简单，其核心就是通过维护一个序号(sequence)来避免读者(Reader)读到错误的数据，而写...
Hazard Pointer
上一篇文章中实现了一个lock-free的队列，但是有一个问题：内存无法被安全的回收。那么，这次就来把这缺失的一环补上：hazard pointer，一种lock-free对象的内存回收机制。 hazard pointer PS：因为hazard pointer完整代码略有些长，不适合贴在文章内...
无锁队列的一种实现
队列作为最常用的基础数据结构之一，相信大家都已经非常非常熟悉了，这里省略关于队列的介绍。在平时开发中队列的出现频率非常非常高，因此我们也会很关心队列的性能问题。当并发访问队列时，队列的性能往往受到同步手段的制约，最简单的方式是使用互斥锁对整个队列加锁，但其并发性能却惨不忍睹。 因此，有了各式各样的无锁队列实现，...
用户态同步之自旋锁
最近花了一些时间研究如何在用户态实现自旋锁，这里简单的总结一下。本文的所有代码以及配套的测试用代码都可以在我的github上找到。 问题在哪 首先明确问题，我们需要一种用户态实现的线程同步机制，正确性当然是最重要的。本文的目的是实现正确的自旋锁（自旋锁比较简单轻量，但了解了原理后实现互斥锁并不困难，自行维护等...
多核并发编程中的cache line对齐问题
先看一段代码： #include <pthread.h> #include <stdlib.h> #include <stdio.h> #include <algorithm> using namespace std; static const int64_t...
2016
推荐几个不错的VPS
最近抽空把服务器迁移到了linode的Fremont机房，没啥特别原因，内存大啊~10刀2G内存，终于可以大胆的多开几个php-fpm进程了：） 于是我又无耻的来贴推广链接了…
Sequential Consistency，Cache-Coherence及Memory barrier
如今多核CPU在服务器中已经是标配，如何更好的发挥多核CPU进行并行计算相信是每个后端开发都会遇到的难题。这篇文章主要是梳理一下我最近学习的一些关于C++多线程编程的知识。 并发 VS 并行 提到并发编程，有很多不同的编程模型，如多进程、多线程、协程，还可以结合使用I/O多路复用技术来进行异步并发编程，由此产...
被误用的“一致性”
想必每个接触过分布式系统的同学都没少看到过“一致性”这个词，但是我最近有一个越来越强烈的感觉：“一致性”这个词已经被严重的误用了，以至于当我看到这个词的时候，我甚至得花些功夫去思考这到底指的是哪个“一致性”，更严重的是，当别人在谈到“一致性”的时候，实际上他们在谈的完全是另一种东西。 无辜的Paxos 故事的...
分布式共识(Consensus)：Viewstamped Replication、Raft以及Paxos
从上篇文章到现在，已经有半年多的时间没有写过什么了，时间真是匆匆而过，感觉从上次写博客到现在似乎也就是一眨眼的功夫。 回顾我这大半年，完全可以用四个字概括：“不务正业”，先是跟着曼昆的书学习了微观、宏观经济学的基础知识，恶补了一下个人理财的基础理论（很有意思，但依然挡不住我买的基金嗷嗷跌），然后又入坑了摄影（其...
2015
博弈论笔记:囚徒困境和重复博弈
继续上次的笔记，记录下之前几周课程中我觉得比较有意思的一个问题：大名鼎鼎的囚徒困境（Prisoner’s dilemma）。 囚徒困境
博弈论笔记:Normal form game and Nash equilibrium
斯坦福在coursera上的博弈论课程又开放了，这么高大上的课程怎么能错过呢？现在课程已经过半，回过头来对前几周的内容做个小结。 真实的博弈
字符串匹配的后缀算法
字符串匹配问题是算法领域的经典问题，C/C++中常用的strstr函数就是这个问题的定义: const char* strstr( const char* str, const char* target ); char* strstr( char* str, const char* target ); ...
Strict Aliasing，神坑？
先来看一段代码： #include <cstdio> void exchange(int input, int* output) { short* pi = (short*)&input; short* po = (short*)output; po[1] = pi...
探索C++虚函数在g++中的实现
本文是我在追查一个诡异core问题的过程中收获的一点心得，把公司项目相关的背景和特定条件去掉后，仅取其中通用的C++虚函数实现部分知识记录于此。 在开始之前，原谅我先借用一张图黑一下C++： “无敌”的C++ 如果你也在写C++，请一定小心…至少，你要先有所了解：当你在写虚函数的时候，g++在...
TCP Maximum Segment Size (MSS)
这篇是一个小小的查缺补漏，还记得大三网络实验最后助教检查实验问过这个问题：“MSS是干什么的？”，当时背了个定义蒙混过去了，没有仔细理解，现在又遇到了，补上~ MSS是什么？ 下图中看到的是TCP连接发送和接收的过程示意图，最大报文段长度（MSS）的作用是限制在TCP层产生的报文段的最大长度（当然要在滑动窗口...
关于Linux环境C/C++网络框架的一点思考
最近又看了一个网络框架的源码，和之前看过的比起来，应该说是各有特色，互有所长。在这个全民写框架的时代，可能是因为框架（Framework）听起来逼格比较高，所以大家都乐于去写一个自己的“框架”，那么，一个合格的网络框架究竟应该是什么样的？我们又该从何下手？ 什么是网络框架 网络框架，顾名思义，是给网络应用程序...
Hello, SciPy!
“学而时习之，不亦乐乎”，利用放假几天时间，简单复习了一下之前学习的Machine Learning课程，并且用刚上手没两天的SciPy重新完成了大部分Ng的课后作业，SciPy真的非常好用~ SciPy 上图是SciPy官方网站对SciPy的介绍，SciPy并不是单个开源项目，而是一组开源项目...
OpenStack网络迷宫：Neutron以及LBaaS
"一团糟" - 我对OpenStack网络实现的第一感觉 OpenStack的网络模块相信不会有人否认是整个OpenStack中最复杂的部分，即使是OpenStack社区的成员也常常被网络模块的复杂性搞的焦头烂额。因为研究负载均衡的关系，我不得不对网络模块进行一点粗浅的了解，这里按照个人的理解把这...
SRM657 DIV1 Problem Sets
原题链接：Problem Sets Cat Snuke came up with some problems. He wants to construct as many problem sets as possible using those problems. Each problem set mus...
SRM656 DIV1 Random Pancake Stack
被虐了……这个题目其实不难，但是从一开始想法有个漏洞没有发现…一直没有转过弯来…还是需要训练训练… 原题链接：Random Pancake Stack Charlie has N pancakes. He wants to serve some of them for breakfast. We wil...
[转]Linux进程调度：CFS调度器的设计框架
一直计划要写一篇Linux内核中关于进程调度的文章，拖欠了很久，准备动手写的时候发现了此文，看过以后觉得着实没有自己重新写的必要了，转载于此。 原文链接：Linux进程调度(1)：CFS调度器的设计框架
有向图强连通分支：Kosaraju’s algorithm
有向图强连通分支算是个基础算法，不过总是忘记，写下来备忘。 无向图强连通分支非常简单，使用图的遍历算法（DFS或BFS）即可，而有向图的强连通分支计算则要复杂一些，Kosaraju’s algorithm实现了$O(n+m)$时间复杂度的有向图强连通分支算法。 算法的核心思想在于：从有向图中任何一个点出发做D...
全局最小割：Karger’s Min Cut Algorithm
Cut in an undirected graph 提到无向图的最小割问题，首先想到的就是Ford-Fulkerson算法解s-t最小割，通过Edmonds–Karp实现可以在$O(nm^2)$时间内解决这个问题（$n$为图中的顶点数，$m$为图中的边数）。 但是全局最小割和s-t最小割不同，...
2014
Machine Learning小结(5)：异常检测
写这篇小结的时候，Ng的课程已经结束了（期待SoA哈哈哈），回顾整个课程内容，虽然Ng有意的屏蔽了大部分的数学内容，但是提纲挈领的为我们展现了常见机器学习算法的基本容貌和应用技巧，令人受益良多。从视频、课后问答到编程作业，都完美的示范了一门在线课程应该是什么样子的，不能感谢更多。 回到正题，异常检测，也称为离群...
Twisted和Reactor模式
因为项目关系，接触学习了大名鼎鼎的Python网络编程框架Twised，Twisted是以高性能为目标的异步（event-driven）网络编程框架。 Twisted book 图中是Twisted官方推荐的学习书籍的封面，我觉得封面设计的非常贴切：Twisted就是很多Python（蟒蛇）纠缠...
Machine Learning小结(4)：主成分分析（PCA）
主成分分析（PCA）是一种通常用来做数据降维的非监督学习算法，下图是数据降维的直观说明： Principal Component Analysis 在PCA中，我们将每个样本看做特征线性空间中的一个向量，左图代表具有三个特征的样本（处于三维空间中，每个特征代表一个维度），通过寻找空间中样本的主成...
Machine Learning小结(3)：K-means
这已经是我第三次学习K-means算法了，K-means算法应该说不是一个复杂的算法，就做一个相对比较简单的记录吧。 K-means
Machine Learning小结(2)：SVM
继续总结Ng的课程内容，这次是SVM。Ng在课程中说： Most people consider the SVM to be the most powerful “black box” learning algorithm. 在实践中，SVM也的确是一种非常流行的“黑盒”学习算法，下图为SVM标志性的...
APUE杂记：解释器文件
一个非常常见的Python脚本如下： #!/usr/bin/env python # -*- coding: utf-8 -*- import sys def main(): """ main method for my test script~ """ print sys....
Linux内核同步
Data protection Linux内核中有很多同步机制，这篇文章主要总结一下在《Linux Kernel Development》看到的部分内核同步机制，依旧是备忘。 内核同步机制和用户空间的同步机制并不是一一对应的，但是基本的思想都是相同的：保护临界区，只是内核同步机制更适合于在解决内...
Machine Learning小结(1)：线性回归、逻辑回归和神经网络
Coursera上machine learning课程的图标 跟风学习Coursera上Andrew Ng叔的数据挖掘课程已经一个多月了，刚开始在Coursera上看到这门课的时候还有些犹豫，因为研一的时候已经修过学校的数据挖掘课了，那为什么还要再学习这个课程呢？现在想想真是庆幸自己还是选择听听看...
广告慎入
这真的只是一篇广告…
C++中实现多线程安全的单体类
最近看了一些算是比较高大上的C++代码，被内力震伤了，赶紧记录下来！最最基础的就是这个：单体类。单体是面向对象中一种非常流行的设计模式，C++的实现百度一下可以找到一坨，但这个稍稍有点特殊——多线程安全。 普通版本的单体类实现如下： # Singleton.h class Singleton { pu...
[转]What is a Full Stack developer?
临睡前转一篇文章，经常看看，提醒自己：不要给自己设限！我可以做的更多更好。 本文转自：Laurence Gellert’s Blog Is it reasonable to expect mere mortals to have mastery over every facet of the develop...
EXC_BAD_ACCESS : UIScrollView crash on iOS7
在我的应用运行在iOS7上时，当用户点击后退退出一个列表时，有可能会导致应用崩溃，错误信息是：EXC_BAD_ACCESS。 其实这个问题存在很久了，但一直不能稳定复现所以放着没管。这一次版本更新似乎出现概率大了很多，所以追了一下终于找到了原因。
OpenStack奇葩配置：Flat network with external DHCP
最近对实验室的实验用OpenStack环境进行调整，遇到的最大的阻力来自于系楼网络的特殊性：系楼网络采用强制DHCP的模式，这就意味着我没有办法通过手工设定IP地址的方式来使用虚拟机——即使这个IP地址是可用的。 OpenStack似乎没有针对这种情况的网络模式（即使FlatManager也不行），因为所有的网...
在LVM上修改卷大小
实验室的服务器是CentOS6.4的系统，默认采用了LVM。这带来了很大的便利，灵活的卷调整是其中之一。有关于LVM的介绍在这里。 碰巧需要对卷大小进行一次调整，CentOS默认安装为”/home”分配了较大的卷而”/”分配了较小的卷，这不符合目前实验室的使用需求，因此需要对卷大小进行调整，过程记录如下。 操...
Largest Rectangle in Histogram
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogra...
Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of ...
Single Number
Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity...
来自Swift的hello,world!
一觉醒来，所有的新闻媒体都充斥着Swift，不过这个Swift可不是那个女歌手Swift，而是apple在WWDC2014上刚刚发布的新编程语言：Swift。 WWDC2014推出Swift编程语言 Swift是什么？ 突然冒出一个新语言，这感觉…还是先来看看苹果怎么说： Swift ...
Nanos note 2 : 内核初始化
在上一篇文章中，我们已经完成了bootloader的运行：设置内核段描述符、进入保护模式、载入ELF格式内核，并将控制交给内核代码。 但是，此时操作系统的启动过程并未完全完成，本篇文章接着bootloader完成的工作，还是以Nanos为范例，具体的分析一下操作系统内核的初始化过程（内核初始化所使用的代码可以在N...
Nanos note 1 : bootloader
Nanos是JYY大神为南大计算机系操作系统课程专门设计的实验用操作系统。出于对操作系统的好奇和对JYY大神的敬仰，我又再次踏上了DIY玩具内核的道路。和本科时候不同，这次希望能对操作系统有更深的理解，而不是仅仅局限于完成实验，也希望能留下一些笔记作为积淀。这是第一篇note，从分析Nanos的bootloade...
[译]主板芯片组和存储地址映射 - Motherboard Chipsets and the Memory Map
原文在此，翻译仅供参考。 我计划写一些关于计算机内部的文章来解释现代的操作系统内核是如何运行的。我希望这些文章会对那些对此类东西感兴趣而没有相关经验的程序猿有所帮助，我会集中关注Linux、Windows和Intel处理器。探究计算机的内部运行原理是我的爱好,我已经写了一些内核态的代码但是还没有怎么写过相关...
[译]计算机启动过程 - How Computers Boot Up
原文在此，如果英文阅读能力不差还是尽量读原文吧。 先前的文章描述了Intel系列计算机的主板和存储地址映射，在此基础上我们来看看计算机启动的初始阶段。计算机的启动是一个复杂、多阶段并且相当有趣的事情。下图描述了整个计算机启动的过程： 计算机启动过程 当你按下计算机的电源按钮时，启动过程就开...
OpenStack Havana（Ubuntu 13.10）安装笔记
安装配置OpenStack最好的资料是OpenStack的官方安装指南，我就是按照官方指南一步一步进行的，虽然基于的操作系统版本不同（指南中使用的是Ubuntu 12.04），所幸没有遇到什么诡异的问题，不废话了，整个过程记录如下。 安装环境 操作系统：Ubuntu 13.10 配置机器数：1（单点安装...
2013
使用python模拟weibo登录
之前写过在python中使用weibo API的方法，见这里，但是因为weibo API有频率限制，不够目前需求使用，所以通过爬虫模拟登录weibo进行直接抓取还是很有必要的，第一步要做的事情就是模拟登录过程。 weibo的登录方法一直在变，不知道现在的方法还能使用多久。 目前登录使用的是RSA加密的方式，总体...
架设简单git服务器
看到标题，最容易想到的问题就是：“为什么不用github？”。 确实github十分好用，但在如下一些情况下你确实需要一个自己的git服务器： 自己的代码太丑，羞于放在github上… 我很自私，不想开源，又很穷，买不起github付费服务… 开发环境不能连接外网（这是真实存在的）… 我就是想...
通过python SDK使用weibo API
之前做JAVA课大作业的时候曾经用过weibo的API，weibo的API采用OAuth2的认证方法进行认证，也就是避免开发者知晓用户密码的一种手段。不过这样对于开发一些简单使用的客户端程序就不太友好了，可以通过程序模拟授权过程来跳过这一步骤。之前是用JAVA做的，现在用Python再做一次…
通过VNC连接Linux远程桌面
因为特殊的需求关系，琢磨了一下如何在本地连接远程Linux主机的桌面环境。翻了不少网上的相关文章，大部分都只讲了步骤没有说为什么这么做，我就简单再复述一遍吧，加深一下印象。 环境如下： 本地：OS X 10.8.2 服务器：CentOS 6(64位) 基本原理其实很简单，要连接服务器的远程桌面环境，首先需...
再见，百度
2013年1月21号，在大厦办理离职，结束了我在百度为期半年多实习。走出大厦的一刻，有种难以表述的感觉，有轻松，也有失落，总的来说更多的还是对这半年百度生活的怀念。 翻看邮件，找出当时收到的邮件Offer，日期是2012年5月12日，五味杂陈。仍清楚的记得收到邮件的时候的那种激动自豪的心情，记得那种对公司憧憬和...
2012
[译]理解timsort, 第一部分：适应性归并排序(Adaptive Mergesort)
Python2.3中开始使用的timsort应该说算是声名在外了，不管是在稳定性还是在速度上都十分的惊人。 前一段刚刚看了《Python CookBook》中的一些章节，对timsort产生了一些兴趣。于是在网上看到了这边文章，讲的相当清楚明了，于是产生了翻译的念头，也于是有了这篇文章。 这应该算是我翻译的第一...
技术评定:不及格
一起实习的一个兄弟今天离职返校了，临走前聊起了一些关于学校、学习、技术和成绩之类的话题，内容略去不提，但却让我惊醒：我已经是一个大四即将毕业的本科生了。 在学校学习了三年，自己究竟有几斤几两？一年后本科毕业，能否称得上是合格的南大（南京大学）计算机毕业生？思前想后，结果是十分悲观的…作为一个在计算机系学习了三年...
码农两月记
算起来在厂里实习也将近两个月时间了，早该写篇总结之类的东西，一拖再拖，今天正好无事，就稍微小结下在厂里实习的方方面面，也算是给即将找工作的同学们一点参考。 首先上我厂清晰无码大图：
实习面试小结
这不是一篇面经，如果你想看到一篇全面、牛*、高端的面经，我们的面霸鸟哥同志已经写过了，请移步这里。我下面要写的只不过是通过两个月来参加找实习大军的奋战过程中经历和学到的一些经验教训，留作纪念，也算是备忘。 这次找实习过程中总共投了四家公司，华为、腾讯、eBay、百度四家，最后确定了去百度实习。