开发者博客 – IT技术 尽在开发者博客

开发者博客 – 科技是第一生产力


  • 首页

  • 归档

  • 搜索

草根学Python(十三)线程和进程 前言 目录 线程与进程

发表于 2017-10-13

前言

拖了好久,不过还是得坚持。喜欢本文的话可以加下公众号【于你供读】。

目录

草根学Python(十三) 线程和进程

线程与进程

线程与进程是操作系统里面的术语,简单来讲,每一个应用程序都有一个自己的进程。

操作系统会为这些进程分配一些执行资源,例如内存空间等。在进程中,又可以创建一些线程,他们共享这些内存空间,并由操作系统调用,以便并行计算。

我们都知道现代操作系统比如 Mac OS X,UNIX,Linux,Windows 等可以同时运行多个任务。打个比方,你一边在用浏览器上网,一边在听敲代码,一边用 Markdown 写博客,这就是多任务,至少同时有 3 个任务正在运行。当然还有很多任务悄悄地在后台同时运行着,只是桌面上没有显示而已。对于操作系统来说,一个任务就是一个进程(Process),比如打开一个浏览器就是启动一个浏览器进程,打开 PyCharm 就是一个启动了一个 PtCharm 进程,打开 Markdown 就是启动了一个 Md 的进程。

虽然现在多核 CPU 已经非常普及了。可是由于 CPU 执行代码都是顺序执行的,这时候我们就会有疑问,单核 CPU 是怎么执行多任务的呢?

其实就是操作系统轮流让各个任务交替执行,任务 1 执行 0.01 秒,切换到任务 2 ,任务 2 执行 0.01 秒,再切换到任务 3 ,执行 0.01秒……这样反复执行下去。表面上看,每个任务都是交替执行的,但是,由于 CPU的执行速度实在是太快了,我们肉眼和感觉上没法识别出来,就像所有任务都在同时执行一样。

真正的并行执行多任务只能在多核 CPU 上实现,但是,由于任务数量远远多于 CPU 的核心数量,所以,操作系统也会自动把很多任务轮流调度到每个核心上执行。

有些进程不仅仅只是干一件事的啊,比如浏览器,我们可以播放时视频,播放音频,看文章,编辑文章等等,其实这些都是在浏览器进程中的子任务。在一个进程内部,要同时干多件事,就需要同时运行多个“子任务”,我们把进程内的这些“子任务”称为线程(Thread)。

由于每个进程至少要干一件事,所以,一个进程至少有一个线程。当然,一个进程也可以有多个线程,多个线程可以同时执行,多线程的执行方式和多进程是一样的,也是由操作系统在多个线程之间快速切换,让每个线程都短暂地交替运行,看起来就像同时执行一样。

那么在 Python 中我们要同时执行多个任务怎么办?

有两种解决方案:

一种是启动多个进程,每个进程虽然只有一个线程,但多个进程可以一块执行多个任务。

还有一种方法是启动一个进程,在一个进程内启动多个线程,这样,多个线程也可以一块执行多个任务。

当然还有第三种方法,就是启动多个进程,每个进程再启动多个线程,这样同时执行的任务就更多了,当然这种模型更复杂,实际很少采用。

总结一下就是,多任务的实现有3种方式:

  • 多进程模式;
  • 多线程模式;
  • 多进程+多线程模式。

同时执行多个任务通常各个任务之间并不是没有关联的,而是需要相互通信和协调,有时,任务 1 必须暂停等待任务 2 完成后才能继续执行,有时,任务 3 和任务 4 又不能同时执行,所以,多进程和多线程的程序的复杂度要远远高于我们前面写的单进程单线程的程序。

因为复杂度高,调试困难,所以,不是迫不得已,我们也不想编写多任务。但是,有很多时候,没有多任务还真不行。想想在电脑上看电影,就必须由一个线程播放视频,另一个线程播放音频,否则,单线程实现的话就只能先把视频播放完再播放音频,或者先把音频播放完再播放视频,这显然是不行的。

多线程编程

其实创建线程之后,线程并不是始终保持一个状态的,其状态大概如下:

  • New 创建
  • Runnable 就绪。等待调度
  • Running 运行
  • Blocked 阻塞。阻塞可能在 Wait Locked Sleeping
  • Dead 消亡

线程有着不同的状态,也有不同的类型。大致可分为:

  • 主线程
  • 子线程
  • 守护线程(后台线程)
  • 前台线程

简单了解完这些之后,我们开始看看具体的代码使用了。

1、线程的创建

Python 提供两个模块进行多线程的操作,分别是 thread 和 threading

前者是比较低级的模块,用于更底层的操作,一般应用级别的开发不常用。

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
复制代码#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import time
import threading


class MyThread(threading.Thread):
def run(self):
for i in range(5):
print('thread {}, @number: {}'.format(self.name, i))
time.sleep(1)


def main():
print("Start main threading")

# 创建三个线程
threads = [MyThread() for i in range(3)]
# 启动三个线程
for t in threads:
t.start()

print("End Main threading")


if __name__ == '__main__':
main()

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
复制代码Start main threading  
thread Thread-1, @number: 0
thread Thread-2, @number: 0
thread Thread-3, @number: 0
End Main threading
thread Thread-2, @number: 1
thread Thread-1, @number: 1
thread Thread-3, @number: 1
thread Thread-1, @number: 2
thread Thread-3, @number: 2
thread Thread-2, @number: 2
thread Thread-2, @number: 3
thread Thread-3, @number: 3
thread Thread-1, @number: 3
thread Thread-3, @number: 4
thread Thread-2, @number: 4
thread Thread-1, @number: 4

注意喔,这里不同的环境输出的结果肯定是不一样的。

2、线程合并(join方法)

上面的示例打印出来的结果来看,主线程结束后,子线程还在运行。那么我们需要主线程要等待子线程运行完后,再退出,要怎么办呢?

这时候,就需要用到 join 方法了。

在上面的例子,新增一段代码,具体如下:

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
复制代码#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import time
import threading


class MyThread(threading.Thread):
def run(self):
for i in range(5):
print('thread {}, @number: {}'.format(self.name, i))
time.sleep(1)


def main():
print("Start main threading")

# 创建三个线程
threads = [MyThread() for i in range(3)]
# 启动三个线程
for t in threads:
t.start()

# 一次让新创建的线程执行 join
for t in threads:
t.join()

print("End Main threading")


if __name__ == '__main__':
main()

从打印的结果,可以清楚看到,相比上面示例打印出来的结果,主线程是在等待子线程运行结束后才结束的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
复制代码Start main threading  
thread Thread-1, @number: 0
thread Thread-2, @number: 0
thread Thread-3, @number: 0
thread Thread-1, @number: 1
thread Thread-3, @number: 1
thread Thread-2, @number: 1
thread Thread-2, @number: 2
thread Thread-1, @number: 2
thread Thread-3, @number: 2
thread Thread-2, @number: 3
thread Thread-1, @number: 3
thread Thread-3, @number: 3
thread Thread-3, @number: 4
thread Thread-2, @number: 4
thread Thread-1, @number: 4
End Main threading

3、线程同步与互斥锁

使用线程加载获取数据,通常都会造成数据不同步的情况。当然,这时候我们可以给资源进行加锁,也就是访问资源的线程需要获得锁才能访问。

其中 threading 模块给我们提供了一个 Lock 功能。

1
复制代码lock = threading.Lock()

在线程中获取锁

1
复制代码lock.acquire()

使用完成后,我们肯定需要释放锁

1
复制代码lock.release()

当然为了支持在同一线程中多次请求同一资源,Python 提供了可重入锁(RLock)。RLock 内部维护着一个 Lock 和一个 counter 变量,counter 记录了 acquire 的次数,从而使得资源可以被多次 require。直到一个线程所有的 acquire 都被 release,其他的线程才能获得资源。

那么怎么创建重入锁呢?也是一句代码的事情:

1
复制代码r_lock = threading.RLock()

4、Condition 条件变量

实用锁可以达到线程同步,但是在更复杂的环境,需要针对锁进行一些条件判断。Python 提供了 Condition 对象。使用 Condition 对象可以在某些事件触发或者达到特定的条件后才处理数据,Condition 除了具有 Lock 对象的 acquire 方法和 release 方法外,还提供了 wait 和 notify 方法。线程首先 acquire 一个条件变量锁。如果条件不足,则该线程 wait,如果满足就执行线程,甚至可以 notify 其他线程。其他处于 wait 状态的线程接到通知后会重新判断条件。

其中条件变量可以看成不同的线程先后 acquire 获得锁,如果不满足条件,可以理解为被扔到一个( Lock 或 RLock )的 waiting 池。直达其他线程 notify 之后再重新判断条件。不断的重复这一过程,从而解决复杂的同步问题。

Condition

该模式常用于生产者消费者模式,具体看看下面在线购物买家和卖家的示例:

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
复制代码#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import threading, time


class Consumer(threading.Thread):
def __init__(self, cond, name):
# 初始化
super(Consumer, self).__init__()
self.cond = cond
self.name = name

def run(self):
# 确保先运行Seeker中的方法
time.sleep(1)
self.cond.acquire()
print(self.name + ': 我这两件商品一起买,可以便宜点吗')
self.cond.notify()
self.cond.wait()
print(self.name + ': 我已经提交订单了,你修改下价格')
self.cond.notify()
self.cond.wait()
print(self.name + ': 收到,我支付成功了')
self.cond.notify()
self.cond.release()
print(self.name + ': 等待收货')


class Producer(threading.Thread):
def __init__(self, cond, name):
super(Producer, self).__init__()
self.cond = cond
self.name = name

def run(self):
self.cond.acquire()
# 释放对琐的占用,同时线程挂起在这里,直到被 notify 并重新占有琐。
self.cond.wait()
print(self.name + ': 可以的,你提交订单吧')
self.cond.notify()
self.cond.wait()
print(self.name + ': 好了,已经修改了')
self.cond.notify()
self.cond.wait()
print(self.name + ': 嗯,收款成功,马上给你发货')
self.cond.release()
print(self.name + ': 发货商品')


cond = threading.Condition()
consumer = Consumer(cond, '买家(两点水)')
producer = Producer(cond, '卖家(三点水)')
consumer.start()
producer.start()

输出的结果如下:

1
2
3
4
5
6
7
8
复制代码买家(两点水): 我这两件商品一起买,可以便宜点吗  
卖家(三点水): 可以的,你提交订单吧
买家(两点水): 我已经提交订单了,你修改下价格
卖家(三点水): 好了,已经修改了
买家(两点水): 收到,我支付成功了
买家(两点水): 等待收货
卖家(三点水): 嗯,收款成功,马上给你发货
卖家(三点水): 发货商品

5、线程间通信

如果程序中有多个线程,这些线程避免不了需要相互通信的。那么我们怎样在这些线程之间安全地交换信息或数据呢?

从一个线程向另一个线程发送数据最安全的方式可能就是使用 queue 库中的队列了。创建一个被多个线程共享的 Queue 对象,这些线程通过使用 put() 和 get() 操作来向队列中添加或者删除元素。

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
复制代码# -*- coding: UTF-8 -*-
from queue import Queue
from threading import Thread

isRead = True


def write(q):
# 写数据进程
for value in ['两点水', '三点水', '四点水']:
print('写进 Queue 的值为:{0}'.format(value))
q.put(value)


def read(q):
# 读取数据进程
while isRead:
value = q.get(True)
print('从 Queue 读取的值为:{0}'.format(value))


if __name__ == '__main__':
q = Queue()
t1 = Thread(target=write, args=(q,))
t2 = Thread(target=read, args=(q,))
t1.start()
t2.start()

输出的结果如下:

1
2
3
4
5
6
复制代码写进 Queue 的值为:两点水  
写进 Queue 的值为:三点水
从 Queue 读取的值为:两点水
写进 Queue 的值为:四点水
从 Queue 读取的值为:三点水
从 Queue 读取的值为:四点水

Python 还提供了 Event 对象用于线程间通信,它是由线程设置的信号标志,如果信号标志位真,则其他线程等待直到信号接触。

Event 对象实现了简单的线程通信机制,它提供了设置信号,清楚信号,等待等用于实现线程间的通信。

  • 设置信号

使用 Event 的 set() 方法可以设置 Event 对象内部的信号标志为真。Event 对象提供了 isSe() 方法来判断其内部信号标志的状态。当使用 event 对象的 set() 方法后,isSet() 方法返回真

  • 清除信号

使用 Event 对象的 clear() 方法可以清除 Event 对象内部的信号标志,即将其设为假,当使用 Event 的 clear 方法后,isSet() 方法返回假

  • 等待

Event 对象 wait 的方法只有在内部信号为真的时候才会很快的执行并完成返回。当 Event 对象的内部信号标志位假时,则 wait 方法一直等待到其为真时才返回。

示例:

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
复制代码# -*- coding: UTF-8 -*-

import threading


class mThread(threading.Thread):
def __init__(self, threadname):
threading.Thread.__init__(self, name=threadname)

def run(self):
# 使用全局Event对象
global event
# 判断Event对象内部信号标志
if event.isSet():
event.clear()
event.wait()
print(self.getName())
else:
print(self.getName())
# 设置Event对象内部信号标志
event.set()

# 生成Event对象
event = threading.Event()
# 设置Event对象内部信号标志
event.set()
t1 = []
for i in range(10):
t = mThread(str(i))
# 生成线程列表
t1.append(t)

for i in t1:
# 运行线程
i.start()

输出的结果如下:

1
2
3
4
5
6
7
8
9
10
复制代码1  
0
3
2
5
4
7
6
9
8

6、后台线程

默认情况下,主线程退出之后,即使子线程没有 join。那么主线程结束后,子线程也依然会继续执行。如果希望主线程退出后,其子线程也退出而不再执行,则需要设置子线程为后台线程。Python 提供了 setDeamon 方法。

进程

Python 中的多线程其实并不是真正的多线程,如果想要充分地使用多核 CPU 的资源,在 Python 中大部分情况需要使用多进程。Python 提供了非常好用的多进程包 multiprocessing,只需要定义一个函数,Python 会完成其他所有事情。借助这个包,可以轻松完成从单进程到并发执行的转换。multiprocessing 支持子进程、通信和共享数据、执行不同形式的同步,提供了 Process、Queue、Pipe、Lock 等组件。

1、类 Process

创建进程的类:Process([group [, target [, name [, args [, kwargs]]]]])

  • target 表示调用对象
  • args 表示调用对象的位置参数元组
  • kwargs表示调用对象的字典
  • name为别名
  • group实质上不使用

下面看一个创建函数并将其作为多个进程的例子:

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
复制代码#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import multiprocessing
import time


def worker(interval, name):
print(name + '【start】')
time.sleep(interval)
print(name + '【end】')


