2018

Python函式的參數設計 – Python Function Parameters

2018 年 10 月 18 日2018 年 11 月 26 日
Python

parameter跟argument的差異

基本上這兩者是一樣的，不過使用在不同的情境下。如果混用了其實是沒關係，可能也沒人會在意

不過值得一提的是以上這個範例的兩個參數在Module Scope跟Function Scope中都是指向同一個記憶體位置

可迭代物件的拆解機制(unpacking)

可迭代的物件都能拆解，很適合用在參數傳遞（主要使用在有序物件上）

a, b = ['A', 'B'] # list

a, b = 'A', 'B' # tuple

a, b = 'AB' # str

a, b = {'A', 'B'} # set 注意這裡會有兩種結果

a, b = {'A': 10, 'B': 20} # dict 注意這裡會有兩種結果

超簡單實現swap

傳統的作法

a = 10

b = 20

tep = a

a = b

b = temp

unpacking的作法

a = 10

b = 20

a, b = b, a

使用`*`和`**`（3.5以上適用）

*a = 'python'

a, *b, c = 1, 2, 3, 4

l1 = [1, 2, 3]

l2 = 'XYZ'

l = [*l1, *l2]

s1 = {1, 2, 3}

s2 = {4}

# merge set

s = {*s1, *s2}

d1 = {'a': 1, 'b': 2}

d2 = {'c': 3}

d3 = {'a': 0}

# merge dictionary

d = {**d1, **d2, **d3} # 注意這裡a的值會被覆寫

d = {**d1, a: 0} # 注意這裡a的值會被覆寫

unpacking範例

巢狀的unpacking

a, b, (c, d) = [1, 2, [3, 4]]

a, *b, (c, d, e) = [1, 2, 3, 'XYZ']

a, *b, (c, *d) = [1, 2, 3, 'python'] # a=1, b=[2, 3], c='p', d=['y', 't', 'h', 'o', 'n']

以Python實作資料結構 – Data Structure Implements in Python

2018 年 10 月 17 日2022 年 11 月 30 日
Python

以Python實作資料結構

tags: `data-structure`, `python`

簡介
陣列 Array
連結串列 Linked List & 雙向連結串列 Double Linked List
堆疊 Stack
佇列 Queue
二元搜尋樹 Binary Search Tree
平衡二元搜尋樹 Balancing Binary Search Tree, AVL Tree
紅黑樹 Red-Black Tree
二元堆積 Binary Heap
關聯陣列/對映/字典 Associative Array/ Map/ Dictionary
三元搜尋樹 Ternary Search Tree

簡介

什麼是資料結構？為什麼要使用資料結構？

是電腦中儲存、組織資料的方式，可以讓我們有效地儲存資料，並讓所有運算能最有效率地完成

演算法的運行時間是根據資料結構決定的，所以使用適當的資料結構來降低演算法的時間複雜度，如：

最短路徑演算法若無適當的資料結構，運行時間是O(N^2)，使用(heap/priority queue)可以大幅降低運行時間至O(N*logN)

抽象資料型態 Abstract Data Types

簡單而言，ADT是針對資料結構的「規範」或「描述」，像是物件導向語言裡面的interface，但不會實作細節

舉例堆疊的ADT描述：

push(): 插入元素 item 至堆疊頂端
pop(): 移除並回傳堆疊頂端的元素
peek(): 看堆疊頂端的資料而不取出
size(): 看堆疊的長度

ADT跟資料結構的關係

每個ADT在底層都有相對應的資料結構去實作ADT裡定義過的行為(method)

ADT	Data Structures
Stack	array, linked list
Queue	array, linked list
Priority Queue	heap
Dictionary/Hashmap	array

時間複雜度 Big O notation

描述演算法的效率（複雜度），舉例來說，A宅想要分享他的D槽給B宅，有以下幾種做法：

從台北騎車到屏東B宅家
用網路傳輸，不考慮被FBI攔截的情況

	1GB	1TB	500TB
騎車運送硬碟	600 min	600 min	600 min
網路傳輸	3 min	3072 min	1536000 min

從上表來看，騎車這個選項雖然聽起來很蠢，但不管硬碟有多大，都能確保10個小時內可以送達—— O(1)；至於網路傳輸隨著檔案越大，所需的時間也越長 —— O(N)；從這裡就可以看出常數時間(constant time)和線性時間(linear time)的差別對效率的影響有多大了

在表現複雜度函數的時候，有幾個通用的規則：

多個步驟用加法: O(a+b)

def func():

# step a

# step b

省略常數: ~~O(3n)~~ O(n)

def func(lst):

for i in lst: # O(n)

# do something ...

for i in lst: # O(n)

# do something ...

for i in lst: # O(n)

# do something ...

不同的input用不同的變數表示: ~~O(N^2)~~ O(a*b)

def func(la, lb):

for a in la:

for b in lb:

# do something ...

省略影響不大的變數: ~~O(n+n^2)~~ O(n^2)

1 2	O(n^2) <= O(n+n^2) <= O(n^2 + n^2)

# n^2是主導的變項，所以省略n

def func(la):

for a in la: # O(n)

# do something ...

for a in la: # O(n^2)

for b in la:

# do something

陣列 Array

物件或值的集合，每個物件或值可以被陣列的索引(index, key)識別

索引從0開始
因為有索引，我們可以對陣列做隨機存取(Random Access)

優點：

隨機存取不用搜尋就能訪問陣列當中所有值，執行速度快O(1)
不會因為鏈結斷裂而遺失資料
循序存取快

缺點：

重建或插入陣列須要逐一複製裏頭的值，時間複雜度是O(N)
編譯的時候必須事先知道陣列的大小，這讓陣列這個資料結構不夠動態(dynamic)
通常陣列只能存同一種型別
不支援連結串列的共享

Implements

	行為	big O
search	搜尋	O(1)
insert	插入第一項	O(N)
append	插入最後一項	O(1)
remove	移除第一項	O(N)
removeLast	移除最後一項	O(1)

以Python實作

random indexing: O(1)

arr = [1, 2, 3]

arr[0]

linear search: O(n)

max = arr[0]

for i in arr:

if i > max:

max = i

連結串列 Linked List & 雙向連結串列 Double Linked List

節點包含data和referenced object
連結的方式是節點(node)記住其他節點的參考(reference)
最後一個節點的參考是NULL

優點

各節點型態、記憶體大小不用相同
動態佔用的記憶體，不須事先宣告大小
插入、刪除快O(1)

缺點

不支援隨機存取，只能循序存取(sequencial access)，時間複雜度為O(N)
須額外空間儲存其他節點的參考
可靠性較差，連結斷裂容易遺失資料
難以向前(backward)訪問，可以用雙向連結串列來處理，不過會多佔用記憶體空間

Implements

	行為	big O
search	搜尋	O(N)
insert	插入第一項	O(1)
append	插入最後一項	O(N)
remove	移除第一項	O(1)
removeLast	移除最後一項	O(N)

註：連結串列沒有index，處理插入或移除第N項會需要先循序找到插入/移除位置，因此會需要O(N)的時間

以Python實作

以下的代碼是我實作的範例，有錯誤煩請指正。

主要概念是實作__getitem__來循序存取(indexing)，另外Double Linked List支援反向存取，故訪問lst[0]和lst[-1]皆可以達成O(1)的時間複雜度

執行結果請參考travishen/gist/linked-list.md

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

from collections import Iterable

class Node:

def __init__(self, data=None, next_node=None):

self.data = data

self.next_node = next_node

def __repr__(self):

return 'Node(data={!r}, next_node={!r})'.format(self.data, self.next_node)

class LinkedList(object):

def __init__(self, inital_nodes=None):

self.head = None

self.inital_nodes = inital_nodes

# garbage collect

for node in self:

del node

if isinstance(inital_nodes, Iterable):

for node in reversed(list(inital_nodes)):

self.insert(node) # insert to head

elif inital_nodes:

raise NotImplementedError('Inital with not iterable object')

def __repr__(self):

return 'LinkedList(inital_nodes={!r})'.format(self.inital_nodes)

def __len__(self):

count = 0

for node in self:

count += 1

return count

def __setitem__(self, index, data):

self.insert(data, index)

def __delitem__(self, index):

self.remove(index, by='index')

def __getitem__(self, index):

count = 0

current = self.head

index = self.positive_index(index)

while count < index and current is not None:

current = current.next_node

count += 1

if current:

return current

else:

raise IndexError

def positive_index(self, index): # inplement negative indexing

"""

Use nagative indexing will increase O(N) time complexity

We can improve it with double linded list

"""

if index < 0:

index = len(self) + index

return index

def insert(self, data, index=0):

index = self.positive_index(index)

if self.head is None: # initial

self.head = Node(data, None)

elif index == 0: # insert to head

new_node = Node(data, self.head)

self.head = new_node

else: # insert to lst[index]

last_node = self[index]

last_node.next_node = Node(data, last_node.next_node)

return None # this instance has changed and didn't create instance

def search(self, data):

for node in self:

if node.data == data:

return node

return None

def remove(self, data_or_index, by='data'):

for i, node in enumerate(self):

if (by == 'data' and node.data == data_or_index) or (by == 'index' and i == data_or_index):

if i == 0:

self.head = node.next_node

node.next_node = None

else:

prev_node.next_node = node.next_node

break

prev_node = node

return None # this instance has changed and didn't create instance

class DoubleLinkedNode(Node):

def __init__(self, data=None, last_node=None, next_node=None):

self.data = data

self.next_node = next_node

self.last_node = last_node

if next_node:

next_node.last_node = self

class DoubleLinkedList(LinkedList):

def __init__(self, *args, **kwargs):

self.foot = None

super(DoubleLinkedList, self).__init__(*args, **kwargs)

def __repr__(self):

return 'DoubleLinkedList(inital_nodes={})'.format(self.inital_nodes)

def __getitem__(self, index):

"""

Support negative indexing in O(N) by setting footer

"""

count = 0

if index >= 0:

current = self.head

while count < index and current is not None:

current = current.next_node

count += 1

else:

current = self.foot

while count > (index + 1) and current is not None:

current = current.last_node

count -= 1

if current:

return current

else:

raise IndexError

def insert(self, data, index=0):

if self.head is None: # initial

self.head = self.foot = DoubleLinkedNode(data, None, None)

elif index == 0: # insert to head

new_node = DoubleLinkedNode(data, None, self.head)

self.head = new_node

else: # insert to lst[index]

last_node = self[index]

last_node.next_node = DoubleLinkedNode(data, last_node, last_node.next_node)

if last_node.next_node.next_node is None: # set foot

self.foot = last_node.next_node

return None # this instance has changed and didn't create instance

Linked List現實中的應用

低級別的內存管理（Low Level Memory Management），以C語言為例：

malloc()、 free(): 見Heap Management
chart * chart_ptr = (chart*)malloc(30);: 取得30byte的heap memory

許多Windows的應用程式：工具列視窗切換、PhotoViewer
區塊鏈技術

[圖片來源]

堆疊 Stack

推疊是一種抽象資料型態，特性是先進後出（LIFO, last in first out）
在高階程式語言，容易用array、linked list來實作
大部分的程式語言都是Stack-Oriented，因為仰賴堆疊來處理method call(呼叫堆疊, Call Stack)。

Implements

	行為	big O
push	將資料放入堆疊的頂端	O(1)
pop	回傳堆疊頂端資料	O(1)
peek	看堆疊頂端的資料而不取出	O(1)

應用

call stack + stack memory
深度優先搜尋演算法（Depth-First-Search）
尤拉迴路（Eulerian Circuit）
瀏覽器回上一頁
PhotoShop上一步(undo)

註：任何遞迴(recursion)形式的演算法，都可以用Stack改寫，例如DFS。不過就算我們使用遞迴寫法，程式最終被parsing還是Stack

def factorial(n, cache={}):

