數字與字元串的查找性能
我正在開發一個使用instagram 密鑰格式的項目。
TL;DR 64 位整數 ID。
它們將用於查找,我們也喜歡它們用於排序和批處理,因為它們自然會按創建時間排序。
這些值介於 2^63 和 2^64 之間,因此(只是)太大而無法放入
BIGINT
.因此,我們的儲存選項似乎是
numeric(20)
或varchar
。varchar
不是很理想,因為我們必須對它們進行零填充才能進行排序,但是使用數字進行查找會影響性能嗎?
討厭在這個上明顯地成為隊長,但Instagram 慷慨地提供了一個你連結到的功能,它將密鑰儲存為
bigint
.CREATE SCHEMA insta5; CREATE SEQUENCE insta5.table_id_seq; CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$ DECLARE our_epoch bigint := 1314220021721; seq_id bigint; now_millis bigint; shard_id int := 5; BEGIN -- The %1024, is just a way of saying they only want 10bit wraparound. SELECT nextval('insta5.table_id_seq') % 1024 INTO seq_id; SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis; result := (now_millis - our_epoch) << 23; result := result | (shard_id << 10); result := result | (seq_id); END; $$ LANGUAGE plpgsql;
他們實際上在使用 PostgreSQL。從該函式中,您可以看到他們正在返回一個
bigint
. 因此,您當然可以將該函式的結果儲存在bigint
. 作為特別說明,這可能不是他們正在使用的功能。該函式可能有一個更像這樣的簽名,insta5.next_id(smallint shard, OUT result bigint);
我們知道這一點是因為硬編碼一個碎片
5
並不是那麼有用,而且它們似乎表明他們正在使用這個功能。所以在那個部落格ID中,他們吹噓他們的ID妥協了
- 總共 64 位
- 64-23 = 41 位時間戳
- 64-41 = 23 位用於分片 + 序列 ID
- 序列 ID 為 10 位。
- 13 位用於分片。
快速測試他們的程式碼,
test=# SELECT insta5.next_id(); next_id --------------------- 1671372309237077023 (1 row)
分解 ID
現在讓我們玩吧。為了更加性感,我們可以創建從 ID 獲取內部組件的輔助函式。如果您想知道 Instagram 正在使用的分片或其內部時間戳。
-- 13 bits for shard CREATE FUNCTION insta5.get_shard(id bigint) RETURNS smallint AS $$ SELECT ((id<<41)>>51)::smallint; $$ LANGUAGE sql; -- 10 bits for sequence id CREATE FUNCTION insta5.get_sequence(id bigint) RETURNS smallint AS $$ SELECT ((id<<54)>>54)::smallint; $$ LANGUAGE sql; -- 41 bits for timestamp CREATE OR REPLACE FUNCTION insta5.get_ts(id bigint) RETURNS timestamp without time zone AS $$ SELECT to_timestamp(((id >> 23) + 1314220021721 ) / 1000 )::timestamp without time zone; $$ LANGUAGE sql;
玩玩,讓我們得到一個測試ID。
SELECT insta5.next_id(); next_id --------------------- 1671390786412876801 (1 row) SELECT insta5id, insta5.get_ts(insta5id), insta5.get_shard(insta5id), insta5.get_sequence(insta5id) FROM (VALUES (1671390786412876801::bigint), (insta5.next_id()) ) AS t(insta5id);
返回以下內容,
insta5id | get_ts | get_shard | get_sequence ---------------------+---------------------+-----------+-------------- 1671390786412876801 | 2017-12-16 17:02:09 | 5 | 1 1671392537048257538 | 2017-12-16 17:05:38 | 5 | 2 (2 rows)
滾動我們自己的 Instagram ID 域
如果你想真正清理它,你甚至可以創建一個顯式
DOMAIN
類型。這就是我個人儲存它的方式,注意我做了一些進一步的修改。
- 我補充說
COMMENTS
——總是好的做法。- 做了功能
IMMUTABLE
- 添加
insta5.next_id
了需要顯式分片。讓我們放下我們所擁有的,
DROP SCHEMA insta5 CASCADE;
而重新開始,
CREATE SCHEMA insta5; COMMENT ON SCHEMA insta5 IS 'Instagram'; CREATE DOMAIN insta5.id AS bigint; COMMENT ON DOMAIN insta5.id IS $$Instagram's internal ID type, based on example from "Sharding & IDs at Instagram"$$; CREATE SEQUENCE insta5.table_id_seq; CREATE OR REPLACE FUNCTION insta5.next_id(shard_id smallint) RETURNS insta5.id AS $$ DECLARE our_epoch bigint := 1314220021721; seq_id bigint; result insta5.id; now_millis bigint; BEGIN SELECT nextval('insta5.table_id_seq') % 1024 INTO seq_id; SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis; result := (now_millis - our_epoch) << 23; result := result | (shard_id << 10); result := result | (seq_id); RETURN result; END; $$ LANGUAGE plpgsql; COMMENT ON FUNCTION insta5.next_id(smallint) IS 'Modifications made to require shard id'; CREATE OR REPLACE FUNCTION insta5.get_shard(id insta5.id) RETURNS smallint AS $$ SELECT ((id<<41)>>51)::smallint; $$ LANGUAGE sql IMMUTABLE; COMMENT ON FUNCTION insta5.get_shard(insta5.id) IS '13 bits from insta5.id representing shard'; CREATE OR REPLACE FUNCTION insta5.get_sequence(id insta5.id) RETURNS smallint AS $$ SELECT ((id<<54)>>54)::smallint; $$ LANGUAGE sql IMMUTABLE; COMMENT ON FUNCTION insta5.get_sequence(insta5.id) IS '10 bits from insta5.id representing sequence'; CREATE OR REPLACE FUNCTION insta5.get_ts(id insta5.id) RETURNS timestamp without time zone AS $$ SELECT to_timestamp(((id >> 23) + 1314220021721 ) / 1000 )::timestamp without time zone; $$ LANGUAGE sql IMMUTABLE; COMMENT ON FUNCTION insta5.get_ts(insta5.id) IS '41 bits from insta5.id representing timestamp';
一切都像以前一樣,但現在你可以
CREATE SCHEMA mySchema; CREATE TABLE mySchema.mydata ( insta5id insta5.id ) ;
這可能是您可以獲得的最好的解決方案,而不是 C 實現,而且您可能不想生成
insta5id
ever. 那是他們的工作。;)另一個重要的問題是,您可能永遠不想這樣做。不要以身作則。這就是
uuid
類型的用途,您應該使用它而不是自己手動滾動。uuid_generate_v1()
具體來說,這與in非常相似uuid-ossp
,它儲存 MAC(分片)和時間戳此函式生成版本 1 UUID。這涉及**電腦的 MAC 地址和時間戳。**請注意,此類 UUID 揭示了創建標識符的電腦的身份以及創建標識符的時間,這可能使其不適用於某些對安全敏感的應用程序。