暑假学习的一点东西,给自己做个笔记,以后可以看看。 mySQL三层: 上层服务器{C/S结构},核心功能{查询、优化...},并发控制{服务器层,存储引擎层} mysql的存储引擎架构: 将查询处理和其他任务处理分离,即:把对数据的操作与其对应的存储操作方式分离,提高系统的灵活性,类似策略模式,可以改变系统的引擎,以提供不同的存储策略,这个和linux的(VFS)文件系统类似。 隔离分级:未提交读(回滚后,有脏读现象),提交读(仅MVCC不加X锁,不同的事务之间不能满足重复读,因为并发会发生并发冲突,虽然是共享内存,但是不加锁的情况下,事务在不同时间看到的数据可能不一样(根据lamport时间戳的因果关系,不能确定因果(先后)关系的操作成为并发),这也是因为不同事务之间消息通信方式的异步性),可重复读(使用MVCC+X锁可以实现,会出现幻读,要加间隙锁),可串行化(这个使用同步的通信方式可以实现)。 如果使用MVCC+X锁+间隙锁,就可以解决脏读,可重复读,幻读,并且可以保证并发读,仅在写时 继续阅读 >>


许博东 16/08/31 17:26:37
以下是对我之前学习的linux网络编程的一些笔记。 int socket(int domain, int type, int protocol); type这个参数,可以加上一个 SOCK_NONBLOCK,把套接字设置为非阻塞,保证这一设置的原子性。 int listen(int sockfd, int backlog); 把sockfd设置成listen状态,之后就可以完成三次握手了,其实三次握手是在内核态完成的,accpet仅仅只是移除已经做好三次握手的链表中的套接字。 而backlog有最大值限制,一般为128。这就是做好三次握手,却没有被accept移除的数据链表大小。 int bind(int sockfd, const struct sockaddr *addr,socklen_t addrlen); 绑定sockfd和端口,以及IP,注意:sockaddr的另一个异构的结构体:sockaddr_in中的sin_port和sin_address必须是网络字节序。 为什么sin_family不用? 因为它不用发送到网络上去, 继续阅读 >>


许博东 16/08/23 21:51:40
CAS     其实CAS是用于乐观锁的一种实现,具体过程是“读-改-写”: (1)读取数据版本号(时间戳); (2)对数据进行修改; (3)对数据进行回写,查看数据版本号,如果版本号没有变化,那么成功写入,如果数据版本号变化了,那么写入失败,放弃此次修改。(最后一点的版本号比较-写入,应该是原子性的,这利用linux的atomic_t或者自己用锁都可实现。) (atomic_cmpxchg是由cmpxchg指令完成的。它把旧值同atomic_t类型的值相比较,如果相同,就把新值存入atomic_t类型的值中,返回atomic_t类型变量中原有的值。) CAS其实是利用了同一台机器上的时间戳的大小是可以表示事件发生的因果关系(不同的机器上是不可以的,在上面的时间戳部分有说明)。 由上面我们可以知道,由于时间戳可以表示不同机器上操作的偏序关系,要定义一种全序才能解决并发冲突的问题,由此,CAS定义了一种“先写入胜利”的关系。发现了没,CAS用的是“先”,又出现 继续阅读 >>


许博东 16/08/16 10:08:35
原文地址:http://blog.csdn.net/sparkliang/article/details/5740882 最近再看,先荡下来。 Paxos一致性算法——分布式系统中的经典算法,论文本身也有一段有趣的故事。一致性问题是分布式系统的根本问题之一,在论文中,作者一步步的加强最初一致性问题(2.1节提出的问题)的约束条件,最终导出了一个可实现的一致性模型。当前Paxos算法的研究越来越多,相关实现也不少,而原论文依然是最不可少的资料。论文通篇没有一个数学公式,这是大牛的坚持! 【】中的是我个人的注释。 先解释文中几个关键词的翻译: Proposal译为“议案”,由proposer提出,被aceeptor批准或否决 Value译为“决议”,它是议案的内容,一个议案就是一个{编号,决议}对 Accept译为“批准”,表示议案被acceptor批准 Choose译为“选择”,表示议案“被选择”,也就是被多数acceptor批准 Paxos Made Simple Leslie Lamport 2001.11.1 简介 Paxos算法,纯文本方式描述,非 继续阅读 >>


许博东 16/08/15 22:31:21
cas和vector clock 都是以时间戳,作为并行的检测手段,那么时间戳为什么可以表现出并行或因果时序呢? 在1978年的lamport论文Time Clocks and the Ordering of Events in a Distributed System就论述了时间戳的原理。 以下是我读完这篇论文的一些自己的理解(不是论文翻译),因为很喜欢物理,所以对这个问题也格外感兴趣。如果有不对的地方还请指正。 在1967年召开的第13届国际度量衡大会对秒的定义:铯-133的原子基态的两个超精细能阶间跃迁对应辐射的9,192,631,770个周期的持续时间。这或许让人大跌眼睛,时间流逝居然是有物质变化定义的。这和我们所了解的绝对时间有很大的出入。 那么分布式的时间又是由什么事物的变化定义的? 就像薛定谔的猫一样,当我们观察猫的时候,猫的状态就确定了,可是当我们不去观察它的时候,它的生死却是不确定的,那么我们可以知道,先后(因果)关系,必须要观察才能得到。 而在分布式中,任何计算机上的事务都可能并行生,那么什么样的事件是可以观 继续阅读 >>