if n == 0: # declare base case to prevent stack overflow

return 1

return n * factorial(n-1)

Stack memory vs Heap memory

stack memory	heap memory
有限的記憶體配置空間	記憶體配置空間較大
存活時間規律可預測的	存活時間不規律不可預測的
CPU自動管理空間(GC)	使用者自主管理空間
區域變數宣告的空間不能更動	物件的值可以變動，如realloc()

以Python實作

class Stack(object):

def __init__(self, initial_data):

self.stack = []

self.initial_data = initial_data

if isinstance(initial_data, Iterable):

self.stack = list(initial_data)

else:

raise NotImplementedError('Inital with not iterable object')

def __repr__(self):

return 'Stack(initial_data={!r})'.format(self.initial_data)

def __len__(self):

return len(self.stack)

def __getitem__(self, i):

return self.stack[i]

@property

def is_empty(self):

return len(self.stack) == 0

def push(self, data):

self.stack.append(data)

def pop(self):

if not self.is_empty:

return self.stack.pop()

def peek(self):

return self.stack[-1]

Using Lists as Stacks

>>> stack = [3, 4, 5]

>>> stack.append(6)

>>> stack.append(7)

>>> stack

[3, 4, 5, 6, 7]

>>> stack.pop()

>>> stack

[3, 4, 5, 6]

>>> stack.pop()

>>> stack

[3, 4]

佇列 Queue

佇列是一種抽象資料型態，特性是先進先出（FIFO, first in first out）
在高階程式語言，容易用array、linked list來實作

應用

多個程序的資源共享，例如CPU排程
非同步任務佇列，例如I/O Buffer
廣度優先搜尋演算法（Depth-First-Search）

以Python實作

class Queue(object):

def __init__(self, initial_data):

self.queue = []

self.initial_data = initial_data

if isinstance(initial_data, Iterable):

self.queue = list(initial_data)

else:

raise NotImplementedError('Inital with not iterable object')

def __repr__(self):

return 'Queue(initial_data={!r})'.format(self.initial_data)

def __len__(self):

return len(self.queue)

def __getitem__(self, i):

return self.queue[i]

@property

def is_empty(self):

return len(self.queue) == 0

def enqueue(self, data):

return self.queue.append(data)

def dequeue(self):

return self.queue.pop(0)

def peek(self):

return self.queue[0]

參考

multiprocessing實作的的Queue
Using Lists as Queues

>>> from collections import deque

>>> queue = deque(["Eric", "John", "Michael"])

>>> queue.append("Terry") # Terry arrives

>>> queue.append("Graham") # Graham arrives

>>> queue.popleft() # The first to arrive now leaves

'Eric'

>>> queue.popleft() # The second to arrive now leaves

'John'

>>> queue # Remaining queue in order of arrival

deque(['Michael', 'Terry', 'Graham'])

二元搜尋樹 Binary Search Tree

主要的優點就是時間複雜度能優化至O(logN)

每個節點最多有兩個子節點
子節點有左右之分
左子樹的節點小於根節點、右子樹的節點大於根節點
節點值不重複

	Average case	Worst case
insert	O(logN)	O(N)
delete	O(logN)	O(N)
search	O(logN)	O(N)

以Python實作insert, remove, search，執行結果請參考gist

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

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

class Node(object):

def __init__(self, data):

self._left, self._right = None, None

self.data = int(data)

def __repr__(self):

return 'Node({})'.format(self.data)

@property

def left(self):

return self._left

@left.setter

def left(self, node):

self._left = node

@property

def right(self):

return self._right

@right.setter

def right(self, node):

self._right = node

class BinarySearchTree(object):

def __init__(self, root=None):

self.root = root

self.search_mode = 'in_order'

# O(logN) time complexity if balanced, it could reduce to O(N)

def insert(self, data, **kwargs):

"""Insert from root"""

BinarySearchTree.insert_node(self.root, data, **kwargs)

# O(logN) time complexity if balanced, it could reduce to O(N)

def remove(self, data):

"""Insert from root"""

BinarySearchTree.remove_node(self.root, data)

@staticmethod

def insert_node(node, data, **kwargs):

node_consturctor = kwargs.get('node_constructor', None) or Node

if node:

if data < node.data:

if node.left is None:

node.left = node_consturctor(data)

else:

BinarySearchTree.insert_node(node.left, data, **kwargs)

elif data > node.data:

if node.right is None:

node.right = node_consturctor(data)

else:

BinarySearchTree.insert_node(node.right, data, **kwargs)

else:

node.data = data

return node

@staticmethod

def remove_node(node, data):

if not node:

return None

if data < node.data:

node.left = BinarySearchTree.remove_node(node.left, data)

elif data > node.data:

node.right = BinarySearchTree.remove_node(node.right, data)

else:

if not (node.left and node.right): # leaf

del node

return None

if not node.left:

tmp = node.right

del node

return tmp

if not node.right:

tmp = node.left

del node

return tmp

predeccessor = BinarySearchTree.get_max_node(node.left)

node.data = predeccessor.data

node.left = BinarySearchTree.remove_node(node.left, predeccessor.data)

return node

def get_min(self):

return self.get_min_node(self.root)

@staticmethod

def get_min_node(node):

if node.left:

return BinarySearchTree.get_max_node(node.left)

return node

def get_max(self):

return self.get_max_node(self.root)

@staticmethod

def get_max_node(node):

if node.right:

return BinarySearchTree.get_max_node(node.right)

return node

def search_decorator(func):

def interface(*args, **kwargs):

res = func(*args, **kwargs)

if isinstance(res, Node):

return res

elif 'data' in kwargs:

for node in res:

if node.data == kwargs['data']:

return node

return res

return interface

@staticmethod

@search_decorator

def in_order(root, **kwargs):

"""left -> root -> right"""

f = BinarySearchTree.in_order

res = []

if root:

left = f(root.left, **kwargs)

if isinstance(left, Node):

return left

right = f(root.right, **kwargs)

if isinstance(right, Node):

return right

res = left + [root] + right

return res

@staticmethod

@search_decorator

def pre_order(root, **kwargs):

"""root -> left -> right"""

f = BinarySearchTree.pre_order

res = []

if root:

left = f(root.left, **kwargs)

if isinstance(left, Node):

return left

right = f(root.right, **kwargs)

if isinstance(right, Node):

return right

res = [root] + left + right

return res

@staticmethod

@search_decorator

def post_order(root, **kwargs):

"""root -> right -> root"""

f = BinarySearchTree.post_order

res = []

if root:

left = f(root.left, **kwargs)

if isinstance(left, Node):

return left

right = f(root.right, **kwargs)

if isinstance(right, Node):

return right

res = left + right + [root]

return res

def traversal(self,

order:"in_order|post_order|post_order"=None,

data=None):

order = order or self.search_mode

if order == 'in_order':

return BinarySearchTree.in_order(self.root, data=data)

elif order == 'pre_order':

return BinarySearchTree.pre_order(self.root, data=data)

elif order == 'post_order':

return BinarySearchTree.post_order(self.root, data=data)

else:

raise NotImplementedError()

def search(self, data, *args, **kwargs):

return self.traversal(*args, data=data, **kwargs)

BST現實中的應用

OS file system
機器學習：決策樹

平衡二元搜尋樹 Balancing Binary Search Tree, AVL Tree

能保證O(logN)的時間複雜度
每次insert, delete都要檢查平衡，非平衡需要額外做rotation
判斷是否平衡：
- 左子樹高度 - 右子樹高度 > 1: rotate to right
- 左子樹高度 - 右子樹高度 < -1: rotate to left

	Average case	Worst case
insert	O(logN)	O(logN)
delete	O(logN)	O(logN)
search	O(logN)	O(logN)

不適合用在排序，時間複雜度為O(N*logN)

插入n個：O(N*logN)
in-order迭代：O(N)

繼承上面BST繼續往下實作，有bug請協助指正，執行結果請參考gist

任一節點設定完left或right，更新該節點height
每個insert的call stack檢查檢查節點是否平衡，不平衡則rotate

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

class HNode(Node):

def __init__(self, *args, **kwargs):

super(HNode, self).__init__(*args, **kwargs)

self._height = 0

def __repr__(self):

return 'HNode({})'.format(self.data)

@property

def height(self):

return self._height

def set_height(self):

if self.left is None and self.right is None:

self._height = 0

else:

self._height = max(self.left_height, self.right_height) + 1

return self._height

@Node.left.setter

def left(self, node):

self._left = node

self.set_height()

@Node.right.setter

def right(self, node):

self._right = node

self.set_height()

@property

def sub_diff(self):

return self.left_height - self.right_height

@property

def left_height(self):

if self.left:

return self.left.height

return -1

@property

def right_height(self):

if self.right:

return self.right.height

return -1

@property

def is_balance(self):

return abs(self.sub_diff) <= 1

def balance(self, data):

if self.sub_diff > 1:

if data < self.left.data: # left left heavy

return self.rotate('right')

if data > self.left.data: # left right heavy

self.left = self.left.rotate('left')

return self.rotate('right')

if self.sub_diff < -1:

if data > self.right.data:

return self.rotate('left') # right right heavy

if data < self.right.data: # right left heavy

self.right = self.right.rotate('right')

return self.rotate('left')

return self

def rotate(self, to:"left|right"):

if to == 'right':

tmp = self.left

tmp_right = tmp.right

# update

tmp.right = self

self.left = tmp_right

print('Node {} right rotate to {}!'.format(self, tmp))

return tmp # return new root

if to == 'left':

tmp = self.right

tmp_left = tmp.left

# update

tmp.left = self

self.right = tmp_left

print('Node {} left rotate to {}!'.format(self, tmp))

return tmp # return new root

raise NotImplementedError()

class AVLTree(BinarySearchTree):

def __init__(self, *args, **kwargs):

super(AVLTree, self).__init__(*args, **kwargs)

def insert(self, data):

AVLTree.insert_node(self.root, data, tree=self) # pass self as keyword argument to update self.root

self.update_height()

def remove(self, data):

AVLTree.remove_node(self.root, data, tree=self) # pass self as keyword argument to update self.root

self.update_height()

def rotate_decorator(func):

def interface(*args, **kwargs):

node = func(*args, **kwargs)

data = args[1]

tree = kwargs.get('tree')

new_root = node.balance(data)

if node == tree.root:

tree.root = new_root

return interface

def update_height(self):

for n in self.traversal(order='in_order'):

n.set_height()

@property

def is_balance(self):

return self.root.is_balance

@rotate_decorator

def insert_node(*args, **kwargs):

return BinarySearchTree.insert_node(*args, node_constructor=HNode, **kwargs)

@rotate_decorator

def remove_node(*args, **kwargs):

return BinarySearchTree.remove_node(*args, **kwargs)

紅黑樹 Red-Black Tree

相較於AVL樹，紅黑樹犧牲了部分平衡性換取插入/刪除操作時更少的翻轉操作，整體效能較佳（插入、刪除快）
不像AVL樹的節點屬性用height來判斷是否須翻轉，而是用紅色/黑色來判斷
- 根節點、末端節點（NULL）是黑色
- 紅色節點的父節點和子節點是黑色
- 每條路徑上黑色節點的數量相同
- 每個新節點預設是紅色，若違反以上規則：
- 翻轉，或
- 更新節點顏色

	Average case	Worst case
insert	O(logN)	O(logN)
delete	O(logN)	O(logN)
search	O(logN)	O(logN)

github上用python實作的範例：Red-Black-Tree

優先權佇列 Priority Queue

相較於Stack或Queue，對資料項目的取出順序是以權重(priority)來決定
常用heap來實作

二元堆積 Binary Heap

是一種二元樹資料結構，通常透過一維陣列(one dimension array)
根據排序行為分成min及max：
- max heap: 父節點的值(value)或權重(key)大於子節點
- min heap: 父節點的值(value)或權重(key)小於子節點
必須是完全(compelete)二元樹或近似完全二元樹

註：

heap資料結構跟heap memory沒有關聯
優勢在於取得最大權重或最小權重項目(root)，時間複雜度為O(1)

	time complexity
insert	O(N) + O(logN) reconsturct times
delete	O(N) + O(logN) reconsturct times

應用

堆積排序法（Heap Sort）
普林演算法（Prim’s Algorithm）
戴克斯特拉演算法（Dijkstra’s Algorithm）

堆積排序 Heapsort

是一種比較排序法（Comparision Sort）
主要優勢在於能確保O(NlogN)的時間複雜度
屬於原地演算法(in-place algorithm)，缺點是每次排序都須重建heap——增加O(N)時間複雜度
在一維陣列起始位置為0的indexing:

用Python實作Max Binary Heap，請參考gist

class Heap(object):

"""Max Binary Heap"""

def __init__(self, capacity=10):

self._default = object()

self.capacity = capacity

self.heap = [self._default] * self.capacity

def __len__(self):

return len(self.heap) - self.heap.count(self._default)

def __getitem__(self, i):

return self.heap[i]

def insert(self, item):

"""O(1) + O(logN) time complexity"""

if self.capacity == len(self): # full

return

self.heap[len(self)] = item

self.fix_up(self.heap.index(item)) # check item's validation

def fix_up(self, index):

"""

O(logN) time complexity

Violate:

1. child value > parent value

"""

parent_index = (index-1)//2

if index > 0 and self.heap[index] > self.heap[parent_index]:

# swap

self.swap(index, parent_index)

self.fix_up(parent_index) # recursive

def fix_down(self, index):

"""

O(logN) time complexity

Violate:

1. child value > parent value

"""

parent = self.heap[index]

left_child_index = 2 * index + 1

right_child_index = 2 * index + 2

largest_index = index

if left_child_index < len(self) and self.heap[left_child_index] > parent:

largest_index = left_child_index

if right_child_index < len(self) and self.heap[right_child_index] > self.heap[largest_index]:

largest_index = right_child_index

if index != largest_index:

self.swap(index, largest_index)

self.fix_down(largest_index) # recursive

def heap_sort(self):

"""

O(NlogN) time complixity

"""

for i in range(0, len(self)):

self.poll()

def swap(self, i1, i2):

self.heap[i1], self.heap[i2] = self.heap[i2], self.heap[i1]

def poll(self):

max_ = self.max_

self.swap(0, len(self) - 1) # swap first and last

self.heap[len(self) - 1] = self._default

self.fix_down(0)

return max_

@property

def max_(self):

return self.heap[0]

python build-in heapq

關聯陣列/對映/字典 Associative Array/ Map/ Dictionary

鍵、值的配對(key-value)
相較於樹狀資料結構，劣勢在於排序困難
主要操作：
- 新增、刪除、修改值
- 搜尋已知的鍵

hash function

division method: modulo operator

h(x) = n % m

n: number of keys, m: number of buckets

Collision

當多個key存取同一個bucket（slot），解決collision會導致時間複雜度提高

h(26) = 26 mod 6 = 2

h(50) = 50 mod 6 = 2

解法：

chaining: 在同一個slot用linked list存放多個關聯
open addressing: 分配另一個空的slot
- linear probing: 線性探測
- quadratic probing: 二次方探測，如1, 2, 4, 8…
- rehashing

Dynamic resizing

load factor（佔用率）: n / m

load factor會影響到存取的效能，因此須要根據使用率動態變更陣列大小；
舉例來說，Java觸發resize的時機點大約是佔用超過75%時、Python則約是66%

應用

資料庫
Network Routing
Rabin-Karp演算法
Hashing廣泛用於資料加密

以Python實作，請參考gist

from collections import Iterable

from functools import reduce

class HashTable(object):

def __init__(self, size=10):

self.size = 10

self.keys = [None] * self.size

self.values = [None] * self.size

def __repr__(self):

return 'HashTable(size={})'.format(self.size)

def put(self, key, value):

index = self.hash(key)

while self.keys[index] is not None: # collision

if self.keys[index] == key: # update

self.values[index] = value

return

index = (index + 1) % self.size # rehash

self.keys[index] = key

self.values[index] = value

def get(self, key):

if key in self.keys:

return self.values[self.hash(key)]

return None

def hash(self, key):

if isinstance(key, Iterable):

sum = reduce(lambda prev, n: prev + ord(n), key, 0)

else:

sum = key

return sum % self.size

	Average case	Worst case
insert	O(1)	O(N)
delete	O(1)	O(N)
search	O(1)	O(N)

三元搜尋樹 Ternary Search Tree, TST

相較其他樹狀資料結構而言，佔用記憶體空間較小
只儲存string，不存NULL或其他物件
父節點可以有3個子節點：left(less)、middle(equal)、right(greater)
可以同時用來當作hashmap使用，也可以做排序
效能上比hashmap更佳，在解析key時是漸進式的（如cat若root沒有c就不用繼續找了）

應用

autocompelete
拼字檢查
最近鄰居搜尋（Near-neighbor）
WWW package routing
最長前綴匹配(perfix matching)
Google Search

以Python實作，請參考gist

class Node(object):

def __init__(self, char):

self.char = char

self.left = self.middle = self.right = None

self.value = None

class TernarySearchTree(object):

def __init__(self):

self.root = None

def __repr__(self):

return 'TernarySearchTree()'

def put(self, key, value):

self.root = self.recursive(key, value)(self.root, 0)

def get(self, key):

node = self.recursive(key)(self.root, 0)

if node:

return node.value

return -1

def recursive(self, key, value=None):

def putter(node, index):

char = key[index]

if node is None:

node = Node(char)

if char < node.char:

node.left = putter(node.left, index)

elif char > node.char:

node.right = putter(node.right, index)

elif index < len(key) - 1:

node.middle = putter(node.middle, index+1)

else:

node.value = value

return node

def getter(node, index):

char = key[index]

if node is None:

return None

if char < node.char:

return getter(node.left, index)

elif char > node.char:

return getter(node.right, index)

elif index < len(key) - 1:

return getter(node.middle, index+1)

else:

return node

if value:

return putter

else:

return getter

互斥集 Disjoint sets / union-find data structure

一堆沒有交集的集合，如10個學生分成4組
主要操作: union、find、makeSet
通常以linked list或tree來實作
訪問disjoint set中的任何節點都回傳同一個root value

set在union過程中會遇到不平衡的問題，有兩種最佳化方法：

union by rank: 讓小的樹接到較大的樹
path compression: 訪問節點時調整樹的結構，直接與root連結

應用

Kruskal: 檢查圖中是否有cycle

以Python實作，輸出請參考gist

class Edge:

"""Sortable edge in the graph"""

def __init__(self, weight, start, target):

self.weight = weight

self.start = start # Node

self.target = target # Node

def __repr__(self):

return 'Edge(weight={}, start={}, target={})'.format(self.weight,

self.start,

self.target)

def __cmp__(self, other):

return self.cmp(self.weight, other.weight)

def __lt__(self, other):

return self.weight < other.weight

class Node:

"""Node live in a graph / disjoint set"""

def __init__(self, name):

self.name = name

self.parent = None

self.set_ = None

def __repr__(self):

return self.name

parent = None

if self.parent:

parent = self.parent.name

return 'Node(name={}, parent={})'.format(self.name, parent)

class DisjointSet:

"""Represent a disjoint set"""

def __init__(self, node):

"""make set"""

self.nodes = set([node])

self.root = node

self.root.set_ = self

def __str__(self):

if not self.nodes:

return 'Empty'

return str(self.nodes)

def __len__(self):

return len(self.nodes)

@staticmethod

def find(node):

"""Find root node in nodes and do path compression"""

root = node

while root.parent is not None:

root = root.parent

# path compression

while node is not root:

temp = node.parent

node.parent = root

node = temp

return root

@staticmethod

def merge(s1, s2):

"""Merge two set base on """

if s1 is s2: # is equal

return

if len(s1) < len(s2): # s1 --> s2

s1.root.parent = s2.root

for n in s1.nodes: # point all node to new set

n.set_ = s2

s2.nodes.update(s1.nodes)

s1.nodes = set()

else: # s2 --> s1

s2.root.parent = s1.root

for n in s2.nodes: # point all node to new set

n.set_ = s1

s1.nodes.update(s2.nodes)

s2.nodes = set()

Docker基礎介紹與實戰

2018 年 10 月 17 日2019 年 7 月 17 日
Ops

Docker簡介

Docker是2013年由DotCloud開發的開源專案，因為軟體的成功，公司之後也改名為Docker.Inc
其實Docker的前身是象龜(@gordonTheTurtle)，之後改成鯨魚

Docker的重要性

容器將會是未來最有影響力的基礎架構
不管你是開發、維運、系統管理、部屬都會須要學一下
成長最快的雲端技術
Infrastructure as code

Docker的優點

過去底層的基礎架構都是為sysops或sysadmins設計的，但Docker的解決方案考慮了developer的使用情境
就是快：develop faster, build faster, test faster, deploy faster, update faster, recover faster
使用容器來減少不同應用程式、不同系統、不同相依性的複雜度
大部分現存的軟體開發得少維護得多，Docker可以減輕我們維護的難度，增加開發的時間

安裝前要注意的

在不同環境下的安裝：

Linux: 直接安裝，不過有分版本
Windows: Win10不直接支援，需要透過virtual machine來安裝，在安裝的流程中會設定到；因為Windows Containers的出現，新的Windows Server 2016之後會開始直接支援Docker，不用再透過Linux Container
Mac: 也是要透過vm，據說不要用brew來裝
Cloud: Docker for GCP/AWS/Azure

看更多有關windows container：

Stable vs Edge(beta)

開源版本的Edge每個月會更新一次，Stable大概四個月更新一次，付費的企業版本會有更穩定的支援

安裝

Windows 10 Pro / Enterprise

使用Pro跟Enterprice的用戶算是比較吃香，會有比較好的體驗
請在此下載安裝Docker for Windows
命令界面(CLI)會建議使用PowerShell
如果你的系統已經有在使用VirtualBox或VMware，Hyper-V啟用可能會發生資源互搶的問題

Windows 7, 8, or 10 Home Edition

Win7, 8與Pro/Enterprise的主要差別是Hyper-V過舊不支援，Win10 Home則是沒有Hyper-V，因此要額外安裝Docker Toolbox，然後透過VirtualBox安裝Linux VM(Linux Container)，也就是 docker-machine 使用網路位址轉換(NAT)存取網路
需要把Toolbox的 http://localhost 改成 http://192.168.99.100

Mac

OSX Yosemite 10.10.3以下版本的需要裝Toolbox，以上版本安裝Docker for Mac

Linux

不要用系統預設的packages直接下指令安裝，例如 apt install docker.io，你可能會裝到過舊的版本
可以經由Docker automated script來安裝相依的程式，例如 curl -ssl https://get.docker.com/ | sh
或者先看過官網上的要求來手動下載安裝檔

1 2	$ sudo curl -ssl https://get.docker.com/ \| sh

Docker會動用到系統核心的功能，需要root權限來操作你可以將使用者加入Docker group，註：有些版本的linux如Red Hat, Fedora沒有此選項，每個指令都要透過 sudo

$ sudo usermod -aG docker <--username-->

$ docker version

Client:

Version: 18.06.1-ce

API version: 1.38

Go version: go1.10.3

Git commit: e68fc7a

Built: Tue Aug 21 17:24:56 2018

OS/Arch: linux/amd64

Experimental: false

Server:

Engine:

Version: 18.06.1-ce

API version: 1.38 (minimum version 1.12)

Go version: go1.10.3

Git commit: e68fc7a

Built: Tue Aug 21 17:23:21 2018

OS/Arch: linux/amd64

Experimental: false

Docker Machine & Docker Compose

