Tag: random

Amazon 的多變數最佳化

在「An efficient bandit algorithm for real-time multivariate optimization」這邊提到了 Amazon 不是走傳統的 A/B testing，而是同時進行多變數的最佳化：

Consider the problem of trying to find a near-optimal version of a promotional message such as this one, which has 5 variable parts and 48 different combinations in total.

在這樣的測試數量下，作者預估需要 66 天才能夠得到有效的結果，而這也表示當變數更多的時候問題就更大了：

Based on the Amazon success rate and traffic size, the authors calculated it would take 66 days to conduct a 48 treatment randomized experiment. Often this isn’t practical.

也就是開頭提到的，如何一個禮拜就提昇 21% conversion rate：

Aka, “How Amazon improved conversion by 21% in a single week!”

作者也提到了這個方法其實打臉了他先前提到的另外一篇論文，在 2014 年提出測試應該要盡可能簡單 XDDD：

Yesterday we saw the hard-won wisdom on display in ‘seven myths‘ recommending that experiments be kept simple and only test one thing at a time, otherwise interpreting the results can get really complicated.

只能說狀況愈來愈複雜，導致需要新方法解決問題。而且這些電商會遇到在測試時不同的 factor 之間有可能會有相依性 (也就是說這些 factor 不是 i.i.d.)，你用本來的方式反而會測不出來。

Swap 對 InnoDB 的影響

Percona 的老大拿 5.7 版做實驗，確認 swap 對 InnoDB 的影響：「The Impact of Swapping on MySQL Performance」。

測試的機器是 32GB RAM，作業系統 (以及 swap) 裝在已經有點年紀的 Intel 520 SSD 上，而 MySQL 則是裝在 Intel 750 NVMe 上。透過對 innodb_buffer_pool 的調整來看情況。

可以看到設為 24GB (記憶體 75% 的量) 時很穩定的在 44K QPS 與 3.5ms (95%)：

This gives us about 44K QPS. The 95% query response time (reported by sysbench) is about 3.5ms.

而當設成 32GB 的時候開始可以觀察到 swap i/o，掉到 20K QPS 與 9ms (95%)：

We can see that performance stabilizes after a bit at around 20K QPS, with some 380MB/sec disk IO and 125MB/sec swap IO. The 95% query response time has grown to around 9ms.

當拉到 48GB 的時候就更掉更多，6K QPS 與 35ms (95%)：

Now we have around 6K QPS. Disk IO has dropped to 250MB/sec, and swap IO is up to 190MB/sec. The 95% query response time is around 35ms.

作者發現掉的比率沒有想像中大：

When I started, I expected severe performance drop even with very minor swapping. I surprised myself by getting swap activity to more than 100MB/sec, with performance “only” halved.

這邊測試用的是 SSD，如果是傳統用磁頭的硬碟，對 random access 應該會很敏感而掉更多：

This assumes your swap space is on an SSD, of course! SSDs handle random IO (which is what paging activity usually is) much better than HDDs.

基本上還是要避免碰到 swap 啦，另外 comment 的地方剛好有提到前陣子在猜測的 best practice，測試時的 vm.swappiness 是設成 1，這應該是作者的 best practice：

Swappiness was set to 1 in this case. I was not expecting this to cause significant impact as swapping is caused by genuine (intended) missconfiguration with more memory required than available.

InnoDB 的 buffer pool preload 功能

Percona 的人討論了 InnoDB 提供的 buffer pool preload 功能：「Using the InnoDB Buffer Pool Pre-Load Feature in MySQL 5.7」。

就如同他所講的，因為硬體設備的進步 (主要是 SSD 的興起)，而導致 preload 的需求已經沒以前重要了：

Frankly, time has reduced the need for this feature. Five years ago, we would typically store databases on spinning disks. These disks often took quite a long time to warm up with normal database workloads, which could lead to many hours of poor performance after a restart. With the rise of SSDs, warm up happens faster and reduces the penalty from not having data in the buffer pool.

由於 SSD 的 random read 很快，反而可以直接推上線讓他邊跑服務邊 warm up。不過相對的，傳統硬碟的 InnoDB database 還是可以規劃需求，畢竟 random read 還是痛點...

Libgcrypt 與 GnuPG 的安全性問題

在「Security fixes for Libgcrypt and GnuPG 1.4 [CVE-2016-6316]」這邊看到這個歷史悠久的 bug：

Felix Dörre and Vladimir Klebanov from the Karlsruhe Institute of Technology found a bug in the mixing functions of Libgcrypt's random number generator: An attacker who obtains 4640 bits from the RNG can trivially predict the next 160 bits of output. This bug exists since 1998 in all GnuPG and Libgcrypt versions.

就這樣的行為，對於自己用的機器應該是還好... 不過得到 4640 bits 後就可以預測接下來的 160 bits，這個 RNG 有點囧 @_@

官方目前是認為應該還好：

A first analysis on the impact of this bug in GnuPG shows that existing RSA keys are not weakened. For DSA and Elgamal keys it is also unlikely that the private key can be predicted from other public information. This needs more research and I would suggest _not to_ overhasty revoke keys.

不過如果你有絕對的安全需求的話還是可以考慮 revoke 再重新生一把...

產生隨機地圖

在「Generating fantasy maps」這邊看到在講產生隨機地圖的方法，就像這樣細緻的地圖：

作者是依照「Polygonal Map Generation for Games」這篇的方法改善的，我之前看過但好像沒寫文章記錄下來...

兩篇文章裡面都寫得很詳細，一步一步提供用到的演算法以及範例說明。

V8 Engine 的 Math.random() 在新版被重寫了...

先前在「V8 的 Math.random() 亂度不足的問題」提到 Math.random() 因為使用 MWC1616 (Fast random number generation using 128 bit multimedia extension registers on Pentium class machines) 而不夠亂的問題。

這個問題在新版 V8 Engine 提出改善了：「There's Math.random(), and then there's Math.random()」。

Untitled drawing

新實作的方法是 xorshift128+，擁有極長的 period length：

This has been pointed out to us, and having understood the problem and after some research, we decided to reimplement Math.random based on an algorithm called xorshift128+. It uses 128 bits of internal state, has a period length of 2128 - 1, and passes all tests from the TestU01 suite.

將會在 Google Chrome 49 (目前是 47) 引入：

The new implementation landed in V8 4.9.41.0 within a few days of us becoming aware of the issue. It will become available with Chrome 49. Both Firefox and Safari switched to xorshift128+ as well.

同時還是再次提醒，這不是 CSPRNG，要用在密碼學相關應用還是要用專門的 library 來產生 pseudo random number：

Make no mistake however: even though xorshift128+ is a huge improvement over MWC1616, it still is not cryptographically secure.

V8 的 Math.random() 亂度不足的問題

在「TIFU by using Math.random()」這篇看到作者踩到地雷，於是在討論 V8 Engine 的 Math.random() 的亂度不足。

其實這個問提早在 2012 年就有人在 StackOverflow 上詢問：「Why is Google Chrome's Math.random number generator not *that* random?」，而且也回答得很清楚。

而 Mozilla 這邊在 2006 年也被提出了類似的問題：「Bug 322529 - Upgrade Math.random() to a better algorithm, such as Mersenne Twister」。

文章中間花了許多篇幅講 PRNG 的介紹，以及 cycle length 的說明，重點其實在結論的部份。

主要是因為 V8 Engine 的 Math.random() 實作的是 MWC1616 演算法 (Fast random number generation using 128 bit multimedia extension registers on Pentium class machines)，而這個演算法用起來也綁手綁腳：

If you’re only using the most significant 16 bits it has a very short effective cycle length (less than 2³⁰).

有兩個方向可以改善 (不衝突的方向)，一個是使用 CSPRNG (保證有極長的 cycle length)，另外一個請求 V8 Engine 把 Math.random() 的演算法換掉，像是 MT19937 這類 cycle length 超級長的演算法。

不知道後續有沒有機會改善...

InnoDB 對 Primary Key 的選擇