if __name__ == "__main__":
p1 = multiprocessing.Process(target=worker, args=(2, '两点水1'))
p2 = multiprocessing.Process(target=worker, args=(3, '两点水2'))
p3 = multiprocessing.Process(target=worker, args=(4, '两点水3'))

p1.start()
p2.start()
p3.start()

print("The number of CPU is:" + str(multiprocessing.cpu_count()))
for p in multiprocessing.active_children():
print("child p.name:" + p.name + "\tp.id" + str(p.pid))
print("END!!!!!!!!!!!!!!!!!")

输出的结果:

多进程输出结果

2、把进程创建成类

当然我们也可以把进程创建成一个类,如下面的例子,当进程 p 调用 start() 时,自动调用 run() 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
复制代码# -*- coding: UTF-8 -*-

import multiprocessing
import time


class ClockProcess(multiprocessing.Process):
def __init__(self, interval):
multiprocessing.Process.__init__(self)
self.interval = interval

def run(self):
n = 5
while n > 0:
print("当前时间: {0}".format(time.ctime()))
time.sleep(self.interval)
n -= 1


if __name__ == '__main__':
p = ClockProcess(3)
p.start()

输出结果如下:

创建进程类

3、daemon 属性

想知道 daemon 属性有什么用,看下下面两个例子吧,一个加了 daemon 属性,一个没有加,对比输出的结果:

没有加 deamon 属性的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
复制代码# -*- coding: UTF-8 -*-
import multiprocessing
import time


def worker(interval):
print('工作开始时间:{0}'.format(time.ctime()))
time.sleep(interval)
print('工作结果时间:{0}'.format(time.ctime()))


if __name__ == '__main__':
p = multiprocessing.Process(target=worker, args=(3,))
p.start()
print('【EMD】')

输出结果:

1
2
3
复制代码【EMD】  
工作开始时间:Mon Oct  9 17:47:06 2017
工作结果时间:Mon Oct  9 17:47:09 2017

在上面示例中,进程 p 添加 daemon 属性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
复制代码# -*- coding: UTF-8 -*-

import multiprocessing
import time


def worker(interval):
print('工作开始时间:{0}'.format(time.ctime()))
time.sleep(interval)
print('工作结果时间:{0}'.format(time.ctime()))


if __name__ == '__main__':
p = multiprocessing.Process(target=worker, args=(3,))
p.daemon = True
p.start()
print('【EMD】')

输出结果:

1
复制代码【EMD】

根据输出结果可见,如果在子进程中添加了 daemon 属性,那么当主进程结束的时候,子进程也会跟着结束。所以没有打印子进程的信息。

4、join 方法

结合上面的例子继续,如果我们想要让子线程执行完该怎么做呢?

那么我们可以用到 join 方法,join 方法的主要作用是:阻塞当前进程,直到调用 join 方法的那个进程执行完,再继续执行当前进程。

因此看下加了 join 方法的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
复制代码import multiprocessing
import time


def worker(interval):
print('工作开始时间:{0}'.format(time.ctime()))
time.sleep(interval)
print('工作结果时间:{0}'.format(time.ctime()))


if __name__ == '__main__':
p = multiprocessing.Process(target=worker, args=(3,))
p.daemon = True
p.start()
p.join()
print('【EMD】')

输出的结果:

1
2
3
复制代码工作开始时间:Tue Oct 10 11:30:08 2017  
工作结果时间:Tue Oct 10 11:30:11 2017
【EMD】

5、Pool

如果需要很多的子进程,难道我们需要一个一个的去创建吗?

当然不用,我们可以使用进程池的方法批量创建子进程。

例子如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
复制代码# -*- coding: UTF-8 -*-

from multiprocessing import Pool
import os, time, random


def long_time_task(name):
print('进程的名称:{0} ;进程的PID: {1} '.format(name, os.getpid()))
start = time.time()
time.sleep(random.random() * 3)
end = time.time()
print('进程 {0} 运行了 {1} 秒'.format(name, (end - start)))


if __name__ == '__main__':
print('主进程的 PID:{0}'.format(os.getpid()))
p = Pool(4)
for i in range(6):
p.apply_async(long_time_task, args=(i,))
p.close()
# 等待所有子进程结束后在关闭主进程
p.join()
print('【End】')

输出的结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码主进程的 PID:7256  
进程的名称:0 ;进程的PID: 1492 
进程的名称:1 ;进程的PID: 12232 
进程的名称:2 ;进程的PID: 4332 
进程的名称:3 ;进程的PID: 11604 
进程 2 运行了 0.6500370502471924 秒
进程的名称:4 ;进程的PID: 4332 
进程 1 运行了 1.0830621719360352 秒
进程的名称:5 ;进程的PID: 12232 
进程 5 运行了 0.029001712799072266 秒
进程 4 运行了 0.9720554351806641 秒
进程 0 运行了 2.3181326389312744 秒
进程 3 运行了 2.5331451892852783 秒
【End】

这里有一点需要注意: Pool 对象调用 join() 方法会等待所有子进程执行完毕,调用 join() 之前必须先调用 close() ,调用close() 之后就不能继续添加新的 Process 了。

请注意输出的结果,子进程 0,1,2,3是立刻执行的,而子进程 4 要等待前面某个子进程完成后才执行,这是因为 Pool 的默认大小在我的电脑上是 4,因此,最多同时执行 4 个进程。这是 Pool 有意设计的限制,并不是操作系统的限制。如果改成:

1
复制代码p = Pool(5)

就可以同时跑 5 个进程。

6、进程间通信

Process 之间肯定是需要通信的,操作系统提供了很多机制来实现进程间的通信。Python 的 multiprocessing 模块包装了底层的机制,提供了Queue、Pipes 等多种方式来交换数据。

以 Queue 为例,在父进程中创建两个子进程,一个往 Queue 里写数据,一个从 Queue 里读数据:

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
复制代码#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

from multiprocessing import Process, Queue
import os, time, random


def write(q):
# 写数据进程
print('写进程的PID:{0}'.format(os.getpid()))
for value in ['两点水', '三点水', '四点水']:
print('写进 Queue 的值为:{0}'.format(value))
q.put(value)
time.sleep(random.random())


def read(q):
# 读取数据进程
print('读进程的PID:{0}'.format(os.getpid()))
while True:
value = q.get(True)
print('从 Queue 读取的值为:{0}'.format(value))


if __name__ == '__main__':
# 父进程创建 Queue,并传给各个子进程
q = Queue()
pw = Process(target=write, args=(q,))
pr = Process(target=read, args=(q,))
# 启动子进程 pw
pw.start()
# 启动子进程pr
pr.start()
# 等待pw结束:
pw.join()
# pr 进程里是死循环,无法等待其结束,只能强行终止
pr.terminate()

输出的结果为:

1
2
3
4
5
6
7
8
复制代码读进程的PID:13208  
写进程的PID:10864
写进 Queue 的值为:两点水
从 Queue 读取的值为:两点水
写进 Queue 的值为:三点水
从 Queue 读取的值为:三点水
写进 Queue 的值为:四点水
从 Queue 读取的值为:四点水

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

毛剑:Bilibili 的 Go 服务实践(上篇)

发表于 2017-10-09

前言

在微服务流行的当下,bilibili(B站)也在业务快速增长的压力下,对历史系统进行了不断的优化,在所谓“大系统小做”的背后付出了挺多的努力,尤其是 Go 作为开发语言的整体运维的支撑相对比较薄弱,例如开发、部署、测试、集成、监控,调试等。在 GopherChina 2017大会上,B 站技术总监毛剑分享了微服务化道路上踩的“坑”以及最终演进后对整个微服务框架的思考。

本次演讲的内容会包含以下几块:1.B站微服务的演进过程;2.高可用;3.中间件;4.持续集成和交付;5.运维体系。

作者介绍

2015年起,在 bilibili(B站)负责 UGC平台和基础架构,开发了直播弹幕开源推送服务 goim ,B站分布式存储 BFS ,引导开发了B站 cache proxy,bili twemproxy 等,对历史主站架构进行迭代和重构,之前六年在猎豹移动工作,当过MySQL DBA,做过C开发,其中开发了gopush-cluster用于猎豹移动的推送体系。喜欢应用服务性能诊断,内核研究,稳定的服务端架构演变。

微服务的演进

原始框架

在刚进入 B站时,面临着技术架构上的一些挑战:首先是部署非常不方便,我们要在没有任何东西依赖的情况下把整套主站搭起来;然后代码方面有两个仓库,要部署的时候全部打包一块往上面扔,结果经常起不来;另外测试的成本也非常高。这样导致的后果是整个开发效率也比较低,因为职责不清晰,整个代码是一坨,不知道哪一个模块是谁负责,甚至有一些是公共的部分是很多人在负责。如图1所示。

图1

升级理念

首先要梳理业务的边界。因为整个B站的业务非常繁杂,我们先从全貌去看到底应该怎么拆分。所以我做了一个图,如图2所示。

图2

最顶层从我的视角看,一个是用户纬度,还有一个帐号,你从中间的服务看,它有会员、投稿、用户财产信息,还有关系链、动态推荐等。从底层的一些辅助服务看,有验证码、IP的查找、推送、配置中心,包括protobuffer的一些服务管理。

为什么要强调这个事情呢?就是起步做微服务的时候,一定要搞清楚整个业务的责权或者叫边界。我们一开始的打法就是农村包围城市,跟所有核心有关的业务逐步拆了。比如用户的播放历史、收藏夹、评论等,这些是跟我们主线没有直接关系的周边业务。先把这些做了。在升级的过程中一定要考虑一个兼容,不能做了一个api跟所有的不兼容。直到现在,我们涉及到最底层的帐号重构的时候,都是非常痛苦的,因为牵扯的部门非常多。

第二个就是资源隔离。怎么隔离呢?就是先买服务器,尽量不要跟不可靠的程序员写代码放在一块,先隔离出来。因为旧代码肯定有很多黑科技的,你先买一个新机器放在那里,你新重构的往这里面塞,老的就不要折腾了。而且在没有文档、什么都没有的时候,旧代码是很难复用的,最好买一个干净的新机器重新部署。

第三个是内外网服务隔离。之前B站在15年的时候也遇到一些安全事故,我们的APP KEY从客户端逆向被泄露,有人去请求了内网的一些接口。这是一个安全事故,也是一个安全风险。为什么出现这个问题呢?因为我们之前没有做内网的隔离,导致内网API就暴露在公网。因为我们当时就决定要把整个服务的职责梳理清楚。

如图3所示,我们从最顶层开始看,首先是SLB入口,进来以后回到 Gateway。举个例子,像我们的移动端对外的一些API,因为有些业务要在一个页面有很多聚合,所以我们封装成一个API。还有就是用户评论,是平台属性的可以直接对外提供API。但是有一些服务是不能对外的,比如像我们内部的服务和面向运营平台的运营审核操作。例如我们的运营平台要给某个帐号进行操作,这个时候一定不能对外的,不然如果有人发现这个接口,无论你用什么手段,他一定有办法来搞你。所以一定要做内外网的隔离,这几个角色定义完以后,Service这一层,其实我们看到微服务的最核心的一块,就是直接面对面的,就是业务的一个模块单元。

图3

接下来讲一个RPC框架。那RPC需要哪些特性呢?首先需要序列化,第一就是使用GOB,我第一个想法就是语言统一,尽可能多的是用Go来写。因为当你出现一个业务短版或者瓶颈的时候,发现这个人不会写Go,会很困难。Go统一之后,我们想用GOB是最方便,因为它什么内置类型都支持。第二个就是超时控制。因为一堵就挂了。假设你有一个提供者,他后面堵了,你越积越多,就挂了。所以要有一个超时控制,包括一些上下文的东西传递。像刚才说的APM的问题就可以通过上下文来控制。第三是要做一些拦截器,所以内网也要做一定的健全机制,包括权限控制、统计、限流等。第四是服务注册,我们当时对比了很多,最终选择的是 zookeeper,这块也在逐步改进去ZK,做一个AP系统。最后是负载均衡,这个地方也考虑了很久,像早期我其实使用像 LVS ,或者 DNS 来做这种调度的,但是这样从性能来说它并不是最好,因为假设你要用LVS,你要经过你的网络多传输几次,其实直点效果是最好的。但是因为当时成本的问题,所以我们用客户端负载直接实现的。

代码级实现

刚才说到用GOB,用GOB以后我们最合适的RPC是用标准库的net rpc,并对它做了一些改造。

首先是支持context,再一个是做了一个超时控制,这是两个测试的demo。如图4-1。

图4-1

有人问我这个东西改造是不是很困难,其实我们看了 net rpc的源码,整个实现非常简单,所以我们只要改极少的代码,风险比较小。

首先加了一个 context 对象,第一个参数必须具体实现一个 context 接口,就做了一步这样的改造就搞定了。我们所有的rpc方法首参数都是 context 。如图4-2所示。

图4-2

图 4-3 一开始也是一个 context 的注入,我们在里面放了比较多的东西,像方法、名字等等。我们对外的 context 其实内部有一个 rpc 的小的 context,放了我们可能会用到的一些东西。拦截器其实也比较简单,首先我定义一个抽象,有限流、有统计、有健全,然后我们在 rpc 库里面 server 端加入几行简单代码。

图4-3

然后我们还做了一些改进。首先如果大家压测过 net rpc,就会发现 get request 和 free request 是有全局锁征用的,所以我们把它改成一个 request scope 级别的一个优化。如图4-4右边,我们在 codec 里面把 response 和 request 放进去了。而且我们为了减少对象,不是用的指针,而是直接用的 struct 包含来做的,这样压力也会小一些。

图4-4

然后看一下握手。如图4-5所示。

图4-5

调度是怎么做的呢?也就是负载均衡。其实也比较简单,我们定义了一个接口,然后可能会实现这几个方法,比如广播、call、设置超时,并且设置某一个方法的超时。第四个其实是全局默认的一个超时,做了这个以后,我们配置的文件上面有地址、协议、分组和权重。我们第一版做的是 wrr 的策略,就是我有一堆client,你告诉我权重是什么,我按权重轮询调度,因为我所有的节点信息都在 zookeeper 上面,只要定期去根据事件拿取它的所有的节点变更,做一个客户端的配合,我觉得这个代码写起来也是比较简单的。

Group其实是后面一版加入的,等下我讲高可用的时候会重点来介绍。

图4-6

刚才我们是服务层搞定了,现在看一下网关层。网关要做聚合,回到刚才的场景,移动端的某个页面调了4、5个业务方,这不可能让移动端的同学直接对接。我们会从 Gateway 层统一做一个 API 给它,这样成本会非常低。协议的统一也在 gateway 层做的。

