Extending Python with C – Jump Consistent Hash
本文的目標是以 C 完成 Jump Consistent Hash 的主體，接著透過 Python-C-API 轉為 Python 可以使用的套件。也就是說，模組的本體將會以 C 語言寫成，接著透過 setuptools 編譯為 so 檔，如此編成的模組將可以讓 Python 無縫接軌使用。
參考文章與程式原始碼：
- A Fast, Minimal Memory, Consistent Hash Algorithm: https://arxiv.org/pdf/1406.2294v1.pdf
- Python c-api: https://docs.python.org/3/c-api/intro.html
- Extending Python with C or C++: https://docs.python.org/3/extending/extending.html
- jchash – Jump Consistent Hash for Python: https://github.com/grapherd/jchash
1.我們的目標
閱讀完 <A Fast, Minimal Memory, Consistent Hash Algorithm> 這樣的經典文章後，我們希望透過 Python 來實現這個 hash function，一點簡單的實驗後發現無法重現論文中的程式碼，因為 Python 沒有整數型態大小的限制，我們無法簡單的把 Key 乘起來然後不 care 溢位的地方。接著採用 Python ctypes 的型態實，實作後發現過於複雜。
因此，我們轉而使用 Python-C-API 的方式來實作 jump consistent hash 演算法。
|
1 2 3 |
>>> import jchash >>> jchash.jchash(100, 20) 4 |
預期達到的目標 – 透過 jchash 即可使用 C 寫成的 Python modules
2. 資料夾結構
- tests
- test_jchash.py
- src
- jchash.c
- jchash.h
- setup.py
3. Unittest
首先撰寫 Unittest，透過 github 我們能搜尋到已經有人實作過這個演算法，我們可以從中擷取一些 test 當作我們的測試資料：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import unittest import jchash class TestIntHash(unittest.TestCase): def test_key_1048_buckets_1_should_return_0(self): # P.3 Exlanation of the algorithm: # Clearly, for any key, k, ch(k, 1) is 0, # since there is only the one bucket. self.assertEqual(jchash.jchash(1048, 1), 0) def test_key_1048_buckets_20_should_return_5(self): self.assertEqual(jchash.jchash(1048, 20), 5) def test_key_100_buckets_20_should_return_4(self): self.assertEqual(jchash.jchash(100, 20), 4) def test_key_401_buckets_20_should_return_12(self): self.assertEqual(jchash.jchash(401, 20), 12) def test_key_100_buckets_500000_should_return_315593(self): self.assertEqual(jchash.jchash(100, 500000), 315593) |
有了 unittest 後，我們之後可以在 setup.py 裏面設定 test 的值，就可以使用 python setup.py test 來跑測試。
4. jchash.c
開始撰寫 jchash.c，檔案的第一行必須要載入 Python 的標頭檔，將 Python API 載入：
|
1 |
#include <Python.h> |
必須要注意，Python 會預設一些預處理定義，因此這個標頭檔必須放在第一個引入的位置。
接下來我們在檔案中加入函式本體，之後在 Python 裏面我們會以 jchash.jchash(key, buckets) 的方式呼叫。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
static PyObject * jchash_jchash(PyObject *self, PyObject *args) { int64_t b = –1, j = 0; uint64_t key = 0; int32_t num_buckets = 0; // Parsing python args to key (unsigned long long) and buckets(int) if (!PyArg_ParseTuple(args, “Ki”, &key, &num_buckets)) { return NULL; } // Jump Consistent Hash while (j < num_buckets) { b = j; key = key * 2862933555777941757ULL + 1; j = (b + 1) * ((double) (1LL << 31) / (double) ((key >> 33) + 1)); } // Return Python Long value return PyLong_FromLongLong(b); } |
最主要的重點，是要將 Python 的 Arguments 轉換為 C types (舉例而言，key 以及 buckets 轉換為 uint64 以及 int32)。而 C function 永遠都只有兩個參數，就是 self 以及 args。
- 參數 self ，如果是 module-level function 將指向 module object，如果是 method 將指向 object instance。
- 參數 args 會是一個指向 Python tuple object 的指標，內有所有的 arguments。每個在 tuple 裡的 item 都代表著一個參數。這些參數目前都是 PyObjects，如果要轉換為 C 的值的話，我們可以透過 PyArg_ParseTuple() 來檢查型態並且轉換為 C 的值。
- 當 PyArg_ParseTuple 回傳非零值的時候，代表所有的轉換都成功。如果回傳 NULL，就代表其中有參數轉換失敗，同時會 raises 一個適當的 Exception 來解決這樣的情況。
4.1 Parsing Arguments and Building Values
參考資料: Parsing arguments and building values
有關轉換型態的字元表示方式，請參考上列參考資料，這邊擷取幾個有用的來說明：
- K (int) [unsigned long long]
- i (int) [int]
- s (str) [const char *]
- O (object) [PyObject *]
我們可以透過 PyArg_ParseTuple()、PyArg_ParseTupleAndKeywords()、PyArg_Parse() ，將 Python Objects 轉換為 C values，而透過 Py_BuildValue() 我們可以把 C values 轉換為 Python Objects。
具體的用法範例如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
PyArg_ParseTuple(args, “”); /* No arguments */ /* Python call: f() */ PyArg_ParseTuple(args, “s”, &s); /* A string */ /* Possible Python call: f(‘whoops!’) */ PyArg_ParseTuple(args, “lls”, &k, &l, &s); /* Two longs and a string */ /* Possible Python call: f(1, 2, ‘three’) */ PyArg_ParseTuple(args, “(ii)s#”, &i, &j, &s, &size); /* A pair of ints and a string, whose size is also returned */ /* Possible Python call: f((1, 2), ‘three’) */ /* s#: [const char *, int or Py_ssize_t] */ |
4.2 Multiple types argument
參考資料: Concrete Objects Layer
從上面的範例我們可以看到，PyArg_Parse 有如 c string format 一樣簡單好用，但是有個問題：
如果同個 argument 有多種型態呢？
在 jchash 裏面有遇到這個問題，jchash 的 key 可以是 bytes 或是 ulonglong，我們沒有辦法使用兩個 PyArg_ParseTuple 來解決這個問題，因為 ParseTuple 出錯的時候會 raises exception。
因此我們必須要先將第一個 argument 轉為 PyObject，透過函式判斷後在將正確數值存入 key 當中。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
PyObject *pykey = NULL; uint64_t key = 0; int32_t num_buckets = 0; // Parsing arguments with PyObject and int if (!PyArg_ParseTuple(args, “Oi”, &pykey, &num_buckets)) { return NULL; } // Check pykey is int or string if (PyLong_Check(pykey)) { key = PyLong_AsLongLong(pykey); } else if (PyBytes_Check(pykey)) { char *s = PyBytes_AsString(pykey); key = string_hash(s); } else if (PyFloat_Check(pykey)) { PyErr_SetString(PyExc_KeyError, “Key should be int or bytes, not float”); return NULL; } else if (PyUnicode_Check(pykey)) { PyErr_SetString(PyExc_KeyError, “Key should be int or bytes, not string”); return NULL; } else { PyErr_SetString(PyExc_KeyError, “Key should be int or bytes”); return NULL; } |
4.3 Determine PyObject’s C Type
我們有兩種方法可以檢查 PyObject 的 C 型態，第一個使用 PyObject_IsInstance()
|
1 2 3 4 5 6 7 |
/* Check if val is Long or Float or Unitcode */ PyObject_IsInstance(val, (PyObject*)&PyLong_Type)) || (PyObject_IsInstance(val, (PyObject*)&PyFloat_Type)) || (PyObject_IsInstance(val, (PyObject*)&PyUnicode_Type))); /* Check if val is Long PyObject_IsInstance(val, (PyObject*)&PyLong_Type)); |
code example from: embl_writer_python.c
或是使用各個 PyObject Layer 的函式：
|
1 2 3 4 5 6 7 8 9 10 11 |
/* Check if val is PyLong */ if (PyLong_Check(val)) /* Check if val is PyBytes */ if (PyBytes_Check(val)) /* Check if val is PyFloat */ if (PyFloat_Check(val)) /* Check if val is PyUnicode */ if (PyUnicode_Check(val)) |
4.4 Convert PyObject to C values
確定 PyObject 的型態後，我們可以使用相對應的 API 來轉換到 C values：
|
1 2 3 4 5 |
/* Convert PyLong to long long */ key = PyLong_AsLongLong(val); /* Convert PyBytes to const char */ char *s = PyBytes_AsString(val); |
4.5 Error and Exception
參考資料: Intermezzo: Errors and Exceptions
這邊只介紹 PyErr_SetString，在 jchash 中 key 只支援使用 bytes 以及 int，其餘型態都不是合法的型態。如果使用者傳入的話，我們希望可以丟出 TypeError 來警告使用者。我們可以透過 PyErr_SetString 達成這個任務。
|
1 2 3 4 5 6 7 8 9 10 |
if (PyFloat_Check(pykey)) { PyErr_SetString(PyExc_TypeError, “Key should be int or bytes, not float”); return NULL; } else if (PyUnicode_Check(pykey)) { PyErr_SetString(PyExc_TypeError, “Key should be int or bytes, not string”); return NULL; } else { PyErr_SetString(PyExc_TypeError, “Key should be int or bytes”); return NULL; } |
標準 Excpetion 可以參考這裡，只要將 PyErr_SetString 第一個參數替換，就會引發相對應的 Exception。
5. Module’s Method Table and Initialization Function
我們必須要先建立一個 “method table”，將 jchash_jchash 放入其中：
|
1 2 3 4 |
static PyMethodDef jchash_methods[] = { {“jchash”, jchash_jchash, METH_VARARGS, “jchash function”}, {NULL, NULL, 0, NULL} /* Sentinel */ }; |
METH_VARARGS 參數是告訴 function 預期會得到 Python-level 的參數以 tuple 型式傳入並且可以被 PyArg_ParseTuple() 解析。
接著 method table 要在 module definition structure 中參照：
|
1 2 3 4 5 6 7 8 |
static struct PyModuleDef jchash_module = { PyModuleDef_HEAD_INIT, JCHASH_MODULE_NAME, /* Name of module */ Py_Jchash_doc, /* Module documentation, may be NULL, or create by PyDoc_STRVAR */ –1, /* size of per-interpreter state of the module, or -1 if the module keeps state in global variables. */ jchash_methods }; |
這個 structure 需要在 module’s 初始化函式傳入 interpreter。初始化函式必須被命名為 PyInit_name()，name 是 module 的名稱，而且是模組中唯一一個 non-static 的函數。
|
1 2 3 4 5 |
PyMODINIT_FUNC PyInit_jchash(void) { return PyModule_Create(&jchash_module); } |
5. 測試，編譯，執行
一切就緒後，在 setup.py 中設定相關的值：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#! /usr/bin/env python3 # -*- coding: utf-8 -*- from setuptools import setup, Extension PACKAGE_NAME = ‘jchash’ PACKAGE_VERSION = ‘1.0’ jchash = Extension(PACKAGE_NAME, define_macros=[ (‘XSTR(s)’, ‘STR(s)’), (‘STR(s)’, ‘#s’), (‘JCHASH_MODULE_NAME’, PACKAGE_NAME), (‘PACKAGE_VERSION’, PACKAGE_VERSION)], sources=[‘src/jchash.c’]) setup( name=PACKAGE_NAME, version=PACKAGE_VERSION, description=‘jchash – Jump Consistent Hash for Python’, test_suite=‘tests’, ) |
在 command line 上，我們可以測試剛剛的 unittest:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
➜ python setup.py test running test running egg_info creating jchash.egg–info writing top–level names to jchash.egg–info/top_level.txt writing jchash.egg–info/PKG–INFO writing dependency_links to jchash.egg–info/dependency_links.txt writing manifest file ‘jchash.egg-info/SOURCES.txt’ reading manifest file ‘jchash.egg-info/SOURCES.txt’ writing manifest file ‘jchash.egg-info/SOURCES.txt’ running build_ext building ‘jchash’ extension creating build creating build/temp.linux–x86_64–3.5 creating build/temp.linux–x86_64–3.5/src gcc –pthread –Wno–unused–result –Wsign–compare –Wunreachable–code –DNDEBUG –g –fwrapv –O3 –Wall –Wstrict–prototypes –march=x86–64 –mtune=generic –O2 –pipe –fstack–protector–strong –fPIC –DXSTR(s)=STR(s) –DSTR(s)=#s -DJCHASH_MODULE_NAME=jchash -DPACKAGE_VERSION=2.2 -Isrc -I/usr/include/python3.5m -c src/jchash.c -o build/temp.linux-x86_64-3.5/src/jchash.o creating build/lib.linux–x86_64–3.5 gcc –pthread –shared –Wl,–O1,—sort–common,—as–needed,–z,relro build/temp.linux–x86_64–3.5/src/jchash.o –L/usr/lib –lpython3.5m –o build/lib.linux–x86_64–3.5/jchash.cpython–35m–x86_64–linux–gnu.so copying build/lib.linux–x86_64–3.5/jchash.cpython–35m–x86_64–linux–gnu.so -> test_key_bytes_node1_buckets_500000_should_return_206811 (tests.test_jchash.TestBytesHash) ... ok test_key_bytes_node2_buckets_500000_should_return_457238 (tests.test_jchash.TestBytesHash) ... ok test_key_1048_0_buckets_20_should_raise_key_error (tests.test_jchash.TestFloatHash) ... ok test_key_100_buckets_20_should_return_4 (tests.test_jchash.TestIntHash) ... ok test_key_100_buckets_500000_should_return_315593 (tests.test_jchash.TestIntHash) ... ok test_key_1048_buckets_1_should_return_0 (tests.test_jchash.TestIntHash) ... ok test_key_1048_buckets_20_should_return_5 (tests.test_jchash.TestIntHash) ... ok test_key_18446744073709551516_buckets_20_should_return_5 (tests.test_jchash.TestIntHash) ... ok test_key_401_buckets_20_should_return_12 (tests.test_jchash.TestIntHash) ... ok test_key_negative_100_buckets_20_should_raise_overflow_error (tests.test_jchash.TestIntHash) ... ok test_key_string_node_1_buckets_500_should_raise_key_error (tests.test_jchash.TestStringHash) ... ok ——————————————————————————————————— Ran 11 tests in 0.001s OK |
沒有問題的話可以安裝：
|
1 |
python setup.py install |
或是編譯成套件
|
1 |
python setup.py sdist |
或是上傳到 PyPI
|
1 2 |
python setup.py register python setup.py sdist upload |
Leave a Reply