Fraci - Fractional Indexing

Fractional indexing that's robust, performant, and secure, with first-class support for Drizzle ORM and Prisma ORM.

What is fractional indexing? It's a technique for maintaining ordered lists in collaborative environments without requiring reindexing. This allows for efficient insertions, deletions, and reordering operations, making it ideal for applications with ordered data such as task lists, kanban boards, or document outlines.

Quick Start

1# Install the package
2npm install fraci

1// With Drizzle ORM (String-based)
2import { BASE62, fraciString, type FractionalIndexOf } from "fraci";
3import { defineDrizzleFraci, drizzleFraci } from "fraci/drizzle";
4
5// Create a string-based fraci instance
6const tasksFraci = fraciString({
7  brand: "tasks.fi",
8  lengthBase: BASE62,
9  digitBase: BASE62,
10});
11
12// Or with binary-based fractional indexing for better performance
13// import { fraciBinary, type FractionalIndexOf } from "fraci";
14// const tasksFraci = fraciBinary({ brand: "tasks.fi" });
15
16// Use it in your schema
17export const tasks = sqliteTable(
18  "tasks",
19  {
20    id: integer("id").primaryKey({ autoIncrement: true }),
21    title: text("title").notNull(),
22    fi: text("fi").notNull().$type<FractionalIndexOf<typeof tasksFraci>>(), // For string-based
23    // fi: blob("fi", { mode: "buffer" }).notNull().$type<FractionalIndexOf<typeof tasksFraci>>(), // For binary-based
24    userId: integer("user_id").notNull(),
25  },
26  (t) => [uniqueIndex("tasks_user_id_fi_idx").on(t.userId, t.fi)],
27);
28
29// Define the fractional index configuration
30export const fiTasks = defineDrizzleFraci(
31  tasksFraci, // Fraci instance
32  tasks, // Table
33  tasks.fi, // Fractional index column
34  { userId: tasks.userId }, // Group (columns that uniquely identify the group)
35  { id: tasks.id }, // Cursor (columns that uniquely identify the row within a group)
36);
37
38// Define a helper function to check for index conflicts (may vary by database)
39function isIndexConflictError(error: unknown): boolean {
40  return (
41    error instanceof Error &&
42    error.message.includes("UNIQUE constraint failed:") &&
43    error.message.includes(".fi")
44  );
45}
46
47// Use it in your application
48const tfi = drizzleFraci(db, fiTasks);
49const indices = await tfi.indicesForLast({ userId: 1 });
50for (const fi of tfi.generateKeyBetween(...indices)) {
51  try {
52    return await db
53      .insert(tasks)
54      .values({ title: "New Task", fi, userId: 1 })
55      .returning()
56      .get();
57  } catch (error) {
58    if (isIndexConflictError(error)) {
59      continue;
60    }
61    throw error;
62  }
63}

See the detailed examples below for more information.

Key Features

• Fractional indexing with arbitrary base characters
• Binary-based fractional indexing - More efficient storage and processing using Uint8Array
• ORM integrations - First-class support for Drizzle ORM and Prisma ORM with human-friendly and strongly typed APIs
• Regeneration on conflict - Automatic regeneration of fractional indices on conflict
• TypeScript support - Strongly typed APIs with branded types (type safety technique to prevent mixing different types) for added protection
• High performance - Optimized for performance with minimal overhead
• Smaller bundle size - Fully tree-shakable
• Zero dependencies - No dependencies, not even on Node.js

String vs Binary Comparison

Feature	String-based	Binary-based
Storage	Stored as text strings	Stored as binary data (Uint8Array)
Performance	Good	Better (faster comparisons, less memory)
Bundle Size	2.06 KiB (Core-only, gzipped)	1.55 KiB (Core-only, gzipped)
Database Column	text or varchar	blob or bytea
Visual Debugging	Easier (human-readable)	Harder (requires conversion)
Configuration	Requires digitBase and lengthBase	Simpler configuration

Bundle Sizes

For bundle size measurement, we use Rolldown for bundling and esbuild for minifying. Run bun run build-examples to see the bundle sizes for each example.

Integration	Total Size (minified)	Total Size (minified + gzipped)
Core only (Binary)	3.49 KiB	1.55 KiB
Core only (String)	4.85 KiB	2.06 KiB
Core only (Both)	7.95 KiB	3.02 KiB
Drizzle ORM (Binary)	4.55 KiB (Core +1.06 KiB)	2.01 KiB (Core +0.46 KiB)
Drizzle ORM (String)	5.92 KiB (Core +1.07 KiB)	2.50 KiB (Core +0.44 KiB)
Drizzle ORM (Both)	8.98 KiB (Core +1.03 KiB)	3.45 KiB (Core +0.44 KiB)
Prisma ORM (Both)	9.29 KiB (Core +1.35 KiB)	3.63 KiB (Core +0.62 KiB)

Security Considerations

Preventing Cross-Group Operations

• ⚠️ IMPORTANT: Never accept user input directly as a fractional index. Instead, use fraci's built-in ORM integrations which safely query fractional indices via cursors (record IDs).
• ⚠️ IMPORTANT: Always filter by group columns (e.g., userId) when updating items to prevent cross-group operations.
• The examples in this README demonstrate this pattern with where clauses that include both ID and group columns.

Type Safety

• Fraci uses branded types (a TypeScript technique that adds a unique "brand" to types) to prevent confusion between fractional indices from different columns.
• This provides compile-time protection against mixing indices from different contexts.

Protection Against Index Expansion Attacks

• Fractional indices can grow in length through repeated operations, especially when repeatedly inserting between the same two indices.
• As shown in the test at the bottom of fractional-indexing-*.test.ts, a malicious user could intentionally create very long indices by repeatedly moving items back and forth.
• Fraci includes a configurable maxLength parameter (default: 50) to prevent these attacks from creating excessively long indices.
• When this limit is exceeded, an exception is thrown, preventing database bloat and performance degradation.

Installation

1npm install fraci
2
3# or
4yarn add fraci
5
6# or
7pnpm add fraci
8
9# or
10bun add fraci

[!NOTE] Adding fractional indexing to existing tables is inherently challenging and not supported by our library. The following examples assume you are creating a new table.

Usage

See the examples directory for full examples.

With Drizzle ORM

1. Define your Drizzle schema

1import {
2  BASE62,
3  fraciString,
4  type AnyStringFraci,
5  type FractionalIndexOf,
6} from "fraci";
7import { defineDrizzleFraci } from "fraci/drizzle";
8
9// Define a utility function to create a fractional index column
10function fi<Fraci extends AnyStringFraci>(_fraci: () => Fraci) {
11  return text().notNull().$type<FractionalIndexOf<Fraci>>();
12}
13
14// Define your table with a fractional index column
15export const articles = table(
16  "articles",
17  {
18    id: integer().primaryKey({ autoIncrement: true }),
19    title: text().notNull(),
20    content: text().notNull(),
21    fi: fi(() => fraciForArticles), // Define the fractional index column
22    userId: integer()
23      .notNull()
24      .references(() => users.id),
25  },
26  (t) => [
27    // IMPORTANT: This compound index is necessary for both uniqueness and performance
28    uniqueIndex("user_id_fi_idx").on(t.userId, t.fi),
29  ],
30);
31
32// Create a fraci instance
33const fraciForArticles = fraciString({
34  brand: "drizzle.articles.fi", // Brand the fractional index type
35  lengthBase: BASE62, // Used to represent the length of the integer part (first character)
36  digitBase: BASE62, // Determines the radix of the fractional index (second character onward)
37  maxRetries: 5, // Maximum number of retries on conflict (default: 5)
38  maxLength: 50, // Maximum length to prevent attacks (default: 50)
39});
40
41// Export the fractional index configuration
42export const fiArticles = defineDrizzleFraci(
43  fraciForArticles, // Fraci instance
44  articles, // Table
45  articles.fi, // Fractional index column
46  { userId: articles.userId }, // Group (columns that uniquely identify the group)
47  { id: articles.id }, // Cursor (columns that uniquely identify the row within a group)
48);