第二步我们做了并行优化,因为我们依赖的业务方非常多,有4-6个,所以要用 errgroup 做一个并行调用。Gateway 的话有两种做法,我们早期所有出口只有一个Gateway,后来发现不行,一个不小心的 bug 可能导致这个进程崩溃,然后它不断崩溃,其实非常危险。所以我们根据一些业务形态重要或非重要等做了一些隔离。它可能叫 APP Gateway,会员 Gateway,我们还是做了一些隔离的。最后的话就是我们在 Gateway上做的一些熔断、降级、限流、高可用等等。接下来就重点讲一下高可用的做法。

高可用

第一个是做隔离。我们看图5,首先是按业务的压力情况,有一些服务压力特别大,有一些服务压力特别小,它是不是可以隔离出来,这样不要因为压力大的服务影响应该小的,然后稳定性高的影响稳定性。

图5

早期没有服务器时,其实都是统一布在一台机器上,有可能AB两个服务,A出问题了,B跟着遭殃。其实经历过一段时间没有容器,就是用物理机的阶段是非常糟糕的,真的要用手动 cgroup ,然后限定每一个资源。那么物理隔离就是买机器。轻重隔离的话,像我们有一些队列可能东西非常多,有一些队列可能东西非常少,如果你都放在一个里面 Topic
,还是有影响的。举个例子,像我们视频转码的时候,它会有分超长和超短的文件。如果超短和超长的放在一种队列里面,它其实就是一种轻重隔离。像我们的集群,甚至有不同的部署,也是腾讯经常提的按集群部署。

第二个要提的就是超时。因为RPCE里面,最重要的就是超时,超时有很多种,如连接超时、读取超时、写入超时等,如图6所示。我当时用 Go 1.3 开始用 Go 写代码,当时发现很多地方是没有的,导致我们有一次出现了一个故障,就是某一个机房的业务连了一台 DB ,当时那个线断了,导致进程全部堵住了。具体是怎么排查的呢,因为我们发现CPU不高,然后数据库报了一下错,之后请求也进不来,后来还是用 GDB 去调,看它正在运行的 gorutnine 的对帐到底卡在哪里,当时还有一些其他的方法。后续的引进,我希望对我们采集到的数据,不断的对我们的服务去调整这个超时。

图6

第三个就是限流。限流也非常多,如图7所示。举一个例子,我们在去年应该说有一个业务夯住了,具体什么问题呢,挂的是上层 Nginx 的 upstream ,因为它没有设置 upstream 的一个 timeout,导致我们的交换机对着三四百个连接,然后交换机挂掉了。发现之前说好的交换机有在备,结果也全部挂掉了。所以我们后来总结了一下,还是要有限流保护的,限流就是避免一波CC攻击就直接把你打挂了。所以我们在这上面做了分布式的限流,类似的方案都有。我们的连接限流,这些都是重要的资源,一定要注意。像 Go 的话,有一个指标里面就有一个限流连接数的,这些都可以使用,避免一下子拖了太多的连接进来把你打死。像请求限流,当发现情况的时候立马调整它的流量,把你打的 CC 的那个流量给去掉。

图7

然后提一下降级。也是非常多,如图8所示。我们早期的话,第一步做UI降级,我们每次发生故障时,发现如果你的移动端打不开,用户会疯狂的刷,可能刷一会就打开了,其实这时候请求数会越来越多。后来我们在客户端做降级,比如你连续刷的话,我会下达一个 TTL ,这些可以在客户端做一些调整,如果实在扛不住的时候可以发一个10秒钟,甚至30秒钟的超长的 TTL 告诉客户端这时候不要请求。我记得支付宝不是收到一个好像太忙了不让你支付还是什么,其实就是有客户端的一个限流,这个是终极手段。

还有功能降级。也比较简单,比如我们某个页面上面有一些大数据,或者人工智能的推荐的数据,这个模块可能会导致某一个实验导致数据的崩溃了,所以这时候就有一些空窗,或者整个页面都打不开,这个体验就不好。那这时候就有很多的方法,比如可以把另一块 UR 返回一个灾备的推荐池,至少避免整个页面打不开。所以你的接口吐出去的时候,如果有一个依赖的业务方挂掉,你一定要考虑你有没有一些手段可以降级,或者是返回一些默认的、甚至返回静态的数据。

我记得京东有一篇分享就讲过,他们如果出现非常严重的故障,商品的详细页是可以返回一个静态的。因为我们商品的很多东西是不可能实时变更它的内容的,我觉得这也是一种方式吧。那还有一些自动的降级,我们其实做的比较多的是像统计失败的降级。比如我请求某一个接口,它如果错误率比较高,或者超时比较多,我是不是可以不调它了。虽然你依赖了很多业务方,你可以降级,但是如果它超时,其实你最终的延时也会增加,所以这时候要把它踢掉。

还有一些情况,比如我们核心业务,或者是一些关键的业务不能做自动降级的时候,这时候你拿捏不准,你一定要做一些功能开关,在适当的时候可以把它打开,不再返回那个数据,或者不请求它。

图8

最后就是容错。如图9所示。容错我们做的比较多的就是熔断,其实也有参考一个 Java 框架,把它改成了 Go 的版本,然后做了一个熔断。其实它的核心思路非常简单,就是当我的请求数量达到多少以后,我的错误率到达多少以后,我是不是可以不调它,不调就可以快速返回,叫 fail-fast。fail-fast 这个阶段一过,我是不是要放一些流量进去试探它有没有恢复。这时候比如100毫秒放一个流量进去,如果成功了,我认为服务器稳定了,再把开关打开,把整个流量放进去,再看如果还不行,会重复这样的过程。

图9

还有一些重要业务,像我们依赖队列的一些业务,它可能会做努力送达模型。这种情况下,我们可能会无限重试,直到它成功,否则就是一直等待。一秒钟加一个随机数,不断的去重试。

由于内容篇幅较长,本文分为上下两篇,在明日发布的下篇中会介绍 B 站在中间件、持续集成和交付,以及运维体系中的实践,敬请期待~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

SSH 详解 - 不挑食的程序员 - SegmentFaul

发表于 2017-09-29

文章同步于Github blog

简介

SSH(Secure Shell)是一个提供数据通信安全、远程登录、远程指令执行等功能的安全网络协议,由芬兰赫尔辛基大学研究员Tatu Ylönen,于1995年提出,其目的是用于替代非安全的Telnet、rsh、rexec等远程Shell协议。之后SSH发展了两个大版本SSH-1和SSH-2。

通过使用SSH,你可以把所有传输的数据进行加密,这样”中间人”这种攻击方式就不可能实现了,而且也能够防止 DNS欺骗 和 IP欺骗。使用SSH,还有一个额外的好处就是传输的数据是经过压缩的,所以可以加快传输的速度。SSH有很多功能,它既可以代替Telnet,又可以为FTP、Pop、甚至为PPP提供一个安全的”通道”。

SSH为一项创建在应用层和传输层基础上的安全协议,为计算机上的 Shell 提供安全的传输和使用环境。

SSH的基本框架

SSH协议框架中最主要的部分是三个协议:

  • 传输层协议(The Transport Layer Protocol):传输层协议提供服务器认证,数据机密性,信息完整性等的支持。
  • 用户认证协议(The User Authentication Protocol):用户认证协议为服务器提供客户端的身份鉴别。
  • 连接协议(The Connection Protocol):连接协议将加密的信息隧道复用成若干个逻辑通道,提供给更高层的应用协议使用。

同时SSH协议框架中还为许多高层的网络安全应用协议提供扩展的支持。它们之间的层次关系可以用如下图来表示:

SSH的加密

SSH从安全和性能两方面综合考虑,结合使用了 Public Key/Private key(公钥/私钥) 和 Secret Key(密钥)。

  • Public Key/Private key:非对称加密,安全,但效率低,不适合大规模进行数据的加密和解密操作
  • Secret Key:对称机密,高效,但安全性相对较低,Key的分发尤其不方便

对密码学基础知识和数字签名了解,可以参考阮一峰的博文

  • 密码学笔记
  • 数字签名是什么

SSH的主要特性

  • 加密:避免数据内容泄漏
  • 通信的完整性:避免数据被篡改,以及发送或接受地址伪装
    (检查数据是否被篡改,数据是否来自发送者而非攻击者) SSH-2 通过 MD5 和 SHA-1 实现该功能,SSH-1 使用 CRC-32
  • 认证:识别数据发送者和接收者身份 客户端验证SSH服务端的身份:防止攻击者仿冒SSH服务端身份,避免中介人攻击和重定向请求的攻击;OpenSSH 通过在 know-hosts 中存储主机名和 host key 对服务端身份进行认证 服务端验证请求者身份:提供安全性较弱的用户密码方式,和安全性更强的 per-user public-key signatures;此外SSH还支持与第三方安全服务系统的集成,如
    Kerberos等
  • 授权:用户访问控制
  • Forwarding or tunneling to encrypt other TCP/IP-based sessions 可以通过SSH为Telnet、FTP等提供通信安全保障,支持三种类型的 Forwarding 操作:Port Forwarding;X Forwarding;Agent Forwarding

SSH中的Key

SSH结合使用了Public Key/Private key和Secret Key:

  • Public Key/Private key(非对称加密)用于在建立安全通道前在客户端和服务端之间传输 Secret Key和进行身份认证;
  • Secret Key(对称加密)则用来作为SSH会话的安全保证,对数据进行加密和解密。

SSH可以处理4种密钥:

名称 生命周期 创建 类型 描述
Host Key 持久化 服务端 Public Key Host Key是服务器用来证明自己身份的一个永久性的非对称密钥
User Key 持久化 用户 Public Key User Key 是客户端用来证明用户身份的一个永久性的非对称密钥(一个用户可以有多个密钥/身份标识)
Server Key 默认为1小时 服务端 Public Key Server Key 是SSH-1协议中使用的一个临时的非对称密钥,每隔一定的间隔(默认是一个小时)都会在服务器重新生成。用于对Session Key进行加密(仅SSH-1协议有,SSH-2对其进行了增强,这里Server Key作为一个概念便于在流程中进行描述)
Session Key 客户端 会话(Session) Secret Key Session Key是一个随机生成的对称密钥,用户SSH客户端和服务器之间的通信进行加密,会话结束时,被销毁

SSH框架:

安全连接的建立

在进行有意义的会话之前,SSH客户端和服务器必须首先建立一条安全连接。该连接可以允许双方共享密钥、密码,最后可以相互传输任何数据。

现在我们介绍SSH-1协议是如何确保网络连接的安全性的。SSH-1客户端和服务器从阿卡似乎经过很多个步骤,协商使用加密算法,生成并共享一个会话密钥,最终建立一条安全连接:

  1. 客户端连接到服务器上
  2. 客户端和服务器交换自己支持的SSH协议版本号
  3. 客户端和服务器切换到基于报文的协议
  4. 服务器向客户端提供自己的身份证明和会话参数
  5. 客户端给服务器发送一个(会话)密钥
  6. 双方启用加密并完成服务器认证
  7. 建立安全连接

每个阶段均涉及到客户端与服务端的多次交互,通过这些交互过程完成包括证书传输、算法协商、通道加密等过程。

1 客户端连接到服务器上

这个步骤没什么好说的,就是向服务器的TCP端口(约定是22)发送连接请求。

2 客户端和服务器交换自己支持的协议版本号

这些协议是以 ASCII 字符串表示,例如:SSH-1.5-1.2.27,其意义为SSH协议,版本号是V1.5,SSH1实现版本为1.2.27。可以使用 Telnet 客户端连接到一个SSH服务器端口是看到这个字符串:

1
2
3
4
5
复制代码➜ telnet 192.168.1.200 22
Trying 192.168.1.200...
Connected to doc.dinghuo123.com.
Escape character is '^]'.
SSH-2.0-OpenSSH_6.0p1 Debian-4+deb7u6

如果客户端和服务器确定其协议版本号是兼容的,那么连按就继续进行,否则,双方都可能决定中断连接。例如,如果一个只使用 SSH-1 的客户端连接到一个只使用 SSH-2 的服务器上,那么客户端就会断开连接并打印一条错误消息。实际上还可能执行其他操作:例如,只使用SSH-2的服务器可以调用SSH-1服务器来处理这次连接请求。

3 客户端和服务器切换基于报文的协议

协议版本号交换过程一旦完成,客户端和服务器都立即从下层的 TCP 连接切换到基于子报文的协议。每个报文都包含一个32位的字段,1 - 8字节的填充位[ 用来防止已知明文攻击unknown-plaintext attack ],一个1字节的报文类型代码, 报文有效数据和一个4字节的完整性检査字段。

4 服务器向客户提洪自己的身份证明和会话参数

服务器向客户端发送以下信息(现在还沒有加密):

  • 主机密钥(Host Key),用于后面证明服务器主机的身份
  • 服务器密钥(Server Key),用来帮助建立安全连接
  • 8个随机字节序列,称为检测字节(check bytes)。客户端在下一次响应中必须包括这些检测字节,否則服务器就会拒绝接收响应信息,这种方法可以防止某些 IP伪装攻击(IP spoofing attack)。
  • 该服务器支持的加密、压缩和认证方法

此时,双方都要计算一个通用的 128 位会话标识符(Session ID)。它在某些协议中用来惟一标识这个 SSH 会话。该值是 主机密钥(Host Key)、服务器密钥(Server Key)和检测字节(check bytes)一起应用 MD5散列函数 得到的结果。

当客户端接收到 主机密钥(Host Key)时,它要进行询问:“之前我和这个服务器通信过吗?如果通信过,那么它的主机密钥是什么呢?”要回答这个问题,客户端就要査阅自己的已知名主机数据库。如果新近到达的主机密钥可以和数据库中以前的一个密钥匹,那么就没有问题了。

但是,此时还存在两种可能:已知名主机数据库中没有这个服务器,也可能有这个服务器但是其主机密钥不同。在这两种情况中,客户端要选择是信任这个新近到达的密钥还是拒绝接受该密钥。此时就需要人的指导参与了,例如,客户端用户可能被提示要求确定是接受还是拒绝该密钥。

1
2
3
复制代码The authenticity of host 'ssh-server.example.com (12.18.429.21)' can't be established.
RSA key fingerprint is 98:2e:d7:e0:de:9f:ac:67:28:c2:42:2d:37:16:58:4d.
Are you sure you want to continue connecting (yes/no)?

如果客户端拒绝接受这个主机密钥,那么连接就中止了。让我们假设客户端接受该密钥,现在继续介绍。

5 客户端给眼务器发送一个(会话)密钥

