compatible

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

Babelfish：讓 PostgreSQL 可以吃 Microsoft SQL Server 的協定

看到「Goodbye Microsoft SQL Server, Hello Babelfish」這篇，AWS 對 Aurora (PostgreSQL) 推出了可以吃 Microsoft SQL Server 協定的 Babelfish：

Today, we are making Babelfish for Aurora PostgreSQL available. Babelfish allows Amazon Aurora PostgreSQL-Compatible Edition to understand the SQL Server wire protocol.

查了一下資料發現是去年年底的時候發表的：「Want more PostgreSQL? You just might like Babelfish」，不過當時沒注意到這東西，大概是因為是 preview 的關係：

We are open sourcing Babelfish in 2021. Until then, you can use Babelfish on Amazon Aurora in a preview to see how it works and to get a sense for whether this is the right approach for you.

用起來不知道怎樣，但感覺很值得注意，目前雖然沒用到 Microsoft SQL Server 的東西，但以後遇到可以考慮看看...

除了在 AWS 上用以外，也可以自己到 GitHub 上拉 patch 回來上：「babelfish-for-postgresql」。

話說回來，PostgreSQL 被 AWS 拿來用在好多地方啊，先前大家也猜是 DocumentDB 後面是 PostgreSQL (參考「大家在猜 Amazon DocumentDB 的底層是不是 PostgreSQL...」這篇)，不知道之後會不會想要跟 Oracle 的律師打架...

用 vttest 測試 terminal 程式實做的相容性

看到「Wez's Terminal」，又一個用 GPU 加速的 terminal 專案，跑去翻一下 Hacker News 上的討論，意外的翻到有趣的東西：「Wezterm – A GPU-accelerated cross-platform terminal emulator and multiplexer (github.com/wez)」。

目前最前面的討論是這個：

I just saw this and after a quick checkout of the latest release (which is what I can quickly install), I feel a bit disappointed. Here is yet another GPU-accelerated terminal that claims to be a VT500 (judging by its Device Attributes report), sets TERM to xterm-256color, while having holes in basic VT100 support (just ran VTTEST in it and saw glaring issues, need not look further than basic VT100 tests, TAB setting/resetting, cursor save/restore).

比較有趣的是裡面提到了 vttest 這套測試軟體可以測 terminal 的標準相容性，在 vttest 的官網上有提到可以測 VT100、VT220 與 VT520：

Vttest tests the compatibility (demonstrates the non-compatibility) of so-called “VT100-compatible” terminals. In conformance of the good old hacker traditions, the only documentation of this program is the source code itself. To understand it, you also need a copy of the original VT100 manual from DEC.

Additional tests (past version 1.7) are provided for analysis of vt220 through vt520 terminals, as well as variants of xterm.

另外比較驚訝的是，terminal 下可以作到這樣的效果 (這邊看官方的截圖應該是 VT420？)：

回到原來講標準相容性的問題，對於泡在 terminal 下的人來說超級重要，有工具可以測試幫助不少... vttest 這套程式在 Ubuntu 內可以直接裝來用：「Ubuntu – Package Search Results -- vttest」。

Backblaze B2 支援相容 Amazon S3 的 API

Backblaze 宣佈支援相容 Amazon S3 的 API：「Backblaze B2 Cloud Storage Now Has S3 Compatible APIs」。

Amazon S3 的 API 算是 object storage 這個領域的 de facto standard 了，支援 Amazon S3 相容層可以讓現有的工具直接套用上去。

很多 client 軟體都藉著設定 API endpoint 的方式來支援 (通常預設會是 Amazon S3 的 s3.amazonaws.com)，這次的 endpoint 可以從 B2 的文件「S3 Compatible API」裡看到：

The format for endpoints for the Backblaze S3 Compatible API:

https://s3.<region>.backblazeb2.com

The Backblaze S3 Compatible API endpoints only accept connections over HTTPS. Non-secure connections will be rejected. The AWS SDKs and most integrations only require an Endpoint URL like the above (without the bucket name included).

另外也支援使用 bucket name 的形式操作：

If making the HTTP calls directly, the Backblaze S3 Compatible API supports specifying the bucket name in the hostname of the URL or in the path section of the URL. Both URLs below are valid examples of an endpoint calling a bucket:

https://bucketname.s3.us-west-001.backblazeb2.com

https://s3.us-west-001.backblazeb2.com/bucketname

B2 的另外一個優勢是 2018 的時候就跟 Cloudflare 合作 (參考「Backblaze 與 Cloudflare 合作，免除傳輸費用」)，從 B2 到 Cloudflare 的流量是不收費的，再加上 Cloudflare 的流量也可以是免費的，組合起來就變成一個很便宜的方案 (只有 B2 的 storage cost)。

PHP 的 Memcached 的眉眉角角...

把 PHP 的 Memcached 整理一下，未必適合其他人用。

設定上：

平常應該要打開 libketama 相關設定，包含了 OPT_DISTRIBUTION 與 OPT_LIBKETAMA_COMPATIBLE。
多台 server 要注意使用 hostname 或是 IP address 連線 (尤其跨程式語言時)，在 consistent hash 時會有差異。要避免因為 hostname 發生的問題，可以把這段設定放到 JSON 檔裡與其他程式語言共用。
使用 SERIALIZER_JSON，一樣是為了與其他程式語言相容。

使用上：

add() 在 key 存在時會失敗，set() 則會覆蓋過去。
在 add()、set() 裡的 expiration 參數是 UNIX timestamp，而非直覺的秒數...
get() 的 callback 不應該使用，因為無法設定 expire time。
memcached 的 manual 有寫預設值是使用冒號 (:) 當作 key 的分隔，這對於統計資料會有幫助。

先整理到這...