Skip to content

Instantly share code, notes, and snippets.

@sc68cal

sc68cal/main.py

Last active August 15, 2024 03:29
Show Gist options
  • Save sc68cal/88311684ab061b491f27c3929aa50138 to your computer and use it in GitHub Desktop.
Save sc68cal/88311684ab061b491f27c3929aa50138 to your computer and use it in GitHub Desktop.
Download ZIP
unreliable block storage coding interview
Raw
readme.md

Resilient File Storage on Unreliable Block Device

In this question, we want you to implement a simple key-value store that will resiliently write and read ASCII text files to/from an unreliable block storage device that we have provided.

db = FileStore()
ret = db.put("hello.txt", "lorem ipsum dolor sit amet")
assert ret == "lorem ipsum dolor sit amet"
db.get("hello.txt")
lorem ipsum dolor sit amet
db.delete("hello.txt")
db.get("hello.txt")
ValueError: file hello.txt does not exist

When we say the block device is unreliable, we mean that data can be corrupted when a block is written to or read from. Once corrupted, the corruption is considered persistent, meaning the original data on the block is lost. If corruption occurs, when content is read from a block, the block will return random data, and when content is written to a block, random data will be written to the block instead.

Your task is to:

  1. Implement the core API (create, get, delete) of FileStore, using BlockDevice as the underlying storage primitive.
  2. Implement a strategy to recover from write-time corruption of file content
  3. Implement a strategy to recover from read-time corruption of file content

The user should experience reliable, error-free use of your FileStore implementation, with two possible exceptions:

  1. When the user runs out of storage space on the block device
  2. When the file is corrupted beyond recovery, a determination we leave up to you

Keep in mind that this is a toy program and not subject to all the constraints of real-world filesystems.

You do not need to worry about efficiency, memory or otherwise. Prioritize a complete, clean, and readable implementation.

You may use any and as many auxiliary data structures as you see fit, and any metadata you need to maintain may be stored in memory exclusively; however, the content of the files themselves needs to be written only to the block device. Class you will be implementing

class FileStore:
    def put(self, file_name: str, file_content: str):
        # Creates a new file with the specified name and content.
        pass
        
    def get(self, file_name: str):
        # Gets the content of the ASCII file.
        pass
    
    def delete(self, file_name: str):
        # Deletes the specified file.
        pass

Block device (Python)

The database should use our prewritten BlockDevice class. This class is essentially an array of fixed-width “blocks” that store arbitrary UTF-8 strings.

>>> # Create a block device with 1024 blocks that can each fit an 8 character string; every read/write has a 1% chance of corruption.
>>> block_device = BlockDevice.get_new_block_device(
            block_count=1024,
            block_size=8,
            corruption_rate=0.01
        )
        
>>> # Write content to block 0.
>>> block_device.write(index=0, content=”12345678”)
12345678

>>> # Read content from block 0.
>>> block_device.read(index=0) 
12345678

>>> # If content length exceeds the block size, the content is truncated.
>>> block_device.write(index=0, content=”123456789”)
12345678

>>> # This read caused a corruption of block 0's content.
>>> block_device.read(index=0)
rcjutrvg

>>> # The corruption is durable (unless corrupted again).
>>> block_device.read(index=0)
rcjutrvg