现在客户端为双方都支持的 bulk箅法 随机生成一个新密钥,称为 会话密钥(Session Key)。其目的是对客户端和服务器之间发送的数据进行加密和解密。所需要做的工作是把这个 会话密钥(Session Key)发送给服务器,双方就可以启用加密并开始安全通信了。

当然,客户端不能简单地把会话密钥(Session Key)发送给服务器。此时数据还没有进行加密,如果第三方中途截获了这个密钥,那么他就可以解密客户端和服务器之间的消息。此后你就和安全性无缘了。因此客户端必须安全地发送会话密钥(Session Key)。 这是通过两次加密实现的:一次使用服务器的公共主机密钥(Host Key),一次使用服务器密钥(Server Key)。

这个步骤确保只有服务器可以读取会话密钥(Session Key)。在会话密钥(Session Key)经过两次加密之后,客户端就将其发送给服务器,同时还会发送检测字节和所选定的算法(这些算法是从第4步中服务器支持的算法列表中挑选出来的)。

6 双方启用加密并完成服务器认证

在发送会话密钥之后,双方开始使用密钥和所选定的 bulk算法 对会话数据进行加密,但是在开始继续发送其他数据之前,客户端要等待服务器发来一个确认消息,该消息(以及之后的所有数据)都必须使用这个会话密钥(Session Key)加密。这是最后一歩,它提供了服务器认证:只有目的服务器才可以解密 会话密钥(Session Key),因为它是使用前面的 主机密钥(Host Key)(这个密钥已经对已知名主机列表进行了验证)进行加密的。

如果没有会话密钥(Session Key),假冒的服务器就不能解密以后的协议通信,也就不能生成有效的通信,客户端会注意到这一点并中断连接。

注意服务器认址是隐含的;并没有显式交换来验证服务器主机密钥(Host Key)。因此客户端在继续发送数椐之前,必须等待服务器使用新会话密钥(Session Key)作出有意义的响应。 从而在处理之前验证服务的身份,虽然 SSH-1 协议在这点上并没有什么特殊 . 但是 SSH-2 需要服务器认证时显示地地交换会话密钥(Session Key)。

使用服务器密钥(Server Key)对会话密钥(Session Key)再进行一次加密就提供了一种称为完美转发安全性的特性。这就是说不存在永久性密钥泄露的可能,因为它不会危害到其他部分和以后SSH会话的安全性。如果我们只使用服务器主机密钥(Host Key)来保护会话密钥(Session Key), 那么主机密钥(Host Key)的泄露就会危害到以后的通倍,并允许解密原来记录下来的会话。使用服务器密钥(Server Key)再加密次就消除了这种缺点,因为服务器密钥(Server Key)是临时的,它不会保存到磁盘上,而且会周期性地更新(缺省情况下,一小时更新一次)。如果一个入侵者已经获取了服务器的私钥,那么他必须还要执行中间人攻击或服务器欺骗攻击才能对会话造成损害。

7 建立安全连接

由于客户端和服务器现在都知道会话密钥(Session Key),而其他人都不知道,因此他们就可以相互发送加密消息(使用他们一致同意的 bulk算法 )并对其进行解密了。而且,客户端还可以完成服务器认证。我们现在就已经准备好开始客户端认证了。

客户端认证

SSH提供多种客户端认证方式。

SSH-1:

  • Password
  • Public Key
  • Kerberos
  • Rhosts && RhostsRSA
  • TIS

SSH-2:

  • Password
  • Public Key
  • hostbased 在SSH-2中考虑 Rhosts 存在安全漏洞,废弃了这种方式。

这里之讨论我们经常使用的的 Password 和 Public Key 方式。

此时安全通道已经及建立,之后的所有内容都通过 Session Key 加密后进行传输。

Password

Password 方式既客户端提供用户和密码,服务端对用户和密码进行匹配,完成认证。类Unix系统中,如 OpenSSH 的框架,一般通过系统的本地接口完成认证。

Password 的优势是简单,无需任何而外的配置就可以使用。缺点密码不便于记忆,过于简单的密码容易被暴力破解。

Public Key

Public Key 认证的基本原理是基于非对称加密方式,分别在服务端对一段数据通过公钥进行加密,如果客户端能够证明其可以使用私钥对这段数据进行解密,则可以说明客户端的身份。因为服务端需要使用客户端生成的密钥对的公钥对数据首先加密,所以需要先将公钥存储到服务端的密钥库(Auhtorized Key)。还记得Github中使用git协议push代码前需要先添加SSH KEY吗?

下面详细介绍一个通过 Public Key 进行客户端认证的过程。

  1. 客户端发起一个 Public Key 的认证请求,并发送 RSA Key 的模数作为标识符。(如果想深入了解RSA Key详细 –> 维基百科)
  2. 服务端检查是否存在请求帐号的公钥(Linux中存储在 ~/.ssh/authorized_keys 文件中),以及其拥有的访问权限。如果没有则断开连接
  3. 服务端使用对应的公钥对一个随机的256位的字符串进行加密,并发送给客户端
  4. 客户端使用私钥对字符串进行解密,并将其结合 Session ID 生成一个MD5值发送给服务端。 结合 Session ID 的目的是为了避免攻击者采用 重放攻击(replay attack)。
  5. 服务端采用同样的方式生成 MD5值 与客户端返回的 MD5值 进行比较,完成对客户端的认证。

图解SSH

参考

  • SSH原理简介
  • SSH协议介绍
  • O‘RELLY的《SSH: The Secure Shell - The Definitive Guide》

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

写出优质Java代码的4个技巧 1 只做有目的性的优化 2

发表于 2017-09-29

原文:4 More Techniques for Writing Better Java
作者:Justin Albano
翻译:Vincent

译者注:如果现在要求对你写的Java代码进行优化,那你会怎么做呢?作者在本文介绍了可以提高系统性能以及代码可读性的四种方法,如果你对此感兴趣,就让我们一起来看看吧。以下为译文。

我们平时的编程任务不外乎就是将相同的技术套件应用到不同的项目中去,对于大多数情况来说,这些技术都是可以满足目标的。然而,有的项目可能需要用到一些特别的技术,因此工程师们得深入研究,去寻找那些最简单但最有效的方法。在前一篇文章中,我们讨论了必要时可以使用的四种特殊技术,这些特殊技术可以创建更好的Java软件;而本文我们将介绍一些有助于解决常见问题的通用设计策略和目标实现技术,即:

  1. 只做有目的性的优化
  2. 常量尽量使用枚举
  3. 重新定义类里面的equals()方法
  4. 尽量多使用多态性

值得注意的是,本文中描述的技术并不是适用于所有情况。另外这些技术应该什么时候使用以及在什么地方使用,都是需要使用者经过深思熟虑的。

1 .只做有目的性的优化

大型软件系统肯定非常关注性能问题。虽然我们希望能够写出最高效的代码,但很多时候,如果想对代码进行优化,我们却无从下手。例如,下面的这段代码会影响到性能吗?

1
2
3
4
5
6
7
8
复制代码public void processIntegers(List<Integer> integers) {

for (Integer value: integers) {
for (int i = integers.size() - 1; i >= 0; i--) {
value += integers.get(i);
}
}
}

这就得视情况而定了。上面这段代码可以看出它的处理算法是O(n³)(使用大O符号),其中n是list集合的大小。如果n只有5,那么就不会有问题,只会执行25次迭代。但如果n是10万,那可能会影响性能了。请注意,即使这样我们也不能判定肯定会有问题。尽管此方法需要执行10亿次逻辑迭代,但会不会对性能产生影响仍然有待讨论。

例如,假设客户端是在它自己的线程中执行这段代码,并且异步等待计算完成,那么它的执行时间有可能是可以接受的。同样,如果系统部署在了生产环境上,但是没有客户端进行调用,那我们根本没必要去对这段代码进行优化,因为压根就不会消耗系统的整体性能。事实上,优化性能以后系统会变得更加复杂,悲剧的是系统的性能却没有因此而提高。

最重要的是天下没有免费的午餐,因此为了降低代价,我们通常会通过类似于缓存、循环展开或预计算值这类技术去实现优化,这样反而增加了系统的复杂性,也降低了代码的可读性。如果这种优化可以提高系统的性能,那么即使变得复杂,那也是值得的,但是做决定之前,必须首先知道这两条信息:

  1. 性能要求是什么
  2. 性能瓶颈在哪里

首先我们需要清楚地知道性能要求是什么。如果最终是在要求以内,并且最终用户也没有提出什么异议,那么就没有必要进行性能优化。但是,当添加了新功能或者系统的数据量达到一定规模以后就必须进行优化了,否则可能会出现问题。

在这种情况下,不应该靠直觉,也不应该依靠检查。因为即使是像Martin Fowler这样有经验的开发人员也容易做一些错误的优化,正如在重构(第70页)一文中解释的那样:

如果分析了足够多的程序以后,你会发现关于性能的有趣之处在于,大部分时间都浪费在了系统中的一小部分代码中里面。如果对所有代码进行了同样的优化,那么最终结果就是浪费了90%的优化,因为优化过以后的代码运行得频率并不多。因为没有目标而做的优化所耗费的时间,都是在浪费时间。

作为一名身经百战的开发人员,我们应该认真对待这一观点。第一次猜测不仅没有提高系统的性能,而且90%的开发时间完全是浪费了。相反,我们应该在生产环境(或者预生产环境中)执行常见用例,并找出在执行过程中是哪部分在消耗系统资源,然后对系统进行配置。例如消耗大部分资源的代码只占了10%,那么优化其余90%的代码就是浪费时间。

根据分析结果,要想使用这些知识,我们应该从最常见的情况入手。因为这将确保实际付出的努力最终是可以提高系统的性能。每次优化后,都应该重复分析步骤。因为这不仅可以确保系统的性能真的得到了改善,也可以看出再对系统进行优化后,性能瓶颈是在哪个部分(因为解决完一个瓶颈以后,其它瓶颈可能消耗系统更多的整体资源)。需要注意的是,在现有瓶颈中花费的时间百分比很可能会增加,因为剩下的瓶颈是暂时不变的,而且随着目标瓶颈的消除,整个执行时间应该会减少。

尽管在Java系统中想要对概要文件进行全面检查需要很大的容量,但是还是有一些很常见的工具可以帮助发现系统的性能热点,这些工具包括JMeter、AppDynamics和YourKit。另外,还可以参见DZone的
性能监测指南,获取更多关于Java程序性能优化的信息。

虽然性能是许多大型软件系统一个非常重要的组成部分,也成为产品交付管道中自动化测试套件的一部分,但是还是不能够盲目的且没有目的的进行优化。相反,应该对已经掌握的性能瓶颈进行特定的优化。这不仅可以帮助我们避免增加了系统的复杂性,而且还让我们少走弯路,不去做那些浪费时间的优化。

2.常量尽量使用枚举

需要用户列出一组预定义或常量值的场景有很多,例如在web应用程序中可能遇到的HTTP响应代码。最常见的实现技术之一是新建类,该类里面有很多静态的final类型的值,每个值都应该有一句注释,描述该值的含义是什么:

1
2
3
4
5
6
7
8
复制代码public class HttpResponseCodes {
public static final int OK = 200;
public static final int NOT_FOUND = 404;
public static final int FORBIDDEN = 403;
}
if (getHttpResponse().getStatusCode() == HttpResponseCodes.OK) {
// Do something if the response code is OK
}

能够有这种思路就已经非常好了,但这还是有一些缺点:

  1. 没有对传入的整数值进行严格的校验
  2. 由于是基本数据类型,因此不能调用状态代码上的方法

在第一种情况下只是简单的创建了一个特定的常量来表示特殊的整数值,但并没有对方法或变量进行限制,因此使用的值可能会超出定义的范围。例如:

1
2
3
4
5
6
复制代码public class HttpResponseHandler {
public static void printMessage(int statusCode) {
System.out.println("Recieved status of " + statusCode);
}
}
HttpResponseHandler.printMessage(15000);

尽管15000并不是有效的HTTP响应代码,但是由于服务器端也没有限制客户端必须提供有效的整数。在第二种情况下,我们没有办法为状态代码定义方法。例如,如果想要检查给定的状态代码是否是一个成功的代码,那就必须定义一个单独的函数:

1
2
3
4
5
6
7
8
9
10
11
复制代码public class HttpResponseCodes {
public static final int OK = 200;
public static final int NOT_FOUND = 404;
public static final int FORBIDDEN = 403;
public static boolean isSuccess(int statusCode) {
return statusCode >= 200 && statusCode < 300;
}
}
if (HttpResponseCodes.isSuccess(getHttpResponse().getStatusCode())) {
// Do something if the response code is a success code
}

为了解决这些问题,我们需要将常量类型从基本数据类型改为自定义类型,并只允许自定义类的特定对象。这正是Java枚举(enum)的用途。使用enum,我们可以一次性解决这两个问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
复制代码public enum HttpResponseCodes {
OK(200),
FORBIDDEN(403),
NOT_FOUND(404);
private final int code;
HttpResponseCodes(int code) {
this.code = code;
}
public int getCode() {
return code;
}
public boolean isSuccess() {
return code >= 200 && code < 300;
}
}
if (getHttpResponse().getStatusCode().isSuccess()) {
// Do something if the response code is a success code
}

同样,现在还可以要求在调用方法的时候提供必须有效的状态代码:

1
2
3
4
5
6
复制代码public class HttpResponseHandler {
public static void printMessage(HttpResponseCode statusCode) {
System.out.println("Recieved status of " + statusCode.getCode());
}
}
HttpResponseHandler.printMessage(HttpResponseCode.OK);

值得注意的是,举这个例子事项说明如果是常量,则应该尽量使用枚举,但并不是说什么情况下都应该使用枚举。在某些情况下,可能希望使用一个常量来表示某个特殊值,但是也允许提供其它的值。例如,大家可能都知道圆周率,我们可以用一个常量来捕获这个值(并重用它):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
复制代码public class NumericConstants {
public static final double PI = 3.14;
public static final double UNIT_CIRCLE_AREA = PI * PI;
}
public class Rug {
private final double area;
public class Run(double area) {
this.area = area;
}
public double getCost() {
return area * 2;
}
}
// Create a carpet that is 4 feet in diameter (radius of 2 feet)
Rug fourFootRug = new Rug(2 * NumericConstants.UNIT_CIRCLE_AREA);

因此,使用枚举的规则可以归纳为:


当所有可能的离散值都已经提前知道了,那么就可以使用枚举


再拿上文中所提到的HTTP响应代码为例,我们可能知道HTTP状态代码的所有值(可以在RFC 7231中找的到,它定义了HTTP 1.1协议)。因此使用了枚举。在计算圆周率的情况下,我们不知道关于圆周率的所有可能值(任何可能的double都是有效的),但同时又希望为圆形的rugs创建一个常量,使计算更容易(更容易阅读);因此定义了一系列常量。

如果不能提前知道所有可能的值,但是又希望包含每个值的字段或方法,那么最简单的方法就是可以新建一个类来表示数据。尽管没有说过什么场景应该绝对不用枚举,但要想知道在什么地方、什么时间不使用枚举的关键是提前意识到所有的值,并且禁止使用其他任何值。

3.重新定义类里面的equals()方法

对象识别可能是一个很难解决的问题:如果两个对象在内存中占据相同的位置,那么它们是相同的吗?如果它们的id相同,它们是相同的吗?或者如果所有的字段都相等呢?虽然每个类都有自己的标识逻辑,但是在系统中有很多西方都需要去判断是否相等。例如,有如下的一个类,表示订单购买…

1
2
3
4
5
6
7
8
9
复制代码public class Purchase {
private long id;
public long getId() {
return id;
}
public void setId(long id) {
this.id = id;
}
}

……就像下面写的这样,代码中肯定有很多地方都是类似于的:

1
2
3
4
5
复制代码Purchase originalPurchase = new Purchase();
Purchase updatedPurchase = new Purchase();
if (originalPurchase.getId() == updatedPurchase.getId()) {
// Execute some logic for equal purchases
}

这些逻辑调用的越多(反过来,违背了DRY原则),Purchase类的身份信息也会变得越来越多。如果出于某种原因,更改了Purchase类的身份逻辑(例如,更改了标识符的类型),则需要更新标识逻辑所在的位置肯定也非常多。

我们应该在类的内部初始化这个逻辑,而不是通过系统将Purchase类的身份逻辑进行过多的传播。乍一看,我们可以创建一个新的方法,比如isSame,这个方法的入参是一个Purchase对象,并对每个对象的id进行比较,看看它们是否相同:

1
2
3
4
5
6
复制代码public class Purchase {
private long id;
public boolean isSame(Purchase other) {
return getId() == other.gerId();
}
}

虽然这是一个有效的解决方案,但是忽略了Java的内置功能:使用equals方法。Java中的每个类都是继承了Object类,虽然是隐式的,因此同样也就继承了equals方法。默认情况下,此方法将检查对象标识(内存中相同的对象),如JDK中的对象类定义(version 1.8.0_131)中的以下代码片段所示:

1
2
3
复制代码public boolean equals(Object obj) {
return (this == obj);
}

这个equals方法充当了注入身份逻辑的自然位置(通过覆盖默认的equals实现):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
复制代码public class Purchase {
private long id;
public long getId() {
return id;
}
public void setId(long id) {
this.id = id;
}
@Override
public boolean equals(Object other) {
if (this == other) {
return true;
}
else if (!(other instanceof Purchase)) {
return false;
}
else {
return ((Purchase) other).getId() == getId();
}
}
}

虽然这个equals方法看起来很复杂,但由于equals方法只接受类型对象的参数,所以我们只需要考虑三个案例:

  1. 另一个对象是当前对象(即originalPurchase.equals(originalPurchase)),根据定义,它们是同一个对象,因此返回true
  2. 另一个对象不是Purchase对象,在这种情况下,我们无法比较Purchase的id,因此,这两个对象不相等
  3. 其他对象不是同一个对象,但却是Purchase的实例,因此,是否相等取决于当前Purchase的id和其他Purchase是否相等

现在可以重构我们之前的条件,如下:

1
2
3
4
5
复制代码Purchase originalPurchase = new Purchase();
Purchase updatedPurchase = new Purchase();
if (originalPurchase.equals(updatedPurchase)) {
// Execute some logic for equal purchases
}

除了可以在系统中减少复制,重构默认的equals方法还有一些其它的优势。例如,如果构造一个Purchase对象列表,并检查列表是否包含具有相同ID(内存中不同对象)的另一个Purchase对象,那么我们就会得到true值,因为这两个值被认为是相等的:

1
2
3
复制代码List<Purchase> purchases = new ArrayList<>();
purchases.add(originalPurchase);
purchases.contains(updatedPurchase); // True

通常,无论在什么地方,如果需要判断两个类是否相等,则只需要使用重写过的equals方法就可以了。如果希望使用由于继承了Object对象而隐式具有的equals方法去判断相等性,我们还可以使用= =操作符,如下:

1
2
3
复制代码if (originalPurchase == updatedPurchase) {
// The two objects are the same objects in memory
}

还需要注意的是,当equals方法被重写以后,hashCode方法也应该被重写。有关这两种方法之间关系的更多信息,以及如何正确定义hashCode方法,请参见此线程。

正如我们所看到的,重写equals方法不仅可以将身份逻辑在类的内部进行初始化,并在整个系统中减少了这种逻辑的扩散,它还允许Java语言对类做出有根据的决定。

4.尽量多使用多态性

对于任何一门编程语言来说,条件句都是一种很常见的结构,而且它的存在也是有一定原因的。因为不同的组合可以允许用户根据给定值或对象的瞬时状态改变系统的行为。假设用户需要计算各银行账户的余额,那么就可以开发出以下的代码:

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
复制代码public enum BankAccountType {
CHECKING,
SAVINGS,
CERTIFICATE_OF_DEPOSIT;
}
public class BankAccount {
private final BankAccountType type;
public BankAccount(BankAccountType type) {
this.type = type;
}
public double getInterestRate() {
switch(type) {
case CHECKING:
return 0.03; // 3%
case SAVINGS:
return 0.04; // 4%
case CERTIFICATE_OF_DEPOSIT:
return 0.05; // 5%
default:
throw new UnsupportedOperationException();
}
}
public boolean supportsDeposits() {
switch(type) {
case CHECKING:
return true;
case SAVINGS:
return true;
case CERTIFICATE_OF_DEPOSIT:
return false;
default:
throw new UnsupportedOperationException();
}
}
}

虽然上面这段代码满足了基本的要求,但是有个很明显的缺陷:用户只是根据给定帐户的类型决定系统的行为。这不仅要求用户每次要做决定之前都需要检查账户类型,还需要在做出决定时重复这个逻辑。例如,在上面的设计中,用户必须在两种方法都进行检查才可以。这就可能会出现失控的情况,特别是接收到添加新帐户类型的需求时。

我们可以使用多态来隐式地做出决策,而不是使用账户类型用来区分。为了做到这一点,我们将BankAccount的具体类转换成一个接口,并将决策过程传入一系列具体的类,这些类代表了每种类型的银行帐户:

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
复制代码public interface BankAccount {
public double getInterestRate();
public boolean supportsDeposits();
}
public class CheckingAccount implements BankAccount {
@Override
public double getIntestRate() {
return 0.03;
}
@Override
public boolean supportsDeposits() {
return true;
}
}
public class SavingsAccount implements BankAccount {
@Override
public double getIntestRate() {
return 0.04;
}
@Override
public boolean supportsDeposits() {
return true;
}
}
public class CertificateOfDepositAccount implements BankAccount {
@Override
public double getIntestRate() {
return 0.05;
}
@Override
public boolean supportsDeposits() {
return false;
}
}

这不仅将每个帐户特有的信息封装到了到自己的类中,而且还支持用户可以在两种重要的方式中对设计进行变化。首先,如果想要添加一个新的银行帐户类型,只需创建一个新的具体类,实现了BankAccount的接口,给出两个方法的具体实现就可以了。在条件结构设计中,我们必须在枚举中添加一个新值,在两个方法中添加新的case语句,并在每个case语句下插入新帐户的逻辑。

其次,如果我们希望在BankAccount接口中添加一个新方法,我们只需在每个具体类中添加新方法。在条件设计中,我们必须复制现有的switch语句并将其添加到我们的新方法中。此外,我们还必须在每个case语句中添加每个帐户类型的逻辑。

在数学上,当我们创建一个新方法或添加一个新类型时,我们必须在多态和条件设计中做出相同数量的逻辑更改。例如,如果我们在多态设计中添加一个新方法,我们必须将新方法添加到所有n个银行帐户的具体类中,而在条件设计中,我们必须在我们的新方法中添加n个新的case语句。如果我们在多态设计中添加一个新的account类型,我们必须在BankAccount接口中实现所有的m数,而在条件设计中,我们必须向每个m现有方法添加一个新的case语句。

虽然我们必须做的改变的数量是相等的,但变化的性质却是完全不同的。在多态设计中,如果我们添加一个新的帐户类型并且忘记包含一个方法,编译器会抛出一个错误,因为我们没有在我们的BankAccount接口中实现所有的方法。在条件设计中,没有这样的检查,以确保每个类型都有一个case语句。如果添加了新类型,我们可以简单地忘记更新每个switch语句。这个问题越严重,我们就越重复我们的switch语句。我们是人类,我们倾向于犯错误。因此,任何时候,只要我们可以依赖编译器来提醒我们错误,我们就应该这么做。

关于这两种设计的第二个重要注意事项是它们在外部是等同的。例如,如果我们想要检查一个支票帐户的利率,条件设计就会类似如下:

1
2
复制代码BankAccount checkingAccount = new BankAccount(BankAccountType.CHECKING);
System.out.println(checkingAccount.getInterestRate()); // Output: 0.03

相反,多态设计将类似如下:

1
2
复制代码BankAccount checkingAccount = new CheckingAccount();
System.out.println(checkingAccount.getInterestRate()); // Output: 0.03

从外部的角度来看,我们只是在BankAccount对象上调用getintereUNK()。如果我们将创建过程抽象为一个工厂类的话,这将更加明显:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
复制代码public class ConditionalAccountFactory {
public static BankAccount createCheckingAccount() {
return new BankAccount(BankAccountType.CHECKING);
}
}
public class PolymorphicAccountFactory {
public static BankAccount createCheckingAccount() {
return new CheckingAccount();
}
}
// In both cases, we create the accounts using a factory
BankAccount conditionalCheckingAccount = ConditionalAccountFactory.createCheckingAccount();
BankAccount polymorphicCheckingAccount = PolymorphicAccountFactory.createCheckingAccount();
// In both cases, the call to obtain the interest rate is the same
System.out.println(conditionalCheckingAccount.getInterestRate()); // Output: 0.03
System.out.println(polymorphicCheckingAccount.getInterestRate()); // Output: 0.03

将条件逻辑替换成多态类是非常常见的,因此已经发布了将条件语句重构为多态类的方法。这里就有一个简单的例子。此外,马丁·福勒(Martin Fowler)的《重构》(p
. 255)也描述了执行这个重构的详细过程。

就像本文中的其他技术一样,对于何时执行从条件逻辑转换到多态类,没有硬性规定。事实上,如论在何种情况下我们都是不建议使用。在测试驱动的设计中:例如,Kent Beck设计了一个简单的货币系统,目的是使用多态类,但发现这使设计过于复杂,于是便将他的设计重新设计成一个非多态风格。经验和合理的判断将决定何时是将条件代码转换为多态代码的合适时间。

结束语

作为程序员,尽管平常所使用的常规技术可以解决大部分的问题,但有时我们应该打破这种常规,主动需求一些创新。毕竟作为一名开发人员,扩展自己知识面的的广度和深度,不仅能让我们做出更明智的决定,也能让我们变得越来越聪明。


2017年10月14日,SDCC 2017之大数据技术实战线上峰会即将召开,邀请圈内顶尖的布道师、技术专家和技术引领者,共话大数据平台构建、优化提升大数据平台的各项性能、Spark部署实践、企业流平台实践、以及实现应用大数据支持业务创新发展等核心话题,七位大牛与你相聚狂欢,详情查看所有嘉宾和议题,以及注册参会。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

《JavaScript 正则表达式迷你书》问世了!

发表于 2017-09-28

1.1版,下载链接:github.com/qdlaoyao/js…之前在本站发表了一篇文章,《JS正则表达式完整教程(略长)》,正如你所看到的那样确实很长,也获得了近1000人的喜欢。但文章太长,想必有很多同学看不下去,大都只是收藏罢了。因此我整理成一本pdf。既然只是收藏,那么收藏文章就不如收藏书来的好。其实,整理成pdf的灵感也来自本站读者的反馈。

同时,我也相信我们不可能只做一个收藏家,有人8小时看完,有人花了一周看完,也有个把小时就能看完的。有很多读者看完反馈说,表示弄懂正则了。对此,个人表示非常欣慰,我的这一丁点儿付出,能让别人有所收获,真是没有比此更让人开心的事情了,也算我也为前端界做出的一点小小的贡献。

本书是第一版,对文章部分内容都修改了一下,当然也难免有笔误(勘误信息在此处)。欢迎大家挑毛病,不管是笔误、还是没有说清楚的地方,都欢迎读者留言。一段时间后,我会整理再出了新的版本。目前此书只有pdf格式,我最近也在学习mobi格式制作方法。

后续的大版本也会出的。可能会添加一些新的章节和专题。只是目前个人再找工作,等安心之后再说哈。

下面的内容是我的感谢和后记(有人已经在本站帮我转发过了,感谢!)

感谢

由于本书是由个人文章修改而成,感谢各平台读者的支持。感谢湖山,是他说我该把这些东西写出来的。

感谢小不,他在多方面给予了我帮助,封面是他设计的。感谢小鱼二,他对全书进行了仔细地校对,并提出了相应的修改意见。

感谢丹迪的支持,他为我设计了多个封面,风格比较前卫,留给后续版本。最后,尤其要感谢各位大佬帮我写的推荐序。他们的名字不分先后如下:大漠穷秋、小鱼二、Jack Lo、程序猿DD、江湖人称向前兄、文蔺、_周末、Dark_Night。

后记

我竟然写了一本书!想想就挺开心的。这是个人的第一本书,虽然不厚,但也算是完成了个人的一个小梦想了。

说起正则表达式,我之所以会去详细地研究它,最初的动机是,当我分析前端常见的框架和库的源码时,发现一般被卡住的地方就是它。后来逐渐学习并看懂了“天书”,仿佛进入了一个新世界。有些工具就是这样,当你没有它时,可能并未觉得有啥不好,可是一旦你拥有了它,再也放不下手了。掌握正则了后,对字符串一些复杂操作,竟然能很快地实现。看待问题的角度也发生了改变,每次看着精炼的正则代码,总是感觉真是妙不可言。

当然,对我而言,正则表达式不仅应用在代码里。生活中也会经常使用它。比如个人平时回答网友问题时,一些网站私信里贴的代码中字符都是转义的。此时我都会贴到某个编辑器里,然后写个正则,再一次性替换,真方便。另外一个例子是,一些代码编辑器的代码格式化功能,总有让人不舒服的地方,此时我都会用写好正则表达式,再格式化一下。

还有一个很应景的例子,在编辑本书时,经常要在指定位置插入特定的语法格式,比如代码段前面要插入

1
2
复制代码[source,javascript]
----

这样的字符,此时,我发现我的大部分代码段,都是var开头的,并且前面有一空行。此时我打开查找替换功能,查找

1
复制代码(^\r\n)var

替换为

1
复制代码[source,javascript]\n----\nvar

这确实也帮我解决一部分工作。当然,正则表达式是跟具体语言(比如JavaScript)无关的。因为正则表达式是用来处理字符串问题的,基本上每门语言都有字符串类型,那么也都会支持正则表达式的。正则表达式是分流派的,也跟实现引擎有关。而JavaScript用到的正则表达式的语法,是市面常见语言都支持的核心子集。关于API,各语言基本大同小异,想用的话,应该很快就能熟悉起来。

关于正则表达式就说到这里,下面说一说自己写这本书的收获。有人说最好的学习方法就是写一本书。其实,要想把知识掌握牢固,归根到底就是用起来。写书或者说写作是一种很好的以教为学的手段。毕竟,形成文字,教给别人算是对知识的最直接的应用了。看似为了教,其实是为了学。只有教会别人才说明你掌握了。“以教为学”的手段除了写东西之外,还有翻译、以及面对面的辅导等。

以目标为导向的做中学,是比较有效的学习手段。本书是用Asciidoc写成的。它类似于Markdown,但在此书之前本人都没有用过。以需求为驱动,逐步百度检索,自己才逐渐把书整理好了。其中遇到了很多与语法无关的问题,比如转换pdf的过程中用的工具运行不起来,自己寻找原因,凭着感觉修改版本号等。又比如导出的pdf有缺字的问题,百度明白后才发现跟字体有关。边干边学,每解决掉一个问题,都挺有满足感的。带着问题去研究去学习,这是一种问题思维。然而一时的解决方案还不够,后来我详细地阅读了Asciidoc使用手册,也经常有“原来,还可以这样写!”的体会。这点跟我们平常工作很像,以项目为导向,用啥学啥。比如初学一个框架,先干起来,边看文档,边敲代码。代码敲完了,还要详细地看一遍文档,届时会发现还有更好的实现方式。不只有眼前的苟且,还会有明天的迭代。

另外一点,我深深体会到了,干着简单繁杂的工作是怎样的体验。一遍遍校对,一遍遍修改。每次,看都会发现新的待完善的地方。以至于现在我感觉已经能把本书背下来了,单调的工作确实考验人的耐心。

就写到这里吧。如果你觉得此书不错的话,欢迎赞赏(书中有微信二维码的,看完之后再决定赞赏也不迟)。

最后,我们该想起陆游诗人对前端做出的贡献:

纸上得来终觉浅,觉知此事要躬行。本文完。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

Java IO使用入门 -- IO其实很简单 总体结构 使用

发表于 2017-09-27

总体结构

IO应该是平时项目里最常用到的功能了,无论是简单的文件读取,还是服务器端口监听,都会用到IO;但是,在面对Java IO包里庞杂的IO基础类库时,经常会很头大,是该选择InputStream还是应该选择Reader,应该为InputStream增加一个Buffer吗?如何根据应用场景选择合适的类库是摆在很多代码人员面前的一个难题,这里我将Java IO包里的常用类库做了一个梳理,包括它们的组织结构,功能特性,适用场景等,以方便后续使用时能方便快捷的根据需求选取最合适的IO类

java-io.png

java-io.png

根据解析图,从大的层面可以IO进行两个维度的划分:

  1. 数据类型,即:字符 or 字节,类上对应于Writer/Reader or OutputStream/InputStream
  2. 操作类型,即:读取(输入) or 写入(输出),类上对应于Reader/InputStream or Writer/OutputStream

使用技巧

Java IO的所有操作都无外乎这两种维度四大主类的扩展,大部分比较简单,下面对于稍微难理解以及值得注意的点进行单独说明

  1. Java IO大量使用了Decorator模式,所以,一般在使用IO类库的时候都是采用Decorator的调用方式:
1
复制代码PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("foo.out")));
  1. 在Java IO中,无论是字符的读与写还是字节的读与写,基本都是一一对应的,换句话说,有一个特定读的类,一般就会有一个特定写的类,把握这一点,可以起到化繁为简的作用,如FileInputStream和FileOutputStream就分别对应于文件的读和写;PipedInputStream和PipedOutputStream分别对应于管道数据的读和写
  2. 如何区分读 or 写,这是一个经常会困扰新手的问题,这里我提供一个简单的区分方式:以你当前运行的程序作为基准(即调用IO的程序),数据从程序传至其它地方则为写(输出),数据从其它地方传至程序则为读(输入);如将程序产生的数据存放至日志文件中,那么就是写,从端口中取得数据并在程序中进行处理,则是读

r_or_w.png

r_or_w.png

  1. 根据要执行的动作以及目标数据类型,同时结合使用场景选择合适的IO类进行组装,注意上面一句话其实涉及到三个步骤:
    • 执行的动作,即是要读还是要写
    • 数据类型,即是字节还是字符,有的时候还需要字符与字节的转换(如OutputStreamWriter);如需要在网络上或内存里存储的数据,一般都是以字节的形式;又或者面对需要写文件的场景,如果是文本类文件,由于其本身就是字符编码所以一般采用字符形式,而对于图片,视频等文件则只能使用字节形式
    • 使用场景,其实使用场景需要分两步考虑,首先考虑显而易见的场景,如是文件的操作还是字符串的操作,抑或是管道通信;其次需要考虑性能,如对文件的写操作是否会比较频繁,若是,则建议通过BufferedWriter对其进行封装,因为每次都对少量数据进行文件打开并写入是一个效率很低的方式

总结

本文主要对基本的IO类做了简单的梳理,并就IO中的基本概念以及如何使用IO基础类库做了说明,当然,本文并未罗列所有的IO实现类,感兴趣的同学可以自己查看Java的文档或源码,同时本文也未阐述如何对已有的IO类库进行自定义扩展,一来这种扩展只需根据需求重写或增加特定方法即可,二来也是因为一般情况下Java提供的基础类库足以满足需求;另外Java在1.4后引入了NIO,即:No Blocking IO,它与原IO的使用场景有一定区别,感兴趣的同学可以查看Java NIO vs. IO

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

