分區的加權有向圖（超過鍵/值數據庫）

我們想分片加權有向圖，分區的加權有向圖（超過鍵/值數據庫）

用戶可以添加的節點和邊動態，首先，DB /圖形是空的。我們將節點和邊保存在一個鍵/值數據庫中（可能爲Redis）：對於每個節點，我們將nodeId作爲鍵，並且引用節點的鍵的排序集合，sortSet中每個nodeId的得分是邊緣的重量。

（見問題就在這裏：Redis: Implement Weighted Directed Graph）

我們沒有一個平衡約束，在圖形上最常見的動作是Dijkstra算法，我們當時想（在網絡最大限度地減少I/O我們情況）

可能的解決方法：每個數據庫服務器包含其他的服務器採用IPS列表：

關鍵：服務器，值：250.1 ....

關鍵：服務器，值：.... 250.2

鍵：server（服務器），值：250.3 ....

每個節點ID將serverX.originalNodeId

什麼將是決定哪些節點出現在算法？我們應該支持重新定位節點嗎？

我猜測，幼稚的做法是，節點A添加到serverX其中argmax（在服務器X具有與節點A的邊緣節點＃），只要serverX沒有完全佔據..

來源

2011-06-19 DuduAlul

「碎片」？我一定會變老。這是什麼意思？ –

http://en.wikipedia.org/wiki/Shard_(database_architecture） – DuduAlul

由於處理髮生在客戶端，這種圖形數據不是太難分割 - 每一步你需要的只是一個單獨的有序集合，所以從哪個節點加載哪個節點並不重要。獲取實際的數據與節點一起發生是最後一步 - 如果只有一個節點，那麼這將是一個簡單的MGET，並且很容易在多個節點上分割。

要確定密鑰將存儲在哪個節點上，您應該使用散列而不是嘗試手動跟蹤它們。我使用一個表將一定範圍的哈希映射到特定的節點。它存儲在redis中用於長期持久化，但實際上是客戶端的一部分。要訪問特定的密鑰，只需獲取密鑰的散列值，在表中查找並連接到該節點。使用具有數千個插槽的表格可以輕鬆將數據移動到另一個節點 - 更新表格，並且對特定插槽的請求將轉到另一個節點。這與Redis集羣中使用的方法並不完全相同。

這就是說，我設置分片的原因不是圖表數據。只包含ID的小型有序集不佔用太多內存 - 您應該能夠在單個節點上處理1億條邊，而不會有太多麻煩。

來源

2011-06-19 22:02:53

這裏的主要問題是，我想盡可能保持連接的圖形節點在同一臺機器上，哈希方式並不接受它考慮到...... – DuduAlul

你使用的是redis腳本嗎？保持節點在一起並不重要。另外，如果連接的節點有時只在同一臺服務器上，那麼您可能會發現選擇服務器的複雜流程的開銷比通常到易於識別的不同服務器的開銷要差。 –

不，我可以一起發送幾個命令。 – DuduAlul

分區的加權有向圖（超過鍵/值數據庫）

回答

相關問題