5
\$\begingroup\$

I referred to the post here but it does not address the question that I have with regards to my implementation. I have a C# implementation of an in-memory database that I came up with during a recent interview. I was told that my code was okay in terms of getting the job done but could be more efficient dealing with transactions. I am not sure how I could improve this. I would greatly appreciate any suggestions.

The database should support GET, SET, DELETE, COUNT as basic operations. END signifies that the user is not going to issue any more commands. Input is read from stdin.

eg.

SET a 10
GET a   //returns 10
COUNT a //returns 1
DELETE a
GET a //returns NULL
COUNT a //returns 0.

A transaction is the equivalent of the DB transactions and supports the above operations in an atomic manner. It is initiated by a BEGIN command, rollback means rolling back the active transaction, since nested transactions are supported, commit writes all open transactions to memory. A rollback or commit issued with no transactions open will result in a "NO TRANSACTIONS" being printed.

BEGIN
SET a 10
GET a
BEGIN
SET a 20
GET a
ROLLBACK
GET a
ROLLBACK
GET a
END

Here are my classes:

public class Operation
{
    private readonly Dictionary<string, int> valueStore;
    private readonly Dictionary<int, int> valueCount;

    public Operation()
    {
        valueStore = new Dictionary<string, int>();
        valueCount = new Dictionary<int, int>();
    }
    //Used for copying over old data for supporting transactions
    public Operation(Operation operation)
    {
        valueStore = new Dictionary<string, int>(operation.valueStore);
        valueCount = new Dictionary<int, int>(operation.valueCount);
    }
    //set a variable to a value in the datastore and update counts
    internal void Set(string variable, int value)
    {
        if (!valueStore.ContainsKey(variable))
        {
            valueStore.Add(variable, value);
        }
        else
        {
            valueCount[valueStore[variable]] -= 1;
            valueStore[variable] = value;
        }
        if (!valueCount.ContainsKey(value))
        {
            valueCount.Add(value, 1);
        }
        else
        {
            valueCount[value] += 1;
        }
    }
    //Get value from datastore, return null if not present
    internal void Get(string variable)
    {
        if (valueStore.ContainsKey(variable))
            Console.WriteLine(valueStore[variable]);
        else
            Console.WriteLine("NULL");
    }
    //Get count from datastore, return 0 if not present
    internal void Count(int value)
    {
        if (valueCount.ContainsKey(value))
            Console.WriteLine(valueCount[value]);
        else
            Console.WriteLine("0");
    }
    //Delete value from data store and update count.
    internal void Delete(string variable)
    {
        if (valueStore.ContainsKey(variable))
        {
            int value = valueStore[variable];
            valueCount[value] -= 1;
            valueStore.Remove(variable);
        }
        else
            Console.WriteLine("Variable does not exist");
    }

    /*
     * We need to override equals to compare two operations 
     * because when we have two begins, 1 commit followed by
     * a rollback we should technically have no transactions
     * to rollback, because the last committed and current 
     * transactions are both same
     */ 

    public bool Equals(Operation other)
    {
        if (valueStore.Keys.Count == other.valueStore.Keys.Count)
        {
            foreach (string variable in valueStore.Keys)
            {
                if (other.valueStore.ContainsKey(variable)
                        && other.valueStore[variable] == valueStore[variable])
                    continue;
                else
                    return false;
            }
        }
        else
            return false;
        return true;
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 17;
            hash = hash * 31 + valueStore.GetHashCode();
            hash = hash * 31 + valueCount.GetHashCode();
            return hash;
        }
    }
}

public class Transaction
{
    private readonly Stack<Operation> transactions;

    public Transaction()
    {
        transactions = new Stack<Operation>();
    }

    internal Operation Begin(Operation operation)
    {
        transactions.Push(operation);
        return new Operation(operation);
    }

    internal Operation Commit(Operation operation)
    {
        transactions.Clear();
        transactions.Push(operation);
        return new Operation(operation);
    }

    internal Operation Rollback(Operation operation)
    {
        if (transactions.Count != 0)
        {
            Operation lastCommitted = transactions.Pop();
            if (lastCommitted.Equals(operation))
            {
                Console.WriteLine("NO TRANSACTION");
                transactions.Push(lastCommitted);
            }
            return lastCommitted;
        }
        else
        {
            Console.WriteLine("NO TRANSACTION");
            return operation;
        }
    }
}