>>> # This write's content is corrupted.
>>> block_device.write(index=0, content="Corrupt")
xtjuvrvr
Raw
main.py
from dataclasses import dataclass
from functools import partial
import hashlib
import math
from os import write
import random
import string
# See below BlockDevice for FileStore skeleton
def get_random_string(length: int) -> str:
return "".join(
random.choice(string.ascii_lowercase) for _ in range(length)
)
@dataclass
class BlockDevice:
block_size: int
blocks: list[str]
corruption_rate: float
@staticmethod
def get_new_block_device(
block_count=1024 * 1024, block_size=8, corruption_rate=0.01
):
"""Create a new block device with the desired parameters."""
blocks = [get_random_string(block_size) for _ in range(block_count)]
return BlockDevice(
block_size=block_size, blocks=blocks, corruption_rate=corruption_rate
)
@property
def block_count(self):
"""How many blocks does this device contain."""
return len(self.blocks)
def read(self, index: int) -> str:
"""Read the block at the specified index.
This method may corrupt the underlying block in a consistent
manner, such that the original data is unretrievable in the
future, as well.
:param index: Index of the block to read.
:returns: Content of the block.
"""
uncorrupted = self.blocks[index]
return self._maybe_corrupt(uncorrupted, index)
def write(self, index: int, content: str) -> str:
"""Write the specified content to the specified block index.
This method may corrupt the data before persisteng it to the
underlying block; however, it will return the content that
was actually written.
:: Note: The input content will be truncated to the block_size
of this block device.
:param index: Block index to write into.
:param content: Content to be written, only uses the first block_size
characters.
:returns: What content was written to the block device
"""
truncated = content[: self.block_size]
current_content = self.blocks[index]
new_content = truncated + current_content[len(truncated) :]
return self._maybe_corrupt(new_content, index)
def _maybe_corrupt(self, content: str, index: int) -> str:
should_corrupt = random.uniform(0, 1) < self.corruption_rate
if should_corrupt:
maybe_corrupted = get_random_string(self.block_size)
else:
maybe_corrupted = content
self.blocks[index] = maybe_corrupted
return maybe_corrupted
# Create a block device with 1024 blocks that can each fit an
# character string; every read/write has a 1% chance of corruption.
block_device = BlockDevice.get_new_block_device(
block_count=1024, block_size=8, corruption_rate=0.01)
# Write content to block 0.
print(f"Writing '12345678' to the block device: {block_device.write(index=0, content='12345678')}")
# Read content from block 0.
print(f"Reading from the block device: {block_device.read(index=0)}")
# If content length exceeds the block size, the content is truncated.
print(f"Writing '123456789' to the block device: {block_device.write(index=0, content='123456789')}")
##########################
# Begin Implementing Below
##########################
class FileStore:
def __init__(self, failure_rate=0.01, retries=3) -> None:
self.blockdevice = BlockDevice.get_new_block_device(corruption_rate=failure_rate)
# File map contains the the filename and the blocks it maps to
# for the file contents
self.filemap = {}
# partials is a dictionary that contains information about blocks
# that were partially written to but did not fully take up
# the entire block_size
self.partials = {}
self.next_free_block = 0
# Dictionary containing a hash for each block to check for data
# corruption
self.checksums = {}
self.retries = retries
def add_checksum(self, block_index: int, content: str):
# Use md5 checksum to calculate a hash, that can
# be used to quickly check for corruption, and
# save it to the checksums dictionary
checksum = hashlib.md5(content.encode()).hexdigest()
self.checksums[block_index] = checksum
return checksum
def attempt_write(self, block_index: int, content: str) -> str:
write_check = None
checksum = self.add_checksum(block_index, content)
result = ""
retry = 0
while write_check != checksum and retry != self.retries:
result = self.blockdevice.write(block_index, content)[:len(content)]
write_check = hashlib.md5(result.encode()).hexdigest()
retry += 1
if retry == self.retries and write_check != checksum:
raise Exception(f"Write failed for block {block_index}, retries exceeded")
return result
def attempt_read(self, block_index: int) -> str:
read_check = None
checksum = self.checksums[block_index]
is_partial = block_index in self.partials
if is_partial:
partial_index = block_index
tries = 0
result = ""
need_rewrite = False
# We only get two shots at reading a block, the main
# block and then the backup block
# TODO - make more copies of the block so tries can be more than 2
while read_check != checksum and tries != 2:
result = self.blockdevice.read(block_index)
if is_partial:
result = result[:self.partials[partial_index]]
read_check = hashlib.md5(result.encode()).hexdigest()
if read_check != checksum:
# Read failed, and the block is now corrupt. Try the backup
block_index += 1
need_rewrite = True
tries += 1
if read_check != checksum:
raise Exception(f"Read has failed and data loss has occured for block {block_index}")
# See if we need to write back data that was lost upon read
if need_rewrite:
self.attempt_write(block_index-1, result)
return result
def put(self, file_name: str, file_content: str) -> str:
# Calculate the number of blocks this file_content will require
chunks = math.ceil(len(file_content) / self.blockdevice.block_size)
# We consume two blocks, one as the primary and one as the backup
# so the amount of space we have is half the number of blocks
# that the block device provides
# TODO - replace with a parity scheme that doesn't waste half the blocks
if self.next_free_block + chunks > len(self.blockdevice.blocks) // 2 - 1:
raise ValueError("Insufficient space")
# Creates a new file with the specified name and content.
result = ""
self.filemap[file_name] = []
for i in range(0, chunks):
# last chunk
if i == chunks - 1:
# grab the last part of file_content, which can be less than a
# full block (block_size)
content = file_content[(chunks - 1)*self.blockdevice.block_size:]
# If chunk is smaller than block_size we need to track
# its length to determine where junk data begins
if len(content) < self.blockdevice.block_size:
self.partials[self.next_free_block] = len(content)
else:
# Grab the i'th chunk of file_content, which is block_size long
content = file_content[(i*self.blockdevice.block_size):(i+1)*self.blockdevice.block_size]
result = result + self.attempt_write(self.next_free_block, content)
# Write a backup block
self.attempt_write(self.next_free_block+1, content)
# Add this block that was just written to the file map
self.filemap[file_name].append(self.next_free_block)
# Advance to the next free block
self.next_free_block += 2
return result
def get(self, file_name: str) -> str:
content = ""
if file_name not in self.filemap:
raise ValueError("Invalid file_name")
# Grab the blocks that make up the file
for i in self.filemap[file_name]:
chunk = self.attempt_read(i)
content = content + chunk
return content
def delete(self, file_name: str) -> bool:
# For every block that a file used to use
for i in self.filemap[file_name]:
# Delete the checksum metadata for the block
del self.checksums[i]
# Delete the partial metadata for the block
if i in self.partials:
del self.partials[i]
del self.filemap[file_name]
return True
import pytest
import unittest
class BlockDeviceTest(unittest.TestCase):
def setUp(self) -> None:
self.block_device = BlockDevice.get_new_block_device(
block_count=1024, block_size=8, corruption_rate=0.01)
def test_write(self):
self.assertEqual(
self.block_device.write(0, '1234abcd'),
'1234abcd'
)
def test_read(self):
self.assertEqual(
len(self.block_device.read(1)),
8
)
class FileStoreTest(unittest.TestCase):
def setUp(self) -> None:
self.file_store = FileStore()
def test_put(self):
self.assertEqual(
self.file_store.put(
"hello.txt",
'lorem ipsum dolor sit amet'
),
"lorem ipsum dolor sit amet"
)
@pytest.mark.skip(reason="CPU intensive")
def test_put_multi(self):
self.assertEqual(
self.file_store.put(
"test1.txt",
'foobar12365799'
),
"foobar12365799"
)
self.assertEqual(
self.file_store.put(
"test2.txt",
'foobar987654213'
),
"foobar987654213"
)
def test_get(self):
self.file_store.put(
"hello.txt",
'lorem ipsum dolor sit amet'
)
self.assertEqual(
self.file_store.get("hello.txt"),
"lorem ipsum dolor sit amet"
)
def test_delete(self):
self.file_store.put(
"hello.txt",
'lorem ipsum dolor sit amet'
)
self.assertEqual(
self.file_store.get("hello.txt"),
"lorem ipsum dolor sit amet"
)
self.assertTrue(self.file_store.delete("hello.txt"))
with self.assertRaises(ValueError):
self.file_store.get("hello.txt")
class Cheating(FileStoreTest):
def setUp(self) -> None:
self.file_store = FileStore(failure_rate=0.0)
class VeryUnreliable(FileStoreTest):
def setUp(self) -> None:
self.file_store = FileStore(failure_rate=.3)
pytest.main(['--verbose','-s', __file__])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment