CharlesXiao‘s Blog

  • 首页

  • 归档

  • 分类

  • 标签

  • 关于

  • 搜索

LeetCode解题总结报告

发表于 2018-12-29 | 更新于 2018-12-30 | 字数统计182字 | 阅读时长1分钟

string字符串

890. Find and Replace Pattern

You have a list of words and a pattern, and you want to know which words in words matches the pattern.
Input: words = [“abc”,”deq”,”mee”,”aqq”,”dkd”,”ccc”], pattern = “abb”
Output: [“mee”,”aqq”]
备注: 字符和数字转换,unordered_map

array数组

math数学

204. Count Primes

Count the number of prime numbers less than a non-negative number, n.
Input: 10
Output: 4
备注: 数学题,注意边界条件,vector标记count

递归

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
备注: helper函数, string拼接, 递归生成vector; 递归终止条件是左括号和右括号剩余数目都=0是递归出口;逻辑:剩余(数>0则继续插入(;剩余)数>0 && 剩余(数>剩余)数, 才能继续插入)

dp动态规划

大象席地而坐

发表于 2018-11-30 | 更新于 2018-12-01 | 字数统计131字 | 阅读时长1分钟 | 分类于 电影

才看了十五分钟,就给人一种扑面而来的压抑感。

少无所教,中无所属,老无所依,这一切的来源都是操蛋的房子。少年要依托于父母的房子,不然动不动开口被赶去姥姥家。老年要因为孙子的学区房而被赶去养老院。当然,这里的赶都不是逼迫,又是逼迫,那种晓之以情、或者失望至极的赶。

看到最后对人生感觉就两个字,操蛋。

The History of the Second World War

发表于 2018-11-25 | 字数统计1.4k字 | 阅读时长4分钟 | 分类于 读书札记

这本书的中文译名是《第二次世界大战回忆录》,二战时英国首相温斯特丘吉尔著,这本书主要的时间线贯穿1919年的《凡尔赛合约》到1945年二战结束,从一战结束一直讲到二战结束,从丘吉尔自己临危受命一直讲到1945年政党落选卸任首相;主要讲述了二战的起因,发展与结局,以及二战中主要战役,战线与格局的发展,可以说是了解与研究二战历史的重要史料,涵盖了军事、政治、外交、经济等方方面面。另外,丘吉尔还因为写了一本《不需要的战争》而获得了1953年的诺贝尔文学奖,传说中卸任后的美国总统都是靠写回忆录为生,果不其然,英国首相也不例外。

打赢了战争只是开始

一战结束之后大家都以为接下来的共识将是和平,然而战胜国对于战败国采取的措施却并不妥当;战胜国在凡尔赛和约中判定战败国需要支付巨量战争赔款,但是显而易见战败国无法支付;更为荒谬的是,战胜国给战败国发放了大量贷款用于战败国的重建,却并没有收到多少的支付赔款,基本都停留在纸面负债上。这意味着什么?战败国在用战胜国的钱重建,但与此同时,战败国国民心里滋生的是更大的怨恨,明面上的剥削和背地里的施与虽然平复了本国人民的愤慨,但是却激起了战败国民的仇恨;这种民族之间的仇恨是酝酿下一次战争的导火索;此外,一战结束之后,德国仍然是欧洲最大的单一民族国家,这让与他相邻的法国人民时时刻刻提醒吊胆,然而其他国家不以为意;而且为了节省开支和为了所谓的“如果战胜国不裁军,有什么理由来要求战败国裁剪军备”的借口,战胜国开始裁军,任由德国做大。在大家集体选择性忽视的情况下,二战的诞生也就具备了足够的条件。

善者的软弱妥协只会助长恶者的凶狠

1932-1933年,在战胜国还在议会上跌跌不休地争论裁军大计时,下士希特勒开始登上德国政治舞台,纳粹党联合了德国陆军,开始带领这个国家走向仇恨之路。与此同时,日本开始向中国挥舞爪牙,侵略中国热河省,并成立伪满洲国。紧接着,德国成立空军和陆军,并重启征兵制,公然违背凡尔赛和约;然而其他国家都只是停留在口头抗议,并没有动用武力的想法。1936年,德国占领莱茵兰,英法等国依然不为所动,两国的首脑人物依然怀着所谓和平的“美好希冀”,毫无做好战争准备的意识。接下来就直接导致了慕尼黑悲剧,英法首脑的绥靖政策和对“和平”的幻想,将捷克这样一个独立国家的领土苏台德割让给了德国,还称之为必要的牺牲。很可惜,他们都被骗了。接下来就是德国撕下自己的伪装了。

起于欧洲战场

1939年,德国闪击波兰,大战爆发。紧接着英法对德宣战。英国首相下台,丘吉尔重新组阁。几年的欧洲战事里,可以说英法的窘迫基本都是自己咎由自取,任由敌人坐大而不自知,丧失了一切先机。在德国闪电战的威力之下,1940年5月荷兰、比利时相继投降,巴黎沦陷,法国政府流亡与伦敦。敦刻尔克大撤退、不列颠空战,无一不是空前壮烈。

战争的蔓延

到了1941年,战争继续蔓延到北非、太平洋、东亚。德国占领希腊之后,开始对苏联开战,此时欧洲第二战场开启,德军围困列宁格勒,接着就是莫斯科保卫战。太平洋上,日本偷袭珍珠港,美国正式参战。紧接着,日本入侵马尼拉,战火蔓延到东南亚地区,菲律宾、新加坡、泰国、澳大利亚无一幸免。

战争的结束

1942年,日本在中途岛惨败,苏联在斯大林格勒进入反攻,1943年墨索尼里被推翻,二战进入尾声,然而最终的结束一直到了1945年;墨索尼里被处死、希特勒自杀、原子弹投放日本,意大利、德国、日本相继无条件投降。而罗斯福也于二战尾声去世,杜鲁门接任;同年,丘吉尔所在保守党在议会选举中落败。两位二战中最重要的人物都并没有真正等到受降那一刻。或许这就是历史的偶然与必然。

警钟长鸣

二战对于全世界人民来说都是一段惨痛的经历,无数人流离失所,无数人血洒山河。人类用自己的智慧创造出了各种杀伤力巨大的武器来毁灭自己和地球,不失为一种嘲讽。i在避免战争这件事情上,仁慈不是放任,战争给世界带来的伤害不可轻言,扼杀在萌芽之中才是良策。

NewSQL数据库探秘

发表于 2018-11-11 | 更新于 2018-11-19 | 字数统计989字 | 阅读时长3分钟

SQL关系型数据库

数据库重难点集锦

NoSQL

键值型

键值数据库的代表是Redis,面对通过主键查询的场景,Redis的效率非常高,但对于内容的查询,则无能为力。分布式只能靠根据主键进行分片,不支持ACID事务。

文档型

文档数据库的代表是MongoDB,查询灵活,拥有自由度极高的Schema模型,可以方便的与JSON数据映射,不支持ACID事务。

列式存储型

HBase用于处理海量数据,不支持ACID事务,并且只能通过行键来查询数据。

NewSQL

NewSQL is a class of modern relational database management systems that seek to provide the same scalable performance of NoSQL systems for online transaction processing (OLTP) read-write workloads while still maintaining the ACID guarantees of a traditional database system.

一种新式的关系型数据库管理系统,具有以下特性:

  1. 针对OLTP(读-写)工作负载,追求提供和NoSQL系统相同的扩展性能
  2. 保持ACID和SQL查询等关系数据库特性

目前业界最流行的分布式数据库有三类:新架构(New Architecture)、透明化分片中间件(Transparent Sharding Middleware)和云数据库(Database-as-a-Service), 2016年Andrew Pavlo与Matthew Aslett发布了一篇论文专门讲述NewSQL,What’s Really New with NewSQL?;新架构以Google Spanner为代表(Shared-Nothing),云数据库以AWS Auraro为代表(Shard-Disk),透明化中间件以Sharding-Proxy(Shared-Nothing)为代表,下文我们一一阐述。