public class Database
{
    private Operation commands;
    private Transaction transaction;

    public Database()
    {
        commands = new Operation();
        transaction = new Transaction();
    }

    public void HandleInput()
    {
        Console.WriteLine("Hello user, enter some commands");
        string line = "";
        while ((line = Console.ReadLine()) != null)
        {
            if (line == "END")
                break;
            else
            {
                HandleUserInput(line);
            }
        }
    }

    private void HandleUserInput(string inputLine)
    {
        /*
         * Need to use exceptions for parsing and use try catch block for FormatException
         * Assuming that input commands will be valid(eg. Get will have 2 params, 
         * Count will have 2 params etc.)
         */ 
        string[] parameters = inputLine.Split(' ');
        string op = parameters[0];
        string variable;
        int value;
        switch (op.ToUpper())
        {
            case "GET":
                variable = parameters[1];
                commands.Get(variable);
                break;

            case "SET":
                variable = parameters[1];
                value = int.Parse(parameters[2]);
                commands.Set(variable, value);
                break;

            case "DELETE":
                variable = parameters[1];
                commands.Delete(variable);
                break;

            case "COUNT":
                value = int.Parse(parameters[1]);
                commands.Count(value);

                break;

            case "BEGIN":
                commands = transaction.Begin(commands);
                break;

            case "ROLLBACK":
                commands = transaction.Rollback(commands);
                break;

            case "COMMIT":
                commands = transaction.Commit(commands);
                break;

            default:
                Console.WriteLine("Invalid operation: " + op + "\nTry again.");
                break;
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Could you please explain what exactly COUNT is supposed to do? \$\endgroup\$ – Ben Aaronson Apr 5 at 10:19
  • \$\begingroup\$ The number of items in the value store that currently have the same value as the input. For eg., if the value store has {{a -> 10}, {b ->10}}, then Count 10 gives 2. \$\endgroup\$ – Sindhu Apr 8 at 22:05
2
\$\begingroup\$

Main problems

  • Several parts of the code interact directly with the console. This mixing of responsibilities results in code that's difficult to reuse and test.
  • Copying all data when a transaction is started is an easy and quick way to implement transactions, but it's indeed not the most efficient approach, and doesn't allow for concurrent transactions. Instead, a transaction could keep track of performed operations, and only apply them to the underlying key-value store on commit. Querying performed within a transaction should check these pending modifications before looking at the parent transaction or the underlying data store.
  • The class names are somewhat confusing:
    • Operation sounds like it represents a single database operation. Instead, it's the actual key-value store, so I would rename this to KeyValueStore.
    • Transaction sounds like it represents a single transaction. Instead, it tracks multiple transactions, so I'd rename this to TransactionManager.
    • I'd expect Database to provide a database or query API, but instead it handles user input directly.

Other notes

  • Operation.Get and Operation.Count are of little use if they don't return their results.
  • Use TryGetValue instead of a ContainsKey call followed by an indexing operation. This gives you the information you need with just a single dictionary lookup.
  • Why does Operation keep track of value counts? Was there a specific requirement that COUNT had to operate in \$O(1)\$ time? If not, why not keep things simple and do a linear search? It's a trade-off, of course, but without a clear reason to do this I would favor the less complicated approach: more code usually means more bugs and more maintenance.
  • I don't see why Operation needs to implement Equals and GetHashCode. It's a potentially expensive operation, and the only place where it's used (Transaction.Rollback) doesn't make sense: rolling back a transaction with no changes should not put that transaction back on the stack.
  • The nesting in Operation.Equals can be reduced by using early-out returns: if (Count != other.Count) return false; ... instead of if (Count == other.Count) { ... } else return false;.
  • I'd expect an empty operations stack to indicate that no transaction is active, but because Commit pushes an operation on the stack that's not always the case. Why would Commit need to do that? It already returns the current (committed) state.
  • You may want to document (in the code) that Commit commits all transactions, while Rollback only rolls back the innermost transaction.
  • By reading input directly in Database, your code cannot be reused in a different context (GUI, server-side, library). Move HandleInput to another place (Program.Main for example), rename HandleUserInput to ExecuteQuery and have that method return results instead of writing them to the console. Now you can reuse your database code elsewhere, and it's possible to write automated tests.
  • Adding a few empty lines here and there would improve code readability: some whitespace between methods, and between unrelated if/else statements makes it easier to tell them apart.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.