[!TIP] The fractional index column should be placed at the end of the compound index for optimal performance.

[!TIP]

Using Binary Fractional Index with Drizzle ORM

For more efficient storage and processing, you can use the binary-encoded fractional index:

1import {
2  fraciBinary,
3  type AnyBinaryFraci,
4  type FractionalIndexOf,
5} from "fraci";
6
7// Define a utility function to create a binary fractional index column
8function fi<Fraci extends AnyBinaryFraci>(_fraci: () => Fraci) {
9  return blob({ mode: "buffer" }).notNull().$type<FractionalIndexOf<Fraci>>();
10}
11
12// Create a binary fraci instance
13const fraciForArticles = fraciBinary({
14  brand: "drizzle.articles.fi", // Brand the fractional index type
15  maxRetries: 5, // Maximum number of retries on conflict (default: 5)
16  maxLength: 50, // Maximum length to prevent attacks (default: 50)
17});
18
19// Use it in your table definition
20export const articles = table(
21  "articles",
22  {
23    // ...other columns
24    fi: fi(() => fraciForArticles), // Binary fractional index column
25    // ...other columns
26  },
27  // ...rest of the table definition
28);

The binary implementation:

• Uses Uint8Array instead of strings for more efficient storage and processing
• Doesn't require digitBase and lengthBase parameters
• Has smaller bundle size (see Bundle Sizes section)
• Works with the same API as the string-based implementation

2. CRUD operations with Drizzle ORM

1import { getFraciErrorCode } from "fraci";
2import { drizzleFraci } from "fraci/drizzle";
3// Or import `drizzleFraciSync` if you're using synchronous database (i.e. Bun SQLite)
4import { articles, fiArticles } from "./schema";
5
6// Create your own function to check if the error is a unique constraint error
7function isIndexConflictError(error: unknown): boolean {
8  return (
9    error instanceof Error &&
10    error.message.includes("UNIQUE constraint failed:") &&
11    error.message.includes(".fi")
12  );
13}
14
15// Prepare the database
16const db = drizzle(/* ... */);
17
18// Get the helper object
19const afi = drizzleFraci(db, fiArticles);
20
21/**
22 * Create (append)
23 * Append a new article to the end
24 */
25async function append() {
26  // Get the fractional indices to generate the new one that represents the last index
27  const indices = await afi.indicesForLast({ userId: 1 });
28  //                                         ^ Specify all group columns
29
30  // Generate a new fractional index and handle conflicts
31  try {
32    for (const fi of afi.generateKeyBetween(...indices)) {
33      try {
34        return await db
35          .insert(articles)
36          .values({
37            title: "Hello, world!",
38            content: "This is a test article.",
39            fi,
40            userId: 1,
41          })
42          .returning()
43          .get();
44      } catch (error) {
45        if (isIndexConflictError(error)) {
46          // Conflict occurred - regenerate and try again
47          continue;
48        }
49        throw error;
50      }
51    }
52
53    // Unreachable code, as the `generateKeyBetween` function throws a `MAX_RETRIES_EXCEEDED` error before this point
54  } catch (error) {
55    const code = getFraciErrorCode(error);
56    if (code === "MAX_LENGTH_EXCEEDED") {
57      throw new HTTPError(500, "Cannot add more items to this group.");
58    }
59    if (code === "MAX_RETRIES_EXCEEDED") {
60      throw new HTTPError(
61        503,
62        "Too many concurrent requests. Please try again.",
63      );
64    }
65  }
66}
67
68/**
69 * Read (list)
70 * List all articles in order
71 */
72async function list() {
73  return await db
74    .select()
75    .from(articles)
76    .where(eq(articles.userId, 1))
77    // To sort by fractional index, just use the `ORDER BY` clause
78    .orderBy(asc(articles.fi))
79    .all();
80}
81
82/**
83 * Update (move)
84 * Move article 3 to the position after article 4
85 */
86async function move() {
87  const indices = await afi.indicesForAfter({ userId: 1 }, { id: 4 });
88  //                                          ^ Group        ^ Cursor
89  if (!indices) {
90    throw new Error("Article 4 does not exist or does not belong to user 1.");
91  }
92
93  try {
94    for (const fi of afi.generateKeyBetween(...indices)) {
95      try {
96        const result = await db
97          .update(articles)
98          .set({ fi })
99          .where(
100            and(
101              eq(articles.id, 3),
102              eq(articles.userId, 1), // IMPORTANT: Always filter by group columns
103            ),
104          )
105          .returning()
106          .get();
107
108        if (!result) {
109          throw new Error(
110            "Article 3 does not exist or does not belong to user 1.",
111          );
112        }
113        return result;
114      } catch (error) {
115        if (isIndexConflictError(error)) {
116          // Conflict occurred - regenerate and try again
117          continue;
118        }
119        throw error;
120      }
121    }
122
123    // Unreachable code, as the `generateKeyBetween` function throws a `MAX_RETRIES_EXCEEDED` error before this point
124  } catch (error) {
125    // TODO: Error handling
126  }
127}
128
129/**
130 * Delete
131 */
132async function remove() {
133  // Just delete the item. No need to touch the fractional index.
134  // There is no need to modify the fractional index even for soft delete.
135  await db.delete(articles).where(eq(articles.id, 3));
136}

