高性能键值存储系统实现
简易Redis的实现这个项目实现了一个简易的redis,使用hashmap来管理键值对数据,使用hashmap+AVL数来管理Zset数据,并实现了hashmap的渐进式扩容,减少因为扩容重新哈希化带来rehash的代价。使用poll技术来实现IO多路复用,完成一个服务端与多个客户端建立连接的过程,使用双向链表来管理连接,通过最小堆来控制val的生存时间,并通过将两者结合的方式,控制poll的最大超时时间,用来确保每一次poll的陷入内核和退出内核在主进程中都有处理的任务。
1、最小堆的维护,当为某一个key设置好ttl时,会将key当中需要维护的ttl放入到最小堆当中,每一次轮询结束以后,会统一进行处理,已经失效的key
2、双向链表的维护,poll当中,会把第一个fd设置成为用于处理连接事件的fd,当有连接事件发生的时候,会处理连接,接受一个新的连接,并将其放入到双向链表的头部,会有一个conn的结构体,里面实现了读写缓存,以及接受当前连接的空闲队列节点,以及建立连接的时间,然后会把这个连接放入到空闲队列当中的头部。
3、过期时间的处理,会在每一次poll以及对应的事件处理结束以 ...
RPC(Remote Procedure Calls)
RPC(Remote Procedure Calls)
论文链接:http://birrell.org/andrew/papers/ImplementingRPC.pdf
这篇论文主要讲了实现远程过程调用,远程过程调用通俗的来讲是在一台计算机A上的进程,调用另一台计算机B上的进程,其中A上调用进程被挂起,而B上的调用进程开始执行,当值返回给A时,A进程继续执行。调用放可以通过使用参数信息传送给被调用方,而后通过传回的结果得到信息。这一过程对于开发人员来说是透明的。
结构当进行远程调用时,有五个程序部分参与:用户、用户存根、RPC通信包(RPCRuntime)、服务器存根和服务器。其中用户、用户存根和RPCRuntime的一个实例在调用者机器上执行;服务器、服务器存根和RPCRuntime的另一个实例在被调用者机器上执行。
当用户希望进行远程调用时,它实际上进行一个完全正常的本地调用,调用对应的用户存根中的过程。用户存根负责将目标过程和参数的规格说明放入一个或多个数据包中,并请求RPCRuntime将这些数据包可靠地传输到被调用者机器。在接收到这些数据包后,被调用者机器上的RPCRu ...
GFS(Google File System)
分布式存储系统的目标通常我们设计大型分布式系统或者大型存储系统的出发点是,我们需要获得巨大的性能加成,进而利用数百台计算机的资源来同时完成大量工作。之后很自然的想法便是将数据分割放到大量的服务器上,这样就可以并行的从多台服务器读取数据。这种方式称之为分片Sharding。
而当我们在成百上千台服务器进行分片,量多了便会出现一些常态的故障。如果我们有数千台服务器,每台服务器平均每三年故障一次,那么我们平均每天就会有3台服务器宕机。所以我们需要自动化的方法而不是人工介入来修复错误,我们需要一个自动容错系统,这便是容错。
实现容错最有用的方式便是复制,我们可以通过维护多个数据的副本,当其中一个故障了以后,变使用另一个。因此想要拥有容错能力,就要有复制。
而很显然,我们是会把同样的数据放在不同的服务器上,也就是说同一份数据会拥有多个副本,有多个副本就有可能因为并发的原因导致不同副本的不一致,也许我们可以通过一些手段去实现一致性,让我们的结果符合是基于其,但是这样的效果,往往伴随着性能的降低,而这便回到了我们开始的性能问题。
GFS(Google File System)
论文链接:https: ...
MapReduce
MapReduce
论文链接
MapReduce是一种编程模型,用于处理和生成大规模数据集,用户指定一个map函数,该函数处理一组输入数据(键值对)以生成一组中间键/值对,并指定一个reduce函数来合并所有与同一个键相关的中间值。
以这种函数式风格编写的程序会自动并行化,并在大规模集群的商品机器上执行。运行时系统负责分割输入数据、在一组机器上调度程序的执行、处理机器故障以及管理必要的机器间通信。这使得没有并行和分布式系统经验的程序员也能轻松利用大型分布式系统的资源。
我们可以理解为MapReduce隐藏了在一组机器运行过程中进行通信的细节,当然还有并行化、容错、数据分发和负载平衡的复杂细节,使得程序员可以和开发普通程序一样开发分布式的应用。
例子-词频统计1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include "mapred ...
C++中常见容器的使用方法
序列容器
不知道如何解释,凭感觉吧,就是我们想象中的那样。
vectorvector是我们常用的动态数组,它通过模板泛型编程的方式,让我们能够使用vector来存储任意对象。
vector的底层是内存当中一段连续的地址空间,地址空间连续的最大好处就是能够支持用户的随机访问,我们可以和操作数组一样,使用下标的方式来获取到容器中的对象。在vector中有两个关键的成员变量size和capacity,其中size表示的是当前容器中存储的对象实际个数,而capacity则是容器的最大容量。这两个成员是实现vector扩容的关键。
常用的接口
类别
成员函数
描述
容量相关
size()
返回容器中元素的个数。
max_size()
返回容器所能容纳的最大元素数量。
resize(n, val)
调整容器的大小到 n 个元素,如果 n 大,则以 val 填充新位置。
capacity()
返回不需要重新分配内存空间的情况下容器可容纳的元素数量。
empty()
检测容器是否为空。
reserve(n)
请求容器容量至少为 n 个元素。
shr ...
如何使用GDB进行调试
如何使用GDB调试GDB (全称为GNU Debuger) 是一款由 GNU 开源组织发布、基于 UNIX/LINUX 操作系统的命令行程序调试工具。对于一名 Linux 下工作的 C++ 程序员,GDB 是必不可少的工具。Linux下工作的程序员都习惯用命令行开发,所以这种命令行调试工具并不会觉得难用;其次,基于 Linux 服务器等的无图形界面开发,使用 Vim+GDB 可以在任意一台电脑上直接调试,不用花时间安装复杂的 IDE 环境。
GDB常见调试命令1、启动GDB
对于 C/C++ 程序调试,需要在编译前加入 -g 参数选项,表示加入一些调试信息。这样在编译后生成的可执行文件才能使用 GDB 进行调试。
123g++ -g main -o demo // 生成可执行文件gdb demo // 启动GDB调试
2、相关命令
123456789101112131415161718192021222324252627282930313233343536373839404142// 查看接下来的10行list// 打断点break nbreak file:nbreak func ...
Go语言学习-协程、管道、并发
Goroutines和ChannelsGo语言中的并发程序一般会使用两种手段来实现。第一种是goroutine,第二种是channel,其支持CSP:communicating sequential processes,叫做顺序通信进程。
CSP是一种现代的并发编程模型,在这种编程模型中值会在不同的运行实例(groutine)中传递,尽管大多数情况下仍然是被限制在单一实例中。
Goroutines-协程
每一个并发的执行单元叫做一个goroutine(协程),如果有多个函数,函数之间不存在调用关系,那么这两个函数就有并发执行的可能。我们可以把协程理解为一个轻量级线程。它们允许我们使用的时候并发的执行函数,和传统的操作系统线程相比,协程更加高效,消耗的资源更少。
当一个程序启动时,其主函数会在一个单独的goroutine中运行,称为主协程,新的协程会使用go语句来创建。在语法上,我们只要在一个方法调用前加上关键字go,就会使得这个函数在一个新创建的goroutine中运行。
当我们的协程已经启动以后,除了从主函数退出或者直接终止程序之外,没有其它的编程方法能够让一个goroutine来 ...
Go语言学习-基本语法
Go语言学习-基本语法GO语言特性
并发编程
Go语言中引入了goroutine,通过调用go关键字,可以让函数以goroutine的方式进行运行,以协程为单位进行运行。
协程相比线程更加轻量级,也更节省系统资源。
goroutine内部采用管道channel进行消息传递,从而实现共享内存。
错误处理
函数通过返回错误类型error或者bool类型表明函数执行结果,通过判断返回值是否为nil。
引入了defer关键字用于标准的错误处理流程,提供内置函数panic,recover完成异常抛出和捕捉
垃圾回收
自带自动回收功能,不需要delete和free来释放内存
多返回值
支持多返回值,可以用下划线作为占用符丢掉不要的返回值
匿名函数
支持常规的匿名函数和闭包
1234567891011// hello.gopackage mainimport ( "fmt" //导入fmt包,调用其中的Println()函数)func main() { fmt.Println("Hello,world!")}
数据类 ...
Go语言学习-函数、方法、接口
函数-functionGo语言中,函数的命名定义需要func来作为唯一标识,并且使用首字母大小写来区分,在当前文件夹下的某一个函数是否可以通过import bag的方式来对其他文件的可见性,如果是大写则说明可以导入,小写则只能在当前文件内可见。
函数通过四个属性来唯一确定函数签名-函数名、形参列表、返回值列表、函数体。
123func name(parameter-list) (result-list) { body}
多返回值
在Go中,一个函数可以返回多个值,并且函数的返回值必须要有变量来接收,如果我们不需要某一个返回值,通常我们会用_下划线来接收这个返回值,作为接收某一个返回值的占位符。
我们通常想要保留函数运行过程中的某一些局部变量的结果,或者想要拥有多个返回变量,比较常见的方法就是,定义一个全局变量,并把变量作为引用类型传入到函数内,这样的方式可以达到效果,但是会有参数列表冗余的现象,如果我们需要保留的局部变量的参数非常多,那么也需要定义多个参数来一一完成。
使用多返回值可以更清晰的表达结果,避免全局变量定义的冗余,以及引用传入的冗余,我们可以将局部 ...