簡而言之 你要在DNS加一筆record
每次更新他會要求你放不同的值
https://community.letsencrypt.org/t/i-am-confused-about-dns-challenge/18754
2019年3月12日 星期二
2017年12月2日 星期六
終於在工作中實際用到了紅黑樹 - 交易所配對引擎
首先了解紅黑樹跟一般的二分查找樹的區別可以看下面連結中的漫畫，清楚明瞭：
https://mp.weixin.qq.com/s/0RKuO0Pk7R09wGzgyA43mw
簡單來講最大的差別在於
二分查找樹有可能會左右極度不平衡，造成查找時效率變慢
而紅黑樹有自平衡系統，可以確保樹的深度是平衡的，缺點是增加或是減少節點時會比較耗資源
最近在開發交易所，研究了 Peatio 的交易所撮合引擎，其中有一段就有用到紅黑樹
確切的 code 在這：https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L11
所以不禁就想問為什麼這邊要用紅黑樹呢？
原因就是因為在這個演算法中我們是根據 order 的 price 來當排序，假設交易所的 orders 中我們第一個 laoding 進來的 order 是最便宜的或是最貴的，那麼用 binary tree 就會變成左右極不平衡的情況，造成搜尋效率低落，相對的如果用紅黑樹就可以讓整個樹長成左右平衡的大樹，這樣搜尋效率就比較高。
其實 base on 演算法的實作，在 peatio 的演算法中是把 orders 一次 load 進 memory 裡面，所以只有在第一次 loading orders 的時候會花很多資源在紅黑樹自平衡，但一但 loading 完之後大部分的時候都會是在查找 order 而不是新增刪除 order，所以這樣的設計是比較合理的。
查找 order 的部分：https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L44
https://mp.weixin.qq.com/s/0RKuO0Pk7R09wGzgyA43mw
簡單來講最大的差別在於
二分查找樹有可能會左右極度不平衡，造成查找時效率變慢
而紅黑樹有自平衡系統，可以確保樹的深度是平衡的，缺點是增加或是減少節點時會比較耗資源
最近在開發交易所，研究了 Peatio 的交易所撮合引擎，其中有一段就有用到紅黑樹
確切的 code 在這：https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L11
所以不禁就想問為什麼這邊要用紅黑樹呢？
原因就是因為在這個演算法中我們是根據 order 的 price 來當排序，假設交易所的 orders 中我們第一個 laoding 進來的 order 是最便宜的或是最貴的，那麼用 binary tree 就會變成左右極不平衡的情況，造成搜尋效率低落，相對的如果用紅黑樹就可以讓整個樹長成左右平衡的大樹，這樣搜尋效率就比較高。
其實 base on 演算法的實作，在 peatio 的演算法中是把 orders 一次 load 進 memory 裡面，所以只有在第一次 loading orders 的時候會花很多資源在紅黑樹自平衡，但一但 loading 完之後大部分的時候都會是在查找 order 而不是新增刪除 order，所以這樣的設計是比較合理的。
查找 order 的部分：https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L44
2017年10月22日 星期日
摘要算法和對稱加密算法
摘要算法不可逆，對稱加密可逆
所謂對稱加密就是用私鑰（也就是密碼）幫訊息加密，所以只要再用私鑰就能解密，例如 AES 算法
而摘要算法呢？就是沒有私鑰的概念，只要是一樣的字串加密出來的內容就會是一樣的，但是摘要算法會確保加密出來的字串無法（應該說：很難）被逆推回原本的值，所以常常用來做 API 訊息的驗證，常見的算法有 MD5 和 SHA 系列
由於以上特性，對稱加密通常用來保護隱私相關的東西，而摘要算法則是確保文檔的正確性，以下舉例說明用法
對稱加密：
最長用來做點對點加密，確保中間人不能得到訊息原文，可以用作在通訊軟體加密
摘要加密：
常用在 API 訊息認證，最常用的作法就是在要傳送的 Params 時多加 API key 到的 Params 裡面, 由於攻擊者不知道公鑰所以即使要竄改 params 內容也沒辦法重新產生正確的加密字串
2017年8月25日 星期五
DATETIME 和 TIMESTAMP 的差別
這邊說的是 database type
幾個結論
1. datetime 存了 date 和 time，可能用到 8 bit
2. datetime 可以支援的 range 比較廣，從 1000~9999 years 都可以
3. timestamp 則是存從 epoch time (1970-01-01) 到現在經過的秒數，只用到 4 bits
4. timestamp 因為存秒數，所以最早只能支援到 epoch time
5. timestamp 只用到 4 bits所以最多到 2038 年
6. rails migration 即使設 timestamp 也是使用 datetime 而不是用 timestamp
From wiki
Because DATETIME stores every digit in the year, month day, hour, minute and second, it uses up a total of 8 bytes. As TIMESTAMP only stores the number of seconds since 1970-01-01, it uses 4 bytes. You can read more about the differences between time formats in MySQL here.
https://stackoverflow.com/questions/3928275/in-ruby-on-rails-whats-the-difference-between-datetime-timestamp-time-and-da
幾個結論
1. datetime 存了 date 和 time，可能用到 8 bit
2. datetime 可以支援的 range 比較廣，從 1000~9999 years 都可以
3. timestamp 則是存從 epoch time (1970-01-01) 到現在經過的秒數，只用到 4 bits
4. timestamp 因為存秒數，所以最早只能支援到 epoch time
5. timestamp 只用到 4 bits所以最多到 2038 年
6. rails migration 即使設 timestamp 也是使用 datetime 而不是用 timestamp
From wiki
Because DATETIME stores every digit in the year, month day, hour, minute and second, it uses up a total of 8 bytes. As TIMESTAMP only stores the number of seconds since 1970-01-01, it uses 4 bytes. You can read more about the differences between time formats in MySQL here.
https://stackoverflow.com/questions/3928275/in-ruby-on-rails-whats-the-difference-between-datetime-timestamp-time-and-da
2017年7月22日 星期六
B+ tree (B plus tree)
前一篇學習了 什麼是 B- balance tree，立馬再來補習一下 B+
其實 B+ tree 就是 B- 的升級版
主要的差別在於「子節點有母節點的資訊」，並且「出現在子節點中的母節點元素都是子節點中最大的元素」，不囉唆，看圖：
我們看第三層的所有子節點可以發現，每個子節點最右邊（也就是最大）的元素都是母節點的元素
如此一來就變成一個依照順序排序的子節點
優點：
1. 可以減少 IO 次數，因為子節點有所有的 data，母節點只有索引而已
2. 在做範圍查詢的時候，B- 如果查詢的範圍橫跨節點的兩邊就必須要先走左邊再走右邊去查資料，但 B+ 可以在最底層的子節點往右邊直接找就行了（因為子節點有所有的 data）
3. 更矮胖
4. 所有查詢都要查到子節點，代表查詢的速度比較一致，不會有些快有些慢（穩定性高）（相對的也可以說成是「一樣快」或是「一樣慢」）
圖片以及資訊來源：
http://mp.weixin.qq.com/s/cK_GIhCuGoUwJpDpoaETxw
其實 B+ tree 就是 B- 的升級版
主要的差別在於「子節點有母節點的資訊」，並且「出現在子節點中的母節點元素都是子節點中最大的元素」，不囉唆，看圖：
我們看第三層的所有子節點可以發現，每個子節點最右邊（也就是最大）的元素都是母節點的元素
如此一來就變成一個依照順序排序的子節點
優點：
1. 可以減少 IO 次數，因為子節點有所有的 data，母節點只有索引而已
2. 在做範圍查詢的時候，B- 如果查詢的範圍橫跨節點的兩邊就必須要先走左邊再走右邊去查資料，但 B+ 可以在最底層的子節點往右邊直接找就行了（因為子節點有所有的 data）
3. 更矮胖
4. 所有查詢都要查到子節點，代表查詢的速度比較一致，不會有些快有些慢（穩定性高）（相對的也可以說成是「一樣快」或是「一樣慢」）
圖片以及資訊來源：
http://mp.weixin.qq.com/s/cK_GIhCuGoUwJpDpoaETxw
什麼是 btree (balance tree) (b-)
常常看到 postgresql 的 index 都是用 btree 的方式 index，但一直沒時間去研究什麼是 btree，最近發現一個不錯的維信號用漫畫的方式解釋各種演算法相關的東西，剛好看到 b- b+ 的介紹，該是時候學習一下了～
所謂的 b- 其實唸作 balance tree 或是 b tree，是跟二元樹有點相關的東西，但最大的差別在於他每個節點最多可以包容兩個值，這樣做的原因是如果我們用二元樹來下 index，雖然時間複雜度很低，但是由於每個節點都寫入在硬碟的不同位置，一旦運氣不好我們要找的節點剛好是在樹的最底端，那硬碟就要從最上面的節點一路讀取到最下面的節點，雖然時間複雜度低但是硬碟讀取的效率差，為了讓硬碟讀取的次數變少於是有了 b- 的結構。
b- 讓一個節點可以容納兩個數值，如此一來下面就可以有三個節點，並且可以在節點內定位省了一次到不同硬碟空間的時間。
所謂的 b- 其實唸作 balance tree 或是 b tree，是跟二元樹有點相關的東西，但最大的差別在於他每個節點最多可以包容兩個值，這樣做的原因是如果我們用二元樹來下 index，雖然時間複雜度很低，但是由於每個節點都寫入在硬碟的不同位置，一旦運氣不好我們要找的節點剛好是在樹的最底端，那硬碟就要從最上面的節點一路讀取到最下面的節點，雖然時間複雜度低但是硬碟讀取的效率差，為了讓硬碟讀取的次數變少於是有了 b- 的結構。
b- 讓一個節點可以容納兩個數值，如此一來下面就可以有三個節點，並且可以在節點內定位省了一次到不同硬碟空間的時間。
另外新增刪減節點的時候也是比較耗時的，為了確保最有效率地運作，新增刪減節點是有機會去更動到母節點的
總之 postgres 是預設使用 btree，瞭解一下更清楚自己平時在做什麼事ＸＤ
另外也寫了一篇 關於 B+ tree的介紹
圖片和資訊來源：
2017年7月7日 星期五
Google Authenticator 的實作原理
簡單來說就是使用密鑰+時間的加密方式，加密細節可以參考下方網站
https://www.zhihu.com/question/20462696
http://www.csdn.net/article/2014-09-23/2821808-Google-Authenticator
使用上來說就是網站先幫使用者產生隨機密鑰，使用者用 Google Authenticator 輸入密鑰後用現在的時間算出一個加密過後的一串很長的 16 進位數，利用這個 16 進位數來雙重認證。
Google Authenticator 本身多做的兩件事情是
1. 使用 30 秒為一個區間加密
2. 將加密出來的 16 進位數再算成六位數的十進位數字讓使用者比較容易輸入
也就是說如果網站開發者要實作 google authenticator 的二階段認證的話就必須
1. 將六位數字換算回 16 進位數字
2. 根據 30 秒為一個區間解密使用者輸入的數字，而不是使用當下時間點
ruby 上的實作：
https://github.com/mdp/rotp
2017年4月25日 星期二
About Redis
In memory, key-value store. 所以其實 redis 就是一個 database，只是他所有的東西都存在 memory 而且是屬於 NoSQL 的 database。
最常用的場景就是拿來快取東西。
In memory 表示是直接存在記憶體上不是存在硬碟裡，由於記憶體上有實作更簡單的演算法所以需要的 CPU 資源較少，而且在 query 資料的時候可以減少搜尋硬碟的時間所以讀寫很快，這也是為什麼大家常常拿 Redis 當 Cache server 的原因
https://en.wikipedia.org/wiki/In-memory_database
當然 Redis 也有提供讓資料存寫進硬碟的功能，關鍵字：Expire
http://huli.logdown.com/posts/926762-redis-introduction
http://stackoverflow.com/questions/7888880/what-is-redis-and-what-do-i-use-it-for
延伸閱讀
https://medium.com/ruby-on-rails/easy-caching-with-rails-4-heroku-redis-5fb36381628
最常用的場景就是拿來快取東西。
In memory 表示是直接存在記憶體上不是存在硬碟裡，由於記憶體上有實作更簡單的演算法所以需要的 CPU 資源較少，而且在 query 資料的時候可以減少搜尋硬碟的時間所以讀寫很快，這也是為什麼大家常常拿 Redis 當 Cache server 的原因
https://en.wikipedia.org/wiki/In-memory_database
當然 Redis 也有提供讓資料存寫進硬碟的功能，關鍵字：Expire
http://huli.logdown.com/posts/926762-redis-introduction
http://stackoverflow.com/questions/7888880/what-is-redis-and-what-do-i-use-it-for
延伸閱讀
https://medium.com/ruby-on-rails/easy-caching-with-rails-4-heroku-redis-5fb36381628
2017年4月4日 星期二
multi-tiered
簡單來說，multi-tiered 的意思就是很多台機器的意思，例如 client 跟 server 是不同的機器所以就是 2-tiered，而現在都是 N-tiered 了畢竟 database 跟 application 可能也是分開的。
References:
http://www.bethel.com.tw/cht/jpTA.aspx?cate_id=5&doc_id=63
訂閱：
文章 (Atom)