[!TIP] Due to limitations of TypeScript, code after a loop that iterates over an infinite generator will not be inferred to be unreachable, even though it is. We recommend using a wrapper function like the one below, which incorporates common error handling.

1async function withKeyBetween<T, FI extends AnyFractionalIndex>(
2  generator: Generator<FI, never, unknown>,
3  callback: (fi: FI) => Promise<T>,
4): Promise<T> {
5  try {
6    for (const fi of generator) {
7      try {
8        return await callback(fi);
9      } catch (error) {
10        if (isIndexConflictError(error)) {
11          // Conflict occurred - regenerate and try again
12          continue;
13        }
14        throw error;
15      }
16    }
17
18    // Unreachable code, as the `generateKeyBetween` function throws a `MAX_RETRIES_EXCEEDED` error before this point
19    throw 1; // To make TypeScript happy
20  } catch (error) {
21    const code = getFraciErrorCode(error);
22    if (code === "MAX_LENGTH_EXCEEDED") {
23      throw new HTTPError(500, "Cannot add more items to this group.");
24    }
25    if (code === "MAX_RETRIES_EXCEEDED") {
26      throw new HTTPError(
27        503,
28        "Too many concurrent requests. Please try again.",
29      );
30    }
31    throw error;
32  }
33}
34
35// Example usage
36const indices = await afi.indicesForAfter({ userId: 1 }, { id: 4 });
37if (!indices) {
38  throw new Error("Article 4 does not exist or does not belong to user 1.");
39}
40
41const result = await withKeyBetween(
42  afi.generateKeyBetween(...indices),
43  async (fi) => {
44    return await db
45      .update(articles)
46      .set({ fi })
47      .where(
48        and(
49          eq(articles.id, 3),
50          eq(articles.userId, 1), // IMPORTANT: Always filter by group columns
51        ),
52      )
53      .returning()
54      .get();
55  },
56);

With Prisma ORM

1. Define your Prisma schema

