Tag: state

LLL lattice basis reduction algorithm

短短幾天內看到兩個不同的地方用到了 1982 年發現的「Lenstra–Lenstra–Lovász lattice basis reduction algorithm」。

第一個是「Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG (github.com/spawnmason)」這篇，作者群利用 LLL 去分析 java.util.Random 的內部狀態，進而得到其他玩家的地點資訊：

Every time a block is broken in Minecraft versions Beta 1.8 through 1.12.2, the precise coordinates of the dropped item can reveal another player's location.

"Randar" is an exploit for Minecraft which uses LLL lattice reduction to crack the internal state of an incorrectly reused java.util.Random in the Minecraft server, then works backwards from that to locate other players currently loaded into the world.

另外一個是在 Hacker News 上面的 id=40080651 提到，前幾天 PuTTY 的 p521 問題在底層也用到了 LLL：

LLL lattice reduction is the same algorithm that can be used for cracking PuTTY keys from biased nonces from the CVE a few days ago. 'tptacek explained a bit about the attack (and links to a cryptopals problem for it, which I can almost pretend to understand if I squint) https://news.ycombinator.com/item?id=40045377

從維基百科的內容也可以看出來 application 非常多，不光是密碼學的領域用到，看起來值得花點力氣來了解...

紐約州在推動電子產品的維修權

在清 Hacker News Daily 的時候看到「New York could become first state with a ‘Right to Repair’ law for electronic devices」這篇，在講紐約州有團體在推動電子產品的維修權。

先前有提過歐盟對電子產品的維修權有在推動法案 (參考「歐盟在推動的設備維修權...」這篇)，確保十年內有料可以維修，後來這個法案已經生效了：「New EU ‘right to repair’ laws require technology to last for a decade」。

可以觀察一下會不會過...

Perl 的 Regular Expression 的強度：NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目，就像是維基百科上的條列：

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇，裡面試著用 Perl 的 regular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。

Recursive descent parser 可以當作是 CFG 的子集合，而 CFG 對應到的語言是 CFL，另外他對應到的自動機是 PDA。

我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern)，所以他能接受的 language 已經超過 RL，但我很好奇他能夠做到什麼程度。

用搜尋引擎翻了翻，查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library)：「Which languages do Perl-compatible regular expressions recognize?」。

在裡面有人提到「The true power of regular expressions」這篇文章，裡面給了一個在 PTIME 演算法，將 3SAT 轉換到 PCRE 裡解，這證明了 PCRE 是 NP-hard；另外也很容易確認 PCRE 是 NP，所以就達成了 NP-complete 的條件了...

本來一直以為 PCRE 只是 CFG/CFL/PDA 而已，沒想到這麼強，NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD

The State of JS 2021

在 Hacker News 上看到「The State of JS 2021」這個，另外也翻了一下 Hacker News 上的討論「State of JavaScript 2021 (stateofjs.com)」，算是年度總結看一下今年 JS 圈子又搞出了什麼新東西，或者說又喜新厭舊了哪些東西 XDDD

看了幾張比較有趣的，首先是「The State of JS 2021: Libraries」這張總表，右上角的表示用的人比較多，而且評價正面的選擇：

然後同一頁也有直接依照滿意度分級列出來：

在「The State of JS 2021: Front-end Frameworks」這頁可以看到 JS 前端喜新厭舊的情況，2018 的時候 Vue.js 上來，然後 2019 下去，2020 時 Svelte 上來，2021 下去，換 Solid 上來：

在「The State of JS 2021: Back-end Frameworks」這邊則是看 JS 後端的喜新厭舊，2020 時 Next.js 爬上來，2021 就被踢下去，換 SvelteKit 上來：

其他的也都可以看出來一直在「迭代」，整個 JS ecosystem 的概念一直都是砍掉重練 XD

Percona XtraDB Cluster (PXC) 節點離開太久後的惡搞法

在 Percona 的「How To Recover Percona XtraDB Cluster 5.7 Node Without SST」這邊看到的技巧，不過只能用在 5.7 版，不能用在 8.0 版。我猜這個方法也可以用在其他跑 Galera Cluster 的資料庫上...

維護一組 Percona XtraDB Cluster 時一個常見的問題是，當節點離線太久後有機會無法用 IST (Incremental State Transfer) 跟回來，也就是只要把先前還沒有同步的部份更新進資料庫的方法，這時候就會需要用 SST (State Snapshot Transfer)，變成抓整個 full copy。

作者提出來的方法是基於 IST 的大小通常比較小，但 binlog 通常都留蠻久的，所以可以利用 binlog 來幫 IST。

方法是先把 Galara Cluster 關掉，用 MySQL 傳統的 replication 同步到一定程度後，再把 IST 相關的位置設定指到已經同步的位置，接著再把 Galara Cluster 接上去就可以恢復了。

這個方法是 5.7 版限定，因為 8.0 的年代沒辦法改 Galara Cluster 的 wsrep 位置資訊：

Unfortunately, a similar solution does not work with Percona XtraDB Cluster 8.0.x, due to the modified way wsrep positions are kept in the storage engine, hence the trick with updating grastate.dat does not work as expected there.

我覺得可能 Percona 之後會弄出 patch 讓使用者可以改...

家裡電腦裝 Ubuntu 18.04

上個禮拜四家裡的桌機開不了機，找了一天發現是系統的 SSD 掛掉了，就買了張 M.2 SSD，然後計畫順便把本來的 Ubuntu 16.04 升級到 Ubuntu 18.04，但 Ubuntu 18.04 把預設的界面從 Unity 換成 GNOME (然後披上 Unity 的皮)，加上前陣子系統從 Intel 平台換到 AMD，整個狀況變得超混亂之後，就變成一連串踩地雷的過程...

最一開始是 UEFI + LUKS 的安裝問題，本來想裝到 M.2 SSD 上面，但 Ubuntu 18.04 的 grub-install 就是硬寫到 /dev/sda 不能改：「“Unable to install GRUB in /dev/sda” when installing GRUB」，照著這篇的 workaround 用還是不行，最後放棄，直接生一顆 SATA SSD 接到 SATA Port 1，把 M.2 當作資料碟。

硬體相關的問題：

軟體相關的問題：

  • 目前不支援從 GUI 設定 PPPoE 的網路 (沃槽)，幾種方式裡面我推薦用 pppoeconf 設定會比較好，然後可以改 /etc/ppp/options 加上 IPv6 的設定。
  • 本來想裝 gnome-shell-extension-system-monitor 觀察系統狀態，但會造成系統超級卡，關掉後就變成普通的卡 (後來就找到 Intel I211-AT 的那個問題了)。

現在至少是堪用的程度了，接下來就是不斷的補各種設定...

WordPress 在 Internet 上的情況

WordPress 在 Internet 有很大的佔有率，在「Usage statistics and market share of WordPress for websites」這邊有一直更新的資料，現在是：

WordPress is used by 59.9% of all the websites whose content management system we know. This is 29.1% of all websites.

這數字可以參考看看。而在「State of the WordPress ecosystem」這邊就看到有人在分析 WordPress 在整個 Internet 上的情況。可以看到裡面有蠻多都是透過 BigQuery 分析出來的...

在分析整個頁面的平均下載量時，可以看到 WordPress 的頁面比較肥：

We get 1590 KB for wordpress=false and 1897 KB for wordpress=true.

但是在 WordPress 上未最佳化的圖片比較少，原文裡猜測是歸功於 plugin 的關係：

@amedina I wonder if this has to do with the availability of tools/plugins in the WordPress ecosystem that optimize images effortlessly, as opposed to other web development pipelines that require manual image optimization or installation of specialized tools.

所以就跑去分析了 WordPress 上使用了哪些 plugin，不過這是看 web request 以及 path 得到的，如果 plugin 是純粹在內部執行的話就看不到了：

整個分析還蠻有趣的，而且還在進行...

查看 Percona XtraDB Cluster 在 IST 時的進度

Percona 的「Tracking IST Progress in Percona XtraDB Cluster」這篇介紹了 PXC 在 IST 時的進度。

是個新功能，很簡單的可以看到目前進度，也可以拿來當作 health check 的一部分，避免開機剛起來時開始提供服務：

mysql> show status like 'wsrep_ist_receive_status';
+--------------------------+--------------------------------------------------------+
| Variable_name | Value |
+--------------------------+--------------------------------------------------------+
| wsrep_ist_receive_status | 3% complete, received seqno 1421771 of 1415410-1589676 |
+--------------------------+--------------------------------------------------------+
1 row in set (0.00 sec)
....
mysql> show status like 'wsrep_ist_receive_status';
+--------------------------+---------------------------------------------------------+
| Variable_name | Value |
+--------------------------+---------------------------------------------------------+
| wsrep_ist_receive_status | 52% complete, received seqno 1506799 of 1415410-1589676 |
+--------------------------+---------------------------------------------------------+
1 row in set (0.00 sec)
....
mysql> show status like 'wsrep_ist_receive_status';
+--------------------------+---------------------------------------------------------+
| Variable_name | Value |
+--------------------------+---------------------------------------------------------+
| wsrep_ist_receive_status | 97% complete, received seqno 1585923 of 1415410-1589676 |
+--------------------------+---------------------------------------------------------+
1 row in set (0.00 sec)
mysql> show status like 'wsrep_ist_receive_status';
+--------------------------+-------+
| Variable_name | Value |
+--------------------------+-------+
| wsrep_ist_receive_status | |
+--------------------------+-------+
1 row in set (0.00 sec)

Galera Cluster (Percona XtraDB Cluster) 同步速度的改善

Percona 的「State Snapshot Transfer (SST) at a glance」這篇給了 Galera Cluster (也就是 Percona XtraDB Cluster) 在同步速度的改善方案，整篇文章一步一步改善，從 51 分鐘降到 18 分鐘。

劃幾個重點。

首先是同步時的設定可以放到系統 my.cnf 的 [sst] 內，像是這樣：

[sst]
inno-apply-opts="--use-memory=20G"

其中改善最大的也就是 --use-memory，依照作者測試的數據，光這步就從 51 分鐘降到 30 分鐘。不過這邊要小心本來就有跑的 mysqld，如果 OOM 就慘了...

再來講的是 wsrep_slave_threads，不同於上面的 sst only 設定，這是在一般性的 tuning (平常在跑的參數，放在 [mysqld] 內)，改完後速度 30 分鐘再提升到 25:32。

然後是壓縮的方式改用支援多 CPU 的 pigz：

[sst]
inno-apply-opts="--use-memory=20G"
compressor="pigz"
decompressor="pigz -d"

很明顯是個 shell command 類的設定，所以如果真的想要測的話，可以再從 -1 測到 -9，作者在這邊沒測，不過效果也很明顯了，從 25:32 降到 21 分鐘。

最後一個大的改變是建議有專門同步的節點 (Donor node)，這個節點上不會有 SQL query 來影響效能，這樣可以讓 pigz 的效率更高：

Since node2 is not getting application traffic, moving into the Donor state and doing an expensive SST with pigz compression should be relatively safe for the rest of the cluster (in this case, node1).

時間最後降到 18:33。

NSA 每天從全世界的基地台蒐集行動電話資料，所以全民公敵裡演的都是真的嘛...

雖然也不怎麼意外了，不過看到還是想要碎碎唸一下...

NSA 每天從「全世界的」基地台蒐集五十億筆資料：「NSA Tracking Cellphone Locations Worldwide」。

全世界啊... 感覺 Hadoop 之類的 big data 技術論壇找 NSA 很有看頭啊 @_@

Update：有人給了模擬案例了「Meet Jack. Or, What The Government Could Do With All That Location Data」：