Compare commits

...

1 Commits

Author SHA1 Message Date
Artem Bakalov b5bb895832 ARSN-157 short-IDs
(cherry picked from commit 07fd3451ab)
2022-05-05 00:30:42 +00:00
2 changed files with 144 additions and 77 deletions

View File

@ -9,6 +9,7 @@
const base62Integer = require('base62');
const BASE62 = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
const base62String = require('base-x')(BASE62);
const assert = require('assert/strict');
// the lengths of the components in bytes
const LENGTH_TS = 14; // timestamp: epoch in ms
@ -116,12 +117,19 @@ function generateVersionId(info, replicationGroupId) {
lastSeq = (lastTimestamp === ts) ? lastSeq + 1 : 0;
lastTimestamp = ts;
// if S3_VERSION_ID_ENCODING_TYPE is "hex", info is used. By default, it is not used.
if (process.env.S3_VERSION_ID_ENCODING_TYPE === 'hex') {
// info field stays as is
} else {
info = ''; // eslint-disable-line
}
// In the default cases, we reverse the chronological order of the
// timestamps so that all versions of an object can be retrieved in the
// reversed chronological order---newest versions first. This is because of
// the limitation of leveldb for listing keys in the reverse order.
return padLeft(MAX_TS - lastTimestamp, TEMPLATE_TS) +
padLeft(MAX_SEQ - lastSeq, TEMPLATE_SEQ) + repGroupId + info;
padLeft(MAX_SEQ - lastSeq, TEMPLATE_SEQ) + repGroupId + info;
}
/**
@ -166,10 +174,11 @@ const B62V_TOTAL = LENGTH_TS + LENGTH_SEQ;
const B62V_HALF = B62V_TOTAL / 2;
const B62V_EPAD = '0'.repeat(Math.ceil(B62V_HALF * (Math.log(10) / Math.log(62))));
const B62V_DPAD = '0'.repeat(B62V_HALF);
const B62V_STRING_EPAD = '0'.repeat(32 - 2 * B62V_EPAD.length);
/**
* Encode a versionId to obscure internal information contained
* in a version ID (less than 40 bytes).
* in a version ID (equal to 32 bytes).
*
* @param {string} str - the versionId to encode
* @return {string} - the encoded base62VersionId
@ -181,9 +190,10 @@ function base62Encode(str) {
const enc1 = base62Integer.encode(part1);
const enc2 = base62Integer.encode(part2);
const enc3 = base62String.encode(part3);
return (B62V_EPAD + enc1).slice(-B62V_EPAD.length) +
(B62V_EPAD + enc2).slice(-B62V_EPAD.length) +
enc3;
const padded1 = (B62V_EPAD + enc1).slice(-B62V_EPAD.length);
const padded2 = (B62V_EPAD + enc2).slice(-B62V_EPAD.length);
const padded3 = (B62V_STRING_EPAD + enc3).slice(-B62V_STRING_EPAD.length);
return padded1 + padded2 + padded3;
}
/**
@ -202,8 +212,19 @@ function base62Decode(str) {
const enc2 = str.substring(start, start + B62V_EPAD.length);
const orig2 = base62Integer.decode(enc2);
start += B62V_EPAD.length;
const enc3 = str.substring(start);
let enc3 = str.substring(start);
// take off prefix 0s which represent null bytes
let idx = 0;
while (idx < enc3.length) {
if (enc3[idx] === '0') {
idx++;
} else {
break;
}
}
enc3 = enc3.slice(idx);
const orig3 = base62String.decode(enc3);
return (B62V_DPAD + orig1.toString()).slice(-B62V_DPAD.length) +
(B62V_DPAD + orig2.toString()).slice(-B62V_DPAD.length) +
orig3.toString();
@ -221,13 +242,13 @@ const ENC_TYPE_BASE62 = 1; // new (tiny) encoding
* in a version ID.
*
* @param {string} str - the versionId to encode
* @param {Number} [encType=ENC_TYPE_HEX] - encode format
* @return {string} - the encoded versionId
*/
function encode(str, encType = ENC_TYPE_HEX) {
if (encType === ENC_TYPE_BASE62) {
function encode(str) {
// default format without 'info' field will always be 27 characters
if (str.length === 27) {
return base62Encode(str);
}
} // legacy format
return hexEncode(str);
}
@ -240,14 +261,21 @@ function encode(str, encType = ENC_TYPE_HEX) {
* @return {(string|Error)} - the decoded versionId or an error
*/
function decode(str) {
if (str.length < 40) {
return base62Decode(str);
// default format is exactly 32 characters when encoded
if (str.length === 32) {
const decoded = base62Decode(str);
assert.strictEqual(decoded.length, 27);
return decoded;
}
return hexDecode(str);
// legacy format
if (str.length > 32) {
return hexDecode(str);
}
return new Error(`cannot decode str ${str.length}`);
}
module.exports = { generateVersionId, getInfVid,
hexEncode, hexDecode,
base62Encode, base62Decode,
encode, decode,
ENC_TYPE_HEX, ENC_TYPE_BASE62 };
hexEncode, hexDecode,
base62Encode, base62Decode,
encode, decode,
ENC_TYPE_HEX, ENC_TYPE_BASE62 };

View File

@ -1,5 +1,6 @@
const VID = require('../../../lib/versioning/VersionID.js');
const assert = require('assert');
const { env } = require('process');
function randkey(length) {
let key = '';
@ -9,83 +10,121 @@ function randkey(length) {
return key;
}
describe('test generating versionIds', () => {
const count = 1000;
process.env.VID_CRYPTO_PASSWORD = randkey(64);
function generateRandomVIDs(count) {
const vids = Array(count).fill(null);
for (let i = 0; i < count; i++) {
vids[i] = VID.generateVersionId(randkey(15), 'PARIS');
}
process.env.VID_CRYPTO_PASSWORD = randkey(64);
return vids;
}
it('sorted in reversed chronological and alphabetical order', () => {
for (let i = 0; i < count; i++) {
if (i !== 0) {
const count = 1000000;
describe('test generating versionIds', () => {
describe('legaxy hex encoding', () => {
env.S3_VERSION_ID_ENCODING_TYPE = 'hex';
const vids = generateRandomVIDs(count);
it('sorted in reversed chronological and alphabetical order', () => {
for (let i = 1; i < count; i++) {
assert(vids[i - 1] > vids[i],
'previous VersionID is higher than its next');
}
}
});
// nodejs 10 no longer returns error for non-hex string versionIds
it.skip('should return error decoding non-hex string versionIds', () => {
const encoded = vids.map(vid => VID.hexEncode(vid));
const decoded = encoded.map(vid => VID.hexDecode(`${vid}foo`));
decoded.forEach(result => assert(result instanceof Error));
});
it('should encode and decode versionIds', () => {
const encoded = vids.map(vid => VID.hexEncode(vid));
const decoded = encoded.map(vid => VID.hexDecode(vid));
assert.deepStrictEqual(vids, decoded);
});
it('should encode and decode correctly with legacy format', () => {
const encoded = vids.map(VID.encode);
const decoded = encoded.map(VID.decode);
assert.strictEqual(vids.every(x => x.length > 27), true);
assert.strictEqual(encoded.every(x => x.length > 32), true);
assert.deepStrictEqual(vids, decoded);
});
});
// nodejs 10 no longer returns error for non-hex string versionIds
it.skip('should return error decoding non-hex string versionIds', () => {
const encoded = vids.map(vid => VID.hexEncode(vid));
const decoded = encoded.map(vid => VID.hexDecode(`${vid}foo`));
decoded.forEach(result => assert(result instanceof Error));
});
it('should encode and decode versionIds', () => {
const encoded = vids.map(vid => VID.hexEncode(vid));
const decoded = encoded.map(vid => VID.hexDecode(vid));
assert.strictEqual(vids.length, count);
assert.deepStrictEqual(vids, decoded);
});
describe('Short IDs', () => {
env.S3_VERSION_ID_ENCODING_TYPE = 'base62';
const vids = generateRandomVIDs(count);
it('simple base62 version test', () => {
const vid = '98376906954349999999RG001 145.20.5';
const encoded = VID.base62Encode(vid);
assert.strictEqual(encoded, 'aJLWKz4Ko9IjBBgXKj5KQT2G9UHv0g7P');
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('sorted in reversed chronological and alphabetical order', () => {
for (let i = 1; i < count; i++) {
assert(vids[i - 1] > vids[i],
'previous VersionID is higher than its next');
}
},
);
it('base62 version test with smaller part1 number', () => {
const vid = '00000000054349999999RG001 145.20.5';
const encoded = VID.base62Encode(vid);
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('simple base62 version test', () => {
const vid = '98376906954349999999RG001 145.20.5';
const encoded = VID.base62Encode(vid);
assert.strictEqual(encoded, 'aJLWKz4Ko9IjBBgXKj5KQT2G9UHv0g7P');
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('base62 version test with smaller part2 number', () => {
const vid = '98376906950000099999RG001 145.20.5';
const encoded = VID.base62Encode(vid);
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('base62 version test with smaller part1 number', () => {
const vid = '00000000054349999999RG001 145.20.5';
const encoded = VID.base62Encode(vid);
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('base62 version test with smaller part3', () => {
const vid = '98376906950000099999R1 145.20.5';
const encoded = VID.base62Encode(vid);
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('base62 version test with smaller part2 number', () => {
const vid = '98376906950000099999RG001 145.20.5';
const encoded = VID.base62Encode(vid);
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('base62 version test with smaller part3 - 2', () => {
const vid = '98376906950000099999R1x';
const encoded = VID.base62Encode(vid);
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('base62 version test with smaller part3', () => {
const vid = '98376906950000099999R1 145.20.5';
const encoded = VID.base62Encode(vid);
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('error case: when invalid base62 key part 3 has invalid base62 character', () => {
const invalidBase62VersionId = 'aJLWKz4Ko9IjBBgXKj5KQT.G9UHv0g7P';
const decoded = VID.base62Decode(invalidBase62VersionId);
assert(decoded instanceof Error);
});
it('base62 version test with smaller part3 - 2', () => {
const vid = '98376906950000099999R1x';
const encoded = VID.base62Encode(vid);
const decoded = VID.base62Decode(encoded);
assert.strictEqual(vid, decoded);
});
it('should encode and decode base62 versionIds', () => {
const encoded = vids.map(vid => VID.base62Encode(vid));
const decoded = encoded.map(vid => VID.base62Decode(vid));
assert.strictEqual(vids.length, count);
assert.deepStrictEqual(vids, decoded);
it('error case: when invalid base62 key part 3 has invalid base62 character', () => {
const invalidBase62VersionId = 'aJLWKz4Ko9IjBBgXKj5KQT.G9UHv0g7P';
const decoded = VID.base62Decode(invalidBase62VersionId);
assert(decoded instanceof Error);
});
it('should encode and decode base62 versionIds', () => {
const encoded = vids.map(vid => VID.base62Encode(vid));
const decoded = encoded.map(vid => VID.base62Decode(vid));
assert.strictEqual(vids.length, count);
assert.deepStrictEqual(vids, decoded);
});
it('should encode and decode correctly with new 32 byte format', () => {
const encoded = vids.map(vid => VID.encode(vid));
const decoded = encoded.map(vid => VID.decode(vid));
assert(vids.every(x => x.length === 27));
assert(encoded.every(x => x.length === 32));
assert.deepStrictEqual(vids, decoded);
});
});
});