1model Article {
2  id Int @id @default(autoincrement())
3  title String
4  content String
5  fi String  // Fractional Index
6  userId Int
7  user User @relation(fields: [userId], references: [id])
8
9  // IMPORTANT: This compound unique index is necessary for both uniqueness and performance
10  // The fractional index column should be placed at the end of the index
11  @@unique([userId, fi])
12}

[!TIP]

Using Binary Fractional Index with Prisma ORM

To use binary fractional index with Prisma ORM, define your schema with a Bytes type:

1model Article {
2  id Int @id @default(autoincrement())
3  title String
4  content String
5  fi Bytes  // Binary Fractional Index
6  userId Int
7  user User @relation(fields: [userId], references: [id])
8
9  @@unique([userId, fi])
10}

2. Configure the Prisma extension

1import { PrismaClient } from "@prisma/client";
2import { BASE62 } from "fraci";
3import { prismaFraci } from "fraci/prisma";
4
5const prisma = new PrismaClient().$extends(
6  prismaFraci({
7    fields: {
8      // Define the fractional index column (table.column)
9      "article.fi": {
10        group: ["userId"], // Group columns
11        digitBase: BASE62, // Determines the radix of the fractional index
12        lengthBase: BASE62, // Used to represent the length of the integer part
13      },
14    },
15    maxRetries: 5, // Maximum number of retries on conflict (default: 5)
16    maxLength: 50, // Maximum length to prevent attacks (default: 50)
17  }),
18);

[!TIP]

Using Binary Fractional Index with Prisma Extension

To configure the Prisma extension for binary fractional indexing:

1import { PrismaClient } from "@prisma/client";
2import { prismaFraci } from "fraci/prisma";
3
4const prisma = new PrismaClient().$extends(
5  prismaFraci({
6    fields: {
7      // Define the binary fractional index column
8      "article.fi": {
9        group: ["userId"], // Group columns
10        type: "binary", // Specify binary type instead of digitBase/lengthBase
11      },
12    },
13    maxRetries: 5, // Maximum number of retries on conflict
14    maxLength: 50, // Maximum length to prevent attacks
15  }),
16);

The usage pattern remains the same as with string-based indices, but with improved performance and smaller storage requirements.

3. CRUD operations with Prisma ORM

1// Get the helper object
2const afi = prisma.article.fraci("fi");
3//                 ^ Table        ^ Column
4
5/**
6 * Create (append)
7 * Append a new article to the end
8 */
9async function append() {
10  // Get the fractional indices to generate the new one that represents the last index
11  const indices = await afi.indicesForLast({ userId: 1 });
12  //                                         ^ Specify all group columns
13
14  try {
15    // Generate a new fractional index and handle conflicts
16    for (const fi of afi.generateKeyBetween(...indices)) {
17      try {
18        return await prisma.article.create({
19          data: {
20            title: "Hello, world!",
21            content: "This is a test article.",
22            fi,
23            userId: 1,
24          },
25        });
26      } catch (error) {
27        if (afi.isIndexConflictError(error)) {
28          // Conflict occurred - regenerate and try again
29          continue;
30        }
31        throw error;
32      }
33    }
34
35    // Unreachable code, as the `generateKeyBetween` function throws a `MAX_RETRIES_EXCEEDED` error before this point
36  } catch (error) {
37    const code = getFraciErrorCode(error);
38    if (code === "MAX_LENGTH_EXCEEDED") {
39      throw new HTTPError(500, "Cannot add more items to this group.");
40    }
41    if (code === "MAX_RETRIES_EXCEEDED") {
42      throw new HTTPError(
43        503,
44        "Too many concurrent requests. Please try again.",
45      );
46    }
47  }
48}
49
50/**
51 * Read (list)
52 * List all articles in order
53 */
54async function list() {
55  return await prisma.article.findMany({
56    where: {
57      userId: 1,
58    },
59    // To sort by fractional index, just use the `orderBy` property
60    orderBy: {
61      fi: "asc",
62    },
63  });
64}
65
66/**
67 * Update (move)
68 * Move article 3 to the position after article 4
69 */
70async function move() {
71  const indices = await afi.indicesForAfter({ userId: 1 }, { id: 4 });
72  //                                          ^ Group        ^ Cursor
73  if (!indices) {
74    throw new Error("Article 4 does not exist or does not belong to user 1.");
75  }
76
77  try {
78    for (const fi of afi.generateKeyBetween(...indices)) {
79      try {
80        await prisma.article.update({
81          where: {
82            id: 3,
83            userId: 1, // IMPORTANT: Always filter by group columns
84          },
85          data: {
86            fi,
87          },
88        });
89        return;
90      } catch (error) {
91        if (afi.isIndexConflictError(error)) {
92          // Conflict occurred - regenerate and try again
93          continue;
94        }
95
96        if (
97          error instanceof Prisma.PrismaClientKnownRequestError &&
98          error.code === "P2025"
99        ) {
100          throw new Error(
101            "Article 3 does not exist or does not belong to user 1.",
102          );
103        }
104        throw error;
105      }
106    }
107
108    // Unreachable code, as the `generateKeyBetween` function throws a `MAX_RETRIES_EXCEEDED` error before this point
109  } catch (error) {
110    // TODO: Error handling
111  }
112}
113
114/**
115 * Delete
116 */
117async function remove() {
118  // Just delete the item. No need to touch the fractional index.
119  await prisma.article.delete({
120    where: {
121      id: 3,
122    },
123  });
124}

[!TIP] Due to limitations of TypeScript, code after a loop that iterates over an infinite generator will not be inferred to be unreachable, even though it is. We recommend using a wrapper function like the one below, which incorporates common error handling.

1async function withKeyBetween<T, FI extends AnyFractionalIndex>(
2  generator: Generator<FI, never, unknown>,
3  isIndexConflictError: (error: unknown) => boolean,
4  callback: (fi: FI) => Promise<T>,
5): Promise<T> {
6  try {
7    for (const fi of generator) {
8      try {
9        return await callback(fi);
10      } catch (error) {
11        if (isIndexConflictError(error)) {
12          // Conflict occurred - regenerate and try again
13          continue;
14        }
15        throw error;
16      }
17    }
18
19    // Unreachable code, as the `generateKeyBetween` function throws a `MAX_RETRIES_EXCEEDED` error before this point
20    throw 1; // To make TypeScript happy
21  } catch (error) {
22    const code = getFraciErrorCode(error);
23    if (code === "MAX_LENGTH_EXCEEDED") {
24      throw new HTTPError(500, "Cannot add more items to this group.");
25    }
26    if (code === "MAX_RETRIES_EXCEEDED") {
27      throw new HTTPError(
28        503,
29        "Too many concurrent requests. Please try again.",
30      );
31    }
32    throw error;
33  }
34}
35
36// Example usage
37const indices = await afi.indicesForAfter({ userId: 1 }, { id: 4 });
38if (!indices) {
39  throw new Error("Article 4 does not exist or does not belong to user 1.");
40}
41
42const result = await withKeyBetween(
43  afi.generateKeyBetween(...indices),
44  afi.isIndexConflictError,
45  async (fi) => {
46    return await prisma.article.update({
47      where: {
48        id: 3,
49        userId: 1, // IMPORTANT: Always filter by group columns
50      },
51      data: {
52        fi,
53      },
54    });
55  },
56);

How It Works

Fractional indexing allows for inserting items between existing items without reindexing:

String-based Example (with BASE62)

1A (index: "V0") --- B (index: "V1")
2                 |
3                 +--- New Item (index: "V0V")

When you need to insert between A and B, fraci generates a new index that sorts lexicographically (in dictionary order) between them. If you need to insert between A and the new item:

1A (index: "V0") --- New Item (index: "V0V") --- B (index: "V1")
2                 |
3                 +--- Another Item (index: "V0F")

Binary-based Example

1A (index: [0x80, 0x00]) --- B (index: [0x80, 0x01])
2                         |
3                         +--- New Item (index: [0x80, 0x00, 0x80])

When you need to insert between A and the new item:

1A ([0x80, 0x00]) --- New Item ([0x80, 0x00, 0x80]) --- B ([0x80, 0x01])
2                  |
3                  +--- Another Item ([0x80, 0x00, 0x40])

Fraci handles the generation of these indices automatically, with conflict resolution and type safety.

Performance Considerations

Key Performance Optimizations

• Database Structure: The compound index structure ([groupId, fi]) is optimized for both uniqueness and query performance
• Character Sets: Using larger character sets (BASE62, BASE95) results in shorter indices, reducing storage requirements
• Binary vs String: Binary-based fractional indexing provides significantly better performance and smaller storage footprint compared to string-based indexing
• Bundle Size: Use fraciBinary or fraciString instead of fraci for instantiation to reduce bundle size
• Efficient Implementation: The library is designed to minimize allocations and computations during index generation
• Concurrency: For optimal performance in high-concurrency scenarios, consider skipping indices for collision avoidance

Performance Impact of Implementation Choices

Choice	Impact
Binary vs String	Binary implementation is ~25% smaller and processes faster
Compound Index	Ensures efficient queries when filtering by group and sorting by index
Index Length	Shorter indices (from larger character sets) improve storage and comparison speed
Conflict Handling	Automatic regeneration with retry limits prevents performance degradation

Skipping Indices for Collision Avoidance

In concurrent environments, index conflicts occur when multiple operations try to insert items at the same position simultaneously. Since fractional indices are generated in a deterministic sequence, concurrent operations will attempt to use the same index value, resulting in conflicts.

Fraci provides a built-in skip parameter in both generateKeyBetween and generateNKeysBetween methods to address this issue. This parameter allows operations to use different indices in the sequence, reducing or eliminating conflicts.

How Index Skipping Works

The skipping technique works because:

1. The fractional index generator produces a sequence of valid indices
2. Any index in this sequence is valid for insertion at the desired position
3. By skipping ahead in the sequence, different operations use different indices
4. If conflicts still occur, the normal conflict resolution mechanism handles them

There are two approaches to index skipping:

Deterministic Skipping with Participant IDs

When pre-coordination is possible, this approach guarantees collision avoidance by assigning each participant a unique sequential identifier and deterministically skipping based on this identifier:

1// Get indices for the position where we want to insert
2const indices = await afi.indicesForAfter({ userId: 1 }, { id: 4 });
3if (!indices) {
4  throw new Error("Reference item not found");
5}
6
7// participantId: unique identifier for each participant (0, 1, 2, ...)
8const skipCount = participantId;
9for (const fi of afi.generateKeyBetween(...indices, skipCount)) {
10  // Each participant uses a different index in the sequence
11  // No conflict handling needed if all participants use their assigned ID
12  await db.insert(items).values({ title: "New Item", fi, userId: 1 });
13  return;
14}

This approach:

• Eliminates randomness
• Guarantees no collisions between participants
• Is ideal when participant identities are known in advance
• Provides predictable index generation

Random Skipping for Uncoordinated Environments

When pre-coordination isn't possible, random skipping provides a probabilistic approach:

1// Get indices for the position where we want to insert
2const indices = await afi.indicesForAfter({ userId: 1 }, { id: 4 });
3if (!indices) {
4  throw new Error("Reference item not found");
5}
6
7// Skip a random number of indices
8const skipCount = Math.floor(Math.random() * 10); // Skip 0-9 indices
9try {
10  for (const fi of afi.generateKeyBetween(...indices, skipCount)) {
11    try {
12      await db.insert(items).values({ title: "New Item", fi, userId: 1 });
13      return; // Success
14    } catch (error) {
15      if (isIndexConflictError(error)) {
16        // Still need conflict resolution
17        continue;
18      }
19      throw error;
20    }
21  }
22
23  // Unreachable code, as the `generateKeyBetween` function throws a `MAX_RETRIES_EXCEEDED` error before this point
24} catch (error) {
25  // TODO: Error handling
26}

