Home » Computer » Archive by category "Programming"

HyperLogLog 與 Bloom Filter

看到 FacebookPresto 裡增加使用 HyperLogLog 計算數量的能力,突然想到常常忘記這兩個拿準確度換速度的資料結構:「HyperLogLog in Presto: A significantly faster way to handle cardinality estimation」。

HyperLogLog (HLL) 是解決 Count-distinct problem 的資料結構,用很少的記憶體就可以給出一個誤差不大的值 (用 1.5KB 的空間處理十億等級的資料,誤差大約在 2%),所以 Presto 利用這個資料結構引進了 APPROX_DISTINCT() 以及其他的函數,就很容易在 L2/L3 cache 裡運算,藉此大幅提昇速度。

Depending upon the problem at hand, we can achieve speed improvements of anywhere from 7x to 1,000x.

先前也提過 Reddit 也用 HLL 統計資料:「Reddit 在處理 Page View 的方式」。

Bloom Filter 也是在處理大量資料的問題,但這個資料結構的功能不太一樣,是給出「有沒有存在」,使用空間與誤差大約是 10 bits per key (1% false positive),另外先前也有提到一些變形,可以提供其他功能。像是「Quotient filter」與「Cuckoo Filter:比 Bloom Filter 多了 Delete」。

AWS 的推薦演算法服務:Amazon Personalize

AWS 把推薦演算法包成服務拿來來賣,叫做 Amazon Personalize:「Amazon Personalize – Real-Time Personalization and Recommendation for Everyone」。

把後面的演算法隱藏起來,只要給使用者的評價資料就可以了,像是文章裡的範例:

userId,movieId,rating,timestamp
1,2,3.5,1112486027
1,29,3.5,1112484676
1,32,3.5,1112484819
1,47,3.5,1112484727
1,50,3.5,1112484580

可以看出來這個使用者對 2,29,32,47,50 這些 movieId 在不同的時間點都給了 3.5 分的評分。

然後經過一連串的 API 操作 (有些參數可以調整,但主要是叫 AWS 運算,並且建立 real-time 的服務),就可以看到推薦哪些其他的 item 了:

$ aws personalize-rec get-recommendations --campaign-arn $CAMPAIGN_ARN --user-id $USER_ID --query "itemList[*].itemId"
["1210", "260", "2571", "110", "296", "1193", ...]

而從 Pricing 的頁面可以看到支援 real-time data 與 batch data:

DATA INGESTION
You are charged per GB of data uploaded to Amazon Personalize. This includes real-time data streamed to Amazon Personalize and batch data uploaded via Amazon S3.

這其實是很多網站都很需要的功能...

AWS Lambda 可以直接掛進 ALB 了...

AWS 這次對 Lambda 還發表了不少功能,除了前面提到透過 Layout 支援其他語言以外 (e.g. Ruby),這邊要再提到另外一個重要的功能。

這次是 ALB 可以直接呼叫 lambda function 了:「Lambda functions as targets for Application Load Balancers」。

以前還得靠 API Gateway 整半天 (因為版本設定),現在直接用 ALB 接就可以了?而且 ALB 這邊有規劃對應的 quota:

There is no change to the hourly price of ALB. The load balancer capacity units (LCUs) of ALB now include 0.4 GB per hour of data processing to AWS Lambda targets.

這樣就更接近 serverless 了...

在 MySQL 上遇到 Replication Lag 的解法

看到 Percona 的 blog 上寫了一篇 MySQL 遇到 replication lag 時要怎麼解決:「MySQL High Availability: Stale Reads and How to Fix Them」,另外在留言也有人提到 Booking.com 的解法:「How Booking.com avoids and deals with replication lag」。

在業務成長到單台 MySQL server 不夠用的情況下,最簡單的擴充方式是架設 slave server,然後把應用程式裡讀取的部份導到 slave 上 (也就是 R/W split),但因為 MySQL 的 replication 是非同步的,所以有可能會發生在 master 寫入資料後 slave 還讀不到剛剛寫的資料,也就是 replication lag。

這就大概有幾種作法,一種是當發現 lag 時就回 master 讀,但通常這都會造成 master 過載... 所以另外一種改善的作法是發現 lag 時就換其他 slave 看看,但這個方法就不保證讀的到東西,因為有可能所有的 slave 都 lag。

以前遇到的時候是拆情境,預設還是 R/W split,但敏感性的資料處理以及金流相關的資料就全部都走 master。

不過文章裡的解法更一般性,在寫入時多寫一份資料,然後在 slave 等這組資料出現。唯一的缺點就是要 GC 把多寫的資料清掉...

同樣的想法,其實可以讓 MySQL 在 commit 時直接提供給 binlog 或 GTID 的資訊,然後在 slave 等待這組 binlog 或 GTID 被執行。

看起來算是很不錯的解法,不知道各家 framework 對這些方式的支援度如何...

走不同方向的 Git Hosting:sr.ht

看到「sr.ht, the hacker's forge, now open for public alpha」這篇,講 sr.ht 這個 Git Hosting。

文章裡面有提到,目前大多數的 Git Hosting 都很像,不管是 BitbucketGitLab、其實大家都是抄 GitHub 的界面與功能抄得很開心...

sr.ht 則是從不同的角度來設計 Git Hosting,避免了大量 js 的界面,但還是提供了很豐富的功能 (支援 markdown 文件、CI、透過 mailing list 討論、有一個 ticket system 可以放各種事項、wiki、...)。

其實還是支援了現在 Git Hosting 常見的功能,只是功能與界面上不太相同而已 XD

AWS 決定花力氣支援 OpenJDK (Corretto 計畫)

AWS 推出了 Amazon Corretto (其中 Corretto 這個名字應該是取自 Caffè corretto,還是跟咖啡有關的字),提供 OpenJDK 的長期支援:「Introducing Amazon Corretto, a No-Cost Distribution of OpenJDK with Long-Term Support」。

文章裡提到了幾個重點,第一個是目前先推出了 Corretto 8 Preview (對應到 OpenJDK 8),而之後 GA 會推出 UbuntuRHEL 上的套件,另外也打算推出 Corretto 11 (對應到將來的 OpenJDK 11):

The Corretto 8 preview corresponding to OpenJDK 8 is available at this time for Amazon Linux 2, Microsoft Windows, and macOS platforms and Docker image. Preview builds can be downloaded by visiting aws.amazon.com/corretto. General Availability is planned for Q1 2019, and will also include Ubuntu and Red Hat Enterprise Linux platforms. Corretto 11 builds corresponding to Open JDK 11 on these platforms will follow with ample time for testing before April 2019.

再來是支援期都差不多是四~五年:

Amazon will distribute security updates to Corretto 8 at no cost until at least June, 2023, and to Corretto 11 until at least August, 2024.

這樣在又多了一些選擇...

實做 Twitter 同步到 Facebook 的程式

幾個月前 Facebook 把 API 拿掉了,大家都不能用 API 發文,本來想說就放掉這個平台,結果被老人家問怎麼都沒更新,因為老人家都是靠兒子的 Facebook 確認生存,看到沒更新就很擔心... XD

由於 API 沒得用了,所以得自己 hack。這邊先列重點:

  • chromium + VNC 登入後,用 chromium headless + selenium 發文。
  • 對於「網頁的穩定性」來說 (i.e. 常不常改版造成我的程式發文失敗),mbasic(.facebook.com) > m > www。

比較重要的方向就是這些,其他的其實就是磨時間、踩地雷,然後把程式刻出來:「gslin/twitter2facebook」。

Cloudflare 的 Workers KV

Cloudflare 推出了 Workers KV 服務:「Building With Workers KV, a Fast Distributed Key-Value Store」。

是個 key-value 結構服務 (全球性,eventually consistent,約 10 秒的同步時間),key 的限制是 2KB,value 是 64KB,一個 namespace 最多 10 億筆資料。

讀取可以到 100k+ read/s,但寫入是 1 write/s/key,可以看出來主要是為了讀取資料而設計的。

現有的 worker ($5/month) 會送一些量,包括 1GB 的空間與一千萬次的讀取:

Your $5 monthly Workers compute minimum includes 1 GB of KV storage and up to 10 million KV reads. If you use less than the 10 million included Worker requests now, you can use KV without paying a single cent more.

超過的部份另外再收:

Beyond the minimums, Workers KV is billed at $0.50 per GB-month of additional storage and $0.50 per million additional KV reads.

這樣好像整個 blog 的基本功能都可以直接在上面跑了... 而搜尋靠外部服務,圖片與影音也可以靠外部空間協助?

Archives