Tag: data

在 PostgreSQL 裡，當 UUID 當作 Primary Key 時要怎麼處理

繼續清 tab，在「PostgreSQL and UUID as Primary Key (maciejwalkowiak.com)」這邊看到的，原文是討論 PostgreSQL 要怎麼處理 PK 是 UUID 的情況：「PostgreSQL and UUID as primary key」。

文章開頭作者就說了，這篇不是要戰 PK 要不要用 UUID，而是已經決定要用了 (i.e. 通常不是你決定的)，在接手以後要怎麼用比較好：

Considering the size of UUID it is questionable if it is a right choice, but often it is not up to us to decide.

This article does not focus on "if UUID is the right format for a key", but how to use UUID as a primary key with PostgreSQL efficiently.

首先是 PostgreSQL 從 8.3 版 (2008 年) 就支援 UUID 的資料型態了，這點從 release note 可以看到：「PostgreSQL 8.3.0」，所以要當 PK 的話沒什麼道理不考慮他。

用 UUID 的空間上就是 128-bit data (16 bytes)，相比於 TEXT 會省蠻多的，尤其 PK 常常會被其他表格 reference 到 (像是 foreign key) 會在其他表格也省下來：

Table that uses text is 54% larger and the index size 85% larger.

第二點則是考慮到 UUID 本身的特性，以前的 UUID 因為是亂數生成的 (通常會用 UUIDv4)，對寫入 B-tree 類的資料結構不是很有效率，改用 UUIDv7 (差不多是這兩年陸陸續續發展出來的規格) 會得益於與 timestamp 有關，對 B-tree 寫入的效率會好很多：

Random UUIDs are not a good fit for a B-tree indexes - and B-tree index is the only available index type for a primary key.

B-tree indexes work the best with ordered values - like auto-incremented or time sorted columns.

UUID - even though always looks similar - comes in multiple variants. Java's UUID.randomUUID() - returns UUID v4 - which is a pseudo-random value. For us the more interesting one is UUID v7 - which produces time-sorted values. It means that each time new UUID v7 is generated, a greater value it has. And that makes it a good fit for B-Tree index.

作者的測試可以看到寫入速度與 UUIDv4 相比比快不少：

BUT we can clearly see, that inserting UUID v7 is ~2x faster and inserting regular UUID v4.

總結來說，當 PK 已經決定是 UUID 後，主要就是這兩個重點可以注意的，當然 Hacker News 上更熱鬧的是兩派人馬在吵要用 integer 類的 SERIAL/BIGSERIAL 還是用 UUID，那又是另外一個話題了...

如果早個二十年前對 memory size 斤斤計較的情況下，答案鐵定是 integer 類的，但年代不同了...？

AWS Direct Connect 開始提供 400Gbps 的選擇

AWS Direct Connect 開始有 400Gbps 的選擇了：「AWS Direct Connect announces native 400 Gbps Dedicated Connections at select locations」。

依照裡面的 AWS Direct Connect Locations 連結可以知道目前開放的地點都在北美：

  • CoreSite VA1, Reston, VA
  • Equinix DC2/DC11, Ashburn, VA
  • CoreSite SV4, Santa Clara, CA
  • Equinix SV5, San Jose, CA

Terabit Ethernet 這邊翻400Gbps 的部分，是 2017 年的標準，另外有些比較長距離的選擇是後續推出來的。

這樣算是給了一些需要穩定大流量的企業的選擇，不然 internet 集縮比的問題造成線路頻寬時高時低。

話說 Direct Connect 在台灣的兩個點目前都還是掛到東京區 (ap-northeast-1) 上，後續台北 region 開點後不知道是會支援多個 region (i.e. 可以掛東京，也可以掛台北)，還是會另外找機房接？

Slack 要拿使用者資料訓練 AI

在「Slack AI Training with Customer Data (slack.com)」這邊看到的，原公告在「Privacy Principles: Search, Learning and Artificial Intelligence」這邊。

預設會被丟進去訓練，Opt-out 無法直接設定，需要透過 e-mail 寫信找 feedback@slack.com (yeah，dark pattern)：

Contact us to opt out. If you want to exclude your Customer Data from Slack global models, you can opt out. To opt out, please have your Org or Workspace Owners or Primary Owner contact our Customer Experience team at feedback@slack.com with your Workspace/Org URL and the subject line “Slack Global model opt-out request.” We will process your request and respond once the opt out has been completed.

拿企業資料來搞事嗎... 這應該已經不只是 privacy 議題而是 security 層面了，PR 層面鐵定很難看，來看後面會不會轉彎？

Common Media Client Data (CMCD)

從 Amazon CloudFront 的公告看到的東西：「Amazon CloudFront now supports Common Media Client Data (CMCD) fields in real-time logs」。