新架构

  1. 主要产品代表为Spanner、TiDB、CockroachDB、OceanBase、TafDB、X-DB。
  2. 主要特点包括弹性扩展、分布式事务、基于Raft/Paxos的多副本复制技术保证一致性、故障容灾高可用;一般会包括master主备节点管理集群元信息、调度数据、负载均衡、分配全局事务ID,SQL节点负责接受用户的SQL并解析以及其它计算工作、访问master元信息去找到存储数据的节点,KV节点负责存储一致性多副本数据(像OB还会把存储节点分为基准数据节点和增量数据节点, 增量数据节点和master共用)。

透明化分片中间件

增加一层proxy,隐藏分库分表的细节,包括MyCat等中间件系统。其实后端还是单机节点中一个MySQL实例内核同时负责存储和计算(Shared-Nothing)。

云数据库

  1. 主要产品代表为Auraro、PolarDB。
  2. 主要特点为计算和存储分离:计算节点基于MySQL内核,并提供主计算节点和多个只读节点来进行容错,计算节点通过RDMA与存储节点连通解决IO性能问题,存储节点基于Raft或者Quorum来做多副本存储,存储其实是共享的(多个数据库实例共享一个分布式存储层)。

数据库构架三种设计模式

Shared Everthting

就是指单机所有资源全部共享,一般是针对单个主机,对外完全透明共享本机的CPU/MEMORY/IO,并行处理能力是最差的,典型的代表SQLServer。

Shared Nothing

各个处理单元都有自己私有的CPU/内存/硬盘等,不存在共享资源,类似于MPP(大规模并行处理)模式,各处理单元之间通过协议通信,并行处理和扩展能力更好。典型代表Hadoop ,各节点相互独立,各自处理自己的数据,处理后的结果可能向上层汇总或在节点间流转。MySQL Proxy和Google Spanner也是Shared Nothing,只需增加服务器数就可以增加处理能力和容量。

Shared Disk

各个处理单元使用自己的私有CPU和Memory,共享磁盘系统,它是数据共享,可通过增加节点来提高并行处理的能力,扩展能力较好。当存储器接口达到饱和的时候,增加节点并不能获得更高的性能。

Golang实现读写缓冲池

发表于 2018-10-29 | 更新于 2018-10-30 | 字数统计1.5k字 | 阅读时长7分钟

所谓读写缓冲池的本质是生产者消费者模型的实际应用。目的是为了避免频繁分配和释放内存,复用最初new出来的固定数目缓冲slice,减少GC压力。

Channel+WaitGroup

Golang并发基本都是这两者搭配使用,通过for+select循环监听发布事件、订阅事件、取消事件。

AsyncReader

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 接口核心方法Begin和Next, Begin用于写数据到blockBuf,Next从blockBuf读取出来数据
type AsyncReader interface {
Begin() error
Stop()
Next() ([]byte, error)
SetTimeoutMs(t uint32)
}

type asyncReader struct {
// 数据来源
reader io.Reader

// buffer配置信息
blockNum uint32
bufferBlockNum uint32 /* blockNum-1 */
blockSize uint32
firstBlockSize uint32
clientTimeout time.Duration
innerTimeout time.Duration

// buffer
blocks []blockBuf

// channal and event
// struct{}不消耗内存空间,一般用来做信号
chRecieve chan struct{} // 读reader数据写到buffer
chStop chan struct{}
chReadEvent chan event // 从buffer读数据
isEof bool
}

// 缓存block
type blockBuf struct {
data []byte
}

type event struct {
/* 在err != nil的时候,readBlockIdx,readLen,isEof的值都是undefined */
readBlockIdx uint32
readLen uint32
isEof bool
err error
}

核心函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
func NewAsyncReader(reader io.Reader, blockSize uint32, blockNum uint32, logId uint32) *asyncReader {
this := &asyncReader{}

/* asyncReader 有多个block作为异步读取数据的缓冲池,
* 当用户调用next读取数据时,会把底层内存块以slice的方式交给调用方读取,
* 所以需要多开辟1块block,避免正在缓冲的block同时被用户读取,产生竞态
* this.blockNum 是asyncReader里实际开辟的block数
* this.bufferBlockNum 是asyncReader 里用来异步缓冲的block数
*/
this.blockNum = blockNum + 1
this.bufferBlockNum = this.blockNum - 1

// 开辟缓存空间
this.blocks = make([]blockBuf, this.blockNum)
for i := uint32(0); i < this.blockNum; i++ {
this.blocks[i].data = nil
}

this.chRecieve = make(chan struct{}, this.bufferBlockNum)
this.chStop = make(chan struct{}, 1)
this.chReadEvent = make(chan event, this.blockNum)

// default:
this.firstBlockSize = this.blockSize
this.SetTimeoutMs(1000)
this.isEof = false
return this
}

/* 异步读取数据 */
func (this *asyncReader) Begin() error {

for i := uint32(0); i < this.bufferBlockNum; i++ {
this.chRecieve <- struct{}{}
}

go func() {
isFirstBlock := true
blockIdx := uint32(0)
for {
select {
case <-this.chStop: // 终止信号
return
case <-time.After(this.innerTimeout):
// 默认协程异步读数据等待客户端读毕的超时时间,是客户端超时的2倍
this.chReadEvent <- NewEvent(fmt.Errorf("asyncReader begin() timeout"))
return
case <-this.chRecieve: // 监听receive信号
}

toReadLen := this.blockSize

len, isEof, err := this.ReadOneBlock(blockIdx, toReadLen)
if err != nil {
this.chReadEvent <- NewEvent(err)
return
}
// 读取成功一个block,就发送一个read event到通道,后续Next函数会主动获取
if len > 0 {
this.chReadEvent <- event{blockIdx, len, isEof, nil}
blockIdx = (blockIdx + 1) % this.blockNum // 接着写下一个block
}
if isEof {
this.chReadEvent <- event{0, 0, true, nil}
break
}
}
}()
return nil
}

/* 读取toReadLen长度的数据,直到满足长度或者EOF */
/* 返回参数 readLen,isEof,error */
func (this *asyncReader) ReadOneBlock(blockIdx uint32, toReadLen uint32) (uint32, bool, error) {
var haveReadLen uint32
for haveReadLen = 0; haveReadLen < toReadLen; {
if this.blocks[blockIdx].data == nil {
this.blocks[blockIdx].data = make([]byte, this.blockSize)
}

readLen, err := this.reader.Read(this.blocks[blockIdx].data[haveReadLen:toReadLen])
if readLen > 0 {
haveReadLen += uint32(readLen)
}
if err == io.EOF {
return haveReadLen, true, nil
} else if err != nil {
log.Logger.Warn("[logid:%d] async reader readLen:%d, error:%s",
this.logId, haveReadLen, err)
return haveReadLen, true, err
}
}
return haveReadLen, false, nil
}

/* 1. asyncReader只支持一个协程读取数据
* 2. 返回的slice是asyncReader底层的buffer,数据有效期到下次调用next之前,
* 返回的slice不允许做写操作,如果有写需求,请copy
* 3. Next一般放在for循环中调用, 直到返回数据为nil
*/
func (this *asyncReader) Next() ([]byte, error) {
if this.isEof {
return nil, nil
}

select {
case <-time.After(this.clientTimeout):
return nil, TimeOutError
case event := <-this.chReadEvent:
if event.err != nil {
return nil, fmt.Errorf("asyncReaderAll.next error. %s", event.err)
}

if event.isEof {
this.isEof = true
if event.readLen > 0 {
return this.blocks[event.readBlockIdx].data[0:event.readLen], nil
} else {
return nil, nil
}
} else {
// 发送继续写buffer的信号,Begin函数里边的协程继续从reader读取下一个block写到缓存; 如果blockNum==bufferBlockNum,此处会出现竞态
this.chRecieve <- struct{}{}
return this.blocks[event.readBlockIdx].data[0:event.readLen], nil
}
}
}

BufferPool

读写缓冲池,Bodybufs是缓冲区,多个slice

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type BufferPool interface {
Write(start []byte, length int, err error) BosErrorCodeType
Read() ([]byte, int, error)
SendCanWriteSignal(signal int) BosErrorCodeType
}

type BufferPoolImp struct {
Bodybufs []BodyBuf
bufWraps chan BufWrap // 读写通道,buffer内容指针
writeSignals chan int // 决定是否可写
currentIndex int // 写入当前的Bodybufs[index]
maxBufferSize int
timeout int
needMallocMemory bool //pre malloc memory or not
}

type BodyBuf struct {
data []byte
}

type BufWrap struct {
index int //index of bodyBufs
n int //size has read from r.Body
err error
}

核心函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
func (bp *BufferPoolImp) Write(start []byte, length int, err error) BosErrorCodeType {
select {
case writeSignal := <-bp.writeSignals:
log.Logger.Debug("[logid:%d] read can write signal ok: %d", bp.logId, writeSignal)
if writeSignal != 0 {
return BosErrorCodeType(writeSignal)
}
case <-time.After(time.Duration(bp.timeout) * time.Second * 2):
log.Logger.Error("[logid:%d] wait writeSignal timeout", bp.logId)
return CODE_INTERNAL_ERROR
}

// start数据写入到BodyBufs, 并往bufWraps chan写内容指针,read函数会监听该通道
bp.Bodybufs[bp.currentIndex] = BodyBuf{start}
bufWrap := BufWrap{bp.currentIndex, length, err}

select {
case bp.bufWraps <- bufWrap:
log.Logger.Debug("[logid:%d] write buffers, index[%d]", bp.logId, bp.currentIndex)
bp.currentIndex = (bp.currentIndex + 1) % bp.maxBufferSize
case <-time.After(time.Duration(bp.timeout) * time.Second):
log.Logger.Error("[logid:%d] write buffers timeout", bp.logId)
return CODE_INTERNAL_ERROR
}

return CODE_OK
}

// read一般放在for循环中调用, 直到返回数据为nil
func (bp *BufferPoolImp) Read() ([]byte, int, error) {
select {
case bufWrap := <-bp.bufWraps: // 获取写的内容
log.Logger.Debug("[logid:%d] read buffers, index[%d], len[%d]",
bp.logId, bufWrap.index, bufWrap.n)
if bufWrap.index < 0 || bufWrap.index > bp.maxBufferSize-1 {
return nil, -1, bufWrap.err
}
return bp.Bodybufs[bufWrap.index].data, bufWrap.n, bufWrap.err
case <-time.After(time.Duration(bp.timeout) * time.Second):
log.Logger.Error("[logid:%d] read buffers timeout", bp.logId)
return nil, -1, ReadTimeOutError
}
}

// 调用read函数时需要同时调用这个函数,以确保write函数可以继续写buffer
// read之后再调用该函数,所以不像async_reader可能出现竞争状态
func (bp *BufferPoolImp) SendCanWriteSignal(signal int) BosErrorCodeType {
select {
case bp.writeSignals <- signal:
log.Logger.Debug("[logid:%d] send can write signal ok", bp.logId)
case <-time.After(time.Duration(bp.timeout) * time.Second * 2):
log.Logger.Error("[logid:%d] write writeSignal timeout", bp.logId)
return CODE_INTERNAL_ERROR
}
return CODE_OK
}
12…18
CharlesXiao

CharlesXiao

在码农炼成之路不断挣扎……stay hungry……keep learning……

87 日志
18 分类
78 标签
github weibo Daijiale的个人站点
推荐阅读
  • RocksDB
  • Google FE
© 2015.05.16 – 2019 CharlesXiao
本站总访问量:
|
总访客数:
|
博客全站共169.6k字