2018秋招面经:斗鱼、滴滴、百度、美团、小米、腾讯(全of

发表于 2017-09-27

一、斗鱼(9.8,现场笔试+技术面+hr面)

现场笔试:(题目比较基础)

1、十几道C++基础简答题或改错题
2、一道字符串分割的算法题
3、一道string类的实现
4、一道快排的实现

斗鱼技术面:(2h+,其实就是将笔试题从上往下问,并且做很多拓展和延伸,记录一些我有印象的)

1、c++多态的种类、C语言的多态怎么实现
2、struct与类的区别
3、union和struct的区别,union如何知道当前使用的是哪一个元素,如何设计
4、vector和map删除时,迭代器失效如何解决
5、线程安全的单例模式(注意volatile和double-check)
6、排序时衡量性能的标准
7、复杂的字节对齐计算(需要分32位和64位讨论,但两种系统最终结果相同,pragma pack 1的应用场景(节省空间,公司统一标准)?
8、用户有两个进程,分别运行while(1){},系统如何切换(时钟中断,进一步延伸到内中断,外中断)
9、项目中有用到模拟退火算法,让我讲了下思路与实现
10、虚函数的实现

hr面:(0.5h)

1、个人情况
2、家庭情况
3、手上offer情况
4、发展规划

二、 滴滴(9.12,3技术+1hr面)

技术一面(50min+, 只记录一些有印象的):

1、项目
2、B+树、B-树的区别
3、数据库隔离级别,幻读和不可重复读的区别
4、有hell, well, hello, world等字符串组,现在问能否拼接成helloworld,代码实现
5、快排
6、线程安全的单例模式

技术二面(1h15min, 纯怼算法和智力题,好难):

1、25匹马赛跑,有一个赛场,只有五个赛道,没有计时器,只能通过目测来记录快慢,求出求3快的马要多少场比赛?
2、kmp算法next数组的求解思路
3、数组中有三个数字出现超过3/4,求着三个数字
4、1到n+2个数组中缺了两个数,如何用O(n)时间,O(1)空间找到这两个数字
5、一条线段长为1,随机选两个点,将改线段分为三段,三段能成三角形的概率是多少?
6、有一个教授,他三个学生,脑袋背后分别各写了一个数字,其中一个数字是另外两个数字的和,经过几轮后,有一个学生猜出了自己的数字请问是什么原因?
7、B+树做索引时,B+树通常高度为多少层?要参考哪些条件?

技术三面:(40min)

1、问我喜欢什么运动,说篮球,聊了篮球和工作,大概近10分钟,后来知道面试官以前是校队,校赛拿mvp的大神,怪不得问我拿过什么篮球的荣誉
2、一个3L的杯子,一个5L的杯子,如何倒出4L的水,要求两种方法
3、情景题:周一领导布置任务,周五完成,周三发现完成不了,你会怎么处理
4、对BAT三家的看法,现在看好谁
5、介意学机器学习吗?(怎么可能介意,求之不得)
6、问我有什么问题要问(我说这不是技术面吗?怎么没怎么问技术,结果面试官加了第七题)
7、二维数组行优先读取和列优先读取哪个快,从操作系统层面解释(从减少缺页中断的角度出发即可)

hr面(都大同小异)

三、百度(9.17/9.19, 三轮技术面,没有hr面)

技术一面(1.5h,面试官平时是负责终面的boss,聊的不完全是技术,有很多内容记不住了)

1、聊了项目。面试官很感兴趣,聊了半个小时
2、操作系统,null指针为什么不可访问(涉及到段页式内存管理中,内存分配问题)
3、socket syn攻击原理,超时重传的次数及时间间隔

技术二面(50min)

1、项目
2、select/poll/epoll
3、线程池
4、ipc,以及共享内存使用的时候需要注意什么
5、手写代码,题目记不清了

技术三面(电话面35min左右)

1、简历细细过一遍
2、cat file | grep x 创建几个进程 他们是什么关系
3、父子进程间,子进程退出后会发生什么
4、如果父进程不需要捕获子进程退出消息怎么办
5、pcb包括什么
6、有一个文件,每一行都有一个IP范围,以及对应城市。你需要检测,同一个城市的IP是否冲突。不同的城市IP相同不算冲突。
7、未来的打算,自我评价,职业生涯规划

四、美团(9.19/9.21)

初试一面

1、自我介绍
2、项目(问的很深)
3、数据库实现原理 B+树 B-树区别
4、数据库索引种类
5、接口响应时间由20 ms偶发提高到1000ms可能是什么原因
6、左联结,右联结,数据库隔离级别
7、数组中找出和为target的两个数的位置
8、Linux命令
9、对Java的了解
还有一些忘了

初试二面:

1、自我介绍
2、项目
3、模拟退火算法,爬山算法,应用场景。。
4、tcp udp,udp的各种应用场景,udp如何实现可靠传输
5、syn攻击
6、黑客怎么越过防火墙,对防火墙内部计算机进行攻击
7、设计餐馆的数据库,需要几张表
8、stl有哪些优缺点 为什么有时候很慢
9、设计模式,观察者模式
10、堆排的实现
11、聊了下个人情况

复试一面:

1、自我介绍
2、socket11种状态,详细介绍
3、阻塞与非阻塞
4、同步与异步
5、connect可以异步吗?
6、如何看待上层应用编程与低层架构编程?
7、看什么书,怎么学习的
还有一些忘记了

复试二面(hr面)

大同小异,不过美团hr给我印象特别好,特别主动介绍了公司的各种情况,好评

五、小米(9.20,只有两轮技术面)

技术一面(35min, 体验不好。一个标间里面试,hr在旁边整理资料,下一个面试者竟然就在房间看我们面试。。)

1、自我介绍
2、介绍操作系统的段页式内存管理
3、socket三次握手,以及半连接的含义,可能出现的问题,以及处理方案
4、写代码,正则表达式模式匹配

技术二面(35min):

1、自我介绍
2、模拟退火算法介绍
3、手写代码:8*8的网格中,一个皇后选择一个位置后,她横竖斜三条直线上都不允许放其他皇后,问放8个皇后有几种方式
4、设计题,有一个车库,里面可以停大车和小车,可以自己拓展需要的信息(我拓展了计费等服务)

六、腾讯(9.21/9.23/9.24,两轮技术面+hr面):

技术一面(45min左右):

1、自我介绍
2、项目
3、进程与线程的区别(这里我说的很细致)
4、管道一般用途,如何用管道实现非亲缘进程间通信(有名管道)
5、实现memcpy(注意区分pSrc和pDes重叠的情况)
6、环形链表检测,以及入口求解,手推公式
7、智力题:A房间三个开关,控制着B房间三个灯,只允许进一次A,进一次B,如何确定开关与电灯的对应情况
8、问其他offer情况

技术二面(45min左右):

1、最满意的项目,详细介绍
2、手写代码:有一个数字N,由1,2,3,4四种数字组成,请问怎么调整其顺序,可以使其整除7
3、手写代码:map中,删除key值为素数的元素,
4、socket中,缓冲区只有2k,要接受4k的数据,怎么处理,代码实现
5、linux里ipc有哪些

hr面(18min)

1、自我介绍
2、如果有人质疑你非计算机专业的,你会怎么看
3、学习了哪些课程,怎么自学
4、家庭情况,职业规划
5、对我骑行2000km的经历感兴趣,聊了下
6、让我提问

七、华为(华为暑期实习生,只参加了实习答辩)

写在最后

所有公司投递岗位的都是C++软件研发工程师/后台研发工程师。截止2017.9.26,确认的有华为、斗鱼、美团、百度。等通知的有腾讯,小米,滴滴。由于已经有一些offer确认,京东、招银网络、网易互娱面试没有去参加了。附自己博客地址,里面有我整理的一些基础知识和面试题,个人觉得应该对大家有所帮助:www.jianshu.com/u/2dab0cda8…

本人非计算机专业出身,读研阶段才开始接触编程,不过读研期间付出了比别人更多的努力。因此,付出总会有回报的,希望大家也继续努力,也预祝找工作的同学也都能拿到满意offer,加油!

2017.9.27 更新:已收腾讯sp,决定去鹅厂了~

附掘金秋招征文大赛链接

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

可能是国内最火的开源项目 —— C/C++ 篇

发表于 2017-09-26

推荐阅读:

  • 可能是最火的开源项目 —— Java 篇
  • 可能是国内最火的开源项目 —— PHP 篇
  • 可能是国内最火的开源项目 —— Python 篇

截止目前开源中国收录了 44513 款开源项目,囊括了最热门的各类开源项目,而软件的评分在一定程度上代表了软件的质量和热度,而 C 和 C++ 语言作为最基础的语言,在各类编程语言排行榜中高居不下,因此本文整理了 C/C++ 语言中评分最高并且收藏量超过 100 的几款项目,以供开发者选择和交流,排名如下:

高性能 TCP/UDP/HTTP 通信框架 HP-Socket

评分:9.8,收藏:1404

HP-Socket 是一套通用的高性能 TCP/UDP/HTTP 通信框架,包含服务端组件、客户端组件和Agent组件,广泛适用于各种不同应用场景的 TCP/UDP/HTTP 通信系统,提供 C/C++、C#、Delphi、E(易语言)、Java、Python 等编程语言接口。HP-Socket 对通信层实现完全封装,应用程序不必关注通信层的任何细节;HP-Socket 提供基于事件通知模型的 API 接口,能非常简单高效地整合到新旧应用程序中。

为了让使用者能方便快速地学习和使用 HP-Socket ,迅速掌握框架的设计思想和使用方法,特此精心制作了大量 Demo 示例(如:PUSH 模型示例、PULL 模型示例、PACK 模型示例、性能测试示例以及其它编程语言示例)。

基于 C++/Python 的开源量化交易研究框架 Hikyuu

评分:8.3,收藏:144

Hikyuu Quant Framework是一款基于C++/Python的开源量化交易研究框架,用于策略分析及回测。其核心思想基于当前成熟的系统化交易方法,将整个系统化交易抽象为由市场环境判断策略、系统有效条件、信号指示器、止损/止盈策略、资金管理策略、盈利目标策略、移滑价差算法七大组件,你可以分别构建这些组件的策略资产库,在实际研究中对它们自由组合来观察系统的有效性、稳定性以及单一种类策略的效果。

10000-overview.png

开源自动驾驶平台 ApolloAuto

评分:8.1,收藏:156

Apollo (阿波罗)是一个开放的、完整的、安全的平台,将帮助汽车行业及自动驾驶领域的合作伙伴结合车辆和硬件系统,快速搭建一套属于自己的自动驾驶系统。

Apollo 是百度重点打造的 AI 开放平台之一,计划主要包含 4 个技术模块:定位/感知模块、车辆规划与运营(AI+大数据,精准控制车辆,适合不同路况)、软件运营框架(支持英特尔、英伟达等多种芯片)。

分布式图片实时动态压缩 ngx-fastdfs

评分:8.1,收藏:215

ngx-fastdfs 是 nginx + lua +fastdfs 实现分布式图片实时动态压缩。

cut.png

高性能 RPC 开发框架 Tars

评分:8.0,收藏:296

Tars 是基于名字服务使用 Tars 协议的高性能 RPC 开发框架,同时配套一体化的服务治理平台,帮助个人或者企业快速的以微服务的方式构建自己稳定可靠的分布式应用。它是将腾讯内部使用的微服务架构 TAF(Total Application Framework)多年的实践成果总结而成的开源项目。

目前该框架在腾讯内部,有 100 多个业务(如手机浏览器、应用宝、手机管家、手机QQ、手机游戏等)、1.6 多万台服务器上运行使用。

Go语言开发工具 LiteIDE

评分:7.9,收藏:384

LiteIDE是一款开源、跨平台的轻量级Go语言集成开发环境(IDE)。

分布式TCP压力测试工具 tcpcopy

评分:7.9,收藏:380

tcpcopy是一种应用请求复制(基于tcp的packets)工具,其应用领域较广,目前已经应用于国内各大互联网公司。总体说来,tcpcopy主要有如下功能:

  • 分布式压力测试工具,利用在线数据,可以测试系统能够承受的压力大小(远比ab压力测试工具真实地多),也可以提前发现一些bug
  • 普通上线测试,可以发现新系统是否稳定,提前发现上线过程中会出现的诸多问题,让开发者有信心上线
  • 对比试验,同样请求,针对不同或不同版本程序,可以做性能对比等试验
  • 利用多种手段,构造无限在线压力,满足中小网站压力测试要求
  • 实战演习(架构师必备)

tcpcopy可以用于实时和离线回放领域,并且tcpcopy支持mysql协议的复制,开源二年以来,功能上越来越完善。如果你对上线没有信心,如果你的单元测试不够充分,如果你对新系统不够有把握,如果你对未来的请求压力无法预测,tcpcopy可以帮助你解决上述难题。

中文文本转语音引擎 Ekho

评分:7.9,收藏:393

Ekho(余音)是一个把文字转换成声音的软件。它目前支持粤语、普通话(国语)、诏安客语、藏语、雅言(中国古代通用语)和韩语(试验中),英文则通过Festival间接实现。支持Linux、Windows、Android.

在 Linux 系统中运行 Android 应用 Anbox

评分:7.8,收藏:191

Anbox 可让你在任何 GNU/Linux 操作系统上运行 Android 应用程序。具有以下特性:

  • 没有限制:由于 Anbox 运行着整个 Android 系统,所以理论上任何应用都可以在其中运行
  • 安全:Anbox 将 Android APP 放进一个密封的盒子中,无需直接访问硬件或数据
  • 性能:无需虚拟化硬件而运行 Android,可以无缝桥接硬件加速功能
  • 集成:与主机操作系统紧密集成,以提供丰富的功能集

机器学习系统 TensorFlow

评分:7.8,收藏:602

TensorFlow 是谷歌的第二代机器学习系统,按照谷歌所说,在某些基准测试中,TensorFlow的表现比第一代的DistBelief快了2倍。

TensorFlow 内建深度学习的扩展支持,任何能够用计算流图形来表达的计算,都可以使用TensorFlow。任何基于梯度的机器学习算法都能够受益于TensorFlow的自动分 化(auto-differentiation)。通过灵活的Python接口,要在TensorFlow中表达想法也会很容易。TensorFlow 对于实际的产品也是很有意义的。将思路从桌面GPU训练无缝搬迁到手机中运行。

MySQL衍生版 Percona Server

评分:7.8,收藏:426

Percona 为 MySQL 数据库服务器进行了改进,在功能和性能上较 MySQL 有着很显著的提升。该版本提升了在高负载情况下的 InnoDB 的性能、为 DBA 提供一些非常有用的性能诊断工具;另外有更多的参数和命令来控制服务器行为。

Percona Server 只包含 MySQL 的服务器版,并没有提供相应对 MySQL 的 Connector 和 GUI 工具进行改进。Percona Server 使用了一些 google-mysql-tools, Proven Scaling, Open Query 对
MySQL 进行改造。

数据中间层项目 ProxySQL

评分:7.8,收藏:128

ProxySQL 是一个高性能,高可用性,的数据中间层项目。它具有先进的多核架构。 它从根本上构建,支持数十万个并发连接,复用到可能数百个后端服务器。 最大的 ProxySQL 部署跨越了几百个代理。

开源网盘云存储 Seafile

评分:7.8,收藏:1499

Seafile 是一款安全、高性能的开源网盘(云存储)软件。Seafile 提供了主流网盘(云盘)产品所具有的功能,包括文件同步、文件共享等。在此基础上,Seafile 还提供了高级的安全保护功能以及群组协作功能。由于 Seafile 是开源的,你可以把它部署在私有云的环境中,作为私有的企业网盘。Seafile 支持 Mac、Linux、Windows 三个桌面平台,支持 Android 和 iOS 两个移动平台。

Seafile 是由国内团队开发的国际型项目,目前已有50万左右的用户,以欧洲用户为多。自发布以来,Seafile 一直保持开放、国际化、高质量的宗旨,受到国内外大型机构的信赖。目前主要的大型客户包括卡巴斯基、中国平安,以及欧美多家知名大学和科研机构。你可以把它想象成是面向团队的开源Dropbox。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

Java字符串那些事儿

发表于 2017-09-25

我们再来看一段代码:

运行一下:

没错,一个true,一个是false,(答错的小朋友去面壁去),大家可能在想编译器肯定又调皮了,编译的时候是不是又偷偷加了些什么,迫不及待的打开class文件看一下:

除了删掉了空行以外和我的java源文件一致呀,这回可冤枉编译器了,那为什么会导致不同的结果呢?我们都知道,Java代码是运行在JVM里的,那是不是JVM在执行这段代码时给我们做了什么?
在JVM中,当代码执行到String s1 = “100” 时,会先看常量池里有没有字符串刚好是“100”这个对象,如果没有,在常量池里创建初始化该对象,并把引用指向它,如下图,绿色部分为常量池,存在于堆内存中。

当执行到String s2 = “100” 时,发现常量池已经有了100这个值,于是不再在常量池中创建这个对象,而是把引用直接指向了该对象,如下图:

这时候我们打印System.out.println(s1 == s2)时,由于==是判断两个对象是否指向同一个引用,所以这儿打印出来的就应该是true。

继续执行到Strings3 = new String(“100”) 这时候我们加了一个new关键字,这个关键字呢就是告诉JVM,你直接在堆内存里给我开辟一块新的内存,如下图所示:

继续执行String s4 = new String(“100”)

这时候再打印System.out.println(s3 == s4) 那一定便是false了,因为s3和s4不是指向对一个引用(对象)。

注:图中只是画出了main方法栈和相关对象在内存中的大致模拟,实际中JVM中内存管理比较复杂,大家有条件的话可以去找《Java虚拟机规范》这本书去深入研究。

结论:我们在比较两个String对象内容时,无论是怎么声明的,都一定要使用equals去比较,不能用==,在Java中没有重载操作符这一说,特别是从其它语言转到Java的童鞋们要注意。equals我会在后续专栏里已经做了详细解说。

上一篇:让人疑惑的Java代码 - Java那些事儿

下一篇:说说Java里的equals(上) - Java那些事儿

如果喜欢本系列文章,请为我点赞或顺手分享,您的支持是我继续下去的动力,您也可以在评论区留言想了解的内容,有机会本专栏会做讲解,最后别忘了关注一下我。

转载无限欢迎,但请注明「作者」和「原文地址」。转载请在文中保留此段,感谢您对作者版权的尊重。如需商业转载或刊登,请联系作者获得授权。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

公司编程竞赛之最长路径问题 前言 前置条件 深度优先搜索算法

发表于 2017-09-25

算法源码地址:https://github.com/wudashan/longest-path-problem

前言

最近产品线举办了一个软件编程大赛,题目非常的有趣,就是在一个9 × 9的格子里,你要和另一个敌人PK,在PK的过程中,你可以吃格子里的果实来提升攻击力。每次可以往正上、正下、正左、正右、左上、左下、右上、右下八个方向走。每次要么连续吃果实要么连续走空白区域,且不能走重复的位置。初始状态如下图所示:

为了提升攻击力,我们需要尽可能地一次吃最多的果实,所以路线可以这样规划:

至此,我们可以对这个问题进行描述:已知空白区域不能走,每次可以往正上、正下、正左、正右、左上、左下、右上、右下八个方向走,走过的位置不能再走,求能吃最多果实的路线(最长路径问题)?


前置条件

地图表示

首先我们将上面的地图使用布尔类型的二维数组表示,其中true表示可以行走的格子,false表示不能行走的格子:

1
2
3
4
5
6
7
8
9
10
11
复制代码boolean[][] simpleMap = new boolean[][] {
{false, false, false, false, false, false, false, false, false},
{false, false, false, false, false, false, true , true , false},
{false, false, false, true , false, false, true , true , false},
{false, false, true , false, false, false, false, false, false},
{false, false, true , false, false, false, false, false, false},
{false, false, true , false, false, false, false, false, false},
{false, false, false, true , false, true , false, false, false},
{false, false, false, false, true , true , false, false, false},
{false, false, false, false, false, false, false, false, false}
};

格子表示

对于地图上的每一个格子,我们用一个简单类来表示:

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
复制代码public class Pos {

private int x; // 横坐标
private int y; // 纵坐标

// get、set、construct方法省略

@Override
public String toString() {
final StringBuffer sb = new StringBuffer("Pos{");
sb.append("x=").append(x);
sb.append(", y=").append(y);
sb.append('}');
return sb.toString();
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Pos pos = (Pos) o;

if (x != pos.x) return false;
return y == pos.y;
}

@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}


}

由于我们是使用横纵坐标而不是几行几列来表示一个格子(没错,我就是这么傲娇),那么我们就需要给地图定义横纵坐标方向。方向如下图所示:

那么起点上方的果实坐标就是[3, 2](横坐标为3,纵坐标为2),但是对应着二维数组为map[2][3](第二行,第三列),即横坐标对应着二维数组的列,纵坐标对应着二维数组的行。

移动表示

为了程序简洁,我们给八个方向的移动定义对应的偏移量,这样每次行走只要对偏移量数组进行for循环就可以了。

1
2
3
4
5
6
7
8
9
10
复制代码Pos[] moveOffset = new Pos[] {
new Pos(-1, 0), // 向左移动
new Pos(-1, -1), // 向左上移动
new Pos( 0, -1), // 向上移动
new Pos( 1, -1), // 向右上移动
new Pos( 1, 0), // 向右移动
new Pos( 1, 1), // 向右下移动
new Pos( 0, 1), // 向下移动
new Pos(-1, 1) // 向左下移动
};

深度优先搜索算法

算法思想

拿到这道题,脑袋里第一个想到的就是深度优先搜索算法,其思想为每次往八个方向递归,当不能继续走下去的时候保存最长路径,并回退到能继续行走的格子,继续递归直到结束。

代码示例

接下来就是我们的深度优先搜索代码:

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
复制代码/**
* 通过深度优先搜索算法获取最长路径
* @param map 地图
* @param start 起点
* @param moveOffset 移动偏移量
* @return 最长路径
*/
public static List<Pos> getLongestPathByDFS(boolean[][] map, Pos start, Pos[] moveOffset) {

List<Pos> longestPath = new ArrayList<>();
dfs(start, map, new ArrayList<>(), longestPath, moveOffset);
return longestPath;

}

/**
* 递归实现深度优先搜索
*/
private static void dfs(Pos pos, boolean[][] map, List<Pos> path, List<Pos> result, Pos[] moveOffset) {

// 记录当前位置向周围格子移动的记录
List<Pos> visited = new ArrayList<>();

// 保存当前位置的周围格子
Pos[] neighbours = new Pos[moveOffset.length];

// 依次向周围移动
for (int i = 0; i < moveOffset.length; i++) {
Pos next = new Pos(pos.getX() + moveOffset[i].getX(), pos.getY() + moveOffset[i].getY());
neighbours[i] = next;
if (inMap(map, next) && !path.contains(next) && map[next.getY()][next.getX()]) {
path.add(next);
visited.add(next);
dfs(next, map, path, result, moveOffset);
}
}

// 若在当前位置下,没有向周围的格子移动过时,保存最长路径
if (visited.isEmpty()) {
if (path.size() > result.size()) {
result.clear();
result.addAll(path);
}
}

// 周围的格子都不可以移动时回退到上一格子
for (Pos neighbour : neighbours) {
if (canPath(map, path, neighbour, visited)) {
return;
}
}
path.remove(pos);

}

/**
* 判断格子是否可以移动
*/
private static boolean canPath(boolean[][] map, List<Pos> path, Pos pos, List<Pos> visited) {

// 不在地图里,不能移动
if (!inMap(map, pos)) {
return false;
}

// 空白格子,不能移动
if (!map[pos.getY()][pos.getX()]) {
return false;
}

// 已经在路径中或经过,不能移动
if (path.contains(pos) || visited.contains(pos)) {
return false;
}

return true;
}

/**
* 判断格子是否在地图内
*/
private static boolean inMap(boolean[][] map, Pos pos) {

if (pos.getY() < 0 || pos.getY() >= map.length) {
return false;
}

if (pos.getX() < 0 || pos.getX() >= map[0].length) {
return false;
}

return true;

}

接下来,就让我们在主函数里验证一下结果吧!

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
复制代码public static void main(String[] args) {

// 初始化参数
boolean[][] simpleMap = new boolean[][] {
{false, false, false, false, false, false, false, false, false},
{false, false, false, false, false, false, true , true , false},
{false, false, false, true , false, false, true , true , false},
{false, false, true , false, false, false, false, false, false},
{false, false, true , false, false, false, false, false, false},
{false, false, true , false, false, false, false, false, false},
{false, false, false, true , false, true , false, false, false},
{false, false, false, false, true , true , false, false, false},
{false, false, false, false, false, false, false, false, false}
};
Pos[] moveOffset = new Pos[] {
new Pos(-1, 0), // 向左移动
new Pos(-1, -1), // 向左上移动
new Pos( 0, -1), // 向上移动
new Pos( 1, -1), // 向右上移动
new Pos( 1, 0), // 向右移动
new Pos( 1, 1), // 向右下移动
new Pos( 0, 1), // 向下移动
new Pos(-1, 1) // 向左下移动
};
Pos start = new Pos(3, 3);

// 执行深度优先算法
List<Pos> longestPath = getLongestPathByDFS(simpleMap, start, moveOffset);

// 打印路径
System.out.println(longestPath);

}

执行Main函数之后,控制台将输出[Pos{x=3, y=2}, Pos{x=2, y=3}, Pos{x=2, y=4}, Pos{x=2, y=5}, Pos{x=3, y=6}, Pos{x=4, y=7}, Pos{x=5, y=6}, Pos{x=5, y=7}],即行走的最长路径。

虽然深度优先搜索算法可以计算出最长路径,但是它的时间复杂度却高得惊人!已知每次可以向8个方向移动,最多可以走m × n步(地图的长和宽),那么时间复杂度就是 O(8mn)。由于我们上面的地图可以走的选择比较单一,所以在我的电脑上1ms就可以算出结果。感兴趣的童鞋可以试试下面这个地图在你们的电脑上需要多久出结果:

1
2
3
4
5
6
7
8
9
10
11
复制代码boolean[][] complexMap = new boolean[][] {
{false, true, true, false, false, true, true, false, true},
{true, false, false, false, true, false, false, false, true},
{true, true, false, false, true, true, false, false, false},
{false, true, true, false, false, true, true, true, false},
{false, true, true, false, false, true, true, false, true},
{true, false, false, false, true, false, false, false, true},
{true, true, false, false, true, true, false, false, false},
{false, true, true, true, false, true, true, true, false},
{false, true, true, false, false, true, true, false, true}
};

至少,在我的电脑上需要5471ms才能得出结果,非常的夸张!由于产品线比赛要求每次计算时间不能超过1000ms,所以使用该算法基本不可行。那么是否有时间更快的算法呢?别走开,答案就在下面。


贪心算法

算法思想

贪心算法采用的是这样一种思想:每次都走出路最少的格子,这样后面可以选择的余地就比较大,最优解的概率也就大的多。

代码示例

下面便是贪心算法的代码:

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
复制代码/**
* 通过贪心算法获取最长路径
* @param map 地图
* @param start 起点
* @param moveOffset 移动偏移量
* @return 最长路径
*/
public static List<Pos> getLongestPathByChain(boolean[][] map, Pos start, Pos[] moveOffset) {

List<Pos> longestPath = new ArrayList<>();
chain(start, map, new ArrayList<>(), longestPath, moveOffset);
return longestPath;

}


/**
* 递归实现贪心算法
*/
private static void chain(Pos pos, boolean[][] map, List<Pos> path, List<Pos> result, Pos[] moveOffset) {

// 获取出路最小的格子
Pos minWayPos = getMinWayPos(pos, map, moveOffset);

if (minWayPos != null) {
// 递归搜寻路径
path.add(minWayPos);
map[minWayPos.getY()][minWayPos.getX()] = false;
chain(minWayPos, map, path, result, moveOffset);
} else {
// 当前无路可走时保存最长路径
if (path.size() > result.size()) {
result.clear();
result.addAll(path);
}
}

}

/**
* 获取当前格子周围出路最小的格子
*/
private static Pos getMinWayPos(Pos pos, boolean[][] map, Pos[] moveOffset) {

int minWayCost = Integer.MAX_VALUE;
List<Pos> minWayPoss = new ArrayList<>();

for (int i = 0; i < moveOffset.length; i++) {
Pos next = new Pos(pos.getX() + moveOffset[i].getX(), pos.getY() + moveOffset[i].getY());
if (inMap(map, next) && map[next.getY()][next.getX()]) {
int w = -1;
for (int j = 0; j < moveOffset.length; j++) {
Pos nextNext = new Pos(next.getX() + moveOffset[j].getX(), next.getY() + moveOffset[j].getY());
if (inMap(map, nextNext) && map[nextNext.getY()][nextNext.getX()]) {
w++;
}
}
if (minWayCost > w) {
minWayCost = w;
minWayPoss.clear();
minWayPoss.add(next);
} else if (minWayCost == w) {
minWayPoss.add(next);
}
}
}

if (minWayPoss.size() != 0) {
// 随机返回一个出路最小的格子
return minWayPoss.get((int) (Math.random() * minWayPoss.size()));
} else {
return null;
}

}

写好算法之后,再验证一下结果!

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
复制代码public static void main(String[] args) {

// 初始化参数
boolean[][] simpleMap = new boolean[][] {
{false, false, false, false, false, false, false, false, false},
{false, false, false, false, false, false, true , true , false},
{false, false, false, true , false, false, true , true , false},
{false, false, true , false, false, false, false, false, false},
{false, false, true , false, false, false, false, false, false},
{false, false, true , false, false, false, false, false, false},
{false, false, false, true , false, true , false, false, false},
{false, false, false, false, true , true , false, false, false},
{false, false, false, false, false, false, false, false, false}
};
Pos[] moveOffset = new Pos[] {
new Pos(-1, 0), // 向左移动
new Pos(-1, -1), // 向左上移动
new Pos( 0, -1), // 向上移动
new Pos( 1, -1), // 向右上移动
new Pos( 1, 0), // 向右移动
new Pos( 1, 1), // 向右下移动
new Pos( 0, 1), // 向下移动
new Pos(-1, 1) // 向左下移动
};
Pos start = new Pos(3, 3);

// 执行贪心算法
List<Pos> longestPath = getLongestPathByChain(simpleMap, start, moveOffset);

// 打印路径
System.out.println(longestPath);

}

执行Main函数之后,控制台将输出[Pos{x=3, y=2}, Pos{x=2, y=3}, Pos{x=2, y=4}, Pos{x=2, y=5}, Pos{x=3, y=6}, Pos{x=4, y=7}, Pos{x=5, y=7}, Pos{x=5, y=6}],路径长度与深度优先搜索算法一致,即也能找到最长路径。

那么在复杂一点的地图上,与深度优先搜索相比,贪心算法的结果怎么样呢?在我的机器上,计算结果如下:

simpleMap complexMap
深度优先搜索算法 最长路径为8步,计算时间为1ms 最长路径为33步,计算时间为5254ms
贪心算法 最长路径为8步,计算时间为1ms 最长路径为4/9/20步,计算时间为1ms

从结果上可以发现,由于贪心算法并没有遍历所有路径,而是每次都往出路最少的格子走,所以时间上快很多,但是其结果却非常地不稳定,这是因为贪心算法容易陷入局部最优解的情况!

显然如果用贪心算法来寻路吃果实,那么能不能打败敌人就要靠运气了。怎么办?是否有折中一点的算法,既耗费可接受的时间,又可以计算出较好的结果呢?答案还是肯定的,接下来就介绍更高端的算法——模拟退火算法。


模拟退火算法

算法思想

模拟退火算法的灵感是来自物理学里的固体退火原理:将固体加热时,固体内部粒子随温度上升变为无序状态,内能不断增大;当慢慢冷却时内部粒子逐渐有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。

用计算机语言来描述的话就是:在函数不断迭代的过程中,以一定的概率来接受一个比当前解要差的新解,因此有可能会跳出这个局部最优解,从而达到全局最优解。

代码示例

由于是高端算法,所以代码会比较多,但据说能看完模拟退火算法代码的人智商都超过180!

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
复制代码/**
* 通过模拟退火算法获取最长路径
* @param map 地图
* @param start 起点
* @param moveOffset 移动偏移量
* @return 最长路径
*/
public static List<Pos> getLongestPathBySA(boolean[][] map, Pos start, Pos[] moveOffset) {

// 初始化退火参数
double temperature = 100.0;
double endTemperature = 1e-8;
double descentRate = 0.98;
double count = 0;
double total = Math.log(endTemperature / temperature) / Math.log(descentRate);
int iterations = map.length * map[0].length;
List<Pos> longestPath = new ArrayList<>();
List<List<Pos>> paths = new ArrayList<>();
for (int i = 0; i < iterations; i++) {
boolean[][] cloneMap = deepCloneMap(map);
List<Pos> path = initPath(cloneMap, start, moveOffset);
paths.add(path);
}

// 降温过程
while (temperature > endTemperature) {

// 迭代过程
for (int i = 0; i < iterations; i++) {

// 取出当前解,并计算函数结果
List<Pos> path = paths.get(i);
int result = caculateResult(path);

// 在邻域内产生新的解,并计算函数结果
boolean[][] cloneMap = deepCloneMap(map);
List<Pos> newPath = getNewPath(cloneMap, path, moveOffset, count / total);
int newResult = caculateResult(newPath);

// 根据函数结果判断是否替换解
if (newResult - result < 0) {
// 替换
path.clear();
path.addAll(newPath);
} else {
// 以一定的概率替换
double p = 1 / (1 + Math.exp(-(newResult - result) / temperature));
if (Math.random() < p) {
path.clear();
path.addAll(newPath);
}
}

}

count++;
temperature = temperature * descentRate;

}

// 返回一条最长路径
for (int i = 0; i < paths.size(); i++) {
if (paths.get(i).size() > longestPath.size()) {
longestPath = paths.get(i);
}
}
return longestPath;

}

/**
* 深拷贝地图
*/
private static boolean[][] deepCloneMap(boolean[][] map) {
boolean[][] cloneMap = new boolean[map.length][];
for (int i = 0; i < map.length; i++) {
cloneMap[i] = map[i].clone();
}
return cloneMap;
}

/**
* 初始化路径
*/
private static List<Pos> initPath(boolean[][] map, Pos start, Pos[] moveOffset) {
List<Pos> path = new ArrayList<>();
getPath(map, start, path, moveOffset);
return path;
}

/**
* 根据当前路径继续移动到底,采用随机移动策略
*/
private static void getPath(boolean[][] map, Pos current, List<Pos> path, Pos[] moveOffset) {

boolean end = true;
List<Pos> neighbours = new ArrayList<>();
for (int i = 0; i < moveOffset.length; i++) {
Pos neighbour = new Pos(current.getX() + moveOffset[i].getX(), current.getY() + moveOffset[i].getY());
if (inMap(map, neighbour) && map[neighbour.getY()][neighbour.getX()]) {
end = false;
neighbours.add(neighbour);
}
}
if (end) {
return;
} else {
Pos random = neighbours.get((int) (Math.random() * neighbours.size()));
map[random.getY()][random.getX()] = false;
path.add(random);
getPath(map, random, path, moveOffset);
}

}

/**
* 计算函数结果,函数结果为路径负长度
*/
private static int caculateResult(List<Pos> path) {
return -path.size();
}


/**
* 根据当前路径和降温进度,生成一条新路径
*/
private static List<Pos> getNewPath(boolean[][] map, List<Pos> path, Pos[] moveOffset, double ratio) {

int size = (int) (path.size() * ratio);
if (size == 0) {
size = 1;
}
if (size > path.size()) {
size = path.size();
}

List<Pos> newPath = new ArrayList<>();
for (int i = 0; i < size; i++) {
Pos pos = path.get(i);
newPath.add(pos);
map[pos.getY()][pos.getX()] = false;
}

getPath(map, newPath.get(newPath.size() - 1), newPath, moveOffset);
return newPath;

}

测试代码我就不再列出了,最后让我们看一下这三种算法在两个地图上的执行结果:

simpleMap complexMap
深度优先搜索算法 最长路径为8步,计算时间为1ms 最长路径为33步,计算时间为5254ms
贪心算法 最长路径为8步,计算时间为1ms 最长路径为4/9/20步,计算时间为1ms
模拟退火算法 最长路径为8步,计算时间为147ms 最长路径为30~33步,计算时间为212ms

总结

求最长路径问题可以看成是哈密尔顿路径问题,由于寻找哈密尔顿路径是一个典型的NPC问题,所以不能在多项式时间内得到最优解。感兴趣的小伙伴可以去了解一下相关的知识,我在参考阅读章节给出了几个相应的链接。

解决这类问题,我们可以通过深度优先搜索算法得到最优解,但是时间复杂度是指数级的;也可以通过贪心算法得到一个局部最优解,其时间复杂度是线性级的,但得到的解时好时坏;还可以通过模拟退火算法得到一个近似解,这个时间复杂度也是线性级的,只要退火参数配置得当,其解是稳定地,且是一个趋向最优解的近似解。


参考阅读

[1] 哈密顿图 - 维基百科

[2] 贪婪算法求解哈密尔顿路径问题 - 51CTO博客

[3] 什么是P问题、NP问题和NPC问题

[4] 最长路径问题 - 维基百科

[5] 模拟退火 - 维基百科

[6] 大白话解析模拟退火算法 - 博客园


本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

1…952953954…956

开发者博客

9558 日志
1953 标签
RSS
© 2025 开发者博客
本站总访问量次
由 Hexo 强力驱动
|
主题 — NexT.Muse v5.1.4
0%