Massive Technical Interviews Tips: OOD Design

关于cache的 eviction policy设计
TODO: https://github.com/apache/ignite/tree/master/modules/core/src/main/java/org/apache/ignite/cache/eviction
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=316982

我觉得可能strategy看起来更好些，考虑到是个behavioral pattern，不同algorithm 重写同一个方法, 但是需要考虑的重点应该变成了如何使得这个重写的方法尽可能够都使用公共的数据存储结构。最坏不做抽象的情况，就是数据结构保存在当前类中，就变成了类似于factory模式的模式了

我刚搜了圈，发现 apache ignite 有类似的抽象的例子
https://ignite.apache.org/releas ... EvictionPolicy.html，不过好像就是把evictionPloicy抽象成abstract class了，然后数据结构也是在子类中定义的。就如同你说的，不一样的policy的数据结构是不一样的，强行去abstract common 数据结构会有点得不偿失，所以用个工厂模式可能会比较好懂，代码也比较直观

就是设计一个cache的eviction policy，你可以选择是LRU, 还是LFU，还是其他eviction policy. 选择哪个，就按照哪个eviction policy执行。
大家认为这种情况，用哪个pattern比较好？

首先回顾一下LeetCode的LRUCache这道题目所设计的接口：

class LRUCache {
public:
// Get the value (will always be positive) of the key if the key exists in the
// cache, otherwise return -1.
int get(int key);
// Set or insert the value if the key is not already present. When the cache
// reached its capacity, it should invalidate the least recently used item
// before inserting a new item.
void put(int key, int value);
};

复制代码

当然这个接口非常简陋，至少有两个问题：

(1) Cache和eviction policy（LRU）的逻辑是合并在一起的

这也正是我们这里OOD设计所要解决的问题：将eviction policy解耦（decouple）出来，使得其可以作为一个参数（或者模板参数）被传入Cache类，那么得到的Cache对象就会使用对应的policy。

(2) 没有触及cache设计的一个重要部分：value的生存期的管理

如果value是占用较多内存空间的大对象（而不是LeetCode题中仅占用4个字节的栈区int），或者是C/C++写的代码，一般是由cache管理生存期。
也就是说当evict一个value时，其占用内存应该立刻被回收，而这时所有对该value对象的引用应当立刻失效 —— 在这种情况下要避免代码出bug（非法内存访问），必须由cache对value进行引用计数，且返回值使用"counted reference"（类似于C++ shared pointer）。
不过如果返回的是栈区对象/对象的拷贝/带GC语言下（例如Java）的对象引用，那么不需要考虑引用计数问题，但是这时cache就无法保证内存的使用量被控制在规定范围内。

第(2)点其实是为了说一下eviction policy设计时关于引用计数的接口 —— 下面简化的代码中没有实现这一接口，但是需要了解一下，因为很多实际系统中是有相关内容的，例如PostgreSQL：https://github.com/postgres/postgres/blob/master/src/backend/storage/buffer/bufmgr.c#L139

现在回到(1)，下面贴的代码主要包含了：
(a) EvictionPolicy的抽象类
(b) 继承了EvictionPolicy的LRU/LFU实现
(c) 一个EvictionPolicy工厂，使得可以比较容易地添加新的Policy实现
(c) 使用EvictionPolicy实现的Cache类

// Eviction policy的抽象
template <typename Entry>
class EvictionPolicy {
public:
virtual Entry chooseEntryToEvict() = 0;
virtual void entryCreated(const Entry &entry) = 0;
virtual void entryReferenced(const Entry &entry) = 0;
// 如果维护引用计数的话需要这个接口
// virtual void entryUnreferenced(const Entry &entry) = 0;
virtual void entryEvicted(const Entry &entry) = 0;
};
// Eviction policy的类型
enum class EvictionPolicyType : int {
kLRU = 0,
kLFU,
kClock,
// ...
};
// 一个简单的LRU实现，不支持并发访问
template <typename Entry>
class LRUPolicy : public EvictionPolicy<Entry> {
public:
Entry chooseEntryToEvict() override {
return list_.back();
}
void entryCreated(const Entry &entry) override {
list_.push_front(entry);
index_.emplace(entry, list_.begin());
}
void entryReferenced(const Entry &entry) override {
const auto &it = index_.at(entry);
if (it != list_.begin()) {
list_.splice(list_.begin(), list_, it, std::next(it));
}
}
void entryEvicted(const Entry &entry) override {
const auto it = index_.find(entry);
list_.erase(it->second);
index_.erase(it);
}
private:
using EntryList = std::list<Entry>;
using EntryListIterator = typename EntryList::iterator;
std::list<Entry> list_;
std::unordered_map<Entry, const EntryListIterator> index_;
};
// 一个简单的LFU实现，不支持并发访问
template <typename Entry>
class LFUPolicy : public EvictionPolicy<Entry> {
public:
Entry chooseEntryToEvict() override {
return std::get<0>(*list_.begin());
}
void entryCreated(const Entry &entry) override {
const auto ret = list_.emplace(entry, Clock::now(), 1);
index_.emplace(entry, ret.first);
}
void entryReferenced(const Entry &entry) override {
auto &it = index_.at(entry);
const std::size_t count = std::get<2>(*it);
list_.erase(it);
const auto ret = list_.emplace(entry, Clock::now(), count + 1);
it = ret.first;
}
void entryEvicted(const Entry &entry) override {
const auto it = index_.find(entry);
list_.erase(it->second);
index_.erase(it);
}
private:
using Clock = std::chrono::high_resolution_clock;
using TimePoint = std::chrono::time_point<Clock>;
using Record = std::tuple<Entry, TimePoint, std::size_t>;
struct RecordComparator {
inline bool operator()(const Record &lhs, const Record &rhs) const {
if (std::get<2>(lhs) != std::get<2>(rhs)) {
return std::get<2>(lhs) < std::get<2>(rhs);
}
if (std::get<1>(lhs) != std::get<1>(rhs)) {
return std::get<1>(lhs) < std::get<1>(rhs);
}
return std::get<0>(lhs) < std::get<0>(rhs);
}
};
using SortedList = std::set<Record, RecordComparator>;
using SortedListIterator = typename SortedList::iterator;
SortedList list_;
std::unordered_map<Entry, SortedListIterator> index_;
};
// Eviction policy的单例工厂
template <typename Entry>
class EvictionPolicyFactory {
public:
static const EvictionPolicyFactory& Instance() {
static EvictionPolicyFactory<Entry> instance;
return instance;
}
EvictionPolicy<Entry>* createEvictionPolicy(const EvictionPolicyType type) const {
switch (type) {
case EvictionPolicyType::kLRU:
return new LRUPolicy<Entry>();
case EvictionPolicyType::kLFU:
return new LFUPolicy<Entry>();
default:
break;
}
throw std::runtime_error("Unsupported eviction policy type");
};
};
// 一个简单的泛型Cache实现
template <typename Key, typename Value>
class Cache {
private:
using Storage = std::unordered_map<Key, Value>;
using Entry = const typename Storage::value_type*;
using Factory = EvictionPolicyFactory<Entry>;
public:
Cache(const std::size_t capacity, const EvictionPolicyType type)
: capacity_(capacity),
eviction_policy_(Factory::Instance().createEvictionPolicy(type)) {
}
const Value* get(const Key &key) {
const auto it = storage_.find(key);
if (it == storage_.end()) {
return nullptr;
}
eviction_policy_->entryReferenced(&(*it));
return &it->second;
}
void put(const Key &key, const Value &value) {
const auto it = storage_.find(key);
if (it == storage_.end()) {
if (storage_.size() >= capacity_) {
const auto ev = eviction_policy_->chooseEntryToEvict();
eviction_policy_->entryEvicted(ev);
storage_.erase(ev->first);
}
const auto ret = storage_.emplace(key, value);
eviction_policy_->entryCreated(&(*ret.first));
} else {
it->second = value;
eviction_policy_->entryReferenced(&(*it));
}
}
private:
const std::size_t capacity_;
Storage storage_;
std::unique_ptr<EvictionPolicy<Entry>> eviction_policy_;
};
/*******************************************************************************
* 可以用于提交LeetCode 146的代码
class LRUCache {
public:
LRUCache(int capacity)
: cache_(capacity, EvictionPolicyType::kLRU) {
}
int get(int key) {
const int *value = cache_.get(key);
return value == nullptr ? -1 : *value;
}
void put(int key, int value) {
cache_.put(key, value);
}
private:
Cache<int, int> cache_;
};
*******************************************************************************/
template <typename C, typename T>
void Print(C &cache, const T &key) {
const auto *value = cache.get(key);
if (value == nullptr) {
std::cout << "[" << key << "] NULL\n";
} else {
std::cout << "[" << key << "] " << *value << "\n";
}
}

[Google] Design Text Editor
Original question is here: https://www.careercup.com/question?id=5726975948226560

This is my implementation using StringBuilder with a cursor index instead of LinkedList. The key point is: use java enum as much as possible and don't use String directly. Using String directly is not a good OOP. As for OOP/OOD, think about how to encapsulate the code, and reuse the code. In TextEditor implemention, it uses the same implementation for undos and normal insert, delete, move cursor.

Java enum is as powerful as a class (in fact, enum is a class). In the code, it demonstrates 2 ways to use java enum:

abstract method can be used in enum
A method can be overriden in enum

Using enum has the following benefits

passing different enums to a method, the method can behavior differently (Strategy pattern).
reduce the usage of if-else or case statement, which in turn reduces the code complexity (see here for explanation).

The below implementation is a little over-engineered, but it demonstrates how OOP/OOD is supposed to be.

public class TextEditor {

private final StringBuilder text;

// store undo edits.

private final Stack<UndoEdit> undoEdits;

private int cursorIndex;

public TextEditor() {

this.text = new StringBuilder();

undoEdits = new Stack<>();

cursorIndex = 0;

}

public boolean moveCursorLeft() {

return moveCursorLeft(Undo.SAVE);

}

private boolean moveCursorLeft(final Undo undo) {

if (cursorIndex == 0) {

return false;

}

cursorIndex--;

undo.add(new UndoEdit(UndoEdit.Operation.MOVE_CURSOR_RIGHT), this);

return true;

}

public boolean moveCursorRight() {

return moveCursorRight(Undo.SAVE);

}

private boolean moveCursorRight(final Undo undo) {

if (cursorIndex == text.length()) {

return false;

}

cursorIndex++;

undo.add(new UndoEdit(UndoEdit.Operation.MOVE_CURSOR_LEFT), this);

return true;

}

public boolean insertCharacter(final char ch) {

return insertCharacter(ch, Undo.SAVE);

}

private boolean insertCharacter(final char ch, final Undo undo) {

text.insert(cursorIndex, ch);

cursorIndex++;

undo.add(new UndoEdit(UndoEdit.Operation.BACKSPACE), this);

return true;

}

public boolean backspace() {

return backspace(Undo.SAVE);

}

private boolean backspace(final Undo undo) {

if (cursorIndex == 0) {

return false;

}

cursorIndex--;

final char ch = text.charAt(cursorIndex);

undo.add(new UndoEdit(UndoEdit.Operation.INSERT_CHARACTER, ch), this);

text.deleteCharAt(cursorIndex);

return true;

}

public boolean undo() {

if (!undoEdits.empty()) {

final UndoEdit edit = undoEdits.pop();

return edit.apply(this);

}

return false;

}

private void saveForUndo(final UndoEdit action) {

undoEdits.add(action);

}

// for unit test/debug

int cursor() {

return cursorIndex;

}

@Override

public String toString() {

return new StringBuilder(text).insert(cursorIndex, "|").toString();

}

enum Undo {

SAVE {

@Override

public void add(final UndoEdit edit, final TextEditor textEditor) {

textEditor.saveForUndo(edit);

}

},

UNSAVE;

/**

* Default implementation for doing nothing

*

* @param edit

* @param textEditor

*/

public void add(final UndoEdit edit, final TextEditor textEditor) {

// do nothing

}

/**

* Helper class to encapsulate undo operation and character.

*/

private static class UndoEdit {

private static final char EMPTY_CHAR = '\0';

private final Operation operation;

private final char ch;

public UndoEdit(final Operation operation) {

this.operation = operation;

this.ch = EMPTY_CHAR;

}

public UndoEdit(final Operation operation, final char ch) {

this.operation = operation;

this.ch = ch;

}

public boolean apply(final TextEditor editor) {

return operation.apply(ch, editor);

}

@Override

public String toString() {

return operation.toString() + " " + ch;

}

enum Operation {

MOVE_CURSOR_LEFT {

@Override

public boolean apply(final char ch, final TextEditor editor) {

return editor.moveCursorLeft(Undo.UNSAVE);

}

},

MOVE_CURSOR_RIGHT {

@Override

public boolean apply(final char ch, final TextEditor editor) {

return editor.moveCursorRight(Undo.UNSAVE);

}

},

INSERT_CHARACTER {

@Override

public boolean apply(final char ch, final TextEditor editor) {

return editor.insertCharacter(ch, Undo.UNSAVE);

}

},

BACKSPACE {

@Override

public boolean apply(final char ch, final TextEditor editor) {

return editor.backspace(Undo.UNSAVE);

}

};

public abstract boolean apply(char ch, TextEditor editor);

}

好像原题有要求“All functions above should take O(1) time. ”
代码里的text.insert和text.deleteCharAt会不会有问题呢……

StringBuilder's deleteChar and insertChar have linear time complexity. Here is the new code to use doubly linkedlist. Since it is well encapsulated, it is easy to switch to a different implementation:

[Java] 纯文本查看复制代码

public class TextEditor {

    private static final char EMPTY_CHAR = '\0';

    private final ListNode head;

    private final ListNode tail;

    // store undo edits.

    private final Stack<UndoEdit> undoEdits;

    private ListNode cursor;

    public TextEditor() {

        head = new ListNode();

        tail = new ListNode();

        head.next = tail;

        tail.prev = head;

        undoEdits = new Stack<>();

        cursor = tail;

    }