This approach:

• Reduces (but doesn't eliminate) the probability of conflicts
• Works without coordination between participants
• Still requires conflict handling as a fallback

Efficiency Considerations

For optimal efficiency:

• Keep the number of indices skipped below the encoding radix being used (e.g., less than 36 for BASE36, less than 62 for BASE62, less than 256 for binary encoding)
• Be aware that skipping indices causes the number of digits to increase faster than necessary
• In high-concurrency environments, this trade-off is acceptable since you would need longer indices anyway after conflicts
• Consider your specific use case when choosing between deterministic and random skipping

Troubleshooting

Index Conflicts

If you're experiencing frequent index conflicts:

• Ensure your compound unique indices are correctly defined
• Implement the skipping indices for collision avoidance technique
• Verify that your conflict detection logic is working correctly

Type Errors

If you're seeing TypeScript errors related to fractional indices:

• Ensure you're using the correct branded type for each column
• Check that you're passing the correct parameters to fraci()
• Ensure your ORM version is compatible with your fraci version (Drizzle ORM v0.30.x - v0.41.x and Prisma v5.x or v6.x required) and that the integration is correctly configured

Runtime Errors

If you encounter runtime errors:

• [INITIALIZATION_FAILED] Base string must have at least 4 unique characters (String-based only)
  • Cause: The digitBase or lengthBase provided to the fraci() function has fewer than 4 characters.
  • Solution: Ensure both base strings have at least 4 unique characters. Consider using the predefined constants like BASE62 or BASE95.
• [INITIALIZATION_FAILED] Base string characters must be unique and in ascending order (String-based only)
  • Cause: The characters in the digitBase or lengthBase are not in ascending order or contain duplicates.
  • Solution: Ensure the characters in your base strings are unique and arranged in ascending order by character code. Consider using the predefined constants.
• [MAX_LENGTH_EXCEEDED] Exceeded maximum length
  • Cause: A generated fractional index has exceeded the configured maximum length (default: 50).
  • Solution: Increase the maxLength parameter when creating your fraci instance. This could also indicate an index expansion attack, so review your security measures.
• [MAX_RETRIES_EXCEEDED] Exceeded maximum retries
  • Cause: The maximum number of retries on conflict has been exceeded (default: 5).
  • Solution: Implement the skipping indices for collision avoidance technique to reduce conflicts. You can also increase the maxRetries parameter when creating your fraci instance.
• [INVALID_FRACTIONAL_INDEX] Invalid indices provided
  • Cause: Invalid fractional indices were provided to key generation functions.
  • Solution: Ensure you're using fractional indices generated by the same fraci instance with the same configuration. Make sure you have not mixed up the items in different groups, and that the first argument item in a group is before the second argument item. File an issue if you use the library correctly and still encounter this error.
• [INTERNAL_ERROR] Unexpected undefined
  • Cause: An internal validation error occurred where a value expected to be defined was undefined.
  • Solution: This indicates an internal library error. File an issue with details about how you encountered this error.
• [INITIALIZATION_FAILED] Could not get field information for <model>.<field> (Prisma ORM only)
  • Cause: When configuring the Prisma extension, the specified model or field doesn't exist or isn't accessible.
  • Solution: Regenerate the Prisma client. Verify that the specified field exists in your Prisma schema and is properly defined as a string or binary field. Check for typos in the model or field name. Also ensure your Prisma version is compatible with the fraci/Prisma integration (Prisma v5.x or v6.x required).

License

This project is licensed under the MIT License - see the LICENSE file for details.

Credits

• Realtime editing of ordered sequences by Figma for the idea
• Implementing Fractional Indexing by David Greenspan for the base implementation