npm 裡的 redis 與 ioredis

前幾天在噗浪的偷偷說上看到有人提到 npmtrends 上的 redis (官方的) 與 ioredis:「https://www.plurk.com/p/p6wdc9」。

意外發現以下載量來看,ioredis 已經超越官方的 redis 了:

找了一下差異,看起來的確有些團隊在 loading 很高的情況下會考慮用 ioredis 取代 redis:「Migrating from Node Redis to Ioredis: a slightly bumpy but faster road」。

但沒有特別需求的話應該還是會用官方版本?

AWS 官方推出了自己的 Amazon S3 FUSE 套件

看到「Mountpoint for Amazon S3」這個專案,AWS 自己推出了自己的 Amazon S3 FUSE 套件。Hacker News 上也有一些討論:「Mountpoint – file client for S3 written in Rust, from AWS (github.com/awslabs)」。

Amazon S3 的價錢比其他 AWS 提供的 storage 都便宜不少。以美東第一區 us-east-1 來說,S3 是 $0.023/GB,而 EBS (gp3) 要 $0.08/GB,即使是 EBS (st1) 也要 $0.045/GB。

S3 相較於 EBS 來說,多了 API call 的費用,所以對於不會產生大量 API call 的應用來說 (像是常常會寫很大包的資料到檔案裡),透過 FUSE 操作 Amazon S3 可以讓現有的套裝軟體或是程式直接跑上去。

另外一個常見的應用是讓套裝軟體或是現成的程式可以讀取 S3 的資料。

之前這類應用馬上會想到的專案是 s3fs-fuse,這個專案很久了,大家也都知道多人寫入的部份會是痛點。

這次 AWS 自己出來做的事情有點重工,看起來他想做的事情 s3fs-fuse 都解的差不多了,目前看起來唯一的賣點應該只有 Rust-based,但 s3fs-fuse 主要是 C++,其實也沒差到哪裡:

Mountpoint for Amazon S3 is optimized for read-heavy workloads that need high throughput. It intentionally does not implement the full POSIX specification for file systems.

目前專案還是 alpha release,不確定專案的方向到底是什麼...

華盛頓郵報怎麼把 Mapbox 換成其他 open source 方案

Hacker News 上面看到「How The Post is replacing Mapbox with open source solutions」這篇,講華盛頓郵報怎麼把 Mapbox 換成 open source 方案,對應的討論在「Replacing Mapbox with open source solutions (kschaul.com)」這邊。

維基百科有提到大概兩年前,2020 年底的時候 Mapbox GL JS 從開源授權換成私有授權了 (也可以參考先前寫的「Mapbox GL JS 的授權改變,以及 MapLibre GL 的誕生」這篇):

In December 2020, Mapbox released the second version of their JavaScript library for online display of maps, Mapbox GL JS. Previously open source code under a BSD license, the new version switched to proprietary licensing. This resulted in a fork of the open source code, MapLibre GL, and initiation of the MapLibre project.

裡面題到了四個工具。

第一個是 OpenMapTiles,下載部份的圖資使用,對於報導只需要某個區域很方便:

OpenMapTiles is an extensible and open tile schema based on the OpenStreetMap. This project is used to generate vector tiles for online zoomable maps. OpenMapTiles is about creating a beautiful basemaps with general layers containing topographic information.

第二個是 Maputnik,可以修改圖資呈現的方式:

A free and open visual editor for the Mapbox GL styles targeted at developers and map designers.

第三個是 PMTiles,可以將圖資檔案塞到一個大檔案裡面,然後透過 HTTP range requests 下載需要的部份就好,大幅下降 HTTP request 所需要的費用 (很多 CDN 會依照 HTTP request 數量收費):

Protomaps is a serverless system for planet-scale maps.

An alternative to map APIs at 1% the cost, via single static files on your own cloud storage. Deploy datasets like OpenStreetMap for your site in minutes.

最後就是 fork 出來開源版本的 maplibre-gl-js

MapLibre GL JS is an open-source library for publishing maps on your websites or webview based apps. Fast displaying of maps is possible thanks to GPU-accelerated vector tile rendering.

It originated as an open-source fork of mapbox-gl-js, before their switch to a non-OSS license in December 2020. The library's initial versions (1.x) were intended to be a drop-in replacement for the Mapbox’s OSS version (1.x) with additional functionality, but have evolved a lot since then.

這樣看起來好像可以用在像 KKTIX 這種下面顯示固定地圖的地方:

Pony ORM

Simon Willison 的 blog 上看到的東西:「Python’s “Disappointing” Superpowers」,裡面提到的原文是「Python’s “Disappointing” Superpowers」這篇,在講 Python 的工具。

雖然是說「disappointing」,但實際上是反義,在原文裡面提到了很多特別的工具,其中 Pony ORM 算是我覺得最有趣的了,他的寫法就非常的 Python:

select(c for c in Customer if sum(c.orders.price) > 1000)

也可以用 lambda 的形式來寫:

Customer.select(lambda c: sum(c.orders.total_price) > 1000)

這樣會產生出對應的 SQL:

SELECT "c"."id"
FROM "customer" "c"
  LEFT JOIN "order" "order-1"
    ON "c"."id" = "order-1"."customer"
GROUP BY "c"."id"
HAVING coalesce(SUM("order-1"."total_price"), 0) > 1000

不會產生 syntax error 的原因是因為他直接解讀 bytecode 分析,產生出對應的 SQL query:

A normal understanding of generator expressions suggests that the select function is consuming a generator. But that couldn’t explain the behaviour here. Instead, it actually introspects the frame object of the calling code, then decompiles the byte code of the generator expression object it finds, and builds a Query based on the AST objects.

用這樣的設計來達到語法的自由度。

看了一下也有一些 integration,像是 Flask 的「Integration with flask」與 FastAPI 的「Integration with FastAPI」。

不過應該是先看看,目前 Python 上用的主力還是 Django,有自己的 ORM 架構...

jQuery 3.6.2

看到 jQuery 出新版的消息:「jQuery 3.6.2 Released!」。

這個版本的說明裡面針對了 :has() 這個功能著墨,主要還是因為這功能 jQuery 支援很久了,而 ChromiumSafai 在最近都開始支援了:「Issue 669058: CSS selectors Level 4: support :has()」、「Using :has() as a CSS Parent Selector and much more」。

不過看起來 jQuery 要整合原生的 :has() 還是有技術困難,因為裡面可能會包括 jQuery 自己定義的 selector extension:

That was problematic in cases where :has() contained another jQuery selector extension (e.g. :has(:contains("Item"))) or contained itself (:has(div:has(a))).

總之,難得又看到 jQuery 的消息... 前一版的 3.6.1 是 2022/08/26,而 3.6.0 則是再一年多前的 2021/03/02,再往前面是 3.5.1 的 2020/05/04 與 3.5.0 的 2020/04/10。

是個歷史...

Python 上的 reals 套件 (需要 3.10+ 以上才能裝)

看到「A lightweight python3 library for arithmetic with real numbers.」這個有趣的 Python 延伸套件,可以用他進行高精度的實數運算...

一開始在 Python 3.9 環境裝,結果就跳出需要 3.10+ 的環境,想了一下,開了一個 Docker container 裝 pyenv 來測,測過以後覺得還蠻有趣的,看起來之後把預設環境變成 3.10+ 應該會裝起來用...

這個 reals 的重點在於保證顯示數字的正確性:

It allows you to compute approximations to an arbitrary degree of precision, and, contrary to most other libraries, guarantees that all digits it displays are correct.

目前支援的常數與操作有這些:

Constants: pi, e, phi
Functions related to powers: sqrt, exp, log
Operators: negation, addition, subtraction, multiplication, division, powers
Trigonometric functions: sin, sinh, csc, csch, cos, cosh, sec, sech, tan, tanh, cot, coth

用法的部份,先把 reals 拉進來:

>>> from reals import sqrt

然後用法算直覺:

>>> sqrt2 = sqrt(2)
>>> sqrt2
<reals._real.Real object at 0x10d182560 (approximate value: 1.41421)>
>>> sqrt2.evaluate(10)
'1.4142135624'
>>> '{:.10f}'.format(sqrt2)
'1.4142135624'
>>> sqrt2.to_decimal(10)
Decimal('1.4142135624')

不過作者有提到效能沒有處理到很好,所以應該是拿來快速做一些運算得到結果而已。

JavaScript 上的 fuzzy search library

Hacker News Daily 上看到 Show HN (作者自己或是主要的 contributor 上來發表的作品) 給了一個號稱速度很快,吃資源很少的 fuzzy search library:「Show HN: uFuzzy.js – A tiny, efficient fuzzy search that doesn't suck (github.com/leeoniya)」。

這種已經發展許久,但突然有一天有人說他的東西超好超棒棒的,除非是有新的基礎演算法突破,不然馬上就會想到很經典的「Three circles model」,中間的那些區塊就懶的畫上去了:

依照他的「測試」,可以看到他宣稱完全領先的狀態:

但回過頭來看評論:

Thank you for this!

I am also quite frustrated with the current state of full text search in the javascript world. All libs I've tried miss the most basic examples and their community seems to ignore it. Will give yours a try but it already looks much better from the comparison page.

Edit: Nope, your lib doesn't seem to handle substitution well (THE most common type of typo), so yep, we are back to square one ...

From fuzzy search I expected that entering "super meet boy" or "super maet boy" will return "Super Meat Boy" but unfortunately currently it doesn't work this way and it's quite disappointing.

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