前幾天 Ant 在「淺入淺出 MySQL & PostgreSQL」剛好有提到，結果 Percona 這兩天也丟出了這個題目，不過這邊討論的是空間的問題：「Illustrating Primary Key models in InnoDB and their impact on disk usage」。

一樣的作法，Primary Key 的選擇有三種：

  • INT + AUTO_INCREMENT
  • BINARY(16) (Ordered UUID)
  • CHAR(36) (Random UUID)

用的是 Jeremy Cole 的 space-lsn-age-illustrate 畫出 LSN 的值 (InnoDB 的 Log Sequence Number，由於嚴格遞增，可以藉由這個值知道每個 page 最新被修改的時間)：

I then used the powerful tool innodb_space’s function space-lsn-age-illustrate (from Jeremy Cole’s innodb_ruby project) to plot the LSN (InnoDB’s Log Sequence Number, an always-incrementing value) pages from each table that uses the different Primary Keys via ASCII colour (so hot, right? Thanks Jeremy!!).

測試是 INSERT-only 的 case，雖然不太能理解為什麼要用 CHAR(36) 存 UUID，而非與 BINARY(16)，但可以看出一些 pattern。

有順序的 INT + AUTO_INCREMENT 與 BINARY(16) (Ordered UUID) 都可以看出層次 (一直往後寫)，而且也看得出來 BINARY(16) 比 INT 大了不少：

而 CHAR(36) 當然是最大的，而且寫入的 i/o 也最隨機：

利用 WPS 實做上的問題攻擊，而取得 WPA 密碼

在「Wi-Fi Router Attack Only Requires a Single PIN Guess」這邊看到利用 WPS 實做上的弱點攻擊而取得 WPA 的密碼。

投影片取自「Offline bruteforce attack on WiFi Protected Setup」這邊：

利用各種方法攻擊，像是不夠安全的 PRNG (Pseudo Random Number Generator)。

作者的建議是，關掉 WPS 會比較安全 XD

RAID 卡的電池維護

實際的世界都是由 workaround 疊 workaround 解決問題的...

MySQL 資料庫一般都用 RAID 10，利用 RAID 1 的特性保護資料，並且利用 RAID 0 的特性提昇 IOPS 能力。

而這些 RAID 卡通常都會提供 cache，預設應該都會開 read cache，可以大幅增加 random read 的速度。而另外也可以打開 write cache (也就是 write-back)，寫入時先寫到 cache 裡，RAID 卡馬上就會跟作業系統回報完成，藉以加速 random write 的速度。

但這樣就會有風險，當資料還沒寫入硬碟就斷電時就會遺失資料。所以在設定 write-back 的 RAID 卡上安裝電池就變成解法之一。

而電池會有壽命問題，所以配電池的 RAID 卡會每隔一陣子就放電測試電池可以撐多久，但在放電測試時，如果斷電就有可能造成資料遺失，於是又冒出很多方法解決。

也就是在「Learning to Deal With Learning」這篇提到 RAID 卡電池維護的事情。

每一層都是 workaround 想辦法解決問題，然後再用 workaround 解決前面造成的問題...

Anyway，有幾種解法，其中仍然對上層作業系統與應用程式透明的解法是：

  • 雙電池架構，很明顯的可以一次只測一顆。
  • 改用 NVRAM，就不需要電池了，不過速度以及成本會是另外一個問題。

另外，對上層作業系統與應用程式有影響的方式：

  • 放電測試時將 write cache 關閉，切回 write-through。這點在原文裡也有提到，效能其實會受到蠻大的影響。
  • 不放電測試了，但這樣的缺點就是拿安全性交換，當斷電時不知道能不撐過去。
  • 或是自己控制放電測試的時間，這可以配合上面切回 write-through 的方式，挑負載比較輕的離峰時間做。

看了下來雙電池架構還不錯，增加的成本還算可以接受，而且因為效能不受到影響，也確保資料安全性，整體維護起來比較簡單。而之後在規模更大的時候，應該就會直接考慮跳到自己放電測試的方式來處理電池問題...