    public boolean moveCursorLeft() {

        return moveCursorLeft(Undo.SAVE);

    }

    private boolean moveCursorLeft(final Undo undo) {

        if (cursor.prev == head) {

            return false;

        }

        cursor = cursor.prev;

        undo.add(new UndoEdit(UndoEdit.Operation.MOVE_CURSOR_RIGHT), this);

        return true;

    }

    public boolean moveCursorRight() {

        return moveCursorRight(Undo.SAVE);

    }

    private boolean moveCursorRight(final Undo undo) {

        if (cursor.next == null) {

            return false;

        }

        cursor = cursor.next;

        undo.add(new UndoEdit(UndoEdit.Operation.MOVE_CURSOR_LEFT), this);

        return true;

    }

    public boolean insertCharacter(final char ch) {

        return insertCharacter(ch, Undo.SAVE);

    }

    private boolean insertCharacter(final char ch, final Undo undo) {

        final ListNode node = new ListNode(ch);

        node.prev = cursor.prev;

        node.next = cursor;

        cursor.prev.next = node;

        cursor.prev = node;

        undo.add(new UndoEdit(UndoEdit.Operation.BACKSPACE), this);

        return true;

    }

    public boolean backspace() {

        return backspace(Undo.SAVE);

    }

    private boolean backspace(final Undo undo) {

        if (cursor.prev == head) {

            return false;

        }

        final char ch = cursor.prev.ch;

        undo.add(new UndoEdit(UndoEdit.Operation.INSERT_CHARACTER, ch), this);

        final ListNode deleted = cursor.prev;

        deleted.prev.next = cursor;

        cursor.prev = deleted.prev;

        deleted.prev = null;

        deleted.next = null;

        return true;

    }

    public boolean undo() {

        if (!undoEdits.empty()) {

            final UndoEdit edit = undoEdits.pop();

            return edit.apply(this);

        }

        return false;

    }

    private void saveForUndo(final UndoEdit action) {

        undoEdits.add(action);

    }

    // for unit test/debug

    ListNode cursor() {

        return cursor;

    }

    @Override

    public String toString() {

        final StringBuilder builder = new StringBuilder();

        ListNode node = head.next;

        while (node != null) {

            if (node == cursor) {

                builder.append("|");

            }

            if (node != tail) {

                builder.append(node.ch);

            }

            node = node.next;

        }

        return builder.toString();

    }

    enum Undo {

        SAVE {

            @Override

            public void add(final UndoEdit edit, final TextEditor textEditor) {

                textEditor.saveForUndo(edit);

            }

        },

        UNSAVE;

        /**

         * Default implementation for doing nothing

         *

         * @param edit

         * @param textEditor

         */

        public void add(final UndoEdit edit, final TextEditor textEditor) {

            // do nothing

        }

    }

    /**

     * Helper class to encapsulate undo operation and character.

     */

    private static class UndoEdit {

        private final Operation operation;

        private final char ch;

        public UndoEdit(final Operation operation) {

            this.operation = operation;

            this.ch = EMPTY_CHAR;

        }

        public UndoEdit(final Operation operation, final char ch) {

            this.operation = operation;

            this.ch = ch;

        }

        public boolean apply(final TextEditor editor) {

            return operation.apply(ch, editor);

        }

        @Override

        public String toString() {

            return operation.toString() + " " + ch;

        }

        enum Operation {

            MOVE_CURSOR_LEFT {

                @Override

                public boolean apply(final char ch, final TextEditor editor) {

                    return editor.moveCursorLeft(Undo.UNSAVE);

                }

            },

            MOVE_CURSOR_RIGHT {

                @Override

                public boolean apply(final char ch, final TextEditor editor) {

                    return editor.moveCursorRight(Undo.UNSAVE);

                }

            },

            INSERT_CHARACTER {

                @Override

                public boolean apply(final char ch, final TextEditor editor) {

                    return editor.insertCharacter(ch, Undo.UNSAVE);

                }

            },

            BACKSPACE {

                @Override

                public boolean apply(final char ch, final TextEditor editor) {

                    return editor.backspace(Undo.UNSAVE);

                }

            };

            public abstract boolean apply(char ch, TextEditor editor);

        }

    }

    static class ListNode {

        char ch;

        ListNode prev;

        ListNode next;

        ListNode() {

            ch = EMPTY_CHAR;

        }

        ListNode(final char ch) {

            this.ch = ch;

        }

        @Override

        public boolean equals(final Object o) {

            final ListNode that = (ListNode) o;

            return ch == that.ch;

        }

    }

}

Tuesday, April 16, 2019

Eviction policy - Design Pattern

Design Text Editor

Labels

Popular Posts