Randomness
我如何在 MD5 空間中獲得 UUID4 的不均勻分佈？
我們有一個處理數據的系統。
uuid4()每個實體都有一個使用Python生成的 ID 。稍後，該 ID 將用作 AWS Kinesis 的分區鍵。Kinesis 文件說他們對這個分區鍵進行 MD5 處理，並使用它在預配置的分片之間分配數據。直到最近，這執行良好，但最近一個擁有 3000 萬條記錄和八個分片的高負載系統開始將幾乎所有內容都放在分片 4 上。
MD5(instance.id)只有在兩者之間結束時才會發生這種情況 $ 4\cdot 2^{125} $ 和 $ 5\cdot 2^{125} $ 數百萬個獨立生成的 UUID。果然，在應用 md5 之後，我在那個桶中有一個巨大的 uuid 列表。這些值肯定是 uuid4 並且它們都是唯一的。如果我將它們分成 16 個桶，我會在其中兩個桶中得到相當均勻的分佈。
我認為在生成 UUID 時系統可能具有低熵，但即使我們的 ID 本身是連續的或不均勻的，我也希望 MD5 雜湊重新分配它們。
我認為 UUID 和 MD5 之間一定存在一種特殊關係，它正在改變分佈。是這樣嗎？什麼可以解釋這種分佈？
以下是 100 個 UUID4 值，以十六進製表示：
8799fd0d38ba4e02b6bf43f5de6799d4 9f5159d9ebae461ebd3733b3aeff87f6 c92d4ecff58a40be9e48be8ebaa456f2 d63ca2bcc9184394ac8e836a0e431cf9 827710f5bcd74da2a05588e34180a75f 5d645c21471b4be5a50192112e13d244 edba5c23fa7142c7a70e4e41a36cab86 e388ac49ee664b04995b09439c4cf000 a004a6b0c59d4599bd8bc7f115a71c1c c98d931a698d4ee396d7403ee3b998df 9d22d0b7741b41ff8e55a2d2171cd4b0 b1a7d86d80b04c608442e7cea1e4f8ab d0f344348b9b48eaba9d8f1d7b41a8d8 926694f6fc874ba48d74c501ddcdde26 ee73f55448604e3c8106b4c0cef3788f cf5fd7fee614456b9a441cec52fa210c 3e35d6dece554ca699c09fece6297db6 0c14c595e6c047eca5829fce48265f1e 3735e410cda748a7b908d38096bcf706 585e0d5f77534247934f946422fc10fe 2e41e81a929b4e8b894ac3fb092bc33f 1b255bf030474fe8af131635e6634647 315f57d0f1b64b1698e2290c9853f6bb b8066497c85547fe8988107be80950fa 17a4a71b47344912835fe6dd3913ae2b dcda6f1dc5e54e3e819f98e3d6ba958b b7c59cafe3f6421ba1d3f5c1fa4d1d93 7723a3d355a04f8b8a873e6aff11b274 b9c8a1babb8b49ec889d8c0795dd5fd4 adfe93e7289c494287bc535c088f04a3 28c212f046e647618c93e00fda239ad1 981523f48f7d4ae9aca2a4b91558aeef 873abfe9f178450a94ecf369c35e63b2 04d41e0ee4604b41a4cd7a03af20ff7f 71fe56d24fc74b95866b9e10e219a6fe 09e463d986034284b055c185fc4c460d bcafb85b0a2d43a2929047c7ffcd210d 2dba964591fd4404ac63e071002c2586 c4ab3e2320aa4de6b7ab1dd36a230184 ef6b88c32e854cd5b59df3e018cce1f6 2736bf1a626741f489e0e3114efd3fbc 2efeb1dfa389425fabd52bf9edbee5fa b3092609d5b34da2ae5773f6ae3e28b5 576bd3c87f1b4da4bc905bcb0322cf3b 5f488e6d754f40caa4cc11bebdef169d ec763ae7f72f42368c34cdad2d936169 658d2ea5db85432f8bbbde7b74a9d505 9d192e219d1e4114aae3bf960ae6ec5f ae4bed0cc9754b4bb337cbc23a550bd6 a35a78d7cb474291b12ed10c3f97bcd0 10f369a3d5534c3ab7ab6275f47f8541 6737e813e8044a09a98b0787de81aa16 c82cee35e5c244228a86cdece99a36f2 501ef498116846f49819e9f7b4d9062b adf5f9e04edc4c769c56f8926972594e 16c4d96b5b6d4aed9c4d5802199dbf42 f64e7c6d65a247adae3c743f142d54d8 21ad704178114a27a9c509a9793d9ed9 9a394ad6440b449e85c77ffae962e2ba b902eaae56134a7a84a02ef53f7f2b4e 20215f6520b149868791327329776d42 91afc6fe15ea4ee8b1eb8c67fc6a901e d4b99047782f42fbb3496f8a083f8841 6a7a2e146382498596e442b93f8b548f 484cf5b6c6e74a50884651d8bd30dd25 7931d06f18474803b81206601093280c 1f8939ec64064ce1a1c0ed1d1656306f 10e40847dabc4384bad75159aaf88376 51fc78e3f2d844de8b305aa5db643d32 bfcbb5192b614747b5b3fd09a4bc6369 7350ea1e4a85475ab9a2324fa9dda195 dbb20005d9644c199c12faa038e3edff 3b0a42fb4bbc49d2a6ef74bfd6da6d5b 1066143d0b8f4d19a88e1c27ca08af7f 3c52547d67404069be61054be3bd4197 a78ecaf1d7cb4f3bbdab3fb34993f90d ab20ce5e2d8e4baa9cd89ce3a6acb699 3f1791072194448c9733e1b89c104a3c a7c5fd52710642a2abf07c42117638ba ee49ca425b11471a88d1c1438dca0df3 7d85bead1c274a439c25fbf0355cf014 e9a6cb3adfca455285cc991723c01c54 eda705703e3d42f6b6750132c00d6bd5 8101aec657a34abb811d45cb1df89913 856521de33474cd08961ba108712c12e c4d51f2350254003afac31171c388cb4 63d6f31ce73249c89b6b5aa9e5b623d8 9841a82199574fe7a205aa5982ba14d8 84ad8c14df7d4909acf842befb36b9bb 3efa41a0e8aa4da19fa9fb7fb749cc2b e96efdee94dc41bea1db7ad87c9bebb6 3c324772db9e4741a16727eba8c02e5d 97f53611475e47a3b294163e1e1b7f26 838cd9e7f88648b9af4fe000999d6451 bb1cbcba73444a34a3fadfa51ed807fa fce44469b3b841f3abe53b771ec21b5d a70413ef89314f8c9aaad620e3d529bb c6f0a9288f7d49febbc28053113d0881 2d3e0e488a104232b5584fdd6a904964 ece6b3c3e63740a38d0751ccb6367117辨識此問題的一種簡單方法是查看這些 uuid 的 md5sum 中的前三位，並註意它們都是
0b100. 就像是#!/usr/bin/env python import fileinput, hashlib, uuid for line in fileinput.input(): hex_ = hashlib.md5(line.strip().encode()).hexdigest() bin_ = bin(int(hex_, 16)) print(bin_[:5])
我們被告知 uuid 是由一個過程生成的（我有信心）甚至不計算其輸出的 MD5，並且觀察到的 uuid 在其 MD5 中具有高度偏差的前 3 位，使它們落在某個桶。
鑑於對於獨立於 MD5 的 128 位初始化值定義的輸入（甚至是惡意定義的），MD5 的輸出與隨機函式一樣均勻分佈，不可避免的結論是觀察到的 uuid 不是生成的 uuid 的統一樣本。一個看似合理的假設是，觀察到的 uuid 被（或傾向於）被觀察到，因為它們落在了那個特定的桶中。
這甚至在問題中說明：
應用 md5 後，我在該儲存桶中有大量 uuid