看起來這個 library 沒有辦法解決 fuzzy search 最常見的 case (小 typo),依照範例描述的更像是 substring 搜尋加上一些額外的的功能,反而比較像是 auto completion library,或是講的比較廣一點,可以算是 auto suggestion library。

不過我覺得真正的重點 (對我來說的重點) 是下面的比較表格,因為列出了目前市場上的方案,這份清單之後可以拿來參考...

這次 OpenSSL 的兩個 CVE

難得在 Hacker News 首頁上看到 OpenSSLCVE:「OpenSSL Security Advisory [5 July 2022]」,相關的討論在「OpenSSL Security Advisory (openssl.org)」。

第一個 CVE 是 RCE 等級,但觸發條件有點多:

首先是 RSA 2048bits,這個條件應該算容易發生的。

第二個是,因為這個安全問題是因為 OpenSSL 3.0.4 才引入的程式碼,而 OpenSSL 3.0.4 是 2022/06/21 發表的,未必有很多人有升級。

第三個是,因為這次出包的段落是用到了 AVX-512 指令集,一定要 Intel 或是 Centaur 的 CPU,後面這家公司前身就是威盛 (VIA) 的一員,去年賣給了 Intel (然後發現連官網用的 domain 都沒續約...)。

AMD 雖然在 Zen 4 架構上支援 AVX-512,但還沒推出產品,所以直接閃避 XD

另外第三個還有額外的限制,因為這次用到的是 IFMA 指令集,所以也不是所有有支援 AVX-512 的 CPU 都會中獎:

只看 Intel 的部份,第一個支援 IFMA 的是 2018 年推出的 Cannon Lake,這個架構只有一顆行動版的 Intel® Core™ i3-8121U Processor

真正大量支援 IFMA 的是 2019 後的 Intel CPU 了,但到了去年推出的 Alder Lake 因為 E-core 不支援 AVX-512 的關係 (但 P-core 支援),預設又關掉了。

所以如果問這個 bug 嚴不嚴重,當然是很嚴重,但影響範圍就有點微妙了。

接下來講第二個 CVE,是 AES OCB 的實做問題,比較有趣的地方是 Hacker News 上的討論引出了 Mosh 的作者跳出來說明,他居然提到他們在二月的時候試著換到 OpenSSL 的 AES OCB 時有測出這個 bug,被 test case 擋下來了:

Mosh uses AES-OCB (and has since 2011), and we found this bug when we tried to switch over to the OpenSSL implementation (away from our own ocb.cc taken from the original authors) and Launchpad ran it through our CI testsuite as part of the Mosh dev PPA build for i686 Ubuntu. (It wasn't caught by GitHub Actions because it only happens on 32-bit x86.) https://github.com/mobile-shell/mosh/issues/1174 for more.

So I would say (a) OCB is widely used, at least by the ~million Mosh users on various platforms, and (b) this episode somewhat reinforces my (perhaps overweight already) paranoia about depending on other people's code or the blast radius of even well-meaning pull requests. (We really wanted to switch over to the OpenSSL implementation rather than shipping our own, in part because ours was depending on some OpenSSL AES primitives that OpenSSL recently deprecated for external users.)

Maybe one lesson here is that many people believe in the benefits of unit tests for their own code, but we're not as thorough or experienced in writing acceptance tests for our dependencies.

Mosh got lucky this time that we had pretty good tests that exercised the library enough to find this bug, and we run them as part of the package build, but it's not that farfetched to imagine that we might have users on a platform that we don't build a package for (and therefore don't run our testsuite on).

這有點有趣 XDDD

Perl 的 Regular Expression 的強度:NP-complete

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

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

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

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇,裡面試著用 Perlregular 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

Python 裡使用超過 Double Precision 的運算

Hacker News 上爬到的,是一篇 2019 的文章:「When Double Precision Is Not Enough (adambaskerville.github.io)」,原文在「T>T: When Double Precision is Not Enough」。

作者是拿矩陣 (matrix) 的運算當例子,遇到了 double precision 造成的計算誤差問題:

There is no error with the program; this discrepancy is caused by a loss of numerical accuracy in the eigenvalue calculation due to the limitation of hardware double precision (16-digit).

解法是用 mpmath 增加精度,算是一種暴力解,到要注意計算會慢很多:

Note that this library is incredibly slow for large matrices, so is best avoided for most applications.

另外在 Hacker News 的討論串裡面看到個有趣的東西:「Herbie: Automatically Improving Floating Point Accuracy」這個專案,你把公式丟進去,Herbie 會試著提供等價公式來維持精度,像是 \sqrt{x+1} - \sqrt{x} = 1 / ( \sqrt{x+1} + \sqrt{x} ) 這種東西。

半自動化幫你改善...