CMCD (Common Media Client Data) 是一個私有的 log format，可以讓 client 透過 HTTP(S) header 回報狀態，所以 AWS 這邊有提到你可以設定讓 CloudFront 記錄下來，然後透過其他軟體分析：

Previously, CloudFront logged CMCD parameters as part of the full query string log field, or the HTTP headers log field. Now, you can simply select to include specific CMCD parameters in your real-time logs and save on compute needed to search and extract the CMCD key-value pairs, and reduce the data set for your log analysis.

現在 CloudFront 則是支援判讀做一些處理：

Starting today, you can enable Common Media Client Data (CMCD) fields in your CloudFront real-time logs. You can select key client-side performance parameters and CloudFront delivery performance parameters in the same log record. This can help you correlate variations in Quality of Experience (QoE) for your viewers to CloudFront performance at the granularity of single viewer sessions, simplifying the troubleshooting of QoE issues that impact your viewers engagement.

看了一下就是定義一些欄位，用 JSON 包起來後讓 client 打回伺服器端，可以利用這些資訊動態從伺服器端調整策略，而不像以前主要的調整策略都放在 client 端。

可以線上查出入境的日期記錄

在 Threads 上看到可以查出入境記錄 (以及其他各種資料)，連結在 https://www.threads.net/@allenwongtw/post/C6OwgH_Bi3Y/ 這邊：

用了一下還蠻方便的，可以用自己門號的手機認證 (另外確認資料的部分是身分證字號 + 健保卡卡號 + 出生日期)，拉下來的檔案是 PDF，有出境日期與入境日期。

看了一下才發現 2019 年因為工作的關係，出入境的次數比 2015 年還多... 本來以為 2015 年是最多次的。

利用 XOR 處理 time series data 壓縮資料

在「The simple beauty of XOR floating point compression (clemenswinter.com)」這邊看到的內容，原文在「The Simple Beauty of XOR Floating Point Compression」這邊。這也是上一篇文章「Golomb coding」的延續。

文章作者在處理 time series data 時預先用 XOR 處理過 (對上一筆資料做)，因為 time series data 的特性，通常 XOR 出來的結果會有很多都是 0 (表示相同的 bit)，然後再用自己設計的演算法讓 raw data 變小。

以作者拿的第一個範例可以看到變小很多 (開原圖可以看比較清楚)，不過這邊 low bit 都是 0 有點作弊：

後面有 unix timestamp 的部分，這個部分的資料就比較接近實際情況，也可以看出來效果不錯：

這邊似乎也可以選擇套 Golomb coding 或是 Rice coding (i.e. M 是 2 的冪次的特殊情況，2^n，這時候 Truncated binary encoding 剛好就是 Binary encoding)。

算是個有趣的處理法... 不過我猜大多數人為了方便處理，還是只會用 framework 提供的壓縮演算法，在底層透明地處理掉，像是 LZ4、gzip 或是 zstd。

Golomb coding

在 Hacker News 上看到 id=40008133 這篇提到 Golomb coding 覺得很有趣，花了些時間把演算法以及使用的場景搞清楚...

Golomb coding 用在 input 是數字 (或是 fixed size 時硬當作一個數字處理)，而且大多數的資料都偏小的情境下，像是「I don't get Golomb / Rice coding: It does make more bits of the input, or does it?」這邊解釋 Golomb coding 時提到的：

they reduce the average length per encoded value compared to fixed-width encoding, if the encoded values are from a large range, but the most common values are generally small (and hence are using only a small fraction of that range most of the time).

Golomb coding 演算法上用到了兩個特殊的表達方式，Unary coding 與 Truncated binary encoding。

Unary coding 很簡單，把 n 表達成 n 個 bit 的 1，再加上一個 0，所以 3 表達成 1110，7 表達成 11111110。

Unary coding 最主要就是要用到他只用一個 bit 0 來表達 n = 0 的情況。

Truncated binary encoding (中文維基百科剛好有條目：「截斷二進制編碼」) 則是很有趣的一個 encoding 方式。先提到傳統的方式，在表示 n 種可能的組合 (0, 1, ..., n-1) 時，會需要 \lceil\log_2 {n}\rceil bit 表達，像是 n = 5 時，會需要 3 個 bit 表達，從 000、001、010、011 到 100。

Truncated binary encoding 則是找到一個方法，編碼成 00 (對應到 0)、01 (1)、10 (2)、110 (3)、111 (4)，針對 n = 0～2 的部分只用 2 bits 表示，省下 1 個 bit。

Truncated binary encoding 的重點在於在可能性非 2^n 的情況下，要怎麼省儲存空間。

而 Golomb coding 需要預先指定一個 M，對於每一個 x 輸入，拿 M 去除他，就會得到一個商 q 與餘數 r：

x = M * q + r

這邊把商 q 用 Unary coding 表示，餘數 r 用 Truncated binary encoding 表示，就是 Golomb coding 了。

