Skip to content

Instantly share code, notes, and snippets.

@ehaynes99
Last active June 5, 2022 20:50
Show Gist options
  • Save ehaynes99/2cd698f5725848bf67fdec8ed8672ce9 to your computer and use it in GitHub Desktop.
Save ehaynes99/2cd698f5725848bf67fdec8ed8672ce9 to your computer and use it in GitHub Desktop.
import { sortBy, pick } from 'lodash';
/**
* NOT A REAL IMPLEMENTATION!! This is just a high level example of how
* dynamo stores data.
*/
type Row = {
hashKey: string;
rangeKey: string;
[k: string]: any;
};
type Index = {
put: (row: Row) => void;
query: (hashKey: string, predicate: (row: Row) => boolean) => Row[];
scan: (predicate: (row: Row) => boolean) => Row[];
};
type Table = Index & {
// keys are unique, so can get a single, unique record
get: (hashKey: string, rangeKey: string) => Row | undefined;
secondaryIndexes: Index[];
addSecondaryIndex: (secondaryIndex: Table) => void;
};
export const createTable = (name: string): Table => {
const dataStore: Record<string, Row[]> = {};
const secondaryIndexes: Index[] = [];
return {
put: (row: Row): void => {
const { hashKey } = row;
if (!(hashKey in dataStore)) {
dataStore[hashKey] = [];
}
const existing = dataStore[hashKey];
if (!existing) {
dataStore[hashKey] = [row];
} else {
const index = existing.findIndex(
(value) => value.rangeKey === row.rangeKey
);
if (index >= 0) {
// replace the existing, because keys are unique
existing[index] = row;
} else {
// add to the list, sorted
existing.push(row);
existing.sort(sortByRangeKey);
}
}
// main practical difference in a table and an index is that you insert
// into the table, and dynamo puts it in the table and all of its indexes
secondaryIndexes.forEach((index) => {
index.put(row);
});
},
get: (hashKey: string, rangeKey: string): Row | undefined => {
const values = dataStore[hashKey];
// hand waiving these details, but since the rows are sorted in the array, it
// will use a binary search to find it much faster than iterating the whole array
return values && values.find((value) => value.rangeKey === rangeKey);
},
// there are specific expressions for use here, but an oversimplification with a function
query: (hashKey: string, predicate: (row: Row) => boolean) => {
const values = dataStore[hashKey] || [];
return values.filter((value) => predicate(value));
},
// searches through EVERYTHING
scan: (predicate: (row: Row) => boolean) => {
const result: Row[] = [];
Object.keys(dataStore).forEach((hashKey) => {
// like `query`, but we're not limited to a particular key...
const values = dataStore[hashKey] || [];
const matches = values.filter((value) => predicate(value));
result.push(...matches);
});
return result;
},
secondaryIndexes,
addSecondaryIndex: (secondaryIndex: Table) => {
secondaryIndexes.push(secondaryIndex);
},
};
};
const createSecondaryIndex = (
hashKeyName: string,
rangeKeyName: string,
projection: string[]
): Index => {
const dataStore: Record<string, Row[]> = {};
return {
put: (row: Row) => {
// filters out keys not in `projection`
row = pick(row, projection);
const hashKey = row[hashKeyName];
if (!(hashKey in dataStore)) {
dataStore[hashKey] = [];
}
// don't care if there is an existing match, because keys aren't unique
// just add to the list, sorted
const existing = dataStore[hashKey];
existing.push(row);
existing.sort(sortByRangeKey);
},
// there are specific expressions for use here, but an oversimplification with a function
query: (hashKey: string, predicate: (row: Row) => boolean) => {
const values = dataStore[hashKey] || [];
return values.filter((value) => predicate(value));
},
scan: (predicate: (row: Row) => boolean) => {
const result: Row[] = [];
Object.keys(dataStore).forEach((hashKey) => {
// like `query`, but we're not limited to a particular key...
const values = dataStore[hashKey] || [];
const matches = values.filter((value) => predicate(value));
result.push(...matches);
});
return result;
},
};
};
declare function sortByRangeKey(first: Row, second: Row): number;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment