シラバス レッスン 148 中 27 · 理解するために AI を使う
理解するために AI を使う

AI オフの双子:ハッシュリング

なぜ大切か 「自分へのこだわり」の一周したログには、中心にひとつの考えがありました。ここで、実際に作るかもしれないシステムの中で、チューターをオフにしてそれがまた出てきます。

この問題ではチューターはオフです。自分で解いてください。

キャッシュのクラスターが、コンシステントハッシュでキーをサーバーに分散させます。どのサーバーも、0 から約 20 億までの整数のリングの上にいくつかの位置を持ちます。キーはひとつの数にハッシュされ、リングを回って、その数以上の最初のノードの位置に属します。最も大きな位置を過ぎると、最も小さな位置へ一周します。

ノードの位置は共有の表に並べて保存されていますが、その表は循環バッファで、最後に書いた人が止めたところから始まります。表を読むたびにネットワークの往復がかかるので、読み取りは数えられます。

データ

from creative.budget import Tape
ring = Tape([700, 900, 100, 300])   # sorted positions 100, 300, 700, 900, stored from 700
hashes = [250, 950]
# owners(ring, hashes) -> [300, 100]
あなたの番

owners(ring, hashes) を書いてください。ring は互いに違うノードの位置の Tape で、並べられていますが回転しているかもしれません(どこから保存されていてもよく、0 からのこともあります)。少なくともひとつのノードを持ちます。それぞれのハッシュ h について、>= h の最も小さな位置を返します。なければ、全体で最も小さな位置を返します。予算:100,000 のノードと 200 のハッシュで、読めるのは最大 20,000 の値です。len(ring) は無料です。

AI オフ:この問題ではチューター、ヒント、解答例はありません。自分の頭だけで考えましょう。

このレッスンに問題を見つけましたか?報告する · このレッスンについて質問する

この演習はまもなく開きます

その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。