Windows和Mac會自動幫你安裝好，Linux系統則要自己安裝這兩個項目

$ base=https://github.com/docker/machine/releases/download/v0.14.0 &&

curl -L $base/docker-machine-$(uname -s)-$(uname -m) >/tmp/docker-machine &&

sudo install /tmp/docker-machine /usr/local/bin/docker-machine

Docker compose

1 2	$ sudo curl -L "https://github.com/docker/compose/releases/download/1.22.0/docker-compose-$(uname -s)-$(uname -m)" -o /usr/local/bin/docker-compose

使用官方文件提供的指令可能會安裝到非最新的Docker compose版本，你可以到github/docker/compose去安裝最新的版本

$ sudo -i curl -L https://github.com/docker/compose/releases/download/1.23.0-rc3/docker-compose-`uname -s`-`uname -m` -o /usr/local/bin/docker-compose

$ sudo -i chmod +x /usr/local/bin/docker-compose

$ docker-compose version

docker-compose version 1.23.0-rc3, build ea3d406e

docker-py version: 3.5.0

CPython version: 3.6.6

OpenSSL version: OpenSSL 1.1.0f 25 May 2017

版本格式

現今版本的格式為 YY.MM，如 18.06.0 就是2018年6月出的版本的第一個release

其他選項

你可以試試Play with Docker，無須安裝任何環境就可以透過瀏覽器體驗Docker的強大，可以參考以下文章：

Play with Docker | 非常酷的Docker在线实验室 (上)

指令格式

舊的指令格式為：docker <command> (options)，例如 docker run，而新的Docker指令的格式已改成：

1 2	docker <command> <sub-command> (options)

例如 docker run 現在要寫成 docker container run，不過舊的指令格式目前還能使用

安裝完成你可以試著執行以下指令：

docker: 檢視所有管理選項
docker version: 確認你可以跟docker engine溝通，和檢查你的版本號
docker info: 檢視docker engine的各項設定值
docker image ls: 檢視本機所有映像檔
docker pull <-- IMAGE -->: 取得映像檔

容器（Containers）

什麼是容器

容器是基於特定映像檔所創造出來的程序

映像檔(image)和容器(container)的差別

映像檔是我們想執行的應用程式的模板，一個映像檔可以包含一個完整的作業系統環境，裡面安裝了需要的應用程式，同一個映像檔可以建立多個容器
容器是從映像檔建立的執行實例，可以被啟動、開始、停止、刪除
大部分的映像檔都可以從Docker Hub下載並取用

基本指令

$ docker container run --publish 80:80 --name webhost1 nginx

Unable to find image 'nginx:latest' locally

latest: Pulling from library/nginx

f17d81b4b692: Pull complete

d5c237920c39: Pull complete

a381f92f36de: Pull complete

Digest: sha256:b73f527d86e3461fd652f62cf47e7b375196063bbbd503e853af5be16597cb2e

Status: Downloaded newer image for nginx:latest

從Docker Hub下載nginx映像檔
建立一個映像檔實例（容器），命名為webhost1並執行
Port Forwarding: 啟用主機的80 port並將容器內部使用的80 port映射到主機上

註：

nginx server預設的對外端口是80 port
你可以更改要映射到主機的哪個port，例如 8888:80，然後用 localhost:8888 訪問

加入detach參數只在背景執行，並回傳容器的id

$ docker container run --publish 80:80 --detach --name webhost2 nginx

6950bd542f5d281cddd7691c5032d4424d7f72585e7e36623028212ddebb4490

顯示目前所有容器

$ docker container ls -a

6950bd542f5d nginx "nginx -g 'daemon of…" 3 minutes ago Up 3 minutes 0.0.0.0:80->80/tcp webhost2

eb05ed09c19c nginx "nginx -g 'daemon of…" 3 hours ago Exited (0) 3 minutes ago webhost1

關閉正在運行的容器

1 2	$ docker container stop 6950bd542f5d

顯示webhost2的log

1 2	$ docker container logs webhost2

檢視webhost2的程序，或檢查是否有正在運行的webhost2

$ docker container top webhost2

UID PID PPID C STIME TTY TIME CMD

root 18871 18852 0 13:59 ? 00:00:00 nginx: master process nginx -g daemon off;

systemd+ 18917 18871 0 13:59 ? 00:00:00 nginx: worker process

強制關閉運行中的容器

1 2	$ docker container rm -f 6950bd542f5d

以上這些指令發生了什麼事

docker container run

尋找特定的映像檔快取，找不到該映像檔的話會從遠端倉庫(remote image repo)尋找（預設是Docker Hub，若沒提供映像檔版本將下載最新的版本）
新增映像檔實例（容器）
Docker引擎會給這個容器一個實體IP(virtual ip)
啟用host的特定埠號將容器的特定埠號映射到host
以映像檔的Dockerfile CMD來執行容器

容器(container)和虛擬機(virtual machine)的差別

很多介紹容器的文章把容器拿來和vm比較，雖然它們相似的地方很多，但事實上它們是完全不同的概念，因為：

容器只是程序(processes)
容器可用的資源是受限的
容器關閉=程序停止

舉個例子來說：

1 2	$ docker run --name mongo -d mongo

檢視此容器是否正在運行

1 2	$ docker top mongo

檢視所有運行中的docker容器，註：docker ps 會對象是host，如果系統是mac或windows，需要先連到docker vm

$ docker ps

CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES

2db362bba01a mongo "docker-entrypoint.s…" 5 minutes ago Up 5 minutes 27017/tcp mongo

檢視系統上所有程序，可以清楚的看到容器是一個系統上正在執行的程序

$ ps aux | grep mongo

USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND

999 19617 0.4 0.9 1089996 75788 ? Ssl 14:28 0:02 mongod --bind_ip_all

練習：開啟多個容器

執行一個nginx實例，在背景執行且聽80port
執行一個httpd(apche)實例，在背景執行且聽8080port
執行一個mysql實例，在背景執行、密碼設定為自動產生，聽3306port

$ docker container run --name nginx -p 80:80 -d nginx

$ docker container run --name httpd -p 8080:80 -d httpd

$ docker container run --name mysql -p 3306:3306 -e MYSQL_RANDOM_ROOT_PASSWORD=yes -d mysql

檢視這三個容器的狀態

$ docker container ls -a

CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES

0e723b2571e0 mysql "docker-entrypoint.s…" 28 seconds ago Up 27 seconds 0.0.0.0:3306->3306/tcp, 33060/tcp mysql

22068e0c1ad2 httpd "httpd-foreground" 38 seconds ago Up 38 seconds 0.0.0.0:8080->80/tcp httpd

45b3a7dc26c9 nginx "nginx -g 'daemon of…" About a minute ago Up About a minute 0.0.0.0:80->80/tcp nginx

檢視mysql密碼

$ docker container logs mysql

Initializing database

...

Database initialized

MySQL init process in progress...

...

GENERATED ROOT PASSWORD: eiCheu9Wae3ohmooxaebooR7quohphai

...

MySQL init process done. Ready for start up.

...

基本指令：監控執行中的容器

檢視容器的設定(metadata)，會回傳json陣列

1 2	$ docker container inspect <-- container id or container name -->

檢視所有容器的即時狀態(live performance)

1 2	$ docker container stats

基本指令：在容器中使用終端機

run -t: Allocate a pseudo-TTY
run -i: Keep STDIN open even if not attached

根據格式 docker container run [OPTIONS] IMAGE [COMMAND] [ARG...]，在指令後面可以再帶入 [COMMAND] 及參數 [ARG...]，以nginx為例，預設程式(default program)是 nginx，參數是 -g、'daemon off;'：