而就如同前面提到的，Golomb coding 會用在資料數字都偏小的情況，當 M 挑的夠好就可以讓 q 常常是 0 或是 10 而省下空間。

這剛好就對到「The simple beauty of XOR floating point compression (clemenswinter.com)」這則提到的東西，在處理 time-series data 時就有機會用這個方式搭配處理...

查詢 GitHub 上面 repository 的公開記錄

起因應該是「Claim: Private GitHub repos included in AI dataset (lurk.org)」這邊的討論，原文是 @emenel@post.lurk.org 在 https://post.lurk.org/@emenel/112111014479288871 這邊宣稱他在 GitHub 的 private repository 被當作 training data 蒐集走使用。

而 GitHub 有公開全站的 public event data，所以 Simon Willison 就拿這份資料直接組了一個工具出來用：「GitHub Public repo history」。

這樣可以直接 auditing 對應的說法，不過看了一下 GitHub 上的帳號 emenel (上面連結是到同一個站，應該是同一個人)，目前看起來已經把所有 repository 都刪掉了...

Google 的 HyperLogLog++

算是接續昨天寫的「Redis 對 HyperLogLog 省空間的實作」，在 Redis 的 HyperLogLog 實作有提到 Google 在 2013 年的論文「HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm」，裡面提出了 HyperLogLog++ (HLL++)。

論文中 Google 提出來的改進主要有三個，第一個是用了 64-bit hash function：

5.1 Using a 64 Bit Hash Function

原因也有提到，當需要處理超過十億筆資料時，32-bit hash 的 4B 上限就有點不太夠用：

To fulfill the requirement of being able to estimate multisets of cardinalities beyond 1 billion, we use a 64 bit hash function.

這點也簡化了原始論文中當 cardinality 接近 232 時的 count 估算修正，因為實務上不太可能遇到 264 上限？

It would be possible to introduce a similar correction if the cardinality
approaches 264, but it seems unlikely that such cardinalities are encountered in practice.

第二個是改善 cardinality 比較低時的 count 估算公式：

5.2 Estimating Small Cardinalities

第三個則是提出了 sparse representation 的概念，在 cardinality 比較低的時候不需要直接用完整的 HLL 資料結構儲存：

5.3 Sparse Representation

另外也是一路往回讀的關係，查資料才了解 (ε, δ)-model 的用法，在「A Quick Introduction to Data Stream Algorithmics」這邊投影片的 Page 17 可以看到指的是，有多少正確性 (randomized) 是給出 ε 內的誤差 (approximation)，像是 Page 18 的範例：

Example: Actual answer is within 5 ± 1 with prob ≥ 0.9

Redis 對 HyperLogLog 省空間的實作

HyperLogLog (HLL) 是用統計方式解決 Count-distinct problem 的資料結構以及演算法，不要求完全正確，而是大概的數量。

演算法其實沒有很難懂，在 2007 年的原始論文「HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm」裡面可以讀到演算法是長這樣：

可以看到一開始要決定好 b 的值 (於是就會有 2b 個 register)，以及單個 register M[j] 的大小，所以是一開始就會決定好固定大小，無論有多少元素都會先吃掉這麼多空間。

但在 Redis 的文件「HyperLogLog」裡面則是提到很少元素的時候會低於 12KB：

The magic of this algorithm is that you no longer need to use an amount of memory proportional to the number of items counted, and instead can use a constant amount of memory; 12k bytes in the worst case, or a lot less if your HyperLogLog (We'll just call them HLL from now) has seen very few elements.

網路上搜了一下沒看到怎麼做到的，不過直接翻 Redis 的程式碼 hyperloglog.c 可以看到答案。

在檔案開頭的註解可以看到有 16384 個 register (對應到論文裡面的 b = 14，因為 214 = 16384)，單個 register 的大小則是 6 bit (對應到論文裡面的 M[j])，相乘後是 12K bytes，剛好符合文件上的說明：

The use of 16384 6-bit registers for a great level of accuracy, using a total of 12k per key.

在「Dense representation」這邊也說明了每個 register 都是 6 bit 的存放方式，到這邊都與 HLL 論文提到的實作一樣。

省空間的方式是在「Sparse representation」這邊做到的，在大多數的 register 都沒有被設定的情況下，用這種方式可以省下大量的空間，而缺點是當元素「有點多」的時候會有比較高的 CPU time：

In the example the sparse representation used just 7 bytes instead of 12k in order to represent the HLL registers. In general for low cardinality there is a big win in terms of space efficiency, traded with CPU time since the sparse representation is slower to access.

依照註解上面的數字，看起來在 10000 個元素以下有機會低於 12KB，然後夠大的時候從 sparse 轉到 dense 上。

本來以為是什麼其他論文可以調整 b 參數 (enlarge)，結果是個比較像是 hack 的方式搞定，但的確是蠻有效的...