许博东 16/08/15 22:14:32
RIP使用Bellman-Ford算法 在开始之前呢,我们先了解一下Bellman-Ford算法吧! Bellman-Ford算法(Dijstra算法也是)是来自于动态规划。动态规划的两点特征:最优子结构和重叠子问题。 首先是最优子结构问题: 最短路径的子路径也是最短路径:从vi经过vj到vk的最短路必须要经过的子路径vj到vk的最短路和子路径vi到vj的最短路,就是说两个子路径必须都是最短路,他们之和才有可能是最短路径。 其次是重叠子问题: 如果我们要求从vi到vz的最短路径,那么我们也要求出从vi到vj,直至 vy的最短路径,每一次求解的过程中都会出现重叠的子问题。比如,求从vi经过vj到vk的最短路,就需要先求得vi到vj的最短路,这就是vi到vk的子问题,而且这个子问题不只出现在当前vi 到vk点最短路的问题中,也会出现在vi到vj最短路的问题中,他们的子问题就是重叠的。 由此我们得到动态规划的动态转移方程: dist[eage[j].v] = min(dist[eage[j].v] ,dist[eage[j].u] + eage 继续阅读 >>


许博东 16/03/17 19:30:20
路由表的更新操作主要来自于: 1)使用netstat,route进行手动添加或者从interface(我的机子是ubuntu)配置文件中添加静态路由。 2)路由守护程序通过RIP或OSPF协议和其他路由器进行信息交换,从而获得网络拓扑图,并使用最短路算法,bellman-ford或者dijstra算法进行最短路计算。 3)由ICMP协议的路由发现报文和重定向差错报文实现。 以上,1是进行静态路由。静态路由是在路由器中设置的固定的路由表。除非网络管理员干预,否则静态路由 不会发生变化。由于静态路由不能对网络的改变作出反映,一般用于网络规模不大、拓 扑结构固定的网络中。静态路由的优点是简单、高效、可靠。在所有的路由中,静态路 由优先级最高。当动态路由与静态路由发生冲突时,以静态路由为准。 2是动态路由动态。路由是网络中的路由器之间相互通信,传递路由信息,利用收到的路由信息更 新路由器表的过程。它能实时地适应网络结构的变化。如果路由更新信息表明发生了网 络变化,路由选择软件就会重新计算路由,并发出新的路由更新信息。这些信息通过各 个网络,引起各路由器重新启动其路 继续阅读 >>


许博东 16/03/16 20:48:51
原文网址:http://blog.csdn.net/dog250/article/details/6612496 说明: 1).本文以TCP的发展历程解析容易引起混淆,误会的方方面面 2).本文不会贴大量的源码,大多数是以文字形式描述,我相信文字看起来是要比代码更轻松的 3).针对对象:对TCP已经有了全面了解的人。因为本文不会解析TCP头里面的每一个字段或者3次握手的细节,也不会解释慢启动和快速重传的定义 4).除了《TCP/IP详解》(卷一,卷二)以及《Unix网络编程》以及Linux源代码之外,学习网络更好的资源是RFC 5).本文给出一个提纲,如果想了解细节,请直接查阅RFC 6).翻来覆去,终于找到了这篇备忘,本文基于这篇备忘文档修改。 1.网络协议设计 ISO提出了OSI分层网络模型,这种分层模型是理论上的,TCP/IP最终实现了一个分层的协议模型,每一个层次对应一组网络协议完成一组特定的功能,该组网络协议被其下的层次复用和解复用。这就是分层模型的本质,最终所有的逻辑被编码到线缆或者电磁波。      继续阅读 >>


许博东 16/03/16 15:35:21
TCP/IP:我们把网络定义为互相连接在一起的设备,网络的本质作用还是“端到端”的通信,然而希望互相通信的设备并不一定要“直接”连接在一起,因此必然需要一些中间的设备(路由)负责转发数据,因此就把连接这些中间设备的线缆上跑的协议定义为链路层协议,实际上所谓链路其实就是始发与一个设备,通过一根线,终止于另一个设备。我们把一条链路称为“一跳”。因此一个端到端的网络包含了“很多跳”。 此话引用自此博客,大神,膜拜 http://blog.csdn.net/dog250/article/details/6612496 IP(网络层)在我看来其实就是复用下层繁多的链路层协议,为上层传输层提供统一的接口,就是说,网络层对下层繁多的协议进行地址管理,每个设备不管它的物理层及其而对应的链路层使用的是什么协议,都对他们统一的使用IP地址进行唯一的标识,进行一跳一跳的传输。而向上,对传输层的协议进行分用(识别IP首部的协议字段),向上分用多个协论(TCP,UDP,ICMP,IGMP),保证不同的协议能被分到不同的协议软件中进行处理。传输层在此基础上就很简单的,他不用再考虑下 继续阅读 >>


许博东 16/03/16 10:16:30
Description Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows 继续阅读 >>


许博东 16/03/15 22:06:08