{

...

"Path": "nginx",

"Args": [

"-g",

"daemon off;"

...

}

加入bash參數來改變預設程式，進入bash shell之後exit，可以看到容器隨之停止：

$ docker container run --name proxy -it nginx bash

root@e78f7e17edbc:/# exit

$ codker container ls -a

CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES

e78f7e17edbc nginx "bash" 25 seconds ago Exited (0) 5 seconds ago proxy

這邊可以看出預設的程式變成bash：

{

...

"Path": "bash",

"Args": [],

...

}

start -a: Attach STDOUT/STDERR and forward signals
start -i： Attach container’s STDIN

重啟容器，注意這裡一樣會開啟bash shell因為我們建立容器時就把command改成bash了：

$ docker container start -ai proxy

root@e78f7e17edbc:/#

如果容器正在執行中，我們如何透過殼程式操作呢（這很常用，在容器執行時debug或設定參數）：

exec: 在執行中的容器上執行額外的程序
exec -t: Allocate a pseudo-TTY
exec -i: Keep STDIN open even if not attached

$ docker container run --name mysql -e MYSQL_RANDOM_ROOT_PASSWORD=yes -d mysql

$ docker container exec -it mysql bash

另外要注意的是，並非所有映像檔都有bash程式，例如Linux的超迷你分支alpine[ 延伸閱讀 ]：

$ docker container run --it alpine bash

docker: Error response from daemon: OCI runtime create failed: container_linux.go:348: starting container process caused "exec: \"bash\": executable file not found in $PATH": unknown.

要使用bash要先透過alpine內建的殼程式sh來安裝

docker container run -it alpine sh

/ # apk add bash

/ # bash

bash-4.4#

Docker背後的網路運作

docker讓你可以建立虛擬網路(virtual network)，並將container加到網路內，建立起屬於你自己應用程式的網路拓墣 [來源]

$ docker container run --name nginx -p 80:80 -d nginx

$ docker container port nginx

80/tcp -> 0.0.0.0:80

docker daemon運作的時候，會建立三個網路

$ docker network ls

NETWORK ID NAME DRIVER SCOPE

81978b8f756d bridge bridge local

4bad3f6e57ed host host local

da7c350f0dc0 none null local

當你建立容器時，使用的ip跟主機並不同，例如以下例子：我的主機內部ip是 192.168.43.63，而我的nginx容器的內部ip則是 172.17.0.2

$ docker container inspect --format '{{ .NetworkSettings.IPAddress }}' nginx

172.17.0.2

$ ip addr show wlp58s0

3: wlp58s0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP group default qlen 1000

link/ether 9c:b6:d0:f1:f2:55 brd ff:ff:ff:ff:ff:ff

inet 192.168.43.63/24 brd 192.168.43.255 scope global dynamic wlp58s0

valid_lft 2871sec preferred_lft 2871sec

inet6 fe80::6228:4a16:e94a:7822/64 scope link

valid_lft forever preferred_lft forever

它們之間透過docker birdge network的模式（預設），此模式透過一個叫docker0的NAT server來掌管容器的網路連線 [圖片來源]

透過以下指令可以看出bridge網路裡有哪些容器

$ docker network inspect bridge

{

...

"Containers": {

"b8b8b86a8825166954069c7884d8ed8181234f5399a9d8e7bac860493c5a132f": {

"Name": "nginx",

"EndpointID": "b80f6f698bcf305689752dd9356ecc14c114275caa28ff7cd9815545d92f74be",

"MacAddress": "02:42:ac:11:00:02",

"IPv4Address": "172.17.0.2/16",

"IPv6Address": ""

}

...

}

新增一個網路(預設是bridge driver)，然後建立新的容器

$ docker network create new_net

$ docker container run --name new_nginx -d --network new_net nginx

連結容器至多個網路

$ docker network connect new_net nginx

$ docker container inspect --format '{{ .NetworkSettings.Networks }}' nginx

map[bridge:0xc4205300c0 my_app_net:0xc420530180]

DNS設置

容器隨著不同設置會改變其狀態，容器間用ip位址來連線是不可靠的，因此我們會需要DNS server

先來看看新網路的DNS能不能運作

$ docker network insepct new_net

{

...

"Containers": {

"1a6c3e7c03caba424cbc5d3cbbdb9e86fd5c39741f5af1835d7446b1758e35a7": {

"Name": "nginx",

"EndpointID": "3958183cb1514d597067aeeb01931ab3e62ce4267848f4471c5c465cecbd6b91",

"MacAddress": "02:42:ac:14:00:03",

"IPv4Address": "172.20.0.3/16",

"IPv6Address": ""

"e285eb6071b133177db6ec2cc922b01b1acfd7000199c927659fd4e0f023742f": {

"Name": "new_nginx",

"EndpointID": "3d451d2884418b5ee7efb2311530ceb255a86688148e9ec637f280fd7f24289c",

"MacAddress": "02:42:ac:14:00:02",

"IPv4Address": "172.20.0.2/16",

"IPv6Address": ""

}

...

}

$ docker container exec -it new_nginx bash

root@e285eb6071b1:/# apt-get update

root@e285eb6071b1:/# apt-get install -y iputils-ping

root@e285eb6071b1:/# exit

$ docker container exec -it new_nginx ping nginx

PING nginx (172.20.0.3) 56(84) bytes of data.

64 bytes from nginx.new_net (172.20.0.3): icmp_seq=1 ttl=64 time=0.074 ms

64 bytes from nginx.new_net (172.20.0.3): icmp_seq=2 ttl=64 time=0.121 ms

同樣在nginx容器安裝ping套件後，測試能不能雙向溝通

$ docker container exec -it nginx ping new_nginx

PING new_nginx (172.20.0.2) 56(84) bytes of data.

64 bytes from new_nginx.new_net (172.20.0.2): icmp_seq=1 ttl=64 time=0.063 ms

64 bytes from new_nginx.new_net (172.20.0.2): icmp_seq=2 ttl=64 time=0.071 ms

註：如果我以上的測試在預設的bridge network做的話會出現錯誤訊息 Name or service not known，原因是預設的bridge網路並沒有內建的DNS server，容器要連線必須手動使用 --link 指令為容器設定連線到bridge網路。建議建立新的網路來省去這一步驟

練習：快速更新Linux分支的CLI套件

分別檢查容器不同分支的Linux上的curl版本
分別在centos:7和ubuntu:14.04的容器中開啟終端機

分別取得各版本的映像檔

$ docker image pull centos:7

$ docker image pull ubuntu:14.04

建立ubuntu映像檔實例，開啟終端機並檢查curl版本

$ docker container run --name ubuntu -it --rm ubuntu:14.04

root@66c81252095f:/# curl --version

bash: curl: command not found

root@66c81252095f:/# apt-get update && apt-get install -y curl

container run --rm: exit之後預期容器被移除

root@66c81252095f:/# exit

$ docker container ls -f "name=ubuntu"

CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES

建立centos映像檔實例，開啟終端機並檢查curl版本

$ docker container run --name ubuntu -it --rm centos:7

root@66c81252095f:/# curl --version

curl 7.29.0 (x86_64-redhat-linux-gnu) libcurl/7.29.0 NSS/3.34 zlib/1.2.7 libidn/1.28 libssh2/1.4.3

root@66c81252095f:/# yum update curl

root@66c81252095f:/# exit

練習:輪替式DNS(DNS Round Robin aka poor man’s load balancer)

建立一個network包含兩個elasticsearch:2的映像檔實例
將兩個容器的網路拓墣別名(network-alias)都命名為search

$ docker network create new_net

$ docker pull elasticsearch:2

$ docker container run --name es1 -d --network new_net --network-alias search elasticsearch:2

$ docker container run --name es2 -d --network new_net --network-alias search elasticsearch:2

透過一個內網centos容器來測試連線

curl -s: Silent mode. Don’t output anything

$ docker container run --name centos --network new_net -it --rm centos:7

[root@570493921bec /]# curl -s search:9200

{

"name" : "Stuntmaster",

"cluster_name" : "elasticsearch",

"cluster_uuid" : "dRpxX5qNQTqm-RDSKy8gaw",

"version" : {

"number" : "2.4.6",

"build_hash" : "5376dca9f70f3abef96a77f4bb22720ace8240fd",

"build_timestamp" : "2017-07-18T12:17:44Z",

"build_snapshot" : false,

"lucene_version" : "5.5.4"

"tagline" : "You Know, for Search"

}

[root@570493921bec /]# curl -s search:9200

{

"name" : "Midas",

"cluster_name" : "elasticsearch",

"cluster_uuid" : "k-8YUFb5TrCFpOqQWLP2Xg",

"version" : {

"number" : "2.4.6",

"build_hash" : "5376dca9f70f3abef96a77f4bb22720ace8240fd",

"build_timestamp" : "2017-07-18T12:17:44Z",

"build_snapshot" : false,

"lucene_version" : "5.5.4"

"tagline" : "You Know, for Search"

}

映像檔(image)

什麼是映像檔？根據官方定義跟我隨翻：

An image is an ordered collections of root filesystem changes and the corresponding execution parameters for use within a container runtime

映像檔 = 檔案系統變動的有序集合 + 執行一個實例時相對應的執行參數

不是作業系統、沒有內核(kernal)、沒有核心模組（kernal module）[ 延伸閱讀 ]
體積非常輕量，小則幾KB（golang static binary），大則幾GB（ubuntu distro + apache + php）

Docker Hub

目前最多人用的映像檔的集散地(image registry)，映像檔repo分成 official 和 non-official，映像檔會用 tag 做區別（正確來說tag不算版本或分支），舉例來說，官方的nginx repo：

1.15.5, mainline, 1, 1.15, latest (mainline/stretch/Dockerfile)
1.15.5-perl, mainline-perl, 1-perl, 1.15-perl, perl (mainline/stretch-perl/Dockerfile)
1.15.5-alpine, mainline-alpine, 1-alpine, 1.15-alpine, alpine (mainline/alpine/Dockerfile)

分別pull下來，可以看出同一個映像檔(相同image id)可以有多個tags

$ docker image ls

REPOSITORY TAG IMAGE ID CREATED SIZE

nginx latest dbfc48660aeb 2 weeks ago 109MB

nginx 1 dbfc48660aeb 2 weeks ago 109MB

nginx alpine aae476eee77d 4 weeks ago 17.7MB

Docker Hub的操作跟Github很類似，可以fork其他repo或是上傳新的repo，你所需要的資訊也都能在detail page或github上找到。

映像檔可以從Github或Bitbucket的repo來建置，從首頁點選 Create Automated Build 連結帳戶即可
- 可以選擇你的映像檔要從哪個分支來build
- 對於dockerfile的 FROM 指令，Docker Hub可以設定Repository Links，設定連結後，來源映像檔如果有偵測到更新，你的映像檔就會跟著rebuild
- 自定義Rebuild的Trigger

Union檔案系統(Union file system) && 映像檔的資料層(Image layers)

映像檔的形成並非一個大的資料區塊，例如當我pull nginx:alpine時，可以看到有些資料層我已經有了

$ docker pull nginx:alpine

alpine: Pulling from library/nginx

4fe2ade4980c: Already exists

c3f09dfaf47d: Pull complete

83283d0e9bb9: Pull complete

e2e530da9538: Pull complete

透過 image history 來檢視映像檔的資料更動紀錄：

$ docker image histroy nginx:alpine

IMAGE CREATED CREATED BY SIZE

aae476eee77d 4 weeks ago /bin/sh -c #(nop) CMD ["nginx" "-g" "daemon… 0B

<missing> 4 weeks ago /bin/sh -c #(nop) STOPSIGNAL [SIGTERM] 0B

<missing> 4 weeks ago /bin/sh -c #(nop) EXPOSE 80/tcp 0B

<missing> 4 weeks ago /bin/sh -c #(nop) COPY file:1d1ac3b9a14c94a7… 1.09kB

<missing> 4 weeks ago /bin/sh -c #(nop) COPY file:af94db45bb7e4b8f… 643B

<missing> 4 weeks ago /bin/sh -c GPG_KEYS=B0F4253373F8F6F510D42178… 13.3MB

<missing> 4 weeks ago /bin/sh -c #(nop) ENV NGINX_VERSION=1.15.5 0B

<missing> 5 weeks ago /bin/sh -c #(nop) LABEL maintainer=NGINX Do… 0B

<missing> 7 weeks ago /bin/sh -c #(nop) CMD ["/bin/sh"] 0B

<missing> 7 weeks ago /bin/sh -c #(nop) ADD file:25c10b1d1b41d46a1… 4.41MB

註：IMAGE ID為 <missing> 只是為了區別——這些資料層不完整代表這個映像檔，只是被這個映像檔所用

所有映像檔都是繼承於特定基礎映像檔（blank layer, scratch），再往上繼承堆疊，不同映像檔之間可以共享基礎的檔案系統層，提升儲存效率 [ 延伸閱讀 ]

[ 圖片來源 ]

透過 image inspect 來檢視映像檔的metadata，可以看到這個映像檔開了哪些port、有哪些環境變數以及建立的時候會執行的指令等

$ docker image inspect nginx:alpine

{

"ContainerConfig": {

...

"ExposedPorts": {

"80/tcp": {}

"Env": [

"PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin",

"NGINX_VERSION=1.15.5"

"Cmd": [

"/bin/sh",

"-c",

"#(nop) ",

"CMD [\"nginx\" \"-g\" \"daemon off;\"]"

...

}

fork一份映像檔到自己的repo

$ docker login

$ docker image tag nginx:alpine ssivart/nginx

$ docker image tag ssivart/nginx ssivart/nginx:testing

docker image push ssivart/nginx:testing

註：

在遠端機器使用 docker login 的時候，操作完要登出才會移除機器上儲存的密碼
欲上傳private映像檔要先建立一個私人的repo

Dockerfile基本指令

範例1

FROM debian:stretch-slim

ENV NGINX_VERSION 1.13.6-1~stretch

ENV NJS_VERSION 1.13.6.0.1.14-1~stretch

RUN apt-get update \

&& apt-get install --no-install-recommends --no-install-suggests -y gnupg1 \

&& \

NGINX_GPGKEY=573BFD6B3D8FBC641079A6ABABF5BD827BD9BF62; \

found=''; \

for server in \

ha.pool.sks-keyservers.net \

hkp://keyserver.ubuntu.com:80 \

hkp://p80.pool.sks-keyservers.net:80 \

pgp.mit.edu \

; do \

echo "Fetching GPG key $NGINX_GPGKEY from $server"; \

apt-key adv --keyserver "$server" --keyserver-options timeout=10 --recv-keys "$NGINX_GPGKEY" && found=yes && break; \

done; \

test -z "$found" && echo >&2 "error: failed to fetch GPG key $NGINX_GPGKEY" && exit 1; \

apt-get remove --purge -y gnupg1 && apt-get -y --purge autoremove && rm -rf /var/lib/apt/lists/* \

&& echo "deb http://nginx.org/packages/mainline/debian/ stretch nginx" >> /etc/apt/sources.list \

&& apt-get update \

&& apt-get install --no-install-recommends --no-install-suggests -y \

nginx=${NGINX_VERSION} \

nginx-module-xslt=${NGINX_VERSION} \

nginx-module-geoip=${NGINX_VERSION} \

nginx-module-image-filter=${NGINX_VERSION} \

nginx-module-njs=${NJS_VERSION} \

gettext-base \

&& rm -rf /var/lib/apt/lists/*

RUN ln -sf /dev/stdout /var/log/nginx/access.log \

&& ln -sf /dev/stderr /var/log/nginx/error.log

EXPOSE 80 443

CMD ["nginx", "-g", "daemon off;"]

FROM: 開頭一定要加的，指定一個 Base Image 來初始化，通常是取用較輕量的分支如alpine
ENV: 設定環境變數
RUN: 每行指令都會往上建築新的 layer(new layer on top)，上面的範例用 && 來連結每一行指令是常見的作法
EXPOSE: 容器沒有任何預設開啟的TCP/UDP埠號，而加了也不代表這些埠號會自動打開，要開啟埠號還是要透過 container run -p
CMD: 容器執行或停止的時候都會執行的指令註：docker能自動幫我們處理logging，上面的範例將log送到stdout跟stderr，讓docker可以捕捉到這些log然後做後續處理

在dockerfile所在的目錄下build image

1 2	$ docker image build -t customnginx:customtag .

稍微更改一下dockerfile再安裝一次，可以看出union file system怎麼運作的，dockfile頂端指令會動到的資料幾乎沒什麼變動：Using cache，而越接近後頭的指令，會有較多的變動

$ docker image build -t customnginx:customtag .

Sending build context to Docker daemon 4.096kB

Step 1/7 : FROM debian:stretch-slim

---> 4b4471f624dc

Step 2/7 : ENV NGINX_VERSION 1.13.6-1~stretch

---> Using cache

---> 5993fe34a11a

Step 3/7 : ENV NJS_VERSION 1.13.6.0.1.14-1~stretch

---> Using cache

---> b1b9fa913700

Step 4/7 : RUN apt-get update && apt-get install --no-install-recommends --no-install-suggests -y gnupg1 && NGINX_GPGKEY=573BFD6B3D8FBC641079A6ABABF5BD827BD9BF62; found=''; for server in ha.pool.sks-keyservers.net hkp://keyserver.ubuntu.com:80 hkp://p80.pool.sks-keyservers.net:80 pgp.mit.edu ; do echo "Fetching GPG key $NGINX_GPGKEY from $server"; apt-key adv --keyserver "$server" --keyserver-options timeout=10 --recv-keys "$NGINX_GPGKEY" && found=yes && break; done; test -z "$found" && echo >&2 "error: failed to fetch GPG key $NGINX_GPGKEY" && exit 1; apt-get remove --purge -y gnupg1 && apt-get -y --purge autoremove && rm -rf /var/lib/apt/lists/* && echo "deb http://nginx.org/packages/mainline/debian/ stretch nginx" >> /etc/apt/sources.list && apt-get update && apt-get install --no-install-recommends --no-install-suggests -y nginx=${NGINX_VERSION} nginx-module-xslt=${NGINX_VERSION} nginx-module-geoip=${NGINX_VERSION} nginx-module-image-filter=${NGINX_VERSION} nginx-module-njs=${NJS_VERSION} gettext-base && rm -rf /var/lib/apt/lists/*

---> Using cache

---> 10da6c1aa8b6

Step 5/7 : RUN ln -sf /dev/stdout /var/log/nginx/access.log && ln -sf /dev/stderr /var/log/nginx/error.log

---> Using cache

---> 9e33d35615e8

Step 6/7 : EXPOSE 80 443 8080

---> Running in 1a79c9e87968

Removing intermediate container 1a79c9e87968

---> efa93a97a5e1

Step 7/7 : CMD ["nginx", "-g", "daemon off;"]

---> Running in d53275212fcd

Removing intermediate container d53275212fcd

---> 873793860fdf

Successfully built 873793860fdf

Successfully tagged customnginx:customtag

範例2

FROM nginx:latest

WORKDIR /usr/share/nginx/html

COPY index.html index.html

如果你能從更末端的映像檔來build，例如 FROM 官方的nginx再做一些客製化，在維護dockerfiles時就會更加容易。如範例A到範例B
WORKDIR: 意同 RUN cd /some/path，不過使用 WORKDIR 會更好
COPY: 這個範例用本地的index.html複寫原本nginx的index.html
這個範例並沒有改寫 CMD，這個指令會繼承 nginx:latest 的command

建立一個容器，訪問主頁面時預期會看到客製後的index.html

$ docker image build -t customnginx:customtag .

$ docker container run --rm -p 80:80 customnginx:customtag

練習：建立Dockerfile(alpine + node.js + tini)

FROM node:6-alpine

RUN apk update \

&& apk add --update tini \

&& mkdir -p /usr/src/app

WORKDIR /usr/src/app

COPY package.json /usr/src/app/

RUN npm install && npm cache clean --force

COPY . /usr/src/app/

EXPOSE 3000

CMD ["/sbin/tini", "--", "node", "./bin/www"]

$ docker image build -t node:tini .

$ docker container run -p 80:3000 node:tini

發布到Docker Hub

$ docker image tag node:tiny ssivart/node:tini

$ docker image push ssivart/node

持久化數據（Persisting Data）

容器的設計理念有兩個特性:

immutable intrastucture: 當你需要更改設定，皆是透過重新建立新的容器
ephemeral：無狀態，代表容器可以被關閉、銷毀或取代

Volumes

先來看一下mysql:8 Dockerfile的 VOLUME 指令

1 2	VOLUME /var/lib/mysql

意即當mysql的容器建立的時候，docker會在本機上新增一個 volume location 然後跟容器裡的數據目錄互通，這兩個路徑指向host同一個位址，資料只有靠手動方式才能移除，不會隨著容器被移除而消失

建立一個mysql容器然後看metadata

$ docker container run --name mysql -d -e MYSQL_ALLOW_EMPTY_PASSWORD=True mysql

$ docker container inspect mysql

{

...

"Mounts": [

{

"Type": "volume",

"Name": "c7eaf7ddfa3ad5d90abbe0372d628f97ddcc2384dae45a35d60c74bfdac37416",

"Source": "/var/lib/docker/volumes/c7eaf7ddfa3ad5d90abbe0372d628f97ddcc2384dae45a35d60c74bfdac37416/_data",

"Destination": "/var/lib/mysql",

"Driver": "local",

"Mode": "",

"RW": true,

"Propagation": ""

}

...

"Config": {

...

"Volumes": {

"/var/lib/mysql": {}

...

}

可以看到data儲存在主機 /var/lib/docker/volumes/c7eaf7ddfa3ad5d90abbe0372d628f97ddcc2384dae45a35d60c74bfdac37416/_data 的位置

而這在使用上會比較不友善：沒辦法從volume看出哪個容器是連結到自身

$ docker volume ls

DRIVER VOLUME NAME

local 0ad326a8fbd002aed0d6ab977140b9ac45a3b056f9885d6cc308b981ff599e4c

local 0ef3e7bc6e024c53b166fb6a2b5a1dead036d703f40608f7094c93569016fd62

這裡稍微改善的方式是用參數 -v 為volume命名（以專案來命名之類的）

$ docker container run --name mysql -d -e MYSQL_ALLOW_EMPTY_PASSWORD=True -v mysql-db:/var/lib/mysql mysql

$ docker volume ls

DRIVER VOLUME NAME

local mysql-db

source的path也變得比較乾淨易讀

...

"Source": "/var/lib/docker/volumes/mysql-db/_data",

...

另外Volume也可以是匿名的(anonymous volume)，會分配一個隨機的名字，在同一個主機中不會重覆[ 官方文件 ]

Bind Mounting

host優先於container
不能在Dockerfile裡使用，只能透過 container run
通常是用 -v 指令，或 --mount，格式為 /path/host:/path/container，如

$ docker container run -v /Users/ssivart/stuff:/path/container # linux / mac

$ docker container run -v //c/Users/ssivart/stuff:/path/container # windows

範例

新增一個nginx容器，把 /home/ssivart/桌面目錄mount至容器的 /usr/share/nginx/html

$ cd /home/ssivart/桌面

$ docker container run --name nginx -d -p 80:80 -v $(pwd):/usr/share/nginx/html nginx

接著我在 /home/ssivart/桌面新增一個index.html，內容為 <h1>Hello World! Bind Mount</h1>

1 2	$ vim index.html

預期在localhost:80會看到我更改過的首頁內容

`-v` 與 `--mount` 的差別[ 文件 ]

現在這兩個指令差別僅在於如果host上目錄不存在，使用 -v 會幫你建立新的目錄，使用 --mount 會顯示錯誤

練習：postgres版本更新用Volumes保持數據

$ docker container run --name pg1 -d -v psql:/var/lib/postgresql/data postgres:9.6.1-alpine

$ docker container stop pg1

$ docker container run --name pg2 -d -v psql:/var/lib/postgresql/data postgres:9.6.2-alpine

$ docker volume ls

DRIVER VOLUME NAME

local psql

$ docker container logs pg1

...

LOG: database system is ready to accept connections

LOG: autovacuum launcher started

LOG: received smart shutdown request

LOG: autovacuum launcher shutting down

LOG: shutting down

LOG: database system is shut down

$ docker container logs pg2

LOG: database system was shut down at 2018-11-05 08:07:27 UTC

LOG: MultiXact member wraparound protections are now enabled

LOG: database system is ready to accept connections

LOG: autovacuum launcher started

練習：使用Bind Mount架設ruby + jekyll[ 來源 ]

$ docker container run -p 80:4000 -v $(pwd):/site -it bretfisher/jekyll-serve sh

/site # bundle lock --add-platform x86-mingw32 x86-mswin32 x64-mingw32 java

/site # bundle exec jekyll serve --force_polling -H 0.0.0.0 -P 4000

Docker Compose[ 官方文件 ]

應用程式常常需要結合多個容器如SQL、proxy、網頁和後端排程等，docker compose便是用來設置容器之間的關係
一鍵完成
可以透過Docker Swarm 1.13以上版本部屬compose file

Docker compose包含兩個部份：

docker-compose.yml: YAML格式的文件來設定容器、網路、Volumes的hierarchy
- 有區分版本，如1, 2, 2.1
- 用 -f 來讀取特定檔案，預設讀取的檔名是 docker-compose.yml
docker-compose: 命令列(CLI)工具用來測試compose file

以下是compose file範例：

version: '3.1' # 預設是v1，但v1功能有限，建議最少設為v2

services:

servicename: # 容器名稱，這個名稱就是容器的DNS name

image: # 非必須，如果你需要build映像檔使用

command: # 非必須, 同docker container run [OPTIONS] IMAGE [COMMAND]的[COMMAND]

environment: # 非必須, 同docker run的-e

volumes: # 非必須, 同docker run的-v

servicename2:

volumes: # 非必須, 同docker volume create

networks: # 非必須, 同docker network create

一個簡單的proxy network設定如下

services:

proxy:

image: nginx:1.13 # this will use the latest version of 1.13.x

ports:

- '80:80' # expose 80 on host and sent to 80 in container

volumes:

- ./nginx.conf:/etc/nginx/conf.d/default.conf:ro

web:

image: httpd # this will use httpd:latest

docker compose CLI

請參考上方提到的安裝流程
僅用於開發測試端，非正式部屬使用

常用指令

docker-compose up: 設定volumes/networks，執行所有容器，使用 -d 讓程序於背景執行
docker-compose down: 停止並移除所有容器，常用 -v 來移除所有volumes/networks

練習: drupal + postgres架站

version: '3'

services:

psql:

image: postgres:latest

environment:

POSTGRES_USER: postgres

POSTGRES_PASSWORD: mypassword

restart: always

web:

image: drupal:latest # this will use the latest version

ports:

- '8080:80' # expose 80 on host and sent to 80 in container

volumes:

- drupal-modules:/var/www/html/modules

- drupal-profiles:/var/www/html/profiles

- drupal-sites:/var/www/html/sites

- drupal-themes:/var/www/html/themes

links:

- psql:postgres

volumes:

drupal-modules:

drupal-profiles:

drupal-sites:

drupal-themes:

使用compose來建置(build)客製化映像檔

使用 docker-compose up，如果找不到該映像檔的cache，會在當下建置
re-build使用 docker-compose up --build 或 docker-compose build

先來看以下compose範例：

version: '2'

# based off compose-sample-2, only we build nginx.conf into image

# uses sample site from https://startbootstrap.com/template-overviews/agency/

services:

proxy:

build:

context: .

dockerfile: nginx.Dockerfile

image: nginx-custom

ports:

- '80:80'

web:

image: httpd

volumes:

- ./html:/usr/local/apache2/htdocs/

當proxy容器執行時，會先在cache找nginx-custom這個映像檔，找不到會build，這邊示範了在 context 提供的目錄下用 dockerfile 來建置映像檔

$ docker-compose down

$ docker image ls

REPOSITORY TAG IMAGE ID CREATED SIZE

nginx-custom latest 4e0717a21563 6 minutes ago 109MB

執行完 down，docker並不會主動移除客製化映像檔，針對要移除上面範例經過命名的映像檔，down 指令加上 --rmi all 參數，如果是不提供映像檔名稱，docker會以 <bulid directory>_<container name> 的規則來命名映像檔，可以透過 --rmi local 移除

composefile配置

這個部份官方還在持續更新 往後針對部署端的compose還會有許多變動（swarm、stack、secrets…），之後會持續更新

compose files

├── docker-compose.yml # base

├── docker-compose.override.yml # local

├── docker-compose.test.yml # ci test

└── docker-compose.prod.yml # deploy

docker-compose會自動辨識.override.yml 的檔案，.test.yml 及.prod.yml 或其他自訂的compose file則需要手動透過指令 -f 來操作

本地開發端：docker-compose.yml + docker-compose.override.yml

1 2	$ docker-compose up

CI測試：docker-compose.yml + docker-compose.test.yml

1 2	$ docker-compose -f docker-compose.yml -f docker-compose.test.yml up -d

部署通常會用 config 輸出成一個完整的compose file：docker-compose.yml + docker-compose.prod.yml

$ docker-compose -f docker-compose.yml -f docker-compose.prod.yml config > production.yml

$ docker-compose -f production.yml

Swarm Mode

Swarm用來做(叢集)架構管理
Swarm內建於Docker
多個Docker host組成1個Swarm mode
Swarm程式獨立於Docker，在Docker環境下透過swarmkit運行（須先啟用）

Node

Swarm中的Docker的實例（Docker host）

Worker:
- 負責容器的執行
Manager:
- 在Swarm中透過Raft Database的設定進行協調與同步
- 負責管理Worker與協調容器的部署工作
- 也可以當Worker，Manager可以想像成有Swarm控制權限的Worker

兩個角色可以互換，node之間透過雙向TLS(mutual Transport Layer Security, 前身是SSL)協定溝通

Service and Task

Task: Container + Command（怎麼run這個容器）
Service: Task A + Task B + Task C（任務的堆疊），基於 docker run 的再封裝

Swarm會確保services持續運作

在新的處事方式上，服務器被編好號，就像牛在牛群中。比如，www001到www100。當一個服務器宕機了，它將會被取出替換上線 —— Randy Bias

Swarm運作

[ 圖片來源 ]

基本指令

docker swarm init 可以新增一個swarm，其中完成這些動作[ 文件 ]：

初始公開金鑰基礎架構(public key infrastructure, PKI)
- Docker先扮演第一個Manager node(root manager)
- 產生一組root certificate authority(.ca)
- 產生token: worker token + manager token
- 其他node可以用這組token加入(join)swarm
初始Raft database
- 儲存憑證
- 在control plane讓Manager之間共享log，透過TLS
- 儲存config data[ 文件 ]

初始後可以看到第一個manager node

$ docker swarm init

$ docker swarm ls

ID HOSTNAME STATUS AVAILABILITY MANAGER STATUS

uvemtlsi7743iqxih5tkwt9v8 * xps13 Ready Active Leader

建立一個service，指定task的容器執行的指令及參數(docker run)

$ docker service create --name myservice -d alpine ping 8.8.8.8

$ docker service ls

ID NAME MODE REPLICAS IMAGE

u2br67fsvqsi myservice replicated 1/1 alpine:latest

檢視service的task，可以看到一個執行中的容器

$ docker service ps myservice

ID NAME IMAGE NODE DESIRED STATE CURRENT STATE ERROR PORTS

sfge35webgpo myservice.1 alpine:latest xps13 Running Running about a minute ago

更新service的參數，提高task數量(replicas)來sacle up

$ docker service update myservice --replicas 3

1/3: running [==================================================>]

2/3: running [==================================================>]

3/3: running [==================================================>]

$ docker service ps myservice

ID NAME IMAGE NODE DESIRED STATE CURRENT STATE ERROR PORTS

sfge35webgpo myservice.1 alpine:latest xps13 Running Running 8 minutes ago

57mukap2p6ck myservice.2 alpine:latest xps13 Running Running 30 seconds ago

mfui4zrgdop4 myservice.3 alpine:latest xps13 Running Running 30 seconds ago

手動停止其中一個容器，service會再add一個task到service queue取代之，確保同時會有3個正常運作的task

$ docker container rm -f myservice.1.sfge35webgpo0nnmejuqsbvnz

$ docker service ps myservice

1o792ip8k75i myservice.1 alpine:latest xps13 Running Running 6 seconds ago

sfge35webgpo \_ myservice.1 alpine:latest xps13 Shutdown Failed 11 seconds ago "task: non-zero exit (137)"

57mukap2p6ck myservice.2 alpine:latest xps13 Running Running 4 minutes ago

mfui4zrgdop4 myservice.3 alpine:latest xps13 Running Running 4 minutes ago

要終止task必須移除整個service，同時會把當中所有的程序清理掉

1 2	$ docker service rm myservice

更新services

指令範例

$ docker service scale web=2

$ docker service update --image nginx:1.13.6 web

$ docker service update --publish-rm 80 --publish-add 8080:80 web

service更新其中的tasks都會重建，task建立時docker會挑負載較小的node做較多分配，所以對service做 force update 可以平衡node之間的負載

1 2	$ docker service update --force web

CLI更新

service create、service update 在不同版本上的參數變更：

17.05前：必須都要透過 service ls 或 service ps 來檢查是否正常執行
17.05後：新增了 --detach 參數，預設為true
17.10後：--detach 參數，預設改為false 結論是17.12版本後要透過shell scripts或automation來建立service的話，記得設定 --detach=true

使用GCP Compute Engine Instance Group來試作多節點Swarm

node-group-1-5188:~$ docker swarm init

Swarm initialized: current node (jxq78ujvpd196whvzos74vqjg) is now a manager.

node-group-1-c1m7:~$ docker swarm join --token SWMTKN-1-0hjsesqene40g6w9pw5usrcfti72bwhqwwccp57xclcozqtn5

h-ab4c4ihrdaekal7sbpww3ga38 10.132.0.2:2377

This node joined a swarm as a worker.

worker node沒有swarm的控制權

node-group-1-c1m7:~$ docker node ls

Error response from daemon: This node is not a swarm manager. Worker nodes can't be used to view or modify cluster sta

te. Please run this command on a manager node or promote the current node to a manager.

提昇host的worker成manager，node狀態變成Reachable

node-group-1-5188:~$ docker node update --role manager node-group-1-c1m7

node-group-1-5188:~$ docker node ls

ID HOSTNAME STATUS AVAILABILITY MANAGER STATUS ENGIN

E VERSION

jxq78ujvpd196whvzos74vqjg * node-group-1-5188 Ready Active Leader 18.09

exs01fiaqanf0efveae7d610c node-group-1-c1m7 Ready Active Reachable 18.09

Overley Network

跨Node間的網路拓樸，基於Routing Mesh

node-group-1-5188:~$ docker network create --driver overlay mydrupal

node-group-1-5188:~$ docker service create --name psql --network mydrupal -e POSTGRES_PASSWORD=example postgres

node-group-1-5188:~$ docker service create --name drupal --network mydrupal -p 80:80 drupal

psql在node1，drupal在node2，node2可以透過dns name:psql來存取node1的資料庫，用80 port連到node1也能看到drupal的歡迎頁面

node-group-1-5188:~$ docker service ps psql

ID NAME IMAGE NODE DESIRED STATE CURRENT STATE

ERROR PORTS

w35eiu38yfii psql.1 postgres:latest node-group-1-5188 Running Running 10 minutes

ago

node-group-1-5188:~$ docker service ps drupal

ID NAME IMAGE NODE DESIRED STATE CURRENT STATE

ERROR PORTS

0blpaalwe5qi drupal.1 drupal:latest node-group-1-c1m7 Running Running about a mi

nute ago

Routing Mesh

為service底下的task提供路由(routes ingress packets)
- container-to-container use Virtual IP
- external traffic incomming to publish ports(all nodes listen)
為services提供負載平衡
- stateless load balancer，如果需要指向特定container的話，須另外設定（如cookie、session）
- 使用linux既有的IPVS(IP Virtual Server)實現load balancing
- load balancer表現於TCP層的(OSI第3層)，針對一個swarm一個對外port的web架構，還會需要Nginx、HAProxy來做DNS層（第4層）的load balancer

無論訪問網路中的哪個節點，即使該節點上沒有運行該service的副本，最終都能訪問到該service 舉例來說，如果後端資料庫有3個副本，當前端web server要取資料時，並非直接訪問某個資料庫副本的ip，而是透過swarm為所有service搭建的Virtual IP(VIP)
外部流量導向所有節點共同監聽的public port

練習：voting app[ dockersamples ]

首先先建立前後端的網路，跨node要用overlay模式

$ docker network create --driver overlay backend

$ docker network create --driver overlay frontend

$ docker service create --name vote --network frontend --replicas 3 -p 80:80 dockersamples/examplevotingapp_vote:before

$ docker service create --name redis --network frontend redis:3.2

$ docker service create --name worker --network frontend --network backend dockersamples/examplevotingapp_worker

$ docker service create --name db --network backend --mount type=volue,source=/var/lib/postgresql/data postgres:9.4

$ docker service create --name result --network backend -p 5001:80 dockersamples/examplevotingapp_result:before

ssivart@ds-1z84:~$ docker service ls

ID NAME MODE REPLICAS IMAGE PORTS

wxh8d5b9vb45 db replicated 1/1 postgres:9.4

8c9t5hehhl6c redis replicated 1/1 redis:3.2

zka68kizvla8 result replicated 1/1 dockersamples/examplevotingapp_result:before *:5001->80/tcp

gbed0pcrympq vote replicated 3/3 dockersamples/examplevotingapp_vote:before *:80->80/tcp

s0ese5a8wlna worker replicated 1/1 dockersamples/examplevotingapp_worker:latest

Stacks

dockerfile版本3以上
適用於部署端的compose(services + volumes + overlay networks + secrets…)
composefile指令跟local端的差異：開發端忽略 deploy 指令，部署端忽略 build
部署不透過docker-compose
針對已經存在的service，再部署會update這些service

上述的範例只要透過一個Composefile就能完成所有部署

$ docker stack deploy -c example-voting-app-stack.yaml voteapp

$ docker stack services voteapp

ID NAME MODE REPLICAS IMAGE PORTS

7alt1ix5vefl voteapp_worker replicated 1/1 dockersamples/examplevotingapp_worker:latest

7zx6l55sybey voteapp_vote replicated 2/2 dockersamples/examplevotingapp_vote:before *:5000->80/tcp

bp4hdcrig4pb voteapp_redis replicated 1/1 redis:alpine

lbejdwn5d9je voteapp_visualizer replicated 1/1 dockersamples/visualizer:stable *:8080->8080/tcp

qvp0jwokpi40 voteapp_result replicated 1/1 dockersamples/examplevotingapp_result:before *:5002->80/tcp

thzyq45ib40w voteapp_db replicated 1/1 postgres:9.4

swarm的可視化工具visualizer

Secrets

儲存：
- 使用者帳密
- TLS憑證、金鑰
- SSH金鑰
- 自訂設定檔
支援動態字串或二進位的內容
儲存在Raft database，只存在於各個manager node的硬碟空間
secrets產生後會先存在swarm再分配到特定service，只有特定的container能訪問
乍看之下是個實體檔案，但實際上是ramfs files system透過記憶體儲存
secrets只適用於swarm，而swarm只適用於部署端(production)，但docker讓docker-compose也能使用，僅提供開發測試，不具真的功能(fake secure)

$ docker secret create psql_user psql_user.txt

zbqddocct68y2evhxy7krfxbd

$ echo "mypassword" | docker secret create psql_pass -

zy2da4ok40jxjc6t3kliw91io

$ docker secret ls

ID NAME DRIVER CREATED UPDATED

zy2da4ok40jxjc6t3kliw91io psql_pass 2 minutes ago 2 minutes ago

zbqddocct68y2evhxy7krfxbd psql_user

secrets無法透過指令檢視內容（廢話），容器要存取secret得先經過指定

1 2	$ docker service create --secret psql_user --secret psql_pass

但這樣還少了怎麼配置這些secret，docker提供一個方便的查找方式，前提是映像檔要有這些變數

1 2	$ docker service create --secret psql_pass -e POSTGRES_PASSWORD_FILE=/run/secrets/psql_pass

終端機進容器檢視密碼

$ docker container exec -it psql.1.g2wh4ybeidc70vifm4xvtl9lf bash

root@0727ea1882ad:/# cat /run/secrets/psql_pass

mypassword

針對已經建立的service可以透過 update --secret-rm 或 update --secret-add 來更新secret，但這樣做會導致整個service重新部署

secrets透過stack部署

dockerfile版本3.1以上

version: "3.1"

services:

psql:

image: postgres

secrets:

- psql_user

- psql_password

environment:

POSTGRES_PASSWORD_FILE: /run/secrets/psql_password

POSTGRES_USER_FILE: /run/secrets/psql_user

secrets:

psql_user:

file: ./psql_user.txt

psql_password:

file: ./psql_password.txt

透過實體檔案儲存密碼的方式是有風險的，記得在部署完成後移除這些檔案

開發端測試secrets

docker-compose CLI版本11以上適用
開發端是使用bind mount的方式把secrets mount到本機目錄，只是用於開發並無secret實際功能
不適用內含external用法，如果部署是用 external:true，可以另外維護一個開發用的compose file，secret的部份改用file來寫入

$ docker-compose up -d

$ docker-compose exec psql cat /run/secrets/psql_pass

mypassword

Healthchecks

回傳0(OK)或1(Error)
支援Dockerfile、Compose、docker run 及swarm services
容器有三種健康狀態: starting, healthy, unhealthy

container

$ docker container run --name psql -d --health-cmd="pg_isready -U postgres || exit 1" postgres

$ docker container ls

CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES

44d6df2dcb5a postgres "docker-entrypoint.s…" 38 seconds ago Up 37 seconds (healthy) 5432/tcp psql

$ docker container inspect psql

{

...

"State": {

...

"Health": {

"Status": "healthy",

"FailingStreak": 0,

"Log": [

{

"Start": "2018-11-14T05:52:14.562405278Z",

"End": "2018-11-14T05:52:16.32755068Z",

"ExitCode": 0,

"Output": "/var/run/postgresql:5432 - accepting connections\n"

{

"Start": "2018-11-14T05:52:46.338006182Z",

"End": "2018-11-14T05:52:46.588202392Z",

"ExitCode": 0,

"Output": "/var/run/postgresql:5432 - accepting connections\n"

...

]

...

}

...

}

services

1 2	$ docker service create --name psql -d --health-cmd="pg_isready -U postgres \|\| exit 1" postgres

Docker Registry

$ docker container run -d -p 5000:5000 --name registry registry

$ docker image tag hello-world 127.0.0.1:5000/hello-world

$ docker image ls

127.0.0.1:5000/hello-world latest 4ab4c602aa5e 2 months ago 1.84kB

hello-world latest 4ab4c602aa5e 2 months ago 1.84kB

1 2	$ docker image push 127.0.0.1:5000/hello-world

push之後映像檔的實體檔案儲存在/var/lib/registry/

Registry in Swarm mode

主要問題是解決nodes之間要訪問同一份映像檔
如果只在其中一個manager node build image，其他node是沒辦法取得該image
解法：
- 使用Docker hub、AWS、Quay來儲存管理映像檔
- 借助Routing Mesh，所有node都能藉由127.0.0.1:5000訪問

以下示範如何使用Routing Mesh建立registry

$ docker service create --name registry --publish 5000:5000 registry

$ docker pull nginx

$ docker tag hello-world 127.0.0.1:5000/nginx

$ docker push 127.0.0.1:5000/nginx

將映像檔push到registry後，所有nodes都能從127.0.0.1:5000取得映像檔

1 2	$ docker service create -p 80:80 --replicas 5 -d 127.0.0.1/nginx

Fluent Python Notes: An array of sequences

2018 年 10 月 9 日2018 年 11 月 22 日
Python

私人筆記，有錯誤煩請指正

Fluent Python Github

序列(Sequence)

可分成容器序列、一般序列；或分成可變及不可變。容器序列保存物件的參考，可以是任何型態；一般序列實際儲存項目的值，但只能保存數字、字元或位元組

容器「有些物件裡面有其他物件的參考，這些物件稱為容器」

collections.abc

List Comprehension(listcomp)

如果你不是只想建構串列，就不該使用listcomp，如果listcomp的長度太長，請考慮用for迴圈。Python 2.x 中listcomp中的變數會影響到外部環境的變數

Generator Expression(genexp)

串列以外的序列類型應該使用genexp，可節省記憶體空間（透過for迴圈一次產生一個項目）

Tuple可充分扮演紀錄的角色，原因是他的拆解機制(Unpacking)

slice跟range排除最後一個項目的原因

容易看出或計算長度，range(start, stop)或my_list[start:stop]的長度都是stop – start
區分序列成多個部份而不會重疊，my_list[:x]與my_list[x:]

建構巢狀串列

重要的Python API慣例

當函式或方法就地改變物件時，必須回傳None，來讓呼叫方知道物件本身已被改變，而且沒有創建新的物件，e.g. list.sort、random.shuffle。這樣做有一個缺點，無法層疊這些方法的呼叫式（Fluent Interface 流式接口）；反之，會回傳新的物件的例子如sorted、所有str的方法

待補充：bisect、memorview, numpy.ndarray, collections.deque

拿list來裝混合型態的物件並不實用，因為list的某些操作可能會無法使用，請用tuple，因為相較之下這種作法自然很多（tuple每個項目其實都代表是個欄位）

list.sort與sorted的排序演算法是用Timesort，會根據資料的排序狀況來決定用插入排序還是合併排序

Fluent Python Notes: Data Model

2018 年 9 月 27 日2018 年 11 月 26 日
Python

私人筆記，有錯誤煩請指正

Fluent Python Github

遵循Steve Holden的做法，在唸出Magic Functions的時候用dunder取代underscore，如__getitem__唸作”dunder-getitem”

善用namedtuple來建構裡面只有一堆屬性，沒有自訂方法的簡單類別，如資料庫的紀錄一般

註：

nametuple是類別工廠，回傳一個tuple的子類別
呼叫屬性asdict回傳OrderedDict物件(3.6後版本)
屬性是immutable（tuple），要更改可以re-create或呼叫_replace
透過__doc__設定docstring
透過__default__或prototype._replace來設定預設值

實作__getitem__讓物件變成可迭代物(iterable)

某個集合可以透過實作__contains__來定義in運算子要如何掃描集合。

關於特殊方法，它們是要讓Python編譯器呼叫的，而不是你（私下呼叫）；使用者程式經常呼叫的特殊方法只有__init__，目的是呼叫你自己寫的__init__；如果你要呼叫特殊方法，呼叫相關的內建函式會比較好（例如len、iter、str等），這些函式不僅會呼叫對應的特殊方法，通常還會提供其他服務，也比較快

__repr__回傳的字串必須精確，而且如果可以的話，必須盡可能匹配原始碼，以重新建立被表示的物件；__str__是讓print函式私下使用的，回傳給終端使用者觀看的格式；如果沒有自訂的__str__可用，Python會呼叫__repr__來提供回饋

https://stackoverflow.com/a/2626364/8100647

注意這裡的方法回傳新的Vector實例。為中綴（infix）運算子的預期行為：為了建立新的物件，並不接觸它們的運算元

len不會被當成方法來呼叫，因為它身為Python資料模型的一部分，會受到特殊對待，如同abs。但是拜特殊方法__len__所賜，你的自訂物件也可以使用len，這是一種在內建物件效率與語言一致性之間取得的平衡

Object construction in JavaScript

2018 年 9 月 19 日
JavaScript

Super Short History

Brendan Eich designed Mocha in 10 days, the language was officially called LiveScript, then was renamed JavaScript because of the spin-off of Java. (a marketing ploy)

JavaScript is noting like Java, but designed to syntaxly like Java.

Function Constructor

Use capital letter for function constructor: prevent missing “new” operator during construction

operator “new”

The “new” keyword is designed to make Java user feel comfortable. It is an operator in JavaScript.

Create an empty object
Invoke the function, point the keyword “this” to the empty object
Pointing prototype to the function constructor
Return the object

We can construct an object via function (function constructor) – just an regular function.

prototype extension

Build-in function constructors

Pure Prototypal Inheritance

Change the prototype along the way

Make object and create new objects by pointing prototype to this object using Object.create(), and override properties and methods.

Implement in newer browsers

Use polyfill, note the scenario of usage

ref:

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/create#Polyfill

ES6 Classes

JavaScript doesn’t have classes until ES6, even though class keyword been added, but it still an object not a definition in other programming language.

Just another syntactical way(syntactic sugar) to construct objects.

2018

Python函式的參數設計 – Python Function Parameters

parameter跟argument的差異

可迭代物件的拆解機制(unpacking)

超簡單實現swap

使用*和**（3.5以上適用）

unpacking範例

巢狀的unpacking

以Python實作資料結構 – Data Structure Implements in Python

以Python實作資料結構

tags: data-structure, python

TOC

簡介

什麼是資料結構？為什麼要使用資料結構？

抽象資料型態 Abstract Data Types

ADT跟資料結構的關係

時間複雜度 Big O notation

陣列 Array

Implements

以Python實作

連結串列 Linked List & 雙向連結串列 Double Linked List

Implements

以Python實作

Linked List現實中的應用

堆疊 Stack

Implements

應用

Stack memory vs Heap memory

以Python實作

佇列 Queue

應用

以Python實作

二元搜尋樹 Binary Search Tree

BST現實中的應用

平衡二元搜尋樹 Balancing Binary Search Tree, AVL Tree

紅黑樹 Red-Black Tree

優先權佇列 Priority Queue

二元堆積 Binary Heap

應用

堆積排序 Heapsort

關聯陣列/對映/字典 Associative Array/ Map/ Dictionary

hash function

Collision

Dynamic resizing

應用

三元搜尋樹 Ternary Search Tree, TST

應用

互斥集 Disjoint sets / union-find data structure

應用

以Python實作，輸出請參考gist

Docker基礎介紹與實戰

TOC

Docker簡介

Docker的重要性

相關工具

安裝前要注意的

Stable vs Edge(beta)

安裝

Windows 10 Pro / Enterprise

Windows 7, 8, or 10 Home Edition

Mac

Linux

Docker Machine & Docker Compose

版本格式

其他選項

指令格式

容器（Containers）

什麼是容器

映像檔(image)和容器(container)的差別

基本指令

以上這些指令發生了什麼事

容器(container)和虛擬機(virtual machine)的差別

練習：開啟多個容器

基本指令：監控執行中的容器

基本指令：在容器中使用終端機

Docker背後的網路運作

DNS設置

練習：快速更新Linux分支的CLI套件

練習:輪替式DNS(DNS Round Robin aka poor man’s load balancer)

映像檔(image)

使用`*`和`**`（3.5以上適用）

tags: `data-structure`, `python`

`-v` 與 `--mount` 的